DOS下无向图深度广度遍历实现与代码

本篇文章主要介绍了如何在DOS环境下实现一个无向图的建立和深度遍历、广度遍历功能。首先，作者提到了程序的目的，即通过用户输入各顶点表示符和边的信息，创建一个无向图，并使用深度优先搜索（DFS）和广度优先搜索（BFS）算法进行遍历。程序在Visual Studio 2010环境中经过多次调试，确保其正确性。 在结构定义部分，文章引入了以下几个关键概念： 1. `vrtype` 和 `vertextype`：分别代表顶点关系类型和顶点类型，其中 `vrtype` 可以是整型（用于有权图的邻接状态，如0表示不相邻，1表示相邻），而 `vertextype` 是字符型，用于存储顶点标识符。 2. `graphkind`：枚举类型，定义了四种类型的图：有向图（dg）、有向非加权图（dn）、无向图（udg）和无向非加权图（udn），这将影响图的遍历方式。 3. `arccell` 和 `adjmatrix`：`arccell` 结构体表示边的元素，包括邻接顶点（`adj`）和边的附加信息（`info`）。`adjmatrix` 是一个二维数组，用于存储无向图的邻接矩阵。 4. `mgraph` 结构体：用于封装图的属性，包括顶点（`vexs`）、邻接矩阵（`arcs`）、顶点数量（`vexnum`）、边的数量（`arcnum`）以及图的类型（`kind`）。 接下来，文章展示了创建不同类型的图的函数，如 `createdg()`、`createdn()`、`createudg()` 和 `createudn()`，它们分别为有向图、有向非加权图、无向图和无向非加权图的构建函数。其中，`createudn()` 函数要求用户输入顶点数和边的条数，以便动态创建图。 最后，程序中的 `locatevex()` 函数用于查找指定顶点在顶点数组中的位置，当找到时返回索引，否则返回 `vexnum` 表示顶点未找到。 核心部分的程序源代码使用了 `iostream` 和 `malloc.h` 库，主要功能是用户交互和内存管理。深度遍历和广度遍历的具体实现代码没有在给定的部分中提供，但根据描述，这部分应该会包含递归或队列操作来遍历图并打印出相应的访问顺序。 总结起来，本文档提供了在C++中创建无向图并进行深度和广度遍历的步骤，包括定义数据结构、函数实现和用户交互流程，这对于理解和实践图算法在实际编程中的应用非常有帮助。