图的遍历

　　从图中某一顶点出发，按某种搜索方法访遍其余顶点，且使每一顶点仅被访问一次。这一过程称为图的遍历。

　　遍历图的基本搜索方法有两种：深度优先搜索DFS（Depth First Search）和广度优先搜索BFS（Broad First Search）。这两种方法都适用于有向图和无向图。

图的遍历算法设计需要考虑3个问题：

  （1）图的特点没有首尾之分，所以算法的参考要指定访问的第一个顶点。

  （2）对图的遍历路径有可能构成一个回路，从而造成死循环，所以算法设计要考虑遍历路径可能的回路问题。

  （3）一个顶点可能和若干个顶点都是想邻顶点，要使一个顶点的所有想邻顶点按照某种次序被访问。

　　对于连通图，从初始顶点出发一定存在路径和图中的所有其他顶点相连，所以对于连通图从初始顶点出发一定可以遍历该图。

1．图的深度优先遍历

　　图的深度优先遍历DFS算法是每次在访问完当前顶点后，首先访问当前顶点的一个未被访问过的邻接顶点，然后去访问这个邻接点的一个未被访问过的邻接点，这样的算法是一个递归算法。

1) 连通图的深度优先遍历算法思想。

（1）访问初始顶点v并标记顶点v已访问。

（2）查找顶点v的第一个邻接顶点w。

（3）若顶点v的邻接顶点w存在，则继续执行；否则回溯到v，再找v的另外一个未访问过的邻接点。

（4）若顶点w尚未被访问，则访问顶点w并标记顶点w为已访问。

（5）继续查找顶点w的下一个邻接顶点wi，如果v取值wi转到步骤（3）。直到连通图中所有顶点全部访问过为止。

2) 深度优先遍历算法

(1)邻接矩阵的深度优先遍历算法：

void AdjMWGraph::Depth(int v,int visited[])

 { 

cout<<""\n 顶点"<权值："<

   visited[v]=1;

 for(int col=0;col

{ 

if(Edge[v][col]==0||Edge[v][col]==MaxWeight)

continue;

if(!visited[col])

Delpth(col,visited);

  }

}

　　故用邻接矩阵表示图时，搜索一个顶点的所有邻接点需花费O(n)时间，则从n个顶点出发搜索的时间应为O(n²)，即DFS算法的时间复杂度是（n²）。

 

(2)邻接链表的深度优先遍历算法：

Void AdjTWGraph::DepthFirst(int v, int visited[])

 { 

int vj; 

Edge *p;

  cout<

  visited[v]=1;

  p=Vertices[v].adj;     //取v的邻接边结点

  while(p!=NULL)

{ 

vj=p->dest;       //取v的邻接点编号

   if(visited[vj]==0)

DepthFirst(vj, visited);

   p=p->next;       //取下一个邻接边结点

  }

 }

　　使用邻接链表来表示图时,其 DFS 算法的时间复杂度为 O(n+e),此处 e 为无向图中边的数目或有向图中弧的数目。

2.图的广度优先遍历

　　图的广度优先遍历BFS算法是一个分层搜索的过程，和树的层序遍历算法类同，它也需要一个队列以保持遍历过的顶点顺序，以便按出队的顺序再去访问这些顶点的邻接顶点。

1) 连通图的广度优先遍历算法思想。

（1）顶点v入队列。

（2）当队列非空时则继续执行，否则算法结束。

（3）出队列取得队头顶点v；访问顶点v并标记顶点v已被访问。

（4）查找顶点v的第一个邻接顶点col。

（5）若v的邻接顶点col未被访问过的，则col入队列。

（6）继续查找顶点v的另一个新的邻接顶点col，转到步骤（5）。

2) 广度优先遍历算法

(1)邻接矩阵的广度优先遍历算法：

void AdjMWGraph::Depth(int v,int visited[])

 {  sqQueueq;        //定义队列queue

   q.EnQueue(v);        //顶点v入队列

   while(!q.IsEmpty())        //当队列非空时循环

       {  

v=q.DeQueue();        //出队列得到队头顶点u

  cout<顶点"<权值："<访问顶点v

      visited[col]=1;//标记顶点v已访问

     for(int col=0;col

if(Edge[v][col]>0;&&Edge[v][col]

          q.EnQueue(col);

   }

   cout<

 };

　　邻接矩阵表示图时，搜索一个顶点的所有邻接点需花费O(n)时间，则从n个顶点出发搜索的时间应为O(n²)，即BFS算法的时间复杂度是（n²）。

(2)邻接链表的深度优先遍历算法：

void AdjTWGraph::BroadFirst(int v, int visited[])

 {  

int vj;  

Edge *p;  

SqQueue Q;

Q.EnQueue(v);

    while(!Q.IsEmpty())               //队列不空，循环

      {  

v=Q.DeQueue();         //出队并且访问顶点v

     cout<

      p=Vertices[v].adj;             //取v的邻接边结点

while(p!=NULL)   {

vj=p->dest;     //取v的邻接点编号vj

     if(visited[vj]==0) Q.EnQueue(vj); //vj未访问，入队

       p=p->next;             //取下一个邻接边结点

    }

   }

  }

　　使用邻接链表来表示图时，其 BFS 算法的时间复杂度为 O(n+e) ，此处 e 为无向图中边的数目或有向图中弧的数目。