Skip to content
TheChatArchiveThe Chat Archive
gpt-3.5-turbo-0301· OpenAIAi2 WildChat-4.8M (AI2)

编写c语言代码实现如下操作 :分别用邻接矩阵和邻接表存储图,输入一定数量的顶点和边,建立一个图; 2)实现图的深度优先遍历并输出结果; 3)实现图的广度优先遍历并输出结果。

  1. User

    编写c语言代码实现如下操作 :分别用邻接矩阵和邻接表存储图,输入一定数量的顶点和边,建立一个图; 2)实现图的深度优先遍历并输出结果; 3)实现图的广度优先遍历并输出结果。

  2. Assistant

    邻接矩阵存储图的代码实现:

    #include<stdio.h> #include<stdlib.h>

    #define MAX_NUM 100

    int graph[MAX_NUM][MAX_NUM];//邻接矩阵 int visited[MAX_NUM];//标记是否访问过

    void DFS(int v, int vertexNum){ printf("%d ", v); visited[v] = 1; for(int i=0;i<vertexNum;i++){ if(graph[v][i]&&!visited[i]){ //如果有边相连并且未访问过 DFS(i, vertexNum); } } }

    void BFS(int v, int vertexNum){ int queue[MAX_NUM]; int front=0, rear=0; visited[v] = 1; queue[rear++] = v;//进队列 while(front<rear){ //队列不为空 int cur = queue[front++]; //出队列 printf("%d ", cur); for(int i=0;i<vertexNum;i++){ if(graph[cur][i]&&!visited[i]){ //如果有边相连并且未访问过 visited[i]=1; queue[rear++]=i; } } } }

    int main(){ int vertexNum;//顶点数 int edgeNum;//边数 int v1, v2;//边的两个顶点

    printf("请输入顶点数和边数:");
    scanf("%d%d", &vertexNum, &edgeNum);
    
    //初始化邻接矩阵和visited数组
    for(int i=0;i<vertexNum;i++){
        for(int j=0;j<vertexNum;j++){
            graph[i][j]=0;
        }
        visited[i]=0;
    }
    
    //输入边
    for(int i=0;i<edgeNum;i++){
        printf("请输入第%d条边的两个顶点:", i+1);
        scanf("%d%d", &v1, &v2);
        graph[v1][v2] = graph[v2][v1] = 1;//建立双向边
    }
    
    //深度优先遍历
    printf("深度优先遍历结果为:");
    for(int i=0;i<vertexNum;i++){
        if(!visited[i]){//未访问过
            DFS(i, vertexNum);
        }
    }
    printf("\n");
    
    //初始化visited数组
    for(int i=0;i<vertexNum;i++){
        visited[i]=0;
    }
    
    //广度优先遍历
    printf("广度优先遍历结果为:");
    for(int i=0;i<vertexNum;i++){
        if(!visited[i]){//未访问过
            BFS(i, vertexNum);
        }
    }
    printf("\n");
    
    return 0;
    

    }

    邻接表存储图的代码实现:

    #include<stdio.h> #include<stdlib.h>

    #define MAX_NUM 100

    typedef struct node{//链表结点 int vertex; struct node* next; }Node;

    Node* graph[MAX_NUM];//邻接表 int visited[MAX_NUM];//标记是否访问过

    void insert(int v1, int v2){ Node* p = (Node*)malloc(sizeof(Node)); p->vertex = v2; p->next = graph[v1]; graph[v1] = p;

    p = (Node*)malloc(sizeof(Node));
    p->vertex = v1;
    p->next = graph[v2];
    graph[v2] = p;
    

    }

    void visit(int v){ printf("%d ", v); }

    void DFS(int v){ visited[v] = 1; visit(v); Node* p = graph[v]; while(p){ if(!visited[p->vertex]){ DFS(p->vertex); } p = p->next; } }

    void BFS(int v){ int queue[MAX_NUM]; int front=0, rear=0; visited[v] = 1; visit(v); queue[rear++] = v; while(front<rear){ int cur = queue[front++]; p = graph[cur]; while(p){ if(!visited[p->vertex]){ visited[p->vertex] = 1; visit(p->vertex); queue[rear++] = p->vertex; } p = p->next; } } }

    int main(){ int vertexNum;//顶点数 int edgeNum;//边数 int v1, v2;//边的两个顶点

    printf("请输入顶点数和边数:");
    scanf("%d%d", &vertexNum, &edgeNum);
    
    //初始化邻接表和visited数组
    for(int i=0;i<vertexNum;i++){
        graph[i] = NULL;
        visited[i] = 0;
    }
    
    //输入边
    for(int i=0;i<edgeNum;i++){
        printf("请输入第%d条边的两个顶点:", i+1);
        scanf("%d%d", &v1, &v2);
        insert(v1, v2);//建立单向边
    }
    
    //深度优先遍历
    printf("深度优先遍历结果为:");
    for(int i=0;i<vertexNum;i++){
        if(!visited[i]){//未访问过
            DFS(i);
        }
    }
    printf("\n");
    
    //初始化visited数组
    for(int i=0;i<vertexNum;i++){
        visited[i]=0;
    }
    
    //广度优先遍历
    printf("广度优先遍历结果为:");
    for(int i=0;i<vertexNum;i++){
        if(!visited[i]){//未访问过
            BFS(i);
        }
    }
    printf("\n");
    
    return 0;
    

    }