一个连通图采用邻接表作为存储结构,设计一个算法,实现从顶点v出发的深度优先遍历的非递归过程。
时间: 2024-01-15 16:44:58 浏览: 141
非递归的深度优先遍历可以借助栈来实现。具体步骤如下:
1. 新建一个栈,将起始顶点v入栈。
2. 新建一个数组visited,记录每个顶点是否被访问过,将v对应的visited值设为true。
3. 取出栈顶元素,访问该顶点。
4. 遍历该顶点的所有邻接点,如果邻接点未被访问过,则将其入栈,并将其visited值设为true。
5. 重复步骤3和步骤4,直到栈为空。
下面是相应的C++代码实现:
```c++
void DFS(Graph& G, int v) {
stack<int> stk;
bool visited[G.numVertices];
for (int i = 0; i < G.numVertices; i++) {
visited[i] = false;
}
stk.push(v);
visited[v] = true;
while(!stk.empty()) {
int curr = stk.top();
stk.pop();
cout << curr << " ";
for (auto it = G.adjList[curr].begin(); it != G.adjList[curr].end(); it++) {
int adj = *it;
if (!visited[adj]) {
stk.push(adj);
visited[adj] = true;
}
}
}
}
```
其中,Graph是邻接表存储的图,numVertices是图的顶点数,adjList是邻接表。函数DFS的参数v是起始顶点。
阅读全文