有向图的创建

有向图是一种图形结构，其中每个节点都有向外的边，表示与其他节点之间的关系。创建有向图的一种常见方法是使用邻接表或邻接矩阵。

1. 邻接表法

邻接表是一个由节点和与该节点相邻的边组成的列表。在有向图中，每个节点列表包含所有指向该节点的边。可以使用字典或哈希表来实现邻接表。

2. 邻接矩阵法

邻接矩阵是一个由节点和与该节点相邻的边组成的矩阵，其中行和列表示节点，而矩阵中的元素表示两个节点之间是否存在边。在有向图中，如果节点 i 有一条指向节点 j 的边，则邻接矩阵中的元素 a[i][j] 为 1。

无论是邻接表还是邻接矩阵，都可以使用编程语言中的数据结构来实现。例如，在 Python 中，可以使用字典或二维数组来实现邻接表和邻接矩阵。以下是一个使用邻接表法创建有向图的 Python 代码示例：

graph = {1: [2, 3], 2: [4], 3: [4], 4: []}

在此示例中，字典 graph 表示有向图，其中键是节点，值是指向该节点的边所连接的其他节点。例如，节点 1 有两条边，分别指向节点 2 和节点 3。节点 4 没有任何出边，因此其值为空列表。

相关问题

有向图创建python代码

在Python中，可以使用邻接表或邻接矩阵来表示有向图，并通过相应的数据结构来创建有向图。下面是使用邻接表表示有向图的Python代码示例：

class DirectedGraph:
    def __init__(self):
        self.graph = {}

    def add_edge(self, start, end):
        if start in self.graph:
            self.graph[start].append(end)
        else:
            self.graph[start] = [end]

    def get_neighbors(self, node):
        if node in self.graph:
            return self.graph[node]
        else:
            return []

# 创建有向图对象
graph = DirectedGraph()

# 添加边
graph.add_edge(1, 2)
graph.add_edge(1, 3)
graph.add_edge(2, 3)
graph.add_edge(3, 4)

# 获取节点的邻居
neighbors = graph.get_neighbors(1)
print(neighbors)  # 输出：[2, 3]

上述代码中，`DirectedGraph`类表示有向图，使用字典`graph`来存储节点和其对应的邻居节点。`add_edge`方法用于添加边，`get_neighbors`方法用于获取节点的邻居。

图的邻接矩阵有向图创建输入案例

假设我们有一个有向图，其中有5个节点，分别为A、B、C、D、E，边的集合为{(A,B),(A,C),(B,C),(C,D),(D,E)}。邻接矩阵的创建过程如下：

首先，创建一个5x5的矩阵，所有元素初始化为0。

然后，对于每条边(A,B)、(A,C)、(B,C)、(C,D)和(D,E)，在邻接矩阵中相应的位置上填入1。注意，因为这是一个有向图，所以只需要在起点节点的行中填入1，而不需要在终点节点的列中填入1。

最终得到的邻接矩阵如下：

  | A | B | C | D | E |
--|---|---|---|---|---|
A | 0 | 1 | 1 | 0 | 0 |
--|---|---|---|---|---|
B | 0 | 0 | 1 | 0 | 0 |
--|---|---|---|---|---|
C | 0 | 0 | 0 | 1 | 0 |
--|---|---|---|---|---|
D | 0 | 0 | 0 | 0 | 1 |
--|---|---|---|---|---|
E | 0 | 0 | 0 | 0 | 0 |
--|---|---|---|---|---|