图的广度优先搜索和深度优先搜索

一、图的基本操作 

二、图的遍历 

图的遍历是指从图中某一个顶点出发，按某种搜索方法沿着图中的边对图中的所有顶点都访问一次且仅访问一次。

图的任一顶点都可能会和其余的顶点相邻接，所以在访问某个顶点后，可能沿着某条路径搜索又回到该顶点上。为避免同一顶点被访问多次，在遍历图的过程中，我们必须记下每个已经访问过的顶点，为此可以设置一个辅助数组visited[]来标记顶点是否被访问过。

图的遍历算法主要有两种：广度优先搜索和深度优先搜索。

①广度优先搜索

(Breadth-First-Search,BFS)类似于树的层序遍历算法。

基本思想

BFS实现方法

• 找一个顶点的所有未访问过的邻接顶点我们用到这两个接口函数FirstNeighbor( G, x)、NextNeighbor( G, x, y )   
• 我们访问完
• bool型辅助数组visited[MAX_VERTEX_NUM]的下标用来代表每个顶点的编号，并存放它们是否被访问过的信息。

BFS算法代码

bool visited[MAX_VERTEX_NUM];
void BFS(Graph G,int V);
void BFSTraverse(Graph G)
{
    for(i=0;i<G.vexnum;i++)
    visited[i]=FALSE;//将顶点都标志为未访问过
    InitQueue(Q);//初始化辅助队列
    for(i=0;i<G.vexnum;i++)
    {
        if(!visited[i])//确保所有连通分量都被访问过一次，即上文基本思想中的6
        BFS(G,i);    
    }
        
}
void BFS(Graph G,int V)
{
    visit(V);//访问初始顶点
    visited[V]=TURE;//标志为已访问
    Enqueue(Q,V);//入队列
    while(!isEmpty(Q))
    {
        DeQueue(Q,V);//出队列去访问它的未访问过的邻接顶点
        for(w=FirstNeighbor(G,v);w>=0;w=NextNeighbor(G,v,w ))
        {//依次访问每一个未访问过的邻接顶点
            if(!visited[w])
            {
                visit(w);
                visited[w]=TURE;
                Enqueue(Q,w);//该顶点入队列   
            }     
    }
}

 BFS算法分析

• 无论是邻接表法还是邻接矩阵的存储方式，我们都需要一个辅助队列Q，空间复杂度为O(|V|)
• 采用邻接表存储方式时，每个顶点都入队一次时间复杂度为O(|V|),每条边都至少被访问一次(出边表遍历)时间复杂度为O(|E|)。故总的时间复杂度为O(|V|+|E|)。采用邻接矩阵存储方式时，查找每个顶点的邻接点所需的时间为O(|V|)，故算法总的时间复杂度为O(||)

BFS算法应用

• 我们可以使用BFS算法求解无权图的单源最短路径问题。这是由BFS算法总是按照距离由近及远来遍历图中的每个顶点的性质决定的。

• #define INFINITY 65535//用65535来代表无穷
  void BFS_MIN_Distance(Graph G,int u)
  {//d[i]表示从u到i的最短路径
    for(i=0;i<G.vexnum;i++)
      { d[i]=65535;//初始化路径长度
        path[i]=-1;//i的最短路径从哪个顶点过来
      }
      visited[u]=TRUE;
      d[u]=0;
      EQueue(Q,u);
   while(!isEmpty(Q))
      {
          DeQueue(Q,u);//队头元素出队列
          for(w=FirstNeighbor(G,u);w>=0;w=NextNeighbor(G,u,w ))
          {
              if(!visited[w])
              {
                  visited[w]=TRUE;
                  d[w]=d[u]+1//注意此处u为刚出队列的那个顶点
                  path[w]=u;//记录w顶点从哪个顶点过来的
                  EnQueue(Q,w);
              }
          }
      }
  }

②深度优先搜索 

(Depth-First-Search,DFS)类似于树的先序遍历算法。

基本思想

1. 首先访问起始顶点v；
2. 然后访问v的未访问过的邻接顶点。
3. 然后访问的未被访问过的邻接顶点；
4. 重复上述过程，当不能再向下访问时，依次退回到最近被访问的顶点，若它还有邻接顶点未被访问过，则从该点开始继续2~4的的过程。直到所有与起始顶点连通的顶点都被访问过为止。
5. 若此时图中尚有顶点未被访问，则另选图中一个未曾被访问过的顶点作为起始顶点，重复上述1~4过程，直到图中所有顶点都被访问过为止。

DFS实现方法

• 找一个顶点的所有未访问过的邻接顶点我们用到这两个接口函数FirstNeighbor( G, x)、NextNeighbor( G, x, y )   
• 我们看到第3步对的操作与第2步对v的操作相同，因此使用同一个函数，第4步的思想我们直接用递归(栈)实现即可。
• bool型辅助数组visited[MAX_VERTEX_NUM]的下标用来代表每个顶点的编号，并存放它们是否被访问过的信息。

DFS算法代码

bool visited[MAX_VERTEX_NUM];
void DFS(Graph G,int V);
void BFSTraverse(Graph G)
{
    for(i=0;i<G.vexnum;i++)
    visited[i]=FALSE;//将顶点都标志为未访问过
    for(i=0;i<G.vexnum;i++)
    {
        if(!visited[i])//确保所有连通分量都被访问过一次，即上文基本思想中的5
        DFS(G,i);    
    }        
}
void DFS(Graph G,int V)
{
    visit(V);//访问初始顶点
    visited[V]=TURE;//标志为已访问
        for(w=FirstNeighbor(G,v);w>=0;w=NextNeighbor(G,v,w ))
        {//步骤234的具体代码实现
            if(!visited[w])
            DFS(G,W);
        }
}

 DFS算法分析

• 深度优先搜索遍历算法是一个递归算法，需要借助一个递归工作栈，故空间复杂度为O(|V|)
• 采用邻接表存储方式时，每个顶点都标记过，故时间复杂度为O(|V|),每条边都至少被访问一次(出边表遍历)时间复杂度为O(|E|)，故时间复杂度为O(|V|+|E|)。采用邻接矩阵存储方式时，查找每个顶点的邻接点所需的时间为O(|V|)，故算法总的时间复杂度为O(||)

DFS算法应用 

深度优先搜索是求有向图的强连通分量的一个有效方法。假设以十字链表作为有向图的存储结构（方便我们一会逆向搜索，即从找出边变为找入边了），求强连通分量的步骤如下：

1. 在有向图G上，从某个顶点出发沿着以该顶点为尾的弧进行深度优先搜索遍历，并按其所有邻接点的搜索都完成(即退出DFS函数)的顺序将顶点排列起来。
2. 在有向图G上，从最后完成搜索的顶点出发，沿着以该顶点为头的弧进行逆向的深度优先搜索遍历。若此次遍历不能访问到有向图中所有顶点，则从余下的顶点中最后完成搜索的顶点出发，继续做逆向的深度优先搜索遍历，直到有向图中的顶点都被访问到为止。

• 由此，第二步每一次调用DFS作逆向深度优先遍历所访问到的顶点集便是有向图G中一个强连通分量的顶点集。

 

三、遍历得到的生成树、生成森林相关问题 

回顾：

1. 任意两个顶点都连通的无向图为连通图，任意两个顶点都强连通的有向图为强连通图。
2. 连通分量是无向图中的极大连通子图，强连通分量是有向图中的极大强连通子图。
3. 生成子图是包含全部顶点的子图，连通图的生成树是包含全部顶点的极小连通子图，非连通无向图的连通分量的生成树构成了非连通无向图的生成森林。
4. 只有一个顶点的入度为0，其余顶点的入度均为1的有向图，称为有向树。
5. 一个有向图的生成森林由若干有向树组成，含有图中的全部顶点，但只有足以构成若干棵不相交的有向树的弧。

广度优先搜索(BFS)

• 无向图：
• 连通图经过广度优先搜索后得到的遍历树为广度优先生成树。
• 非连通无向图经过广度优先搜索后得到的遍历树集合为广度优先生成森林。
• 有向图：
• 强连通图经过广度优先搜索后得到的遍历树为广度优先生成树。
• 非强连通有向图经过广度优先搜索后得到的遍历树集合为广度优先生成森林。

  ---

  王道教材上给的解释是只说了连通图，也就是无向图的生成森林问题。但举的例子又是一个有向图，很明显是牛头不对马嘴。具体怎么样不用管了，先按这样理解。

• 图按邻接矩阵存储时表示是唯一的，故其广度优先生成树、森林也是唯一的。按邻接表法存储时是不唯一的，故其广度优先生成树、森林也是不唯一的。

深度优先搜索 (DFS)

• 无向图：
• 连通图经过深度优先搜索后得到的遍历树为深度优先生成树。
• 非连通无向图经过深度优先搜索后得到的遍历树集合为深度优先生成森林。
• 有向图：
• 强连通图经过深度优先搜索后得到的遍历树为深度优先生成树。
• 非强连通有向图经过深度优先搜索后得到的遍历树集合为深度优先生成森林。

  ---

• 图按邻接矩阵存储时表示是唯一的，故其深度优先生成树、森林也是唯一的。按邻接表法存储时是不唯一的，故其深度优先生成树、森林也是不唯一的。

BFS与DFS综合对比 

• 对于无向图的广度优先生成树，起点到其他顶点的路径是图中对应的最短路径，即所有生成树中树高最小。此外，深度优先总是尽可能“深”地搜索图，因此路径可能会更长，故深度优先生成树的树高总是大于或等于广度优先生成树的树高。
• 对于无向图而言，void BFSTraverse(Graph G)调用遍历函数（BFS或DFS）的次数为无向图的连通分量的个数。
• 对于有向图而言，如果调用一次遍历函数（BFS或DFS)可以遍历到所有结点，不能说明该有向图强连通。调用遍历函数（BFS或DFS）的次数与有向图的强连通分量的个数无关，具体求强连通分量的算法见上述DFS算法的应用。

正文结束。 

DFS算法求强连通分量好像也可以这么做，不知道对不对。

可以看到也可以求出强连通分量 。