以邻接矩阵给出一张以整数编号为顶点的图

邻接矩阵是一种表示图的方法，其中矩阵的行和列分别表示图中的顶点，矩阵中的元素表示两个顶点之间是否有边相连。

以下是一张以整数编号为顶点的图的邻接矩阵：

   1  2  3  4  5
1    1    1  
2  1    1  1  
3    1      1
4  1  1      1
5      1  1  

其中，矩阵中的第 i 行第 j 列的元素为 1 表示顶点 i 和顶点 j 之间有一条边相连，为 则表示没有边相连。例如，矩阵中的第 1 行第 2 列的元素为 1，表示顶点 1 和顶点 2 之间有一条边相连。

相关问题

实现图的邻接矩阵的存储 编写程序，输入顶点的个数、边的个数、每个顶点的值、 每一条边及其权值,建立带权无向图 G 的邻接矩阵，并输出其邻接矩阵。 输入格式： 第一行两个整数分别表示图的顶点个数 m、边的个数 n，两个整数之间以空格分隔； 第二行的字符序列分别表示图的 m 个顶点的数据(为简单，每个顶点的数据为一个字符)； n 行数据，每行数据表示图的一条边的信息，每条边依附的两个顶点的值以及这条边的权 值。

以下是 Python 代码实现：

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

    def add_edge(self, u, v, weight):
        self.adj_matrix[u][v] = weight
        self.adj_matrix[v][u] = weight

    def print_adj_matrix(self):
        for row in self.adj_matrix:
            print(row)


m, n = map(int, input().split())
vertex_data = input().split()

g = Graph(m)

for i in range(n):
    u, v, weight = input().split()
    u = vertex_data.index(u)
    v = vertex_data.index(v)
    weight = int(weight)
    g.add_edge(u, v, weight)

g.print_adj_matrix()

首先输入图的顶点个数 `m` 和边的个数 `n`。然后输入顶点的数据 `vertex_data`，用一个字符序列表示。

接着依次输入每条边的信息，包括两个顶点的值和这条边的权值。在添加边的时候，根据输入的顶点值找到对应的顶点序号，然后调用 `add_edge` 方法添加边。

最后调用 `print_adj_matrix` 方法打印邻接矩阵。

示例输入：

5 7
A B C D E
A B 1
A C 2
A E 3
B C 4
B D 5
B E 6
C D 7

示例输出：

[0, 1, 2, 0, 3]
[1, 0, 4, 5, 6]
[2, 4, 0, 7, 0]
[0, 5, 7, 0, 0]
[3, 6, 0, 0, 0]

其中，矩阵的第 $i$ 行第 $j$ 列的元素表示顶点 $i$ 和顶点 $j$ 之间的边权值。如果两个顶点之间没有边，则为 $0$。

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

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


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

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