输出其中图的深度优先遍历代码
时间: 2023-10-30 13:19:18 浏览: 29
以下是图的深度优先遍历代码示例:
```
void DFS(int u, vector<int> adj[], vector<bool> &visited) {
visited[u] = true;
cout << u << " ";
for (int v : adj[u]) {
if (!visited[v]) {
DFS(v, adj, visited);
}
}
}
void DepthFirstSearch(vector<int> adj[], int V) {
vector<bool> visited(V, false);
for (int u = 0; u < V; u++) {
if (!visited[u]) {
DFS(u, adj, visited);
}
}
}
```
其中,`adj[]` 表示图的邻接表,`V` 表示节点数,`DFS()` 函数进行深度优先搜索,`DepthFirstSearch()` 函数遍历所有未被访问过的节点。在遍历过程中,我们首先将当前节点标记为已访问,并输出该节点。然后遍历该节点的所有邻居节点,如果邻居节点未被访问,则递归调用 `DFS()` 函数。
相关问题
输出图的深度优先遍历
深度优先遍历是一种图的遍历算法,它从图的某个顶点开始遍历,沿着一条路径遍历到底,直到该路径不能继续为止,然后回溯到前一个节点,再沿着另一条路径继续遍历,直到所有的节点都被访问到为止。下面是输出图的深度优先遍历的代码:
```
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`函数进行遍历。
图的深度优先遍历代码
以下是邻接矩阵存储图的深度优先遍历的代码实现:
```python
def DFS(graph, start):
visited = [False] * len(graph) # 初始化visited数组
stack = [start] # 初始化栈
while stack:
vertex = stack.pop() # 取出栈顶元素
if not visited[vertex]:
visited[vertex] = True # 标记为已访问
print(vertex, end=' ') # 输出遍历结果
for i in range(len(graph)):
if graph[vertex][i] == 1 and not visited[i]:
stack.append(i) # 将未访问的邻居节点入栈
```
其中,graph是邻接矩阵,start是遍历的起点。该算法使用了一个栈来存储待访问的节点,每次取出栈顶元素,将其未访问的邻居节点入栈,直到栈为空为止。