数据结构—图的遍历BFS、DFS

图的遍历算法可以用来判断图的连通性。

对于无向图来说，访问图中所有顶点所需调用BFS/DFS的次数就是连通分量数。但是对于有向图来说，具体问题需要具体分析，对于强连通图，只需调用一次，但是对于非强连通图就要具体分析。  

0、图的存储结构定义

1.  
   //图的邻接矩阵存储结构定义
2.  
   #define MaxVerNum 100 //顶点数目的最大值
3.  
   typedef struct{
4.  
   char Vex[MaxVerNum]; //顶点表
5.  
   int Edge[MaxVerNum][MaxVerNum]; //邻接矩阵，边表
6.  
   int vexnum,archnum; //图的当前顶点数和弧数
7.  
   }Graph;
8.  
    
9.  
   //图的邻接表存储结构定义
10.  
    #define MaxVerNum 100 //顶点数目的最大值
11.  
    typedef struct ArcNode{ //边表结点
12.  
    int adjvex; //该弧所指向的顶点的位置
13.  
    struct ArcNode *next; //指向下一条弧的指针
14.  
    int num; //图的权值
15.  
    }ArcNode;
16.  
    typedef struct VNode{ //顶点表信息
17.  
    char data; //顶点信息
18.  
    ArcNode *first; //指向第一条依附于该顶点的弧的指针
19.  
    }VNode,AdjList[MaxVerNum];
20.  
    typedef struct{
21.  
    AdjList vertices; //邻接表
22.  
    int vexnum,arcnum; //图的顶点数和弧数
23.  
    }Graph;

1、图的广度优先遍历（BFS）

图的广度优先遍历算法思想和二叉树的层次遍历算法思想几乎是相同的，需要一个辅助队列实现。

1.  
   //广度优先遍历
2.  
   bool visit[Maxnum]; //标记数组，防止顶点被多次访问
3.  
   void BFSTraverse(Graph G)
4.  
   {
5.  
   for(int i=0;i<G.vexnum;i ) //对标记数组进行初始化
6.  
   {
7.  
   visit[i]=false;
8.  
   }
9.  
   InitQueue(Q); //初始化辅助队列
10.  
    for(int i=0;i<G.vexnum;i ) //对每个连通分量调用一次BFS
11.  
    {
12.  
    if(!visit[i])
13.  
    BFS(G,i);
14.  
    }
15.  
    }
16.  
    void BFS(Graph G,int v)
17.  
    {
18.  
    visit[v]; //访问
19.  
    visit[v]=True; //标记
20.  
    EnQueue(Q,v); //顶点v入队
21.  
    while(!isEmpty(Q))
22.  
    {
23.  
    DeQueue(Q,v); //访问完出队
24.  
    for(w=FirstNeighbor(G,v);w>=0;w=NextNeighbor(G,V,W)) //寻找顶点v的所有邻接点
25.  
    {
26.  
    if(!visit[w])
27.  
    {
28.  
    visit[w];
29.  
    visit[w]=true;
30.  
    EnQueue(Q,w);
31.  
    }
32.  
    }
33.  
    }
34.  
    }

时间复杂度：邻接表：O(|V| |E|)；邻接矩阵：O(|V|^2)；

空间复杂度为：O(|V|)；主要来自于辅助队列

由广度优先遍历得到的遍历树称为：广度优先遍生成树。对于非连通图的广度优先遍历可得到广度优先森林。

2、图的深度优先遍历（DFS）

图的深度优先遍历算法思想和二叉树的先序遍历算法思想几乎相同。由于该算法是一个递归算法，所以它需要借助一个递归工作栈。 

1.  
   //图的深度优先遍历
2.  
   bool visit[Maxnum]; //标记数组，防止顶点被多次访问
3.  
   void DFSTraverse(Graph G)
4.  
   {
5.  
   for(int i=0;i<G.vexnum;i )
6.  
   {
7.  
   visit[i]=false;
8.  
   }
9.  
   for(int i=0;i<G.vexnum;i )
10.  
    {
11.  
    if(!visit[i])
12.  
    DFS(G,i);
13.  
    }
14.  
    }
15.  
    void DFS(Graph G,int v)
16.  
    {
17.  
    visit[v];
18.  
    visit[v]=true;
19.  
    for(w=FirstNeighbor(G,v);w>=0;w=NextNeighbor(G,V,W)) //从顶点v出发，深度优先遍历G
20.  
    {
21.  
    if(!visit[w]);
22.  
    DFS(G,w);
23.  
    }
24.  
    }

时间复杂度：邻接表：O(|V| |E|)；邻接矩阵：O(|V|^2)；

空间复杂度：O（|V|）；主要来自于递归工作栈。

深度优先搜索对连通图会产生深度优先生成树，对不连通图的深度优先遍历会产生深度优先森林。

这篇好文章是转载于：学新通技术网