邻接矩阵创建图用非递归深度优先遍历
时间: 2024-06-05 15:04:46 浏览: 21
邻接矩阵是一种表示图的方式,它使用一个二维矩阵来表示图中各个节点之间的连接关系。具体而言,邻接矩阵中第i行第j列的元素表示第i个节点和第j个节点之间是否有边相连。如果有边相连,则为1;否则为0。
非递归深度优先遍历是一种遍历图的方法,它借助栈的数据结构来实现。具体而言,首先将起始节点压入栈中,然后依次从栈中取出一个节点进行遍历,并将该节点的所有未访问过的邻居节点压入栈中。当栈为空时,遍历结束。
邻接矩阵创建图用非递归深度优先遍历的步骤如下:
1. 创建一个邻接矩阵来表示图;
2. 创建一个空栈,并将起始节点压入栈中;
3. 当栈不为空时,从栈中取出一个节点进行遍历,并将该节点的所有未访问过的邻居节点压入栈中;
4. 标记已访问过的节点;
5. 重复步骤3和4,直到栈为空。
相关问题
c语言实现邻接矩阵非递归深度优先遍历
邻接矩阵是表示图的一种方式,非递归深度优先遍历是指不使用递归算法来实现深度优先遍历。下面是C语言实现邻接矩阵非递归深度优先遍历的步骤:
1. 定义一个栈结构,用于存储待遍历的节点。
2. 定义一个visited数组,用于记录每个节点是否已经被遍历。
3. 从某个起始节点开始,将其压入栈中,并将visited数组中对应位置标记为已访问。
4. 循环执行以下步骤直到栈为空:
a. 取出栈顶元素,并输出该节点。
b. 遍历该节点的所有邻居节点,若该邻居节点未被访问,则将其压入栈中并标记为已访问。
下面是邻接矩阵非递归深度优先遍历的C语言实现代码:
```c
#include <stdio.h>
#include <stdlib.h>
#define MAX_VERTEX_NUM 100
typedef int VertexType;
typedef int EdgeType;
typedef struct {
VertexType vertex[MAX_VERTEX_NUM];
EdgeType edge[MAX_VERTEX_NUM][MAX_VERTEX_NUM];
int vertex_num, edge_num;
} MGraph;
typedef struct {
VertexType data[MAX_VERTEX_NUM];
int top;
} Stack;
void InitStack(Stack *S) {
S->top = -1;
}
void Push(Stack *S, VertexType x) {
S->data[++S->top] = x;
}
VertexType Pop(Stack *S) {
return S->data[S->top--];
}
int IsEmpty(Stack *S) {
return S->top == -1;
}
void CreateGraph(MGraph *G) {
int i, j;
printf("请输入图的顶点数和边数:\n");
scanf("%d %d", &G->vertex_num, &G->edge_num);
printf("请输入各个顶点:\n");
for (i = 0; i < G->vertex_num; i++) {
scanf("%d", &G->vertex[i]);
}
for (i = 0; i < G->vertex_num; i++) {
for (j = 0; j < G->vertex_num; j++) {
G->edge[i][j] = 0;
}
}
printf("请输入各条边的起点和终点:\n");
for (i = 0; i < G->edge_num; i++) {
int u, v;
scanf("%d %d", &u, &v);
G->edge[u][v] = G->edge[v][u] = 1;
}
}
void DFS(MGraph *G, int v, int visited[]) {
Stack S;
InitStack(&S);
Push(&S, v);
visited[v] = 1;
while (!IsEmpty(&S)) {
int i, w = Pop(&S);
printf("%d ", G->vertex[w]);
for (i = 0; i < G->vertex_num; i++) {
if (G->edge[w][i] && !visited[i]) {
Push(&S, i);
visited[i] = 1;
}
}
}
}
void DFSTraverse(MGraph *G) {
int visited[MAX_VERTEX_NUM] = {0};
int i;
for (i = 0; i < G->vertex_num; i++) {
if (!visited[i]) {
DFS(G, i, visited);
}
}
}
int main() {
MGraph G;
CreateGraph(&G);
DFSTraverse(&G);
return 0;
}
```
邻接矩阵非递归深度遍历和邻接链表非递归层次遍历
以下是邻接矩阵非递归深度遍历和邻接链表非递归层次遍历的Python实现:
邻接矩阵非递归深度遍历:
```python
def DFS_iterative(graph, start):
visited = set() # 用集合存储已访问的节点
stack = [start] # 用栈存储待访问的节点
while stack:
vertex = stack.pop() # 取出栈顶节点
if vertex not in visited:
visited.add(vertex) # 将节点标记为已访问
print(vertex, end=' ')
# 将该节点的未访问过的邻居节点入栈
stack.extend([v for v in range(len(graph[vertex])) if graph[vertex][v] and v not in visited])
# 示例
graph = [[0, 1, 1, 0],
[1, 0, 0, 1],
[1, 0, 0, 1],
[0, 1, 1, 0]]
DFS_iterative(graph, 0) # 从节点0开始深度遍历
```
输出结果为:0 2 3 1
邻接链表非递归层次遍历:
```python
from collections import deque
def BFS_iterative(graph, start):
visited = set() # 用集合存储已访问的节点
queue = deque([start]) # 用队列存储待访问的节点
while queue:
vertex = queue.popleft() # 取出队首节点
if vertex not in visited:
visited.add(vertex) # 将节点标记为已访问
print(vertex, end=' ')
# 将该节点的未访问过的邻居节点入队
queue.extend([v for v in graph[vertex] if v not in visited])
# 示例
graph = {0: [1, 2],
1: [0, 3],
2: [0, 3],
3: [1, 2]}
BFS_iterative(graph, 0) # 从节点0开始层次遍历
```
输出结果为:0 1 2 3