图的周游

1. 图的周游简介

1.1定义

图的周游：是一种按某种方式系统地访问图中的所有节点的过程，它使每个节点都被访问且只访问一次。图的周游也称图的遍历。

1.2分类

图的周游的方式有两种，分为深度优先周游（Depth First Traversal）和广度优先周游（Breadth First Traversal）。

深度优先周游又称深度优先搜索（DFS-Depth First Search），广度优先周游又称广度优先搜索（BFS-Breadth First Search）。

2. 深度优先周游

2.1基本思想

（1）给定图中的某个节点v，作为周游的起始节点，先访问v并标记为已访问； （2）然后选择一个与v邻接的未被访问的节点w，从w出发，按同样的方式出发； （3）当遇到这样一个节点，它的所有邻接节点都被访问，那么退回到已访问节点序列中最后一个拥有未被访问过的相邻节点的节点，访问它的一个未被访问的相邻节点u，再从u出发按同样方式前进。 （4）当所有已经被访问过的节点的相邻节点都被访问时，如果图中还有未被访问的节点，则从另一未被访问的节点出发，重复上面的过程，直到图中所有顶点都被访问过时，周游结束。

对图进行深度优先周游时，按访问顶点的先后次序所得到的顶点序列，成为该图的深度优先搜索序列，简称DFS序列。

2.2实例分析

以下面的一个连通图为例。

给定节点V1，那么深度遍历的顺序： V1->V2->V4->V8->V5->V3->V6->V7。

2.3算法实现

给定图G，在进行深度优先周游时，由于图中的每个顶点可能与图中其他多个顶点邻接并存在回路，为了避免重复访问已访问过的顶点，通常要对已访问的顶点作标记。为此，在顶点中增设一个标记字段mark。算法执行前，所有的mark字段均置为false，表示均为被访问，周游过程中将被访问的顶点的mark值设置为true。

伪代码描述如下：

void dfs(Graph g,Vertex v){
    v.mark=true; //设置已访问
    Vertex w;
    for(w=firstAdjacent(g,v);w!=NULL;w=nextAdjacent(g,v)){
        if(w.mark==false)
            dfs(g,w);
    }   
}

以下面的有向图为例，根据上面的伪代码可以实现出深度优先遍历的算法，并且还可以指定不经过指定节点集进行深度优先周游。图的存储方式采用邻接矩阵。并且假定节点从0开始编号且连续。

//func:不经过指定节点集的图的深度优先遍历
//param:matrix:邻接矩阵；node:起始节点；nodeVec：不经过的节点集；nodeNum:图的节点总数；mark:节点是否已被访问的标记
//retu:void 
void dfs(int* (*matrix),int node,vector<int>& nodeVec,int nodeNum,vector<bool>& mark){
    mark[node]=true; //设置为已访问
    cout<<node<<" "; //访问i节点
    for(int i=0;i<nodeNum;++i){ //寻找未被访问的相邻节点
        if(mark[i]==false){
            if(node==i) continue;
            if(matrix[node][i]!=INFINITY){ //如果是相邻节点
                vector<int>::iterator it=std::find(nodeVec.begin(),nodeVec.end(),i);
                if(it!=nodeVec.end()) //跳过指定节点
                    continue;
                dfs(matrix,i,nodeVec,nodeNum,mark);
            }
        }
    }
}

给定起点0，那么遍历输出结果为：0,1,2,3。给定起点1，遍历结果为：1,0,2,3。

如果指定不经过的节点2的话，且起始节点为1，那么遍历结果为：1,0,3。

2.4算法时间复杂度分析

分析上述算法，在遍历时，对图中每个顶点至多调用一次DFS 函数，因为一旦某个顶点被标志成已被访问，就不再从它出发进行搜索。因此，遍历图的过程实质上是对每个顶点查找其邻接点的过程。其耗费的时间则取决于所采用的存储结构。当用二维数组表示邻接矩阵图的存储结构时，查找每个顶点的邻接点所需时间为O(n2) ，其中n为图中顶点数。而当以邻接表作图的存储结构时，找邻接点所需时间为O(e)，其中e为无向图中边的数或有向图中弧的数。由此，当以邻接表作存储结构时，深度优先搜索遍历图的时间复杂度为O(n+e) 。

3.广度优先周游

3.1基本思想

广度优先遍历类似于树的按层次遍历的过程。其基本思想是： （1）从图的某个（未访问过的）顶点v出发，先访问v并标记为已访问； （2）接着依次访问v的所有未被访问过的相邻节点w1, w2, w3…,wi； （3）然后再依次访问与w1, w2, w3…,wi邻接的所有未被访问的节点； （4）以此类推，直到所有已访问顶点的相邻节点都被访问过为止。如果图中还有未被访问过的顶点，则从某个未被访问过的顶点出发进行同样方法搜索，主调图中所有顶点都被访问过，周游结束。

对图进行广度优先周游得到的顶点序列称为广度优先搜索序列，简称BFS。

3.2实例分析

还是以上面的图为例，

其广度优先遍历序列为：V1->V2->V3->V4->V5->V6->V7->V8。

3.3算法实现

因为广度优先搜索类似于树的层次遍历，所以需要用到队列存储各个层次访问过的节点。其伪代码实现如下：

//广度优先遍历二叉树，使用队列实现
void bfs(Graph g,Vertex v){
    if(g==NULL||v==NULL) return;
    Vertex vTemp;
    queue<Vertex> queue; //创建队列
    queue.push(v);       //起始节点如队列
    while(!queue.empty()){
        Vertex cur=queue.front();
        queue.pop(); //出队列
        if(cur.mark==true;)
             continue;
        cout<<" "<<cur.m_key;  //visit
        cur.mark=true;

        vTemp=firstAdjacent(g,cur);
        while(vTemp!=NULL){ //循环将所有当前节点的所有未被访问的相邻节点入队列
            if(vTemp.mark==false) queue.push(vTemp); //如果节点未被访问，入队列
            vTemp=nextAdjacent(g,cur); //获取cur的下一个相邻节点
        }
    }
}    
}

这里就不给出具体实现和测试了，按照上面的伪代码，应该很容易根据实际的需求实现自己想要的功能。

3.4算法时间复杂度分析

广度优先搜索的时间复杂度与深度优先搜索的时间复杂度相同。在遍历的过程中，时间主要花费在寻找当前节点的相邻节点上。具体见深度优先搜索的时间复杂度分析。

参考文献

[1]http://wenku.baidu.com/view/ed5dc92ded630b1c59eeb5b2.html [2]算法与数据结构——C语言描述（第二版）[M].张乃孝.高等教育出版社