《数据结构》实验报告 实验内容： （一）判断一个图有无回路 （二）求一个无向图G 的连通分量的个数 一、 目的和要求（需求分析）： 1、 了解图的定义和图的存储结构。 2、 熟悉掌握图的邻接矩阵和邻接表。 3、 理解图的遍历算法---深度优先搜索和广度优先搜索。 4、 学会编程处理图的连通性问题。 二、程序设计的基本思想，原理和算法描述： （包括程序的结构，数据结构，输入/输出设计，符号名说明等） 判断一个图有无回路： 在程序设计中，先必须确定所要创建的图是有向还是无向，是图还是网，其次再根据各自的特点，用连接表来实现创建。 在有向图中，先找出入度为 0 的顶点，删除与这个顶点相关联的边（出边），将与这些边相关的其它顶点的入度减 1，循环直到没有入度为 0 的顶点。如果此时还有未被删除的顶点，则必然存在环路，否则不存在回路。 无向图则可以转化为： 如果存在回路，则必然存在一个子图，是一个回路。因此回路中所有定点的度>=2。 第一步：删除所有度<=1 的顶点及相关边，并将另外与这些边相关的其它顶点的度减 1。 第二步：将度数变为 1 的顶点排入队列，并从该队列中（使用栈）取出一个顶点，并重复步骤一。 如果最后还有未删除的顶点，则存在回路，否则没有。 求一个无向图G 的连通分量的个数： 用连接表创建图，对于非连通图，则需从多个顶点出发进行搜索，而每一次从一个新的起始点出发进行搜索过程中得到的顶点访问序列恰为其各个连通分量中的顶点集。所以在设计中，为了统计出无向图中的连通分量个数，则因在其深度优先所搜无向图时对函数DFSTrav erse(ALGraph G)调用 DFS 次数进行统计，其结果便为无向图中连通分量个数。 三、调试和运行程序过程中产生的问题及采取的措施： 在调试和运行求一个无向图G 的连通分量的个数程序时，由于执行语句块 v oid DFSTrav erse(ALGraph G)先于 v oid DFS(ALGraph G,int v )， 而 v oid DFSTrav erse(ALGraph G)内调用了 DFS( )，因此计算机无法正确运行，将两者顺序进行了交换，程序便实现了其功能，且运行正常。 四、源程序及注释： 判断一个图有无回路： #include #include #include // 输出有向图的一个拓扑序列。 // 图的邻接表存储表示 #define MAX_NAME 3 // 顶点字符串的最大长度+1 #define MAX_VERTEX_NUM 20 #define STACK_INIT_SIZE 10 // ...
