建立无权值有向图的邻接矩阵
时间: 2023-09-05 10:07:51 浏览: 65
对于一个无权值有向图,我们可以使用邻接矩阵来表示。邻接矩阵是一个二维数组,其中第 i 行第 j 列的元素表示从顶点 i 到顶点 j 是否存在一条有向边。如果存在,则值为 1,否则为 0。
假设该图有 n 个顶点,则邻接矩阵的大小为 n × n。下面是一个示例代码,展示如何建立无权值有向图的邻接矩阵:
```python
# 建立一个有向图
graph = {
0: [1, 2],
1: [3],
2: [3],
3: [4],
4: []
}
# 初始化邻接矩阵
n = len(graph)
adj_matrix = [[0] * n for i in range(n)]
# 填充邻接矩阵
for i in range(n):
for j in graph[i]:
adj_matrix[i][j] = 1
# 输出邻接矩阵
for i in range(n):
print(adj_matrix[i])
```
输出结果为:
```
[0, 1, 1, 0, 0]
[0, 0, 0, 1, 0]
[0, 0, 0, 1, 0]
[0, 0, 0, 0, 1]
[0, 0, 0, 0, 0]
```
其中,第 i 行第 j 列的元素表示从顶点 i 到顶点 j 是否存在一条有向边。例如,第一行表示从顶点 0 出发可以到达顶点 1 和顶点 2,但是不能到达其它顶点。
相关问题
python根据邻接矩阵创建有向无权图
要根据邻接矩阵创建有向无权图,首先需要明确图的基本概念。有向图是由顶点集和边集构成的,而邻接矩阵则是通过一个二维矩阵表示了图中各个顶点之间是否存在边的信息。
对于给定的邻接矩阵,我们可以通过遍历矩阵中的每一个元素来创建相应的有向无权图。具体的步骤如下:
1. 创建一个空的有向无权图,使用字典来表示图中的顶点和边。每一个顶点对应一个键值对,键为顶点的名称,值为一个空列表,用来存储以该顶点为起点的边。
2. 遍历邻接矩阵的每一个元素,如果矩阵中的值为1,表示起点顶点到终点顶点存在一条有向边。
3. 根据矩阵的行和列的下标,找到对应的顶点名称,将终点顶点添加到起点顶点对应的边列表中。
4. 重复步骤2和3,直到遍历完整个邻接矩阵。
5. 返回创建好的有向无权图。
以一个简单的邻接矩阵为例,假设矩阵如下所示:
[[0, 1, 0],
[0, 0, 1],
[1, 0, 0]]
根据上述步骤,将矩阵转化为有向无权图,可以得到如下结果:
{
"A": ["B"],
"B": ["C"],
"C": ["A"]
}
其中,顶点的名称分别为A、B、C,A到B存在有向边,B到C存在有向边,C到A存在有向边。
这样就实现了通过给定的邻接矩阵创建有向无权图的过程。
扮演matlab,利用邻接矩阵构造无权有向图
首先,我们需要了解邻接矩阵的定义。邻接矩阵是一种表示图形的矩阵,其中每个元素[a] [b]表示从节点a到节点b的边的存在与否。
现在,我们利用邻接矩阵构造一个无权有向图。假设我们有5个节点,分别编号为1、2、3、4和5。那么我们可以先创建一个5x5的邻接矩阵,其中每个元素都初始化为0。
接下来,我们可以添加边来表示节点之间的连接。例如,如果我们想要从节点1指向节点2和节点3,我们可以将邻接矩阵中的[1] [2]和[1] [3]元素设置为1。同样地,如果我们想要从节点2指向节点4,我们可以将[2] [4]元素设置为1。
最终,我们可以得到以下邻接矩阵:
0 1 1 0 0
0 0 0 1 0
0 0 0 0 0
0 0 0 0 0
0 0 0 0 0
该邻接矩阵表示了一个无权有向图,其中节点1指向节点2和节点3,节点2指向节点4。节点3、4和5没有任何出边。