图的遍历和树的遍历类似,最直接的理解就是,在图中某个顶点出发,访遍图中其余顶点,并且其中每个顶点仅被访问一次,这个过程就是图的遍历。
图的遍历主要有两种方式,一种是深度优先搜索,一种是广度优先搜索。我们先来看深度优先搜索。
深度优先搜索定义
深度优先搜索(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)。
评论区