邻接矩阵存储图的深度优先遍历
时间: 2023-07-24 14:38:48 浏览: 53
深度优先遍历(Depth-First-Search,DFS)是一种经典的图遍历算法,邻接矩阵存储图的深度优先遍历可以通过递归实现。具体步骤如下:
1. 首先访问起始节点,并将其标记为已访问。
2. 遍历起始节点的所有邻居节点,如果邻居节点未被访问,则递归遍历该邻居节点。
3. 重复步骤2,直到所有节点都被访问过。
代码实现如下:
```python
# 定义邻接矩阵
graph = [[0, 1, 1, 0],
[1, 0, 1, 1],
[1, 1, 0, 1],
[0, 1, 1, 0]]
# 定义访问数组
visited = [False] * len(graph)
# 定义深度优先遍历函数
def dfs(graph, visited, node):
visited[node] = True
print(node, end=' ')
for i in range(len(graph)):
if graph[node][i] == 1 and not visited[i]:
dfs(graph, visited, i)
# 调用深度优先遍历函数
dfs(graph, visited, 0)
```
输出结果为:0 1 2 3,表示深度优先遍历的顺序为节点0、节点1、节点2和节点3。
相关问题
邻接矩阵存储图的深度优先遍历 代码
以下是邻接矩阵存储图的深度优先遍历的代码实现:
```C++
#define MaxVertexNum 100 // 最大顶点数设为100
typedef char VertexType; // 顶点类型设为字符型
typedef int EdgeType; // 边权值设为整型
typedef struct{
VertexType Vex[MaxVertexNum]; // 顶点表
EdgeType Edge[MaxVertexNum][MaxVertexNum];// 邻接矩阵,可看作边表
int vexnum, arcnum; // 图的当前点数和边数/弧数
}MGraph;
bool visited[MaxVertexNum]; // 访问标记数组,初始化为false
// 邻接矩阵的深度优先递归算法
void DFS(MGraph G, int v){
visited[v] = true; // 标记v已访问
printf("%c ", G.Vex[v]); // 输出顶点的数据
for(int i = 0; i < G.vexnum; i++){
if(G.Edge[v][i] != 0 && !visited[i]){
DFS(G, i); // 对访问的邻接顶点递归调用
}
}
}
// 邻接矩阵的深度遍历操作
void DFSTraverse(MGraph G){
for(int i = 0; i < G.vexnum; i++){
visited[i] = false; // 初始化所有顶点状态都是未访问过状态
}
for(int i = 0; i < G.vexnum; i++){
if(!visited[i]){ // 对未访问过的顶点调用DFS,若是连通图,只会执行一次
DFS(G, i);
}
}
}
```
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;
}
```