用栈函数实现图的深度优先遍历代码
时间: 2023-10-30 18:12:01 浏览: 62
以下是使用栈函数实现图的深度优先遍历的代码:
```
void depthFirstSearch(int start, vector<vector<int> >& graph) {
stack<int> stk;
vector<bool> visited(graph.size(), false);
stk.push(start);
while (!stk.empty()) {
int curr = stk.top();
stk.pop();
if (visited[curr]) {
continue;
}
visited[curr] = true;
cout << curr << " ";
for (int i = graph[curr].size() - 1; i >= 0; i--) {
stk.push(graph[curr][i]);
}
}
}
```
这里假设图用邻接矩阵存储,graph[i] 表示与节点 i 相邻的其他节点。visited[i] 表示节点 i 是否被访问过。算法首先将起始节点压入栈中,然后不断从栈中弹出节点,访问它,并将它未被访问的相邻节点压入栈中,直到栈为空。
相关问题
C语言利用栈函数实现邻接表的深度优先遍历和广度优先遍历,用代码显示出来
深度优先遍历代码:
```c
#include <stdio.h>
#include <stdlib.h>
#define MAX_VERTEX_NUM 100
typedef struct ArcNode {
int adjvex;
struct ArcNode *nextarc;
} ArcNode;
typedef struct {
char data;
ArcNode *firstarc;
} VNode;
typedef struct {
VNode adjlist[MAX_VERTEX_NUM];
int vexnum, arcnum;
} ALGraph;
typedef struct {
int data[MAX_VERTEX_NUM];
int top;
} Stack;
void InitStack(Stack *S) {
S->top = -1;
}
int StackEmpty(Stack *S) {
return S->top == -1;
}
void Push(Stack *S, int x) {
S->data[++(S->top)] = x;
}
int Pop(Stack *S) {
return S->data[(S->top)--];
}
void DFS(ALGraph *G, int v, int visited[]) {
printf("%c ", G->adjlist[v].data);
visited[v] = 1;
ArcNode *p = G->adjlist[v].firstarc;
while (p) {
if (!visited[p->adjvex]) {
DFS(G, p->adjvex, visited);
}
p = p->nextarc;
}
}
void DFSTraverse(ALGraph *G) {
int visited[MAX_VERTEX_NUM] = {0};
for (int i = 0; i < G->vexnum; i++) {
if (!visited[i]) {
DFS(G, i, visited);
}
}
}
int main() {
ALGraph G;
int visited[MAX_VERTEX_NUM] = {0};
printf("请输入图的顶点数和边数:\n");
scanf("%d%d", &G.vexnum, &G.arcnum);
printf("请输入%d个顶点的值:\n", G.vexnum);
for (int i = 0; i < G.vexnum; i++) {
scanf(" %c", &(G.adjlist[i].data));
G.adjlist[i].firstarc = NULL;
}
printf("请输入%d条边的弧尾和弧头:\n", G.arcnum);
for (int i = 0; i < G.arcnum; i++) {
int u, v;
scanf("%d%d", &u, &v);
ArcNode *newArcNode = (ArcNode *)malloc(sizeof(ArcNode));
newArcNode->adjvex = v;
newArcNode->nextarc = G.adjlist[u].firstarc;
G.adjlist[u].firstarc = newArcNode;
}
printf("深度优先遍历结果为:");
DFSTraverse(&G);
printf("\n");
return 0;
}
```
广度优先遍历代码:
```c
#include <stdio.h>
#include <stdlib.h>
#define MAX_VERTEX_NUM 100
typedef struct ArcNode {
int adjvex;
struct ArcNode *nextarc;
} ArcNode;
typedef struct {
char data;
ArcNode *firstarc;
} VNode;
typedef struct {
VNode adjlist[MAX_VERTEX_NUM];
int vexnum, arcnum;
} ALGraph;
typedef struct {
int data[MAX_VERTEX_NUM];
int front, rear;
} Queue;
void InitQueue(Queue *Q) {
Q->front = Q->rear = -1;
}
int QueueEmpty(Queue *Q) {
return Q->front == Q->rear;
}
void EnQueue(Queue *Q, int x) {
Q->data[++(Q->rear)] = x;
}
int DeQueue(Queue *Q) {
return Q->data[++(Q->front)];
}
void BFS(ALGraph *G, int v, int visited[]) {
Queue Q;
InitQueue(&Q);
printf("%c ", G->adjlist[v].data);
visited[v] = 1;
EnQueue(&Q, v);
while (!QueueEmpty(&Q)) {
int u = DeQueue(&Q);
ArcNode *p = G->adjlist[u].firstarc;
while (p) {
int w = p->adjvex;
if (!visited[w]) {
printf("%c ", G->adjlist[w].data);
visited[w] = 1;
EnQueue(&Q, w);
}
p = p->nextarc;
}
}
}
void BFSTraverse(ALGraph *G) {
int visited[MAX_VERTEX_NUM] = {0};
for (int i = 0; i < G->vexnum; i++) {
if (!visited[i]) {
BFS(G, i, visited);
}
}
}
int main() {
ALGraph G;
printf("请输入图的顶点数和边数:\n");
scanf("%d%d", &G.vexnum, &G.arcnum);
printf("请输入%d个顶点的值:\n", G.vexnum);
for (int i = 0; i < G.vexnum; i++) {
scanf(" %c", &(G.adjlist[i].data));
G.adjlist[i].firstarc = NULL;
}
printf("请输入%d条边的弧尾和弧头:\n", G.arcnum);
for (int i = 0; i < G.arcnum; i++) {
int u, v;
scanf("%d%d", &u, &v);
ArcNode *newArcNode = (ArcNode *)malloc(sizeof(ArcNode));
newArcNode->adjvex = v;
newArcNode->nextarc = G.adjlist[u].firstarc;
G.adjlist[u].firstarc = newArcNode;
}
printf("广度优先遍历结果为:");
BFSTraverse(&G);
printf("\n");
return 0;
}
```
实现图的深度优先遍历 实现图的广度优先遍历
实现图的深度优先遍历可以使用递归或者栈来实现。具体步骤如下:
1. 从起始节点开始,将其标记为已访问。
2. 对于当前节点的每个未访问的邻居节点,递归调用深度优先遍历函数。
3. 重复步骤2,直到所有节点都被访问过。
以下是一个使用递归实现的Python代码示例:
```python
def dfs(graph, start, visited=None):
if visited is None:
visited = set()
visited.add(start)
print(start)
for next_node in graph[start] - visited:
dfs(graph, next_node, visited)
return visited
```
其中,graph是一个字典,表示图的邻接表;start是起始节点;visited是一个集合,用于记录已经访问过的节点。
实现图的广度优先遍历可以使用队列来实现。具体步骤如下:
1. 将起始节点加入队列,并标记为已访问。
2. 从队列中取出一个节点,访问它的所有未访问的邻居节点,并将它们加入队列。
3. 重复步骤2,直到队列为空。
以下是一个使用队列实现的Python代码示例:
```python
from collections import deque
def bfs(graph, start):
visited, queue = set(), deque([start])
visited.add(start)
while queue:
vertex = queue.popleft()
print(vertex)
for neighbor in graph[vertex]:
if neighbor not in visited:
visited.add(neighbor)
queue.append(neighbor)
```
其中,graph是一个字典,表示图的邻接表;start是起始节点。
相关推荐
![pdf](https://img-home.csdnimg.cn/images/20210720083512.png)
![pdf](https://img-home.csdnimg.cn/images/20210720083512.png)
![application/x-rar](https://img-home.csdnimg.cn/images/20210720083606.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)