深度优先搜索

类似于树的前序遍历
从某顶点v出发，依次从v的邻接点出发深度优先遍历

从V0出发，选择邻接点V1，从V1接着出发，以此类推访问V3、V7、V4。V4访问结束后由于其邻接点都已访问，则回到V7，同理回到V3、V1、V0，从V0的另外一个邻接点出发访问V2、直到V5、V6.

为便于区别顶点是否已经访问，利用访问标志数组。
已经访问过的标志1
以邻接表 表示

#define False 0
#define True 1
void ALGraph::DFStraverse( )       //深度优先搜索遍历以邻接表表示的图G
{
    int  v;
for(v=0; v<vertexNum; v++)
    visited[v]=False;              //标志向量初始化，visited数组已在类中数据成员部分定义
for(v=0; v<vertexNum; v++)
    if(! visited[v])DFS(v);
}//DFS

void ALGraph::DFS(int v)           //从第v个顶点出发深度优先遍历图G
{
    
    EdgeNode  ＊p; int  w;
    Visit(v);
    visited[v]=True;               //访问第v个顶点，并把访问标志置True
    for(p=adjlist[v].firstedge; p; p=p->next)
    {
     w=p->adjvertex;
    if(! visited[w])DFS(w);        //对v尚未访问的邻接顶点w递归调用DFS
    }
}

用二维数组表示，查找每个顶点的邻接点所需要时间O（n²），n为顶点数。用邻接表表示，查找顶点所需时间O(e)，e为边/弧数。所以时间复杂度是O(n+e)

广度优先搜索

类似于树的按层次遍历

以v为起始点，由近至远，依次访问和v有路径相通且路径长度为1,2, …的顶点。

上图以BFS：v0→v1→v2→v3→v4→v5→v6→v7

在遍历的过程中也需要一个访问标志数组。
为了顺次访问路径长度为2,3, …的顶点，需附设队列以存储已被访问的路径长度为1,2, …的顶点。

以邻接表为存储结构

void ALGraph ::BFS(int v)
{
    //从v出发按广度优先搜索遍历图G；使用辅助队列Q和访问标志数组visited
    EdgeNode  ＊p;
        int u, w;
        SeqQueue Q;
        for(v=0; v<vertexNum; v++)
            visited[v]=False;             //标志向量初始化
            Visit(v);                     //访问v，注意Visit函数和visited数组的区别
            visited[v]=True;              //把访问标志置True
            Q.En_Queue(v);                //v入队列
            while(! Q. Empty_Queue())
            {
    
                  Q.De_Queue(u);            //出队列
                  for(p=adjlist[u].firstedge; p; p=p->next)
                      {
    
                      w=p->adjvertex;
                      if(! visited[w])
                          {
    
                          Visit(w);
                          visited[w]=True;
                          Q.En_Queue(w); //u的尚未访问的邻接顶点w入队列Q
                          }
                      }
            }
} // BFS

以邻接矩阵为存储结构

void  MGraph ::BFStraverse( )
{
                                              //广度优先搜索遍历图G
    int  v;
    for(v=0; v<vertexNum; v++)
          visited[v]=False;                //标志向量初始化
    for(v=0; v<vertexNum; v++)
          if(! visited[v])BFS(v); //v未访问过，从v开始BFS
}

void  MGraph ::BFS(int  v)
{
    //以v为出发点，对图G进行BFS
    int i, j;
    SeqQueue Q;
    for(v=0; v<vertexNum; v++) visited[v]=False; //标志向量初始化
    Visit(v);                                  //访问
    visited[v]=True;
    Q.En_Queue(v);
    while(! Q.Empty_Queue())
      {
      Q.De_Queue(i);
        for(j=0; j<vertexNum; j++)
        //依次搜索i的邻接点j
          if(arcs[i][j]= =1 && ! visited[j])     //若j未访问
                {
      Visit(j);
                  visited[j]=True;
                  Q.En_Queue(j);                //j入队列
                }
        }
}//BFS

判定一个无向图是否为连通图/几个连通分量

（a）是一个非连通图，用邻接表存储调用两次DFS(分别从V0、V2出发)，得到（b）两个连通分量。