已知有向图G=(V,E),其中:V={1,2,3,4,5,6},E={<2,1><2,4><3,2><3,6><4,3><4,6><5,1><6,1><6,2><6,5>设计一个算法,采用邻接矩阵创建有向图
时间: 2023-08-22 19:06:36 浏览: 153
邻接矩阵是一种用二维数组来表示有向图的方法,其中数组的行和列分别对应图中的顶点,数组中的元素表示顶点之间的边。对于有向图,邻接矩阵中的元素 a[i][j] 表示从顶点 i 出发是否有一条有向边可以到达顶点 j。
根据题目给出的有向图 G=(V,E),其中:V={1,2,3,4,5,6},E={<2,1><2,4><3,2><3,6><4,3><4,6><5,1><6,1><6,2><6,5>},我们可以设计如下算法来创建邻接矩阵:
1. 创建一个 V*V 的二维数组 A,并将其所有元素初始化为0。
2. 遍历所有的边 e(i,j),对于每一条边,将数组 A 中的元素 A[i][j] 设为 1。
3. 返回数组 A,即为该有向图的邻接矩阵。
Python 代码实现如下:
```python
V = [1, 2, 3, 4, 5, 6]
E = [(2, 1), (2, 4), (3, 2), (3, 6), (4, 3), (4, 6), (5, 1), (6, 1), (6, 2), (6, 5)]
def create_adjacency_matrix(V, E):
# 创建 V*V 的二维数组,并将其所有元素初始化为0
A = [[0] * len(V) for _ in range(len(V))]
# 遍历所有的边 e(i,j),将数组 A 中的元素 A[i][j] 设为 1
for e in E:
i, j = e
A[i-1][j-1] = 1
# 返回数组 A,即为该有向图的邻接矩阵
return A
adjacency_matrix = create_adjacency_matrix(V, E)
print(adjacency_matrix)
```
输出结果为:
```
[[0, 0, 0, 0, 0, 0],
[1, 0, 0, 1, 0, 0],
[0, 1, 0, 0, 0, 1],
[0, 0, 1, 0, 0, 1],
[1, 0, 0, 0, 0, 0],
[1, 1, 0, 0, 1, 0]]
```
相关推荐
![rar](https://img-home.csdnimg.cn/images/20210720083606.png)
![doc](https://img-home.csdnimg.cn/images/20210720083327.png)
![doc](https://img-home.csdnimg.cn/images/20210720083327.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)