建立一个以邻接矩阵形式存储的图

好的，让我们来建立一个无向图，其中包含5个节点和6条边：

    1 -- 2
    |    |
    3 -- 4 -- 5

我们可以使用邻接矩阵表示这个图。邻接矩阵是一个 $n\times n$ 的矩阵，其中 $n$ 是节点的数量。矩阵的元素 $a_{i,j}$ 表示节点 $i$ 和节点 $j$ 之间是否有边相连。如果节点 $i$ 和节点 $j$ 之间有边相连，则 $a_{i,j}=1$；否则，$a_{i,j}=0$。

对于上面的图，邻接矩阵为：

    0 1 1 0 0
    1 0 0 1 0
    1 0 0 1 0
    0 1 1 0 1
    0 0 0 1 0

其中，第 $i$ 行和第 $j$ 列的元素 $a_{i,j}$ 表示节点 $i$ 和节点 $j$ 之间是否有边相连。例如，$a_{1,2}=1$，表示节点1和节点2之间有一条边。

相关问题

建立一个以邻接矩阵形式存储的图的代码

下面是一个以邻接矩阵形式存储的有向图的 Python 代码示例：

class Graph:
    def __init__(self, num_vertices):
        self.num_vertices = num_vertices
        self.adj_matrix = [[0] * num_vertices for _ in range(num_vertices)]

    def add_edge(self, v1, v2):
        self.adj_matrix[v1][v2] = 1

    def remove_edge(self, v1, v2):
        self.adj_matrix[v1][v2] = 0

    def __str__(self):
        return '\n'.join([' '.join([str(x) for x in row]) for row in self.adj_matrix])

g = Graph(5)
g.add_edge(0, 1)
g.add_edge(1, 2)
g.add_edge(2, 3)
g.add_edge(3, 4)
g.add_edge(4, 0)

print(g)

输出：

0 1 0 0 0
0 0 1 0 0
0 0 0 1 0
0 0 0 0 1
1 0 0 0 0

在这个实现中，我们使用了一个二维列表 `adj_matrix` 来存储邻接矩阵。在初始化时，我们将所有项都设置为 0，表示没有边相连。每当我们添加一条边时，我们将相应的位置设置为 1。因为这是一个有向图，所以我们只在起点处设置 1，终点处不设置。如果需要删除一条边，我们只需要将相应位置的值设置为 0。最后，我们重载了 `__str__` 方法，使其返回邻接矩阵的字符串表示形式，方便输出和调试。

c语言建立一个以邻接矩阵形式存储的图 测试输入： 3 2 A B V A B 2 A V 4 预期输出： ∞ 2 4 2 ∞ ∞ 4 ∞ ∞

以下是使用C语言实现输入邻接矩阵形式存储的图，并输出其邻接矩阵的代码：

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

#define MAX_VERTEX_NUM 20
#define INFINITY 65535

typedef struct {
    char vexs[MAX_VERTEX_NUM];  // 存储顶点的数组
    int arcs[MAX_VERTEX_NUM][MAX_VERTEX_NUM];  // 存储邻接矩阵的二维数组
    int vexnum, arcnum;  // 图的顶点数和边数
} MGraph;

// 初始化邻接矩阵
void InitMGraph(MGraph *G) {
    int i, j;
    for (i = 0; i < G->vexnum; i++) {
        for (j = 0; j < G->vexnum; j++) {
            G->arcs[i][j] = INFINITY;  // 先全部置为无穷大
        }
        G->arcs[i][i] = 0;  // 自身到自身距离为0
    }
}

// 建图
void CreateMGraph(MGraph *G) {
    scanf("%d %d", &(G->vexnum), &(G->arcnum));  // 读入顶点数和边数
    getchar();  // 将回车符从缓冲区中取出
    int i, j, k, w;
    char vex1, vex2;
    for (i = 0; i < G->vexnum; i++) {
        scanf("%c", &(G->vexs[i]));  // 读入顶点
        getchar();  // 将回车符从缓冲区中取出
    }
    InitMGraph(G);  // 初始化邻接矩阵
    for (k = 0; k < G->arcnum; k++) {
        scanf("%c %c %d", &vex1, &vex2, &w);  // 读入边的信息
        getchar();  // 将回车符从缓冲区中取出
        for (i = 0; i < G->vexnum; i++) {
            if (G->vexs[i] == vex1) break;
        }
        for (j = 0; j < G->vexnum; j++) {
            if (G->vexs[j] == vex2) break;
        }
        G->arcs[i][j] = w;  // 存储边的权值
        G->arcs[j][i] = w;  // 无向图需要将(i,j)和(j,i)都存储
    }
}

// 输出邻接矩阵
void PrintMGraph(MGraph *G) {
    int i, j;
    for (i = 0; i < G->vexnum; i++) {
        for (j = 0; j < G->vexnum; j++) {
            if (G->arcs[i][j] == INFINITY) printf("∞   ");
            else printf("%-3d ", G->arcs[i][j]);
        }
        printf("\n");
    }
}

int main() {
    MGraph G;
    CreateMGraph(&G);
    PrintMGraph(&G);
    return 0;
}

输入测试数据：

3 2
A B V
A B 2
A V 4

输出：

0   2   4   
2   0   ∞   
4   ∞   0   

注意：输入时每行末尾可能会有一个回车符，需要将其从缓冲区中取出，否则这个回车符会被误认为是下一行的输入。