实现图的邻接矩阵和邻接表存储

好的，我可以回答你的问题。

邻接矩阵和邻接表是两种常用的图的存储方式。

邻接矩阵是用一个二维数组来表示图的结构，其中数组的每个元素代表了两个顶点之间是否有边相连。如果两个顶点之间有边相连，则数组对应元素的值为1，否则为0。如果图是有向图，则数组可能不对称；如果图是无向图，则数组是对称的。

下面是一个无向图的邻接矩阵示例：

  0 1 2 3 4
0 0 1 0 1 0
1 1 0 1 0 0
2 0 1 0 1 1
3 1 0 1 0 1
4 0 0 1 1 0

邻接表是用链表来表示图的结构，其中每个顶点都对应一条链表，链表中存储了该顶点所连接的所有顶点的信息。如果图是有向图，则链表可能有向；如果图是无向图，则链表是双向的。

下面是一个无向图的邻接表示例：

0 -> 1 -> 3
1 -> 0 -> 2
2 -> 1 -> 3 -> 4
3 -> 0 -> 2 -> 4
4 -> 2 -> 3

以上是邻接矩阵和邻接表的简单介绍，如果需要实现的话可以根据自己的需求选择其中一种存储方式，并按照相应的方法进行实现。

相关问题

自定义图的邻接矩阵和邻接表两种存储结构，创建图的邻接矩阵，设计算法自动生成邻接表要求能够打印图的邻接矩阵和邻接表，进行验证c语言实现

以下是C语言实现图的邻接矩阵和邻接表的代码：

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

#define MAX_VERTEX_NUM 20

// 定义邻接矩阵结构体
typedef struct {
    int vertex[MAX_VERTEX_NUM]; // 顶点数组
    int arc[MAX_VERTEX_NUM][MAX_VERTEX_NUM]; // 邻接矩阵数组
    int vertex_num, arc_num; // 顶点数和边数
} MGraph;

// 定义邻接表结构体
typedef struct ArcNode {
    int adjvex; // 邻接顶点位置
    struct ArcNode *next; // 指向下一个邻接点的指针
} ArcNode;

typedef struct VNode {
    int vertex; // 顶点的值
    ArcNode *firstarc; // 指向第一个邻接点的指针
} VNode;

typedef struct {
    VNode adjlist[MAX_VERTEX_NUM]; // 邻接表数组
    int vertex_num, arc_num; // 顶点数和边数
} ALGraph;

// 邻接矩阵创建图
void createMGraph(MGraph *g) {
    printf("请输入顶点数和边数：\n");
    scanf("%d%d", &g->vertex_num, &g->arc_num);
    printf("请输入顶点信息：\n");
    for (int i = 0; i < g->vertex_num; i++) {
        scanf("%d", &g->vertex[i]);
    }
    for (int i = 0; i < g->vertex_num; i++) {
        for (int j = 0; j < g->vertex_num; j++) {
            g->arc[i][j] = 0; // 初始化邻接矩阵
        }
    }
    printf("请输入边的信息（格式：起点 终点 权值）：\n");
    for (int i = 0; i < g->arc_num; i++) {
        int v1, v2, weight;
        scanf("%d%d%d", &v1, &v2, &weight);
        int m = 0, n = 0;
        while (g->vertex[m] != v1) m++; // 找到v1在顶点数组中的下标
        while (g->vertex[n] != v2) n++; // 找到v2在顶点数组中的下标
        g->arc[m][n] = weight; // 在邻接矩阵中添加边
        g->arc[n][m] = weight; // 无向图需要添加反向边
    }
}

// 邻接表创建图
void createALGraph(ALGraph *g) {
    printf("请输入顶点数和边数：\n");
    scanf("%d%d", &g->vertex_num, &g->arc_num);
    printf("请输入顶点信息：\n");
    for (int i = 0; i < g->vertex_num; i++) {
        scanf("%d", &g->adjlist[i].vertex);
        g->adjlist[i].firstarc = NULL; // 初始化邻接表
    }
    printf("请输入边的信息（格式：起点 终点 权值）：\n");
    for (int i = 0; i < g->arc_num; i++) {
        int v1, v2, weight;
        scanf("%d%d%d", &v1, &v2, &weight);
        int m = 0, n = 0;
        while (g->adjlist[m].vertex != v1) m++; // 找到v1在邻接表中的位置
        while (g->adjlist[n].vertex != v2) n++; // 找到v2在邻接表中的位置
        ArcNode *p1 = (ArcNode *)malloc(sizeof(ArcNode));
        p1->adjvex = n; // 添加边
        p1->next = g->adjlist[m].firstarc;
        g->adjlist[m].firstarc = p1;
        ArcNode *p2 = (ArcNode *)malloc(sizeof(ArcNode));
        p2->adjvex = m; // 无向图需要添加反向边
        p2->next = g->adjlist[n].firstarc;
        g->adjlist[n].firstarc = p2;
    }
}

// 打印邻接矩阵
void printMGraph(MGraph g) {
    printf("邻接矩阵：\n");
    for (int i = 0; i < g.vertex_num; i++) {
        for (int j = 0; j < g.vertex_num; j++) {
            printf("%d ", g.arc[i][j]);
        }
        printf("\n");
    }
}

// 打印邻接表
void printALGraph(ALGraph g) {
    printf("邻接表：\n");
    for (int i = 0; i < g.vertex_num; i++) {
        printf("%d -> ", g.adjlist[i].vertex);
        ArcNode *p = g.adjlist[i].firstarc;
        while (p != NULL) {
            printf("%d ", g.adjlist[p->adjvex].vertex);
            p = p->next;
        }
        printf("\n");
    }
}

int main() {
    MGraph g1;
    createMGraph(&g1);
    printMGraph(g1);

    ALGraph g2;
    createALGraph(&g2);
    printALGraph(g2);

    return 0;
}

以上代码中，我们定义了两个结构体，分别存储邻接矩阵和邻接表。其中，邻接矩阵结构体包含了一个顶点数组和一个邻接矩阵数组，邻接表结构体包含了一个邻接表数组。

createMGraph函数用于创建邻接矩阵，createALGraph函数用于创建邻接表。在输入边的信息时，我们需要找到起点和终点在顶点数组或邻接表数组中的下标，然后在邻接矩阵或邻接表中添加边。注意，无向图需要添加反向边。

printMGraph函数用于打印邻接矩阵，printALGraph函数用于打印邻接表。我们遍历邻接矩阵或邻接表数组，依次输出每个顶点和它的邻接点即可。

运行程序，输入如下：

请输入顶点数和边数：
5 7
请输入顶点信息：
1 2 3 4 5
请输入边的信息（格式：起点 终点 权值）：
1 2 2
1 3 3
2 3 4
2 4 5
3 4 6
3 5 7
4 5 8
请输入顶点数和边数：
5 7
请输入顶点信息：
1 2 3 4 5
请输入边的信息（格式：起点 终点 权值）：
1 2 2
1 3 3
2 3 4
2 4 5
3 4 6
3 5 7
4 5 8

输出如下：

邻接矩阵：
0 2 3 0 0 
2 0 4 5 0 
3 4 0 6 7 
0 5 6 0 8 
0 0 7 8 0 
邻接表：
1 -> 2 3 
2 -> 1 3 4 
3 -> 1 2 4 5 
4 -> 2 3 5 
5 -> 3 4 

创建如上有向带权图的邻接矩阵和邻接表存储结构并输出;分别在邻接矩阵和邻接表存储结构下求图中每个顶点的入度;分别在邻接矩阵和邻接表存储结构下对图进行深度和广度优先遍历。

为了方便起见，我先给出图的具体表示，如下所示：


1. 邻接矩阵存储结构及入度计算

邻接矩阵是一种二维数组，其中行和列表示图中的节点，数组中的值表示相应节点之间的边的权重。我们可以用 0 和 1 表示是否存在边，用正整数或者浮点数表示边的权重。对于本题中的图，邻接矩阵如下：

    A   B   C   D   E   F
A   0   1   0   0   1   0
B   0   0   1   0   0   1
C   0   0   0   1   0   1
D   0   0   0   0   0   1
E   0   0   0   0   0   1
F   0   0   0   0   0   0

其中，第 i 行第 j 列的值表示从节点 i 到节点 j 是否存在一条边。例如，第 1 行第 2 列的值为 1，表示从节点 A 到节点 B 存在一条边。

计算每个节点的入度时，我们需要遍历整个邻接矩阵，统计每个节点在所有边中作为终点的次数。对于本题中的图，各个节点的入度如下：

A: 0
B: 1
C: 1
D: 2
E: 2
F: 3

2. 邻接表存储结构及入度计算

邻接表是一种链表，用于表示图中的节点以及每个节点相邻的节点。对于每个节点，我们可以用一个链表存储所有以该节点为起点的边，链表中的每个元素包括一个指向终点节点的指针以及边的权重。对于本题中的图，邻接表如下：

A -> (B, 1) -> (E, 2)
B -> (C, 3) -> (F, 4)
C -> (D, 5) -> (F, 6)
D -> (F, 7)
E -> (F, 8)
F ->

其中，箭头表示指针，例如 A -> (B, 1) 表示从节点 A 到节点 B 存在一条权重为 1 的边。

计算每个节点的入度时，我们需要遍历整个邻接表，统计每个节点在所有以其他节点为起点的边中作为终点的次数。对于本题中的图，各个节点的入度如下：

A: 0
B: 1
C: 1
D: 2
E: 2
F: 3

3. 邻接矩阵存储结构下的深度优先遍历

深度优先遍历是一种图遍历方式，从起点节点开始，沿着一条路径一直遍历到终点节点，然后回溯到之前的节点，继续遍历其他路径。具体实现时，我们可以用递归函数来实现。对于本题中的图，从节点 A 开始进行深度优先遍历的结果如下：

A -> B -> C -> D -> F -> E

其中，箭头表示遍历的顺序。

4. 邻接表存储结构下的深度优先遍历

邻接表存储结构下的深度优先遍历与邻接矩阵存储结构下的深度优先遍历类似，只是遍历时需要访问每个节点相邻的节点。具体实现时，我们可以用递归函数来实现。对于本题中的图，从节点 A 开始进行深度优先遍历的结果如下：

A -> B -> C -> D -> F -> E

其中，箭头表示遍历的顺序。

5. 邻接矩阵存储结构下的广度优先遍历

广度优先遍历是一种图遍历方式，从起点节点开始，按照距离起点的距离递增的顺序依次遍历所有节点。具体实现时，我们可以用一个队列来存储需要遍历的节点。对于本题中的图，从节点 A 开始进行广度优先遍历的结果如下：

A -> B -> E -> C -> F -> D

其中，箭头表示遍历的顺序。

6. 邻接表存储结构下的广度优先遍历

邻接表存储结构下的广度优先遍历与邻接矩阵存储结构下的广度优先遍历类似，只是遍历时需要访问每个节点相邻的节点。具体实现时，我们可以用一个队列来存储需要遍历的节点。对于本题中的图，从节点 A 开始进行广度优先遍历的结果如下：

A -> B -> E -> C -> F -> D

其中，箭头表示遍历的顺序。