c语言编程：邻接表和邻接矩阵实现图的广度遍历和深度遍历

邻接表和邻接矩阵是两种常见的图的表示方法。其中，邻接表是一个数组，每个元素表示一个节点，每个节点还有一个链表，存储与该节点相邻的节点；邻接矩阵则是一个二维数组，每个元素表示两个节点之间是否有边相连。

以下是使用邻接表和邻接矩阵实现图的广度遍历和深度遍历的代码示例：

1. 邻接表实现：

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

#define MAX_NODE 10

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

typedef struct VertexNode {
    int data;
    EdgeNode* firstedge;
} VertexNode;

typedef struct {
    VertexNode vertex[MAX_NODE];
    int vexnum, arcnum;
} Graph;

int visited[MAX_NODE];

// 建立邻接表
void CreateGraph(Graph* G) {
    int i, j, k;
    int v1, v2;
    EdgeNode* e;

    printf("请输入节点数和边数： ");
    scanf("%d%d", &G->vexnum, &G->arcnum);

    for (i = 0; i < G->vexnum; i++) {
        printf("请输入第%d个节点的值： ", i + 1);
        scanf("%d", &G->vertex[i].data);
        G->vertex[i].firstedge = NULL;
    }

    for (k = 0; k < G->arcnum; k++) {
        printf("请输入边(vi, vj)的顶点序号： ");
        scanf("%d%d", &v1, &v2);

        e = (EdgeNode*)malloc(sizeof(EdgeNode));

        e->adjvex = v2 - 1;
        e->next = G->vertex[v1 - 1].firstedge;
        G->vertex[v1 - 1].firstedge = e;

        e = (EdgeNode*)malloc(sizeof(EdgeNode));

        e->adjvex = v1 - 1;
        e->next = G->vertex[v2 - 1].firstedge;
        G->vertex[v2 - 1].firstedge = e;
    }
}

// 邻接表的深度遍历
void DFS(Graph* G, int v) {
    EdgeNode* p;

    visited[v] = 1;
    printf("%d ", G->vertex[v].data);

    p = G->vertex[v].firstedge;
    while (p) {
        if (!visited[p->adjvex]) {
            DFS(G, p->adjvex);
        }
        p = p->next;
    }
}

// 邻接表的广度遍历
void BFS(Graph* G, int v) {
    int queue[MAX_NODE];
    int front = 0, rear = 0;
    int u, w;
    EdgeNode* p;

    printf("%d ", G->vertex[v].data);
    visited[v] = 1;
    queue[rear++] = v;

    while (front != rear) {
        u = queue[front++];
        p = G->vertex[u].firstedge;

        while (p) {
            w = p->adjvex;
            if (!visited[w]) {
                printf("%d ", G->vertex[w].data);
                visited[w] = 1;
                queue[rear++] = w;
            }
            p = p->next;
        }
    }
}

int main() {
    Graph G;
    int i;

    CreateGraph(&G);

    // 初始化 visited 数组
    for (i = 0; i < G.vexnum; i++) {
        visited[i] = 0;
    }

    printf("邻接表的深度优先遍历结果：");
    for (i = 0; i < G.vexnum; i++) {
        if (!visited[i]) {
            DFS(&G, i);
        }
    }

    // 重新初始化 visited 数组
    for (i = 0; i < G.vexnum; i++) {
        visited[i] = 0;
    }

    printf("\n邻接表的广度优先遍历结果：");
    for (i = 0; i < G.vexnum; i++) {
        if (!visited[i]) {
            BFS(&G, i);
        }
    }

    return 0;
}

2. 邻接矩阵实现：

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

#define MAX_NODE 10

typedef struct {
    int vertex[MAX_NODE];
    int arc[MAX_NODE][MAX_NODE];
    int vexnum, arcnum;
} Graph;

int visited[MAX_NODE];

// 建立邻接矩阵
void CreateGraph(Graph* G) {
    int i, j, k;
    int v1, v2;

    printf("请输入节点数和边数： ");
    scanf("%d%d", &G->vexnum, &G->arcnum);

    for (i = 0; i < G->vexnum; i++) {
        printf("请输入第%d个节点的值： ", i + 1);
        scanf("%d", &G->vertex[i]);
    }

    for (i = 0; i < G->vexnum; i++) {
        for (j = 0; j < G->vexnum; j++) {
            G->arc[i][j] = 0;
        }
    }

    for (k = 0; k < G->arcnum; k++) {
        printf("请输入边(vi, vj)的顶点序号： ");
        scanf("%d%d", &v1, &v2);

        G->arc[v1 - 1][v2 - 1] = 1;
        G->arc[v2 - 1][v1 - 1] = 1;
    }
}

// 邻接矩阵的深度遍历
void DFS(Graph* G, int v) {
    int i;

    visited[v] = 1;
    printf("%d ", G->vertex[v]);

    for (i = 0; i < G->vexnum; i++) {
        if (G->arc[v][i] && !visited[i]) {
            DFS(G, i);
        }
    }
}

// 邻接矩阵的广度遍历
void BFS(Graph* G, int v) {
    int queue[MAX_NODE];
    int front = 0, rear = 0;
    int i, u;

    printf("%d ", G->vertex[v]);
    visited[v] = 1;
    queue[rear++] = v;

    while (front != rear) {
        u = queue[front++];

        for (i = 0; i < G->vexnum; i++) {
            if (G->arc[u][i] && !visited[i]) {
                printf("%d ", G->vertex[i]);
                visited[i] = 1;
                queue[rear++] = i;
            }
        }
    }
}

int main() {
    Graph G;
    int i;

    CreateGraph(&G);

    // 初始化 visited 数组
    for (i = 0; i < G.vexnum; i++) {
        visited[i] = 0;
    }

    printf("邻接矩阵的深度优先遍历结果：");
    for (i = 0; i < G.vexnum; i++) {
        if (!visited[i]) {
            DFS(&G, i);
        }
    }

    // 重新初始化 visited 数组
    for (i = 0; i < G.vexnum; i++) {
        visited[i] = 0;
    }

    printf("\n邻接矩阵的广度优先遍历结果：");
    for (i = 0; i < G.vexnum; i++) {
        if (!visited[i]) {
            BFS(&G, i);
        }
    }

    return 0;
}