C/C++实现有向图的邻接表创建与遍历

本文档是关于使用C/C++语言实现有向图的邻接表表示的程序代码。主要内容包括创建有向图、显示有向图以及进行深度优先遍历的函数定义。 在计算机科学中，数据结构是组织和管理数据的重要工具。有向图是一种特殊的数据结构，其中的边具有方向性，即每个连接两个顶点的边都有明确的起点和终点。邻接表是一种常用的表示有向图的方式，它通过数组和链表组合来高效地存储图的结构。 代码中定义了以下主要结构： 1. `ArcNode` 结构体：表示有向图中的边，包含一个整型变量 `adjvex` 表示边的目标顶点，以及一个指向下一个边的指针 `nextarc`。 2. `VNode` 结构体：表示有向图的顶点，包含一个 `data` 字段用于存储顶点的信息，以及一个 `firstarc` 指针指向第一条与该顶点相邻的边。 3. `AdjList` 数组：存储 `VNode` 结构体，用于表示邻接表。 4. `ALGraph` 结构体：存储整个有向图的信息，包括 `AdjList` 邻接表，顶点数量 `vexnum` 和边数量 `arcnum`。 `CreateDG` 函数用于创建有向图。它首先初始化所有顶点的数据和邻接链表，然后根据用户输入的边信息逐个添加边到邻接表中。在输入过程中，用户需提供顶点总数和边总数，然后依次输入每条边的起始顶点和目标顶点。 `Disp` 函数用于显示有向图的结构，遍历每个顶点并打印其相邻顶点的信息。 `dfs` 函数虽然没有详细实现，但根据命名，应该是深度优先遍历的函数。深度优先遍历是从一个顶点开始，沿着边尽可能深地搜索图的分支，直到访问完一个分支上的所有顶点，然后回溯到上一层继续搜索其他分支。 这个程序对于理解有向图的邻接表表示以及如何在C/C++中实现这种数据结构非常有帮助。通过对邻接表的操作，可以实现图的各种操作，如遍历、查找路径等。同时，深度优先遍历是图算法中常见的基础操作，对于理解和实现其他图算法（如拓扑排序、强连通分量等）也很重要。