2. 图的遍历算法

作者: 執著我們的執著 | 来源:发表于2018-06-26 12:37 被阅读0次

2. 图的遍历算法
从0开始——图
三叉链表的遍历算法
树的遍历
DFS(深搜)算法
图和遍历
图的存储与遍历
二叉树的遍历--迭代法
（原创）不过如此的 DFS 深度优先遍历
搜索

图的遍历算法包括： 1. 深度优先搜索. 2. 广度优先搜索

1. 深度优先搜索 DFS （Depth First Search）

类似于二叉树的 先序遍历算法

算法： DFS(S)

访问S顶点
若S尚有未被访问的邻接点，则任取其一u，递归执行DFS(u)
否则，依次退回到最近被访问的顶点

注：典型的递归调用，为提高递归的效率，防止重复计算，通常引入一个标记数组来标记已经访问过的顶点

代码模版

DFS Code：
//伪码实现，类似于树的先序遍历
void DFS(Vertex v){
    visited[v] = true;
    for(v 的每个邻接点 W){
    if(!visited[W]){
        DFS(W);
    }
    }
}
/*******************************/

bool Visited[MAX_VERTEX_NUM]; // 标记数组
void DFS(Graph G, int v)
{
    visit(v);
    Visted[v] = true;
    for (w = FirstNeighbour(G,v); w >= 0; w = NextNeighbour(G,v,w)) {
        // 枚举 v 的每一个邻接点 w
        if (!Visited[w]) {      // w 为 v 的尚未访问的邻接点
            DFS(G, w);          // 以 w 为顶点，递归执行DFS
        }
    }
}

// 利用 DFS 遍历图G
void DFSTraverse(Graph G)
{
    for (int v = 0; v < G.vexNum; ++ v) {
        Visited[v] = false;
    }

    for (int v = 0; v < G.vexNum; ++ v) {
        // 本模板从 v=0 开始遍历
        if (!Visited[v]) {
            DFS(G, v);
        }
    }
}  
// 这个方法的作用在于，若图G为非连通图（多个连通域），仍可以深度遍历所有的顶点

DFS算法性能分析：
DFS是一个递归算法，需借助栈，空间复杂度为 O(|V|)
遍历图的实质是对每个顶点查找其邻接点的过程
以邻接矩阵存储的图为例：查找每个顶点的邻接点所需的时间为O(|V|)，故遍历全图的总时间为O(|V * V|)
（邻接表，O(|E|)，O(|V|＋|E|)）

补充：
深度优先遍历会产生一棵深度优先生成树，条件是： 对连通图调用DFS
否则产生的将是深度优先生成森林

图例：对非(强)连通有向图G进行 DFS 有
DFS

2. 广度优先搜索 BFS （Breadth First Search）

类似于二叉树的 层次遍历算法

算法：始于顶点S的广度优先搜索

访问顶点S
依次访问S所有尚未访问的邻接顶点
依次访问它们尚未访问的邻接顶点
... ...
如此反复执行 3 ，直到没有尚未访问的邻接顶点

广度优先搜索是一种分层的查找过程，每向前走一步可能访问一批顶点，不像DFS那样，有回退过程。因此BFS不是一个递归算法，为了实现逐层访问，必须借助一个辅助队列

代码模版

BFS Code ：

bool Visited[MAX_VERTEX_NUM];

void BFS(Graph G, int v)
{ // 从顶点v开始，借助一个一个辅助队列 Q
    visit(v);  // 访问 v
    Visited[v] = true;  // 标记为已访问
    Enqueue(Q, v);  // 将顶点 v 入队列

    while (!Q.empty()) {  // 队列不空
        Dequeue(Q, v);  // 出队列 v顶点
        for (w = FirstNeighbour(G,v); w >= 0; w = NextNeighbour(G,v,w)) { // 检测v所有的邻接点
            if (!Visited[w]) { // w为v未fangwen的邻接点
                visite(w);
                Visited[w] = true;
                Enqueue(Q, w); // 顶点w入队
            }
        }
    }
}

// 一幅图G中可能含有多个连通域，从一个顶点s出发，未必能够到达其他连通域，so，如何处理？使BFS适用于整幅图，而不是特定的连通域
void BFSTraverse(Graph G)
{
    for (int i = 0; i < G.vexNum; ++i) {
        Visited[i] = false;
    }
    InitQueue(Q);  // 初始化辅助队列Q
    for (int i = 0; i < G.vexNum; ++i) {
        if (!Visited[i]) {
            BFS(G,i);
        }
    }
}

BFS算法性能分析：
最坏情况下，空间复杂度为O(|V|)
时间复杂度：

邻接矩阵，总的时间复杂度为 O(|V|*|V|) 平方
邻接表，总的时间复杂度为 O(|V|+|E|)

BFS算法的应用

单源最短路径问题： 图G中，顶点u到顶点v的最短路径
G = (V , E)为非带权图，定义从顶点u到顶点v的最短路径d(u,v)为u到v的所有路径中最短的路径长度（边数最少），若u到v没有通路，则d(u,v) = ∞，实现求顶点u到顶点v的最短路径
d(u,v)
利用BFS算法来求解