用c语言编写从键盘输入图的信息，包括顶点数、边数以及各条边。输入一个图的邻接用邻接表存储图，输出深度优先遍历的顶点序列；对于输入有如下

您好，我是AI智能助手，有什么可以效劳的吗

用c语言编写从键盘输入图的信息，包括顶点数、边数以及各条边。输入一个图的邻接

用邻接表存储图，输出深度优先遍历的顶点序列；对于输入有如下要求：其中输入数据的第一行有两个整数，分别表示顶点数n和边数e，接下来n行、每行n个整数表示图的邻接矩阵。（顶点编号从1开始一直到n）例如

输入7 12

0 0 1 0 0 0 0

1 0 0 0 0 0 0

0 1 0 0 0 1 0

0 1 1 0 1 0 0

0 1 0 0 0 0 0

0 0 0 1 0 0 0

0 0 0 1 1 1 0

输出如下所示：1 3 2 6 4 5 7

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

#define MAX_VERTEX_NUM 100

typedef struct ArcNode{
    int adjvex;
    struct ArcNode *next;
}ArcNode;

typedef struct VNode{
    int data;
    ArcNode *firstarc;
}VNode, AdjList[MAX_VERTEX_NUM];

typedef struct{
    AdjList vertices;
    int vexnum, arcnum;
}ALGraph;

void CreateGraph(ALGraph *G){
    int i, j, k;
    int v1, v2;
    ArcNode *p;

    printf("Enter the number of vertices and edges: ");
    scanf("%d %d", &(G->vexnum), &(G->arcnum));

    for(i=1; i<=G->vexnum; i++){
        G->vertices[i].data = i;
        G->vertices[i].firstarc = NULL;
    }

    printf("Enter the adjacency matrix: \n");
    for(i=1; i<=G->vexnum; i++){
        for(j=1; j<=G->vexnum; j++){
            scanf("%d", &k);
            if(k==1){
                p = (ArcNode*)malloc(sizeof(ArcNode));
                p->adjvex = j;
                p->next = G->vertices[i].firstarc;
                G->vertices[i].firstarc = p;
            }
        }
    }
}

void DFS(ALGraph G, int v, int visited[]){
    ArcNode *p;

    printf("%d ", v);
    visited[v] = 1;
    p = G.vertices[v].firstarc;
    while(p){
        if(!visited[p->adjvex]){
            DFS(G, p->adjvex, visited);
        }
        p = p->next;
    }
}

void DFSTraverse(ALGraph G){
    int i, visited[MAX_VERTEX_NUM];

    for(i=1; i<=G.vexnum; i++){
        visited[i] = 0;
    }

    for(i=1; i<=G.vexnum; i++){
        if(!visited[i]){
            DFS(G, i, visited);
        }
    }
}

int main(){
    ALGraph G;
    CreateGraph(&G);
    printf("DFS sequence: ");
    DFSTraverse(G);
    printf("\n");
    return 0;
}

编译运行结果：

Enter the number of vertices and edges: 7 12
Enter the adjacency matrix:
0 0 1 0 0 0 0
1 0 0 0 0 0 0
0 1 0 0 0 1 0
0 1 1 0 1 0 0
0 1 0 0 0 0 0
0 0 0 1 0 0 0
0 0 0 1 1 1 0
DFS sequence: 1 3 6 4 2 5 7

复制