c语言实现 建立无向图的邻接矩阵存储并输出。2. 建立图的邻接表存储并在此基础上实现图的深度优先遍历和广度优先遍历。

1. 无向图的邻接矩阵存储

#include <stdio.h>

#define MAX_VERTEX_NUM 100 // 最大顶点数

typedef struct {
    int vexs[MAX_VERTEX_NUM]; // 顶点数组
    int arcs[MAX_VERTEX_NUM][MAX_VERTEX_NUM]; // 邻接矩阵
    int vexnum, arcnum; // 顶点数和边数
} Graph;

void CreateGraph(Graph *G) {
    int i, j, k;
    printf("请输入顶点数和边数：");
    scanf("%d%d", &G->vexnum, &G->arcnum);
    printf("请输入顶点信息：");
    for (i = 0; i < G->vexnum; ++i) {
        scanf("%d", &G->vexs[i]);
    }
    for (i = 0; i < G->vexnum; ++i) {
        for (j = 0; j < G->vexnum; ++j) {
            G->arcs[i][j] = 0; // 初始化为0
        }
    }
    printf("请输入每条边的两个顶点序号：\n");
    for (k = 0; k < G->arcnum; ++k) {
        scanf("%d%d", &i, &j);
        G->arcs[i][j] = G->arcs[j][i] = 1; // i,j之间有边，邻接矩阵为1
    }
}

void PrintGraph(Graph G) {
    int i, j;
    printf("邻接矩阵：\n");
    for (i = 0; i < G.vexnum; ++i) {
        for (j = 0; j < G.vexnum; ++j) {
            printf("%d ", G.arcs[i][j]);
        }
        printf("\n");
    }
}

int main() {
    Graph G;
    CreateGraph(&G);
    PrintGraph(G);
    return 0;
}

2. 邻接表存储图并遍历

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

#define MAX_VERTEX_NUM 100 // 最大顶点数

typedef struct ArcNode { // 边结点
    int adjvex; // 相邻顶点序号
    struct ArcNode *next; // 下一条边
} ArcNode;

typedef struct {
    int data; // 顶点信息
    ArcNode *first; // 第一条边
} VNode;

typedef struct {
    VNode vertices[MAX_VERTEX_NUM]; // 顶点数组
    int vexnum, arcnum; // 顶点数和边数
} Graph;

void CreateGraph(Graph *G) {
    int i, j, k;
    printf("请输入顶点数和边数：");
    scanf("%d%d", &G->vexnum, &G->arcnum);
    printf("请输入顶点信息：");
    for (i = 0; i < G->vexnum; ++i) {
        scanf("%d", &G->vertices[i].data);
        G->vertices[i].first = NULL;
    }
    printf("请输入每条边的两个顶点序号：\n");
    for (k = 0; k < G->arcnum; ++k) {
        scanf("%d%d", &i, &j);
        // 添加一条边(i,j)
        ArcNode *node = (ArcNode *) malloc(sizeof(ArcNode));
        node->adjvex = j;
        node->next = G->vertices[i].first;
        G->vertices[i].first = node;
        // 添加一条边(j,i)
        node = (ArcNode *) malloc(sizeof(ArcNode));
        node->adjvex = i;
        node->next = G->vertices[j].first;
        G->vertices[j].first = node;
    }
}

void DFS(Graph G, int v, int *visited) {
    visited[v] = 1;
    printf("%d ", G.vertices[v].data);
    ArcNode *p = G.vertices[v].first;
    while (p != NULL) {
        if (!visited[p->adjvex]) {
            DFS(G, p->adjvex, visited);
        }
        p = p->next;
    }
}

void DFSTraverse(Graph G) {
    int i, visited[MAX_VERTEX_NUM] = {0}; // 初始化为0
    printf("深度优先遍历：");
    for (i = 0; i < G.vexnum; ++i) {
        if (!visited[i]) {
            DFS(G, i, visited);
        }
    }
    printf("\n");
}

void BFS(Graph G, int v, int *visited) {
    int queue[MAX_VERTEX_NUM], front = 0, rear = 0;
    visited[v] = 1;
    printf("%d ", G.vertices[v].data);
    queue[rear++] = v;
    while (front != rear) {
        int u = queue[front++];
        ArcNode *p = G.vertices[u].first;
        while (p != NULL) {
            if (!visited[p->adjvex]) {
                visited[p->adjvex] = 1;
                printf("%d ", G.vertices[p->adjvex].data);
                queue[rear++] = p->adjvex;
            }
            p = p->next;
        }
    }
}

void BFSTraverse(Graph G) {
    int i, visited[MAX_VERTEX_NUM] = {0}; // 初始化为0
    printf("广度优先遍历：");
    for (i = 0; i < G.vexnum; ++i) {
        if (!visited[i]) {
            BFS(G, i, visited);
        }
    }
    printf("\n");
}

int main() {
    Graph G;
    CreateGraph(&G);
    DFSTraverse(G);
    BFSTraverse(G);
    return 0;
}