有向图 的邻接表

### 有向图的邻接表表示法 在计算机科学中，有向图可以通过多种方式进行存储和操作，其中一种常见的方法是使用邻接表来表示。邻接表是一种紧凑的数据结构，适合于稀疏图（即边数远少于顶点平方数量的情况）。它通过为每个顶点维护一个链表或数组，记录该顶点所指向的所有其他顶点。 以下是基于 Java 和 C++ 的两种实现方式： #### 基于 Java 的实现 Java 中可以利用 `Map` 数据结构来构建邻接表。下面是一个简单的例子，展示了如何定义一个有向图以及添加边的操作[^1]。 ```java import java.util.*; public class DirectedGraph { private Map<Integer, List<Integer>> adjacencyList; public DirectedGraph() { this.adjacencyList = new HashMap<>(); } public void addEdge(int from, int to) { adjacencyList.computeIfAbsent(from, k -> new ArrayList<>()).add(to); } public List<Integer> getNeighbors(int vertex) { return adjacencyList.getOrDefault(vertex, Collections.emptyList()); } public static void main(String[] args) { DirectedGraph graph = new DirectedGraph(); graph.addEdge(0, 1); graph.addEdge(0, 4); graph.addEdge(1, 2); graph.addEdge(1, 3); for (Map.Entry<Integer, List<Integer>> entry : graph.adjacencyList.entrySet()) { System.out.println(entry.getKey() + " -> " + entry.getValue()); } } } ``` 此代码片段展示了一个简单的方式去初始化一个有向图，并为其增加若干条边。最后打印出每一对节点及其对应的邻居列表。 #### 基于 C++ 的实现 C++ 提供了标准模板库 STL，其中包括 `vector` 容器，非常适合用来模拟邻接表的行为。这里给出一段类似的程序说明如何用 C++ 来完成相同的功能[^2]。 ```cpp #include <iostream> #include <vector> using namespace std; class DirectedGraph { private: vector<vector<int>> adj; int V; public: DirectedGraph(int vertices) : V(vertices), adj(vertices) {} void addEdge(int u, int v) { adj[u].push_back(v); } const vector<int>& getNeighbors(int u) const { return adj[u]; } friend ostream& operator<<(ostream &os, const DirectedGraph &g); }; ostream& operator<<(ostream &os, const DirectedGraph &g) { for (size_t i = 0; i < g.V; ++i) { os << i << ": "; for(auto neighbor : g.adj[i]) { os << neighbor << ' '; } os << '\n'; } return os; } int main(){ DirectedGraph G(5); // 创建具有五个顶点的图 G.addEdge(0, 1); G.addEdge(0, 4); G.addEdge(1, 2); G.addEdge(1, 3); cout << G; return 0; } ``` 以上两段代码分别演示了如何在不同编程语言环境下建立并管理有向图中的关系网络。它们都采用了邻接表的形式来进行内部数据组织。 ### 总结 无论是采用何种具体技术栈或者工具集，在实际应用过程中都需要考虑性能需求、内存消耗等因素的影响。因此选择合适的算法与数据结构至关重要。对于大多数场景而言，当涉及到大规模复杂度较高的运算时，推荐优先选用高效的解决方案如邻接表而非邻接矩阵形式表达图形信息[^3]。