Skip to content
The Chat Archive
gpt-3.5-turbo-0613· OpenAI WildChat-4.8M (AI2)

试设计C算法,对以邻接矩阵存储的无向图进行深度优先遍历

  1. User

    试设计C算法,对以邻接矩阵存储的无向图进行深度优先遍历

  2. 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;
    

    }