图的遍历 课程设计

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

图的遍历

课 程 设 计

题 目 教 学 院 专 业 班 级 姓 名 指导教师

图的遍历 计算机

2011 年 12 月 31 日

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

课程设计任务书

2010 ～2011 学年第1 学期

学生姓名： 专业班级：

指导教师： 工作部门：

一、课程设计题目

图的遍历

二、课程设计内容（含技术指标）

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

三、进度安排

1．初步完成总体设计，搭好框架；

2．完成最低要求：两种必须都要实现，写出画图的思路；

3．进一步要求：画出图的结构，有兴趣的同学可以进一步改进图的效果。

四、基本要求

1．界面友好，函数功能要划分好 2．程序要加必要的注释 3．要提供程序测试方案

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

目 录

一 概述 .............................................1

1.问题描述 ………………………………………………………………………………………..1 2.系统分析 ………………………………………………………………………………………..1 3.课程设计（论文）进程安排 …………………………………………………………………..1

二.总体设计方案......................................2

1．整体设计思路...............................................................................................................................2 2．算法的整体思路 ……………………………………………………………………………….3 3．工作内容 ……………………………………………………………………………………….3

三 详细设计 4

1.详细设计思路及算法 …………………………………………………………………………..4 2.程序流程图 ……………………………………………………………………………………11

四 程序的调试与运行结果说明 12

１.运行结果 ………………………………………………………………………………………12

五．课程设计总结 15 参考文献 16 附录A 原程序清单 16

数据结构课程设计成绩评定表 30

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

一 概述

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;

}ArcCell,AdjMatrix[20][20];

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

typedef struct {

char vexs[20]; AdjMatrix arcs; int vexnum,arcnum; }MGraph_L;

A 0 50 60

0 0 0 0 B 50

0 0 65 40 0 0 C 60 0 0 52 0 0 45 D 0 65 52 0 50 30 0 E 0 40 0 50 0 70 0 F 0 0 0 30 70 0 80 G 0 0 45 0 0 80 0

图1-2 邻接矩阵

3.邻接表： 表1-1 邻接表

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

4.深度优先遍历：

void adjprint(algraph gra)

5.广度优先遍历：

void bfstra(algraph gra)

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

6.最小生成树PRIM算法：

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

课程设计(论文)

8

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

7.最小生成树KRUSCAL算法：

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

课程设计(论文)

10

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

2.程序流程图

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

四 程序的调试与运行结果说明

运行结果

图2-1 输入顶点数

图2-2 输入权值 无向图创建成功

１.

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

图2-3 菜单

图2-4 邻接矩阵

图2-5 邻接表

图2-6 深广度优先遍历

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

图2-7 最小生成树

图2-8 连通分量

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

五．课程设计总结

课程设计是把我们所学的理论知识进行系统的总结并应用于实践的良好机会，有利于加强我们用知识理论来分析实际问题的能力，进而加强了我们对知识认识的实践度，巩固了我们的理论知识，深化了对知识的认识，并为走向社会打下一个良好的基础。

对于我们学生来讲，此次课程设计是为了让我们训练自己的实际设计能力，通过设计实践，去真正获得此项目管理和团队协作等方面的基本训练和工作经验。通过课程设计的一系列训练，我们能提高如何综合运用所学知识解决实际问题的能力，以及获得此项目管理和团队协作等等众多方面的具体经验，增强对相关课程具体内容的理解和掌握能力，培养对整体课程知识综合运用和融会贯通能力。

通过这近一个星期的数据结构课程设计实践，我学到了很多东西。本次课程设计对我来说正是一个提高自己能力的机会，我好好的抓住机会，努力做好每一步，完善每一步。自己的C语言知识和数据结构知识得到了巩固，编程能力也有了一定的提高。同时也学会了解决问题的方法。

此次课程设计也让我认识到必须培养严谨的态度。自己在编程时经常因为一些类似于“少了分号”的小错误而导致错误，不够认真细致，这给自己带来了许多麻烦。编程是一件十分严谨的事情，容不得马虎。所以在今后自己一定要培养严谨的态度。我想这不仅是对于程序设计，做任何事都应如此。

在实践过程中，我和组员分工合作，勇于提出问题，解决难题，在实践中，我遇到了许多困难，但都一一克服了。最终我圆满的完成此次课程设计，学到了很多东西。同时，程序还存在着一些缺陷，就是不能输出原图，存在一些局限性，不过我会继续努力思考，完善程序，做到最好。

此次试验，老师对我的指导是至关重要的，在此我非常感谢老师，从她那我学到了很多有关c语言的知识，为以后的学习打下了一定的基础。

总的来说，本次课程设计，不仅我的知识面有所提高，另外我的综合素质也有所提高，，比如说：团队精神、提问能力、思考能力等等。这次课程设计为我以后更好的学习和使用c语言打下了基础。

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

参考文献

[1]数据结构—使用C语言（第3版）朱战立 编，西安交通大学出版社。

[2] Visual C++程序设计──基础与实例分析.北京：清华大学出版社，2004

附录A 原程序清单

#include <iostream> #include <malloc.h> using namespace std; #define int_max 10000 #define inf 9999 #define max 20

// 邻接矩阵定义 typedef struct ArcCell {

int adj; char *info;

}ArcCell,AdjMatrix[20][20]; typedef struct {

char vexs[20]; AdjMatrix arcs; int vexnum,arcnum; }MGraph_L;

//^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^ int localvex(MGraph_L G,char v)//返回V的位置 {

int i=0;

while(G.vexs[i]!=v) { ++i; }

return i;

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

}

int creatMGraph_L(MGraph_L &G)//创建图用邻接矩阵表示 {

char v1,v2; int i,j,w;

cout<<" 创建无向图 "<<endl;<<"请输入图G顶点和弧的个数:(4 6)不包括“()”"<<endl;

cin>>G.vexnum>>G.arcnum; for(i=0;i!=G.vexnum;++i) {

cout<<"输入顶点"<<i<<endl; cin>>G.vexs[i]; }

for(i=0;i!=G.vexnum;++i) for(j=0;j!=G.vexnum;++j) {

G.arcs[i][j].adj=int_max; G.arcs[i][j].info=NULL; }

for(int k=0;k!=G.arcnum;++k) {

cout<<"输入一条边依附的顶点和权:(a b 3)不包括()"<<endl; cin>>v1>>v2>>w;//输入一条边依附的两点及权值 i=localvex(G,v1);//确定顶点V1和V2在图中的位置 j=localvex(G,v2); G.arcs[i][j].adj=w; G.arcs[j][i].adj=w; }

cout<<"图G邻接矩阵创建成功！"<<endl; return G.vexnum; }

void ljjzprint(MGraph_L G) {

int i,j;

for(i=0;i!=G.vexnum;++i) {

for(j=0;j!=G.vexnum;++j) cout<<G.arcs[i][j].adj<<" "; cout<<endl; } }

int visited[max];//访问标记

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

int we;

typedef struct arcnode//弧结点 {

int adjvex;//该弧指向的顶点的位置

struct arcnode *nextarc;//弧尾相同的下一条弧 char *info;//该弧信息 }arcnode;

typedef struct vnode//邻接链表顶点头接点 {

char data;//结点信息

arcnode *firstarc;//指向第一条依附该结点的弧的指针 }vnode,adjlist;

typedef struct//图的定义 {

adjlist vertices[max]; int vexnum,arcnum; int kind; }algraph;

// 队列定义 typedef struct qnode {

int data;

struct qnode *next;

}qnode,*queueptr;

typedef struct {

queueptr front; queueptr rear;

}linkqueue;

//……………………………………………………………………… typedef struct acr {

int pre;//弧的一结点 int bak;//弧另一结点 int weight;//弧的权 }edg;

int creatadj(algraph &gra,MGraph_L G)//用邻接表存储图 {

本文来源：https://www.bwwdw.com/article/3sp4.html