图的遍历课程设计(3)

时间：2025-02-24

关于图的遍历的数据结构课程设计

一概述

1.问题描述

1) 函数功能要划分好 2) 总体设计应画流程图 3) 程序要加必要的注释 4) 要提供程序测试方案

2.系统分析

1) 掌握数据结构与算法的设计方法，具备初步的独立分析和设计能力

2) 初步掌握软件开发过程的问题分析、系统设计、程序编码、测试等基本方法和技

能

3) 提高综合运用所学的理论知识和方法独立分析和解决问题的能力

4) 训练用系统的观点和软件开发一般规范进行软件开发，培养软件工作者所应具备

的科学的工作方法和作风

3.课程设计（论文）进程安排

关于图的遍历的数据结构课程设计

二.总体设计方案

1．整体设计思路

图的邻接矩阵：

对于一个具有n个顶点的图，可以使用n*n的矩阵（二维数组）来表示它们间的邻接关系。图的邻接表：

邻接表由表头结点和表结点两部分组成，其中图中每个顶点均对应一个存储在数组中的表头结点。如这个表头结点所对应的顶点存在相邻顶点，则把相邻顶点依次存放于表头结点所指向的单向链表中。深度优先遍历的递归算法思想：

假定以图中某个顶点Vi为出发点，首先访问出发点，然后选择一个Vi的未访问过的邻接点Vj，以Vj为新的出发点继续进行深度优先搜索，直至图中所有顶点都被访问过。

1) 访问结点V并标记结点V为已访问； 2) 查找结点V的第一个邻接结点W；

3) 若结点W的临界结点W存在，则继续执行，否则算法结束； 4) 若结点W尚未被访问，则递归访问结点W；

5) 查找结点V的W临界结点的下一个临界结点W ，转到步骤（3）。广度优先遍历算法：

从图的某一顶点Vi出发，访问此顶点后，依次访问Vi的各个未曾访问过的邻接点，然后分别从这些邻接点出发，直至图中所有已有已被访问的顶点的邻接点都被访问到。

1) 2) 3) 4)

访问初始结点V并标记结点V为已访问；结点V入队列；

当队列非空时则继续执行，否则算法结束；出队列取得队头结点U；

关于图的遍历的数据结构课程设计

5) 查找结点U的第一个邻接结点W；

6) 若结点U的邻接结点W不存在，则转到步骤（3），否则循环执行下列步骤：

a) （6.1）若结点W尚未被访问，则访问结点W并标记结点W

为已访问；

b) （6.2）结点W入队；

c) （6.3）查找结点U的W邻接结点的下一个邻接结点W，转到

步骤（6）。普利姆算法思想：

令集合U的初值为U={u0}，集合T的初值为T={}。从所有结点u属于U和结

点v属于V\U的带权边中选出具有最小权值的边（u，v），将结点v加入集合U中，将边（u，v）加入集合T中。如此不断反复，当U=V时，最小生成树便构造完毕。克鲁斯卡尔算法思想：

设无向连通带权图G=(V,E)，其中V为结点的集合，E为边的集合。设带权图G的最小生成树T由结点集合和边的集合构成，其初值为T=(v,{}),即初始时最小生成树T只由带权图G中的结点集合组成，各结点之间没有一条边。这样，最小生成树T中的各个结点各自构成一个连通分量。然后，按照边的权值递增的顺序考察带权图G中边集合E的各条边，若被考察的边的两个结点属于T的两个不同的连通分量，则将此边加入懂啊最小生成树T中，同时，把两个连通分量连接为一个连通分量；若被考察的边的两个结点属于T的同一个连通分量，则将此边舍去。如此下去，当T中的连通分量个数为1时，T中的该连通分量即为带权图G的一棵最小生成树。连通分量：

非连通图的每一个连通部分。

2．算法的整体思路

本系统能分别用邻接矩阵存储结构和邻接表存储结构构造无向图，然后在此无向

图中能实现深度优先遍历，广度优先遍历，最小生成树和连通分量的算法。

3．工作内容

1.显示图的邻接矩阵, 图的邻接表, 深度优先遍历, 广度优先遍历, 最小生成树PRIM算法, 最小生成树KRUSCAL算法,图的连通分量。 2.当用户选择的功能错误时，系统会输出相应的提示。 3.通过图操作的实现，把一些实际生活中的具体的事物抽象出来。

关于图的遍历的数据结构课程设计

三详细设计

1.详细设计思路及算法

图1-1 无向图

1.程序中所用变量的定义: #include <iostream> #include <malloc.h> using namespace std; #define int_max 10000 #define inf 9999 #define max 20

2.邻接矩阵的定义： typedef struct ArcCell { int adj; char *info;