输出图的深度优先遍历
时间: 2023-11-20 20:54:12 浏览: 48
深度优先遍历是一种图的遍历算法,它从图的某个顶点开始遍历,沿着一条路径遍历到底,直到该路径不能继续为止,然后回溯到前一个节点,再沿着另一条路径继续遍历,直到所有的节点都被访问到为止。下面是输出图的深度优先遍历的代码:
```
void DFS(Graph G, int v) {
visited[v] = true; cout << v << " ";
for (int w = 0; w < G.vexnum; w++) {
if (G.arcs[v][w] != 0 && !visited[w]) {
DFS(G, w);
}
}
}
void DFSTraverse(Graph G) {
for (int v = 0; v < G.vexnum; v++) {
visited[v] = false;
}
for (int v = 0; v < G.vexnum; v++) {
if (!visited[v]) {
DFS(G, v);
}
}
}
```
其中,`DFS`函数是深度优先遍历的核心算法,`DFSTraverse`函数是对整个图进行深度优先遍历的函数。在`DFS`函数中,首先将当前节点标记为已访问,然后输出该节点的值。接着,遍历该节点的所有邻接节点,如果邻接节点未被访问,则递归调用`DFS`函数。在`DFSTraverse`函数中,首先将所有节点的访问标志初始化为未访问,然后对每个未访问的节点调用`DFS`函数进行遍历。