输入城市信息和城市之间公路信息,建立图的邻接矩阵存储结构。
时间: 2024-02-01 14:16:51 浏览: 21
好的,以下是一个简单的示例代码:
```python
# 定义城市列表
cities = ['A', 'B', 'C', 'D']
# 定义邻接矩阵
adj_matrix = [
# A B C D
[0, 1, 0, 1], # A
[1, 0, 1, 1], # B
[0, 1, 0, 1], # C
[1, 1, 1, 0] # D
]
# 打印邻接矩阵
for i in range(len(cities)):
for j in range(len(cities)):
print(adj_matrix[i][j], end=' ')
print()
```
上述代码中,我们定义了一个城市列表 `cities`,其中包含了四个城市,分别用字母 A、B、C、D 表示。我们还定义了一个邻接矩阵 `adj_matrix`,它是一个 4x4 的矩阵,用于存储城市之间的公路信息。矩阵中的每个元素表示两个城市之间是否有公路,如果有公路则为 1,否则为 0。例如,`adj_matrix[0][1]` 表示城市 A 和城市 B 之间是否有公路,如果有,则为 1,否则为 0。
最后,我们通过两个嵌套的循环打印出整个邻接矩阵。
相关问题
构造图的邻接矩阵存储结构和邻接表存储结构
邻接矩阵是一种二维数组,其中数组的行和列分别代表图中的顶点,数组元素的值表示这两个顶点之间是否有边。如果顶点i和j之间有边,则邻接矩阵中第i行第j列的元素为1,否则为0。对于无向图来说,邻接矩阵是对称的,即第i行第j列和第j行第i列的元素是相同的。
邻接表是一种链表的形式,其中每个顶点对应一个链表,链表中存储与该顶点相连的其他顶点。邻接表的优点是可以动态地添加或删除边,节省了存储空间。但是,查找任意两个顶点之间是否有边需要遍历链表,效率相对较低。
在实际应用中,邻接矩阵适用于稠密图,而邻接表适用于稀疏图。同时,邻接矩阵更加适合进行矩阵计算(比如矩阵乘法),而邻接表更加适合进行图的遍历。
有向图的邻接矩阵和邻接表存储结构
有向图的邻接矩阵和邻接表存储结构是用于表示有向图中顶点之间相邻关系的两种方法。
1. 邻接矩阵存储结构:
有向图的邻接矩阵是一个n×n的方阵,其中n为图中顶点的个数。对于有向图中的每一条边(i,j),如果存在,则在邻接矩阵中第i行第j列的位置上标记为1,否则标记为0。如果有权值,则在对应位置上存储权值。邻接矩阵存储结构的空间复杂度为O(n^2)。
2. 邻接表存储结构:
邻接表是由一个一维数组和若干个链表组成,数组中的每个元素表示一个顶点,每个顶点vi的所有邻接点构成一个单链表,链表中的每个元素表示vi的一个邻接点。邻接表存储结构的空间复杂度为O(n+e),其中e为边的个数。
下面是Python代码示例:
```python
# 邻接矩阵存储结构
class DirectedGraph:
def __init__(self, vertex_num):
self.vertex_num = vertex_num
self.adj_matrix = [[0] * vertex_num for i in range(vertex_num)]
def add_edge(self, start, end, weight=1):
self.adj_matrix[start][end] = weight
# 邻接表存储结构
class DirectedGraph:
def __init__(self, vertex_num):
self.vertex_num = vertex_num
self.adj_list = [[] for i in range(vertex_num)]
def add_edge(self, start, end, weight=1):
self.adj_list[start].append((end, weight))
```