Print Adjacency List for a Directed Graph in Java

邻接列表是图论中表示图的一种基本方法。在有向图中，每个顶点都跟踪它拥有出边的其他顶点。特别是对于稀疏图，这种形式在空间和时间复杂度方面都非常经济。本文解释了如何创建和显示有向图的邻接列表。

邻接列表表示

一个有向图的邻接列表是列表或数组的集合。此集合中的每个索引代表一个顶点，并且该索引处的每个列表包含可以直接从该顶点到达的顶点。例如，如果顶点“v”有边指向顶点“w”和“x”，则“v”的邻接列表将包含“w”和“x”。

实现有向图邻接列表的步骤

1.选择数据结构

我们将使用 HashMap 来存储邻接列表，其中

• 键代表顶点。
• 值是列表（或其他合适的数据结构），其中包含可以从键顶点直接到达的顶点。

为了表示顶点到顶点的边列表，我们将使用 ArrayList，它允许高效地添加边。

2.类设计

我们将定义一个 Graph 类来表示有向图。该类将包含用于

• 向图中添加顶点。
• 添加从一个顶点到另一个顶点的边。
• 打印邻接列表表示。

3.添加顶点和边

添加顶点时，我们将初始化邻接列表中的一个空边列表。添加边时，我们将目标顶点附加到源顶点关联的列表中。

4.打印邻接列表

通过遍历 map 并显示每个顶点及其连接顶点列表来打印邻接列表。

让我们在 Java 程序中实现上述步骤。

文件名: Graph.java

输出

 
Vertex 1: 2 3 
Vertex 2: 3 
Vertex 3: 4 
Vertex 4: 1   

解释

邻接列表是一种表示有向图的简单方法，其中每个元素都包含通过有向边连接到它的元素列表。为了表示上述 Java 图数据结构，我们可以使用 HashMap，其中 map 的键持有图的每个顶点，并且 map 中每个键的值持有图的每个顶点所指向的邻居列表或数组。

为此，我们设计了一个 Graph 类，它允许添加顶点、添加有向边以及打印邻接列表。邻接列表使用 hashmap 存储，其中实际的键是 ArrayList 邻居的值，这对于存储稀疏图很有效。

它还涉及创建可用的顶点以及边，然后遍历 map 来打印邻接列表。顶点插入、边插入和边删除都以 O(1) 的恒定时间运行，而列表打印需要 O(V + E) 的时间，其中 V 是顶点数，E 是边数。

复杂度分析

时间复杂度

添加顶点的时间复杂度为 O(1)，因为它只涉及 HashMap 中的插入。添加边平均需要 O(1) 时间，因为向 ArrayList 添加元素需要恒定时间。

打印需要 O(V + E) 的时间来打印列表。每当打印顶点时，该过程将需要 V，而打印边需要 E，因为我们将遍历所有边。

空间复杂度

空间复杂度为 O(V + E)，因为我们存储了每个顶点及其连接的边列表。

结论

邻接列表非常适合表示图，特别是稀疏图，如上述示例所示。在本文中，我们学习了如何使用 Java 语言中的邻接列表构建有向图。我们告诉您如何添加顶点和边以及如何打印邻接列表。这种结构对于任何基于节点遍历的图算法都很有用，例如深度优先搜索 (DFS) 或广度优先搜索 (BFS)。