图的存储与遍历图的存储与遍历.doc

图的存储与遍历 本课程设计旨在让学生掌握《数据结构》课程中的相关知识，包括图的存储结构、队列的基本运算实现、邻接表的算法实现、图的广度优先搜索周游算法实现、图的深度优先搜索周游算法实现等。通过本次课程设计，学生将能够熟练掌握《数据结构》课程的相关知识，并提高自己的 C 语言基础和编程能力。 图的存储结构是本课程设计的核心内容之一。在本课程设计中，我们采用邻接表的存储结构来存储图。邻接表是一种链式的存储结构，在邻接表中，对图中每个顶点建立一个单链表，第 i 个单链表中的结点表示依附于顶点 Vi 的边（对有向图是以顶点 Vi 为尾的弧）。每个结点由 3 个域组成，其中邻接点域（adjvex）指示与顶点 Vi 邻接的点在图中的位置，链域（nextarc）指示下一条边或弧的结点；数据域（info）存储和边或弧相关的信息，如权值等。 为了实现图的存储，我们首先定义了邻接表的边结点类型以及邻接表类型，并对邻接表进行初始化。然后根据所输入的相关信息，包括图的顶点数、边数、是否为有向，以及各条边的起点与终点序号，建立图的邻接表。在建立邻接表时，我们需要分两种情况：有向图与无向图。对于无向图，一条边的两端顶点互为邻接点，所以在存储时，应向起点的单链表表头插入一边结点，即终点。同时将终点的单链表表头插入一边结点，即起点。对于有向图，只能向起点的单链表表头插入一个边结点，即终点。但不能反过来。 在输出邻接表时，我们采用 for 语句输出各结点，并配合一些符号完成邻接表的输出。由于不了解 C++ 中的绘图操作，我们无法使用图形化的方式输出邻接表。 图的遍历是本课程设计的另一个核心内容。在本课程设计中，我们实现了图的广度优先遍历和深度优先遍历两种遍历算法。对于广度优先遍历，我们利用队列的五种基本运算（置空队列、进队、出队、取队头元素、判队空）来实现。首先建立一空队列，从初始点出发进行访问，当被访问时入队，访问完出队。并以队列是否为空作为循环控制条件。对于深度优先遍历，则采用递归或非递归算法来实现。 在本课程设计中，我们还实现了图的深度优先遍历算法。深度优先遍历算法是一种遍历图的方法，它从一个顶点开始，沿着一条边或弧访问图中的所有顶点。深度优先遍历算法可以用来解决许多图论问题，如查找图中的环、检测图中的连通分量等。 本课程设计的实现环境为 Windows xp 系统，Microsoft Visual C++6.0 版本。在实现中，我们使用了 C 语言来编写程序，并使用 Visual C++6.0 作为开发环境。 本课程设计旨在让学生掌握《数据结构》课程中的相关知识，并提高自己的 C 语言基础和编程能力。通过本次课程设计，学生将能够熟练掌握图的存储结构、队列的基本运算实现、邻接表的算法实现、图的广度优先搜索周游算法实现、图的深度优先搜索周游算法实现等相关知识。