数据结构 - 图的遍历

2021年5月4日 1点热度 0条评论 来源: 陆讯

图的遍历

图的遍历(Traversing Graph):从图的某一顶点出发,访遍图中的其余顶点,且每个顶点仅被访问一次。
图的遍历算法是各种图的操作的基础。但图的遍历存在以下特点:
◆ 复杂性:图的任意顶点可能和其余的顶点相邻接,可能在访问了某个顶点后,沿某条路径搜索后又回到原顶点,而有些顶点却还没有被遍历到的情况。
◆ 解决办法:在遍历过程中记下已被访问过的顶点。设置一个辅助向量Visited1…n,其初值为0,一旦访问了顶点vi后,使Visited[i]为1或为访问的次序号。
图的遍历算法有深度优先搜索算法和广度优先搜索算法。

深度优先搜索(Depth First Search–DFS)

深度优先搜索(Depth First Search–DFS)遍历类似树的先序遍历,是树的先序遍历的推广。
1 算法思想
设初始状态时图中的所有顶点未被访问,则:
⑴ :从图中某个顶点vi出发,访问vi;然后找到vi的一个邻接顶点vi1 ;
⑵:从vi1出发,深度优先搜索访问和vi1相邻接且未被访问的所有顶点;
⑶:转⑴ ,直到和vi相邻接的所有顶点都被访问为止
⑷:继续选取图中未被访问顶点vj作为起始顶点,转(1),直到图中所有顶点都被访问为止。
算法实现
由算法思想知,这是一个递归过程。因此,先设计一个从某个顶点(编号)为v0开始深度优先搜索的函数,便于调用。
在遍历整个图时,可以对图中的每一个未访问的顶点执行所定义的函数。

typedef  emnu {
  FALSE , TRUE} BOOLEAN ;
BOOLEAN  Visited[MAX_VEX] ;
3  结点及其类型定义
#define MAX_VEX  30              /* 最大顶点数 */
typedef char VertexType; /* 顶点类型应由用户定义 */
typedef int EdgeType;      /* 边上的权值类型应由用户定义 */


typedef struct EdgeNode  /* 边表结点 */
{
    int adjvex;    /* 邻接点域,存储该顶点对应的下标 */
    EdgeType info;   /* 用于存储权值,对于非网图可以不需要 */
    struct EdgeNode *next; /* 链域,指向下一个邻接点 */
}EdgeNode;
typedef struct VertexNode /* 顶点表结点 */
{
    VertexType data;          /* 顶点域,存储顶点信息 */
    /* int indegree ; //顶点的度, 有向图是入度或出度 (亦可不要) */
    EdgeNode *firstarc;   /* 边表头指针 */
}VertexNode, AdjList[MAX_VEX];

typedef struct
{
    AdjList adjList;  //顶点数组(亦成为头结点向量)
    int numNodes,numEdges; /* 图中当前顶点数和边数 */
}GraphAdjList;
void  DFS( GraphAdjList *GL , int v)
{     EdgeNode *p ;
Visited[v]=TRUE ; 
Visit[v] ;       /* 置访问标志,访问顶点v */ 
p=GL->adjList[v].firstarc;   /* 链表的第一个结点 */
while (p!=NULL)
{  if  (!Visited[p->adjvex]) 
    DFS(GL, p->adjvex) ; // 从v的未访问过的邻接顶点递归调用
    p=p->next ;
}   }
void DFSTraverse (GraphAdjList *GL)
{       int v ;
        for (v=0 ; v<GL->vexnum ; v++)
        Visited[v]=FALSE ;    /* 访问标志初始化 */ 
        for (v=0 ; v<GL->vexnum ; v++)
            if (!Visited[v])   
                DFS(GL , v);
}

3 算法分析
采用邻接表作为存储结构遍历时,找邻接点所需的时间取决于顶点和边的数量,总时间复杂度为O(n+e) 。

采用邻接矩阵的深度优先递归算法
void DFS(MGraph G, int i)
{   int j;
    visited[i] = TRUE;
    Visit[v] ; 
    for(j = 0; j < G.numVertexes; j++)
        if(G.arc[i][j] == 1 && !visited[j])
            DFS(G, j); /* 对为访问的邻接顶点递归调用 */
}
void DFSTraverse(MGraph G)
{   int i;
    for(i = 0; i < G.numVertexes; i++)
         visited[i] = FALSE; /* 初始所有顶点状态都是未访问过状态 */
    for(i = 0; i < G.numVertexes; i++)
         if(!visited[i]) // 对未访问过的顶点调用DFS,若是连通图,只会执行一次
        DFS(G, i);
}

广度优先搜索(Breadth First Search–BFS)

广度优先搜索(Breadth First Search–BFS)遍历类似树的按层次遍历的过程。
1 算法思想
设初始状态时图中的所有顶点未被访问,则:
⑴ :从图中某个顶点vi出发,访问vi;
⑵:访问所有与vi相邻接且未被访问的所有顶点vi1,vi2,…,vim;
⑶:以vi1,vi2, …,vim的次序,以vij(1≦j≦m)依次作为vi ,转⑴;
⑷ :继续选取图中未被访问顶点vk作为起始顶点,转⑴,直到图中所有顶点都被访问为止。
2 算法实现
为了标记图中顶点是否被访问过,同样需要一个访问标记数组;
在访问vi时,为了依次访问与vi相邻接的各个顶点,需要附加一个队列来保存与vi相邻接的顶点。

bool  Visited[MAX_VEX] ;
typedef struct Queue
{  int   elem[MAX_VEX] ;
int  front , rear ;
}Queue ;     /* 定义一个队列保存将要访问顶点 */
void BFSTraverse (GraphAdjList *G)
{        建立空队列并初始化 (Q->front=Q->rear=0)
         访问标志初始化  (Visited[i]=false0≤i< G->vexnum ) 
          for (i=0 ; i<G->vexnum ; i++)
          {    if (!visited[i])
                {   visited[i]=true; 
                     访问该顶点;然后将让该顶点入队,
             while(!QueueEmpty(Q))
            {   DeQueue(&Q,&i);
                p = GL->adjList[i].firstedge; //找到当前顶点的边链表头指针                   while(p)
        {  if(!visited[p->adjvex])  /* 若此顶点未被访问 */
            {   visited[p->adjvex]=true;
                访问该顶点;然后将让该顶点入队
                               } //end of if                    
                            p = p->next;    /* 指针指向下一个邻接点 */
                 }//end of while
                     } 
               }
          }
}

广度优先搜索算法和深度优先搜索算法在时间复杂度上是一样的,不同之处仅仅在于顶点访问次序不同。
图的遍历可以系统地访问图中的每个顶点,因此,图的遍历算法是图的最基本、最重要的算法,许多有关图的操作都是在图的遍历基础之上加以变化来实现的。

最小生成树

如果连通图是一个带权图,则其生成树中的边也带权,生成树中所有边的权值之和称为生成树的代价。
最小生成树(Minimum Spanning Tree) :带权连通图中代价最小的生成树称为最小生成树。
构造最小生成树的算法有许多,最经典的有两种:
普里姆(Prim)算法
克鲁斯卡尔(Kruskal)算法

普里姆(Prim)算法

    从连通网N=(U,E)中找最小生成树T=(U,TE) 。
1 算法思想
⑴  若从顶点v0出发构造,U={v0},TE={};
⑵ 先找权值最小的边(u,v),其中u∈U且v∈V-U,并且子图不构成环,则U= U∪{v},TE=TE∪{(u,v)} ;
⑶ 重复⑵ ,直到U=V为止。则TE中必有n-1条边, T=(U,TE)就是最小生成树。

2 算法实现说明
设用邻接矩阵(二维数组)表示图,两个顶点之间不存在边的权值为机器允许的最大值。
为便于算法实现,设置一个一维数组closedge[n],用来保存V- U中各顶点到U中顶点具有权值最小的边。数组元素的类型定义是

struct 
{   int  adjvex ;     /* 权值最小的边所依附于U中的顶点 */
int  lowcost ;    /* 该边的权值 */
}closedge[MAX_EDGE] ;
如:closedge[j].adjvex=k,表明边(vj, vk)是V-U中顶点vj到U中权值最小的边,而顶点vk是该边所依附的U中的顶点。 
       closedge[j].lowcost存放该边的权值。
        在Prime算法中,图采用邻接矩阵存储,所构造的最小生成树用一维数组存储其n-1条边,每条边的存储结构描述:
typedef struct MSTEdge
{  int  vex1, vex2 ;    /* 边所依附的图中两个顶点 */
WeightType  weight ;     /* 边的权值 */
}MSTEdge ;
算法实现(略讲)
#define INFINITY MAX_VAL /* 最大值 */ 
MSTEdge *Prim_MST(AdjGraph *G , int u)
                                 /* 从第u个顶点开始构造图G的最小生成树 */
{  
          MSTEdge TE[] ;  // 存放最小生成树n-1条边的数组指针
          int j , k , v , min ;
          for (j=0; j<G->vexnum; j++)
         {  closedge[j].adjvex=u  ;
            closedge[j].lowcost=G->adj[j][u] ; 
          }                                          /* 初始化数组closedge[n] */ 
        closedge[u].lowcost=0 ;      /* 初始时置U={u} */ 
TE=(MSTEdge *)malloc((G->vexnum-1)*sizeof(MSTEdge)) ;
for (j=0; j<G->vexnum-1; j++)
{ min= INFINITY ;
  for (v=0; v<G->vexnum; v++) 
 if  (closedge[v].lowcost!=0&& closedge[v].Lowcost<min)
                                  {  min=closedge[v].lowcost ; k=v ;  }
                         TE[j].vex1=closedge[k].adjvex ; 
                         TE[j].vex2=k ;
                         TE[j].weight=closedge[k].lowcost ;
                         closedge[k].lowcost=0 ;      /* 将顶点k并入U中 */
                         for (v=0; v<G->vexnum; v++)
                               if (G->adj[v][k]<closedge[v]. lowcost)
                                 {  closedge[v].lowcost= G->adj[v][k] ;
                                    closedge[v].adjvex=k ; 
                                 }  /* 修改数组closedge[n]的各个元素的值 */
                       }
          return(TE) ;
}   /* 求最小生成树的Prime算法 */ 

克鲁斯卡尔(Kruskal)算法

1 算法思想
算法思想:设连通网N=(V,E),令最小生成树
初始状态为只有n个顶点而无边的非连通图T=(V,),每个顶点自成一个连通分量
在E中选取代价最小的边,若该边依附的顶点落在T中不同的连通分量上,则将此边加入到T中;否则,舍去此边,选取下一条代价最小的边
依此类推,直至T中所有顶点都在同一连通分量上为止
2 算法实现说明
Kruskal算法实现的关键是:当一条边加入到TE的集合后,如何判断是否构成回路?
解决方法:定义一个一维数组Vset[n] ,存放图T中每个顶点所在的连通分量的编号。
Vset[n] :
◆ 初值:Vset[i]=i,表示每个顶点各自组成一个连通分量,连通分量的编号简单地使用顶点在图中的位置(编号)。
◆ 当往T中增加一条边(vi,vj) 时,先检查Vset[i]和Vset[j]值:
若Vset[i]=Vset[j]:表明vi和vj处在同一个连通分量中,加入此边会形成回路;
若Vset[i]≠Vset[j],则加入此边不会形成回路,将此边加入到生成树的边集中。
◆ 加入一条新边后,将两个不同的连通分量合并:将一个连通分量的编号换成另一个连通分量的编号。

算法分析:设带权连通图有n个顶点,e条边,则算法的主要执行是:
◆ Vset数组初始化:时间复杂度是O(n) ;
◆ 边表按权值排序:若采用堆排序或快速排序,时间复杂度是O(e㏒e) ;
◆ while循环:最大执行频度是O(n),其中包含修改Vset数组,共执行n-1次,时间复杂度是O(n2) ;
整个算法的时间复杂度是O(e㏒e+n2) 。

    原文作者:陆讯
    原文地址: https://blog.csdn.net/wangzi11322/article/details/45417349
    本文转自网络文章,转载此文章仅为分享知识,如有侵权,请联系管理员进行删除。