gpt-3.5-turbo-0613· OpenAI WildChat-4.8M (AI2)
试设计C算法,对以邻接矩阵存储的无向图进行深度优先遍历
- User
试设计C算法,对以邻接矩阵存储的无向图进行深度优先遍历
- Assistant
#include <stdio.h> #include <stdbool.h>
#define MAX_SIZE 100
int graph[MAX_SIZE][MAX_SIZE]; // 邻接矩阵表示的图 bool visited[MAX_SIZE]; // 访问标记数组 int n; // 图中节点的个数
// 深度优先遍历函数 void DFS(int u) { visited[u] = true; // 标记节点u为已访问
printf("%d ", u); // 输出访问的节点 // 遍历节点u的邻接点 for (int v = 0; v < n; v++) { if (graph[u][v] != 0 && visited[v] == false) { DFS(v); // 递归访问节点v } }}
int main() { int m; // 图中边的个数 printf("Enter the number of nodes: "); scanf("%d", &n);
printf("Enter the number of edges: "); scanf("%d", &m); printf("Enter the edges:\n"); for (int i = 0; i < m; i++) { int u, v; // u和v之间有一条边 scanf("%d %d", &u, &v); // 无向图的邻接矩阵两边都要标记为1 graph[u][v] = 1; graph[v][u] = 1; } printf("Depth First Traversal: "); for (int i = 0; i < n; i++) { visited[i] = false; // 初始化访问标记数组 } DFS(0); // 从节点0开始进行深度优先遍历 return 0;}