图的遍历（上）—— 深度优先搜索

图的遍历和树的遍历类似，最直接的理解就是，在图中某个顶点出发，访遍图中其余顶点，并且其中每个顶点仅被访问一次，这个过程就是图的遍历。

图的遍历主要有两种方式，一种是深度优先搜索，一种是广度优先搜索。我们先来看深度优先搜索。

深度优先搜索定义

深度优先搜索（Depth First Search），简称 DFS，这种算法有点像走迷宫，沿着一条路径一直走，如果某个路径不通，则回到前驱节点，以此为出发点继续尝试下一条路径，以此类推，直到访遍所有顶点。

深度优先搜索也是这样，它从图的某个顶点出发，访问此顶点，然后从该顶点未被访问的邻接顶点出发，深度遍历图，在未遇到已访问过的重复顶点前，我们约定右手优先原则，一直往前走，遇到已经访问过的顶点，则回溯到前驱顶点，访问与其相邻路径对应的邻接顶点，继续做上述判断，依次类推，直到图中所有与该顶点路径想通的顶点都被访问到，如下图所示：

如果还有顶点未被访问，则将其作为起点，重复上述过程，直到图中所有顶点都被访问到。

typedef int VertexType;
typedef int EdgeType;
//定义存储方式为邻接矩阵
typedef struct {
    VertexType vex[100];
    EdgeType edge[100];
    int vexNum, edgeNum;
}MGraph;

bool visited[100];
void DFSTravel(MGraph g) {
    int v;
    for ( v = 0; v < g.vexNum; ++v) {
        visited[v] = false;
    }
    for (v = 0; v < g.vexNum; v++) {
        if (!visited[v]) {
            DFS(G,v)
        }
    }
}
void DFS(MGraph g, int v) {
    std::cout<<v<<std::endl;
    visited[v] = true;
    for (int i = FirstNeighbor(G, v); i >= 0 ; i = NextNeighbor(G, v, i)) {
        if (!visited[i]) {
            DFS(G, i);
        }
    }
}

• FirstNeighbor(G, v)表示顶点 v 在图 G 中的一个邻接点
• NextNeighbor(G, v, i) 表示顶点 v 在图 G 中除 i 之外的其他邻接点

深度优先搜索的时间复杂度很显然是 O(v+e)，其中 v 表示顶点数，e 表示边数，需要额外的数组存储已访问顶点和前驱顶点，对应的空间复杂度是 O(v)。