下载文档原格式
图是一种较线性表和树更为复杂的数据结构。
在线性表中,数据元素之间仅有线性关系,每一个数据元素惟独一个直接前驱和一个直接后继；在树形结构中, 数据元素之间有着明显的层次关系,并且每一层上的数据元素可能和下一层中多个元素〔及其孩子结点相关但只能和上一层中一个元素〔即双亲结点相关；而在图形结构中,节点之间的关系可以是任意的,图中任意两个数据元素之间都可能相关。
生成树求解主要利用普利姆和克雷斯特算法求解最小生成树,惟独强连通图才有生成树。
1> 先任意创建一个图；2> 图的 DFS,BFS 的递归和非递归算法的实现3> 最小生成树〔两个算法的实现,求连通分量的实现4> 要求用邻接矩阵、邻接表等多种结构存储实现输入数据类型为整型和字符型,输出为整型和字符a.图的邻接矩阵存储：根据所建无向图的结点数 n,建立n*n 的矩阵,其中元素全是无穷大〔int_max,再将边的信息存到数组中。
其中无权图的边用 1 表示, 无边用 0 表示；有全图的边为权值表示,无边用∞表示。
b.图的邻接表存储：将信息通过邻接矩阵转换到邻接表中,即将邻接矩阵的每一行都转成链表的形式将有边的结点进行存储。
c.图的广度优先遍历：假设从图中的某个顶点 v 出发,在访问了 v 之后挨次访问 v 的各个未曾经访问过的邻接点,然后再访问此邻接点的未被访问的邻接点, 并使"先被访问的顶点的邻接点"先于"后被访问的顶点的邻接点"被访问,直至图中所有已被访问的顶点的邻接点都被访问到。
若此时图中还有未被访问的,则另选未被访问的重复以上步骤,是一个非递归过程。
d.图的深度优先遍历：假设从图中某顶点 v 出发,依挨次访问 v 的邻接顶点, 然后再继续访问这个邻接点的系一个邻接点,如此重复,直至所有的点都被访问, 这是个递归的过程。
e.图的连通分量：这是对一个非强连通图的遍历,从多个结点出发进行搜索, 而每一次从一个新的起始点出发进行搜索过程中得到的顶点访问序列恰为其连通分量的顶点集。
实验三最小生成树问题班级：计科1101班学号：0909101605姓名：杜茂鹏2013年5月23日一、实验目的掌握图的存储表示和以及图的最小生成树算法。
二、实验内容1.实现图的存储，并且读入图的内容。
2.利用普里姆算法求网络的最小生成树。
3.实现构造生成树过程中的连通分量抽象数据类型。
4.以文本形式输出对应图的最小生成树各条边及权值。
三、实验要求1．在上机前写出全部源程序；2．能在机器上正确运行程序；3．用户界面友好。
四、概要设计、首先采用图的邻接矩阵存储结构，然后从终端输入图的顶点名称、弧以及弧的权值建立邻接矩阵，并将图存储在文件Graph.txt中。
然后利用已经建好的图，分别对其进行深度、广度优先遍历，一次输出遍历的顶点最后建立此图的最小生成树，并将对应的边及权值写入文件graph_prim.txt 中。
六、详细设计实验内容(原理、操作步骤、程序代码)#include<stdio.h>#include<stdlib.h>#include<limits.h>#define INFINITY INT_MAX //最大值#define MAX_VERTEX_NUM 20 //最大顶点个数int visited[MAX_VERTEX_NUM];typedef struct ArcCell{int adj;int *info; //该弧相关信息的指针}ArcCell,AdjMatrix[MAX_VERTEX_NUM][MAX_VERTEX_NUM];typedef struct close{char adjvex;int lowcost;}closedge[MAX_VERTEX_NUM];typedef struct{char vexs[MAX_VERTEX_NUM]; //顶点向量AdjMatrix arcs; //邻接矩阵int vexnum,arcnum; //图的当前顶点数和弧数closedge cld;}MGraph;typedef struct QNode{char data;struct QNode *next;}QNode,*QueuePtr;typedef struct{QueuePtr front1;QueuePtr rear;}LinkQueue;void (*VisitFunc)(MGraph G,int v);void DFSTraverse(MGraph G,void (* Visit)(MGraph G,int v)); void DFS(MGraph G,int v);void InitQueue(LinkQueue &Q){Q.front1=Q.rear=(QueuePtr)malloc(sizeof(QNode));if(!Q.front1)exit(0);Q.front1->next=NULL;}void EnQueue(LinkQueue &Q,char e){QueuePtr p=(QueuePtr)malloc(sizeof(QNode));if(!p)exit(0);p->data=e;p->next=NULL;Q.rear->next=p;Q.rear=p;}char DeQueue(LinkQueue &Q){if(Q.front1==Q.rear)exit(0);QueuePtr p=Q.front1->next;char e=p->data;Q.front1->next=p->next;if(Q.rear==p)Q.rear=Q.front1;free(p);return e;}int QueueEmpty(LinkQueue Q){if(Q.front1==Q.rear)return 1;return 0;}int LocateVex(MGraph &G,char v1){int i=0;while(!(G.vexs[i]==v1))i++;return i;}char GetVex(MGraph G,int i){char u;u=G.vexs[i];return u;}int minimum(MGraph G,closedge cld){int mini=1000,s1;for(int i=0;i<G.vexnum;i++){if(cld[i].lowcost!=0&&mini>cld[i].lowcost){mini=cld[i].lowcost;s1=i;}}return s1;}void CreateUDN(MGraph &G){int IncInfo;printf("请分别输入顶点数/弧数/以及弧所含信息:");scanf("%d %d %d",&G.vexnum,&G.arcnum,&IncInfo);getchar();for(int i=0;i<G.vexnum;i++){ //构造顶点向量printf("请输入顶点:");scanf("%c",&G.vexs[i]);getchar();}for(int i=0;i<G.vexnum;i++) //初始化邻接矩阵for(int j=0;j<G.vexnum;j++){G.arcs[i][j].adj=INFINITY;G.arcs[i][j].info=NULL;}for(int k=0;k<G.arcnum;k++){char v1,v2;int w,i,j;printf("输入一条边依附的顶点及权值:"); //构造邻接矩阵scanf("%c %c %d",&v1,&v2,&w); //输入一条边依附的顶点及权值i=LocateVex(G,v1);j=LocateVex(G,v2);G.arcs[i][j].adj=w;if(IncInfo)*G.arcs[i][j].info=IncInfo;G.arcs[j][i]=G.arcs[i][j];getchar();}}//深度优先遍历void Visit(MGraph G,int v){printf("%c",G.vexs[v]);}void DFSTraverse(MGraph G,void (* Visit)(MGraph G,int v)){VisitFunc=Visit;for(int v=0;v<G.vexnum;v++)visited[v]=0;for(int v=0;v<G.vexnum;v++)if(!visited[v]){DFS(G,v);}}void DFS(MGraph G,int v){visited[v]=1;VisitFunc(G,v);for(int j=0;j<G.vexnum;j++)if(!visited[j]&&G.arcs[v][j].adj!=INFINITY)DFS(G,j);}void BFSTraverse(MGraph G,void(*Visit)(MGraph G,int v)) {LinkQueue Q;for(int v=0;v<G.vexnum;v++)visited[v]=0;InitQueue(Q);for(int v=0;v<G.vexnum;v++)if(!visited[v]){visited[v]=1;Visit(G,v);EnQueue(Q,G.vexs[v]);while(!QueueEmpty(Q)){DeQueue(Q);for(int j=0;j<G.vexnum;j++)if(!visited[j]&&G.arcs[v][j].adj!=INFINITY) {visited[j]=1;Visit(G,j);EnQueue(Q,G.vexs[j]);}}}}void MiniSpanTree_PRIM(MGraph G,char u){FILE *IN;if((IN=fopen("graph_prim.txt","w+"))==NULL){printf("file open error!");exit(1);}int k=LocateVex(G,u);for(int j=0;j<G.vexnum;j++)if(j!=k){G.cld[j].adjvex=u;G.cld[j].lowcost=G.arcs[k][j].adj;}G.cld[k].lowcost=0;for(int i=1;i<G.vexnum;i++){k=minimum(G,G.cld);printf("%c%c",G.cld[k].adjvex,G.vexs[k]);int m=LocateVex(G,G.cld[k].adjvex);printf("%d\n",G.arcs[m][k].adj);fprintf(IN,"%c,%c,%d",G.cld[k].adjvex,G.vexs[k],G.arcs[m][k].adj);fputs("\n",IN);G.cld[k].lowcost=0;for(int j=0;j<G.vexnum;j++)if(G.arcs[k][j].adj<G.cld[j].lowcost){G.cld[j].adjvex=G.vexs[k];G.cld[j].lowcost=G.arcs[k][j].adj;}}fclose(IN);}void menu(){printf("1.生成无向网G\n");printf("2.最小生成树\n");printf("3.深度遍历\n");printf("4.广度遍历\n");printf("0.退出\n");}int main(void){MGraph G;int m;do{menu();printf("输入你想要进行的操作的序号:");scanf("%d",&m);getchar();switch(m){case 1:CreateUDN(G);break;case 2:char u;u=GetVex(G,0);MiniSpanTree_PRIM(G,u);break;case 3:DFSTraverse(G,Visit);break;case 4:BFSTraverse(G,Visit);break;case 0:break;default:break;}}while(m);}七、测试结果(截图)主界面八、实验心得1拼写错误节应该避免2尽量用通俗易懂的标示符定义函数、变量3变量应该先定义再使用4应该从使用者的角度考虑，做出简洁的主界面5编好一个函数时应该加注释方便以后阅读时好理解。
实现图的遍历算法实验报告实现图的遍历算法实验报告⼀实验题⽬: 实现图的遍历算法⼆实验要求:2.1:（1）建⽴如图（p126 8.1）所⽰的有向图 G 的邻接矩阵，并输出之（2）由有向图G的邻接矩阵产⽣邻接表，并输出之（3）再由（2）的邻接表产⽣对应的邻接矩阵，并输出之2.2 （1）输出如图8.1所⽰的有向图G从顶点0开始的深度优先遍历序列（递归算法）（2）输出如图8.1所⽰的有向图G从顶点0开始的深度优先遍历序列（⾮递归算法）（3）输出如图8.1所⽰的有向图G从顶点0开始的⼴度优先遍历序列三实验内容:3.1 图的抽象数据类型:ADT Graph{数据对象V：V是具有相同特性的数据元素的集合，称为顶点集。
数据关系R：R={VR}VR={|v,w∈V且P(v,w)，表⽰从v到w的弧，谓词P(v,w)定义了弧的意义或信息}基本操作：CreateGraph( &G, V, VR )初始条件：V是图的顶点集，VR是图中弧的集合。
操作结果：按V和VR的定义构造图G。
DestroyGraph( &G )初始条件：图G存在。
操作结果：销毁图G。
LocateVex( G, u )初始条件：图G存在，u和G中顶点有相同特征。
操作结果：若G中存在顶点u，则返回该顶点在图中位置；否则返回其它信息。
GetVex( G, v )初始条件：图G存在，v是G中某个顶点。
操作结果：返回v的值。
PutVex( &G, v, value )初始条件：图G存在，v是G中某个顶点。
初始条件：图G存在，v是G中某个顶点。
操作结果：返回v的第⼀个邻接顶点。
若顶点在G中没有邻接顶点，则返回“空”。
NextAdjVex( G, v, w )初始条件：图G存在，v是G中某个顶点，w是v的邻接顶点。
操作结果：返回v的（相对于w的）下⼀个邻接顶点。
若w是v 的最后⼀个邻接点，则返回“空”。
InsertVex( &G, v )初始条件：图G存在，v和图中顶点有相同特征。
图的遍历算法实验报告
《图的遍历算法实验报告》
在计算机科学领域，图的遍历算法是一种重要的算法，它用于在图数据结构中
访问每个顶点和边。
图的遍历算法有两种常见的方法：深度优先搜索（DFS）
和广度优先搜索（BFS）。
在本实验中，我们将对这两种算法进行实验，并比较
它们的性能和应用场景。
首先，我们使用深度优先搜索算法对一个简单的无向图进行遍历。
通过实验结
果可以看出，DFS算法会首先访问一个顶点的所有邻居，然后再递归地访问每
个邻居的邻居，直到图中所有的顶点都被访问到。
这种算法在一些应用场景中
非常有效，比如寻找图中的连通分量或者寻找图中的环路。
接下来，我们使用广度优先搜索算法对同样的无向图进行遍历。
通过实验结果
可以看出，BFS算法会首先访问一个顶点的所有邻居，然后再按照距离递增的
顺序访问每个邻居的邻居。
这种算法在一些应用场景中也非常有效，比如寻找
图中的最短路径或者寻找图中的最小生成树。
通过对比实验结果，我们可以发现DFS和BFS算法各自的优势和劣势。
DFS算
法适合用于寻找图中的连通分量和环路，而BFS算法适合用于寻找最短路径和
最小生成树。
因此，在实际应用中，我们需要根据具体的需求来选择合适的算法。
总的来说，图的遍历算法是计算机科学中非常重要的算法之一，它在许多领域
都有着广泛的应用。
通过本次实验，我们对DFS和BFS算法有了更深入的了解，并且对它们的性能和应用场景有了更清晰的认识。
希望通过这篇实验报告，读
者们也能对图的遍历算法有更深入的理解和认识。
一、实验目的1. 理解生成树的概念和作用；2. 掌握Prim算法和Kruskal算法实现生成树的方法；3. 分析算法的时间复杂度和空间复杂度；4. 提高算法设计与分析能力。
二、实验原理生成树（Spanning Tree）是一个无向图的所有顶点构成的一棵树，且该树包含了原图的所有顶点。
生成树在计算机网络、电路设计等领域具有广泛的应用。
在无向图中，如果任意两个顶点之间都存在路径，则称该图是连通的。
对于连通图，一定存在一棵生成树。
Prim算法和Kruskal算法是两种常见的生成树算法，它们分别采用贪心策略和最小生成树算法实现。
三、实验内容1. Prim算法实现生成树（1）初始化：设置一个数组来记录每个顶点与当前生成树的连接情况，以及一个数组来记录每个顶点到生成树的距离。
（2）选择一个顶点作为起始顶点，将其距离设置为0，其他顶点距离设置为无穷大。
（3）在当前生成树上选择距离最小的顶点，将其加入生成树，并将该顶点与其他顶点的距离更新。
（4）重复步骤（3），直到所有顶点都被加入生成树。
2. Kruskal算法实现生成树（1）将所有边按照权值从小到大排序。
（2）创建一个并查集，用于判断两个顶点是否属于同一个集合。
（3）遍历排序后的边，对于每条边，判断其两个顶点是否属于同一个集合：（a）如果属于同一个集合，则跳过该边；（b）如果不属于同一个集合，则将这条边加入生成树，并将两个顶点所属的集合合并。
（4）重复步骤（3），直到生成树包含所有顶点。
四、实验步骤1. 创建一个无向图，包含若干顶点和边。
2. 使用Prim算法实现生成树，记录算法运行时间。
3. 使用Kruskal算法实现生成树，记录算法运行时间。
4. 分析两种算法的时间复杂度和空间复杂度。
五、实验结果与分析1. Prim算法实现生成树（1）顶点集合：V = {A, B, C, D, E, F}（2）边集合：E = {(A, B, 1), (A, C, 3), (A, D, 2), (B, C, 2), (B, D, 2), (C, D, 1), (C, E, 4), (D, E, 3), (D, F, 2), (E, F, 1)}（3）Prim算法运行时间：0.001秒2. Kruskal算法实现生成树（1）顶点集合：V = {A, B, C, D, E, F}（2）边集合：E = {(A, B, 1), (A, C, 3), (A, D, 2), (B, C, 2), (B, D, 2), (C, D, 1), (C, E, 4), (D, E, 3), (D, F, 2), (E, F, 1)}（3）Kruskal算法运行时间：0.001秒通过实验，我们可以得出以下结论：1. Prim算法和Kruskal算法均可以有效地实现生成树，且在时间复杂度和空间复杂度上表现良好。
摘要图(Gｒaph)是一种复杂的非线性结构。
图可以分为无向图、有向图。
若将图的每条边都赋上一个权，则称这种带权图网络。
在人工智能、工程、数学、物理、化学、计算机科学等领域中，图结构有着广泛的应用。
在图结构中，对结点（图中常称为顶点)的前趋和后继个数都是不加以限制的,即结点之间的关系是任意的。
图中任意两个结点之间都可能相关。
图有两种常用的存储表示方法:邻接矩阵表示法和邻接表表示法。
在一个图中，邻接矩阵表示是唯一的，但邻接表表示不唯一。
在表示的过程中还可以实现图的遍历（深度优先遍历和广度优先遍历）及求图中顶点的度。
当然对于图的广度优先遍历还利用了队列的五种基本运算(置空队列、进队、出队、取队头元素、判队空)来实现。
这不仅让我们巩固了之前学的队列的基本操作，还懂得了将算法相互融合和运用。
目录第一章课程设计目的..................................................................................... 错误!未定义书签。
第二章课程设计内容和要求....................................................................... 错误!未定义书签。
2．1课程设计内容.................................................................................. 错误!未定义书签。
2.1.1图的邻接矩阵的建立与输出ﻩ错误!未定义书签。
2．１.２图的邻接表的建立与输出............................................... 错误!未定义书签。
2.1.3图的遍历的实现.................................................................... 错误!未定义书签。
实验五图的基本操作一、实验目的1、使学生可以巩固所学的有关图的基本知识。
2、熟练掌握图的存储结构。
3、熟练掌握图的两种遍历算法。
二、实验内容[问题描述]对给定图，实现图的深度优先遍历和广度优先遍历。
[基本要求]以邻接表为存储结构，实现连通无向图的深度优先和广度优先遍历。
以用户指定的结点为起点，分别输出每种遍历下的结点访问序列。
【测试数据】由学生依据软件工程的测试技术自己确定。
三、实验前的准备工作1、掌握图的相关概念。
2、掌握图的逻辑结构和存储结构。
3、掌握图的两种遍历算法的实现。
四、实验报告要求1、实验报告要按照实验报告格式规范书写。
2、实验上要写出多批测试数据的运行结果。
3、结合运行结果，对程序进行分析。
编程思路：深度优先算法：计算机程序的一种编制原理，就是在一个问题出现多种可以实现的方法和技术的时候，应该优先选择哪个更合适的，也是一种普遍的逻辑思想，此种思想在运算的过程中，用到计算机程序的一种递归的思想。
度优先搜索算法：又称广度优先搜索，是最简便的图的搜索算法之一，这一算法也是很多重要的图的算法的原型。
Dijkstra单源最短路径算法和Prim 最小生成树算法都采用了和宽度优先搜索类似的思想。
其别名又叫BFS，属于一种盲目搜寻法，目的是系统地展开并检查图中的所有节点，以找寻结果。
换句话说，它并不考虑结果的可能位址，彻底地搜索整张图，直到找到结果为止。
以临接链表作为存储结构，结合其存储特点和上面两种算法思想，给出两种遍历步骤：（1）既然图中没有确定的开始顶点，那么可从图中任一顶点出发，不妨按编号的顺序，先从编号小的顶点开始。
（2）要遍历到图中所有顶点，只需多次调用从某一顶点出发遍历图的算法。
所以，下面只考虑从某一顶点出发遍历图的问题。
（3）为了在遍历过程中便于区分顶点是否已经被访问，设置一个访问标志数组visited[n]，n为图中顶点的个数，其初值为0，当被访问过后，其值被置为1。
（4）这就是遍历次序的问题，图的遍历通常有深度优先遍历和广度优先遍历两种方式，这两种遍历次序对无向图和有向图都适用。
课程设计报告课程名称数据结构课题名称图的遍历专业网络工程班级学号姓名指导教师陈淑红、张晓清、黄哲2015年 6 月25 日湖南工程学院课程设计任务书课程名称数据结构课题图的遍历专业班级网络工程学生姓名学号指导老师陈淑红、张晓清、黄哲审批任务书下达日期2015 年 3 月 1 日任务完成日期2015 年6月25 日目录一、设计内容与设计要求 (2)1.1设计内容---------------------------------------------------------------------------------------2 1.2选题方案---------------------------------------------------------------------------------------2 1.3设计要求---------------------------------------------------------------------------------------21.4进度安排---------------------------------------------------------------------------------------5二、需求分析 (5)2.1程序功能---------------------------------------------------------------------------------------52.2输入输出要求---------------------------------------------------------------------------------5三、概要设计 (5)3.1流程图------------------------------------------------------------------------------------------5 3.2数据结构---------------------------------------------------------------------------------------63.3函数的调用关系图，主要函数的流程---------------------------------------------------9四、详细设计 (14)4.1定义图------------------------------------------------------------------------------------------14 4.2自动生成无向图------------------------------------------------------------------------------14 4.3手动生成无向图------------------------------------------------------------------------------16 4.4广度优先遍历---------------------------------------------------------------------------------174.5深度优先遍历---------------------------------------------------------------------------------20五、调试运行 (22)5.1 测试数据--------------------------------------------------------------------------------------22 5.2运行程序---------------------------------------------------------------------------------------22 5.3自动生成图操作------------------------------------------------------------------------------235.4手动生成图操作------------------------------------------------------------------------------26六、心得体会 (29)七、源代码 (29)八、评分表 (38)第一章设计内容与设计要求1.1设计内容1.1.1 算术24游戏演示由系统随机生成4张扑克牌，用户利用扑克牌的数字及运算符号“+”、“—”、“*”、“/”及括号“（”和“）”从键盘上输入一个计算表达式，系统运行后得出计算结果，如果结果等于24，则显示“Congratulation!”，否则显示“Incorrect!”设计思路：从键盘输入中缀表达式，然后将中缀表达式转换为后缀表达式，利用后缀表达式求值。
图的遍历操作实验报告一、实验目的本次实验的主要目的是深入理解图的遍历操作的基本原理和方法，并通过实际编程实现，掌握图的深度优先遍历（DepthFirst Search，DFS）和广度优先遍历（BreadthFirst Search，BFS）算法，比较它们在不同类型图中的性能和应用场景。
二、实验环境本次实验使用的编程语言为 Python，开发环境为 PyCharm。
实验中使用的数据结构为邻接表来表示图。
三、实验原理（一）深度优先遍历深度优先遍历是一种递归的图遍历算法。
它从起始节点开始，沿着一条路径尽可能深地访问节点，直到无法继续，然后回溯到上一个未完全探索的节点，继续探索其他分支。
（二）广度优先遍历广度优先遍历则是一种逐层访问的算法。
它从起始节点开始，先访问起始节点的所有相邻节点，然后再依次访问这些相邻节点的相邻节点，以此类推，逐层展开。
四、实验步骤（一）数据准备首先，定义一个图的邻接表表示。
例如，对于一个简单的有向图，可以使用以下方式创建邻接表：｀｀｀pythongraph ＝｛＇A'：＇B'，＇C'，＇B'：＇D'，＇E'，＇C'：＇F'，＇D'：，＇E'：，＇F'：｝｀｀｀（二）深度优先遍历算法实现｀｀｀pythondef dfs(graph, start, visited=None)：if visited is None:visited ＝ set(）visitedadd(start)print(start)for next_node in graphstart:if next_node not in visited:dfs(graph, next_node, visited)｀｀｀（三）广度优先遍历算法实现｀｀｀pythonfrom collections import deque def bfs(graph, start)：visited ＝｛start}queue ＝ deque(start)while queue:node ＝ queuepopleft(）print(node)for next_node in graphnode:if next_node not in visited:visitedadd(next_node)queueappend(next_node)｀｀｀（四）测试与分析分别使用深度优先遍历和广度优先遍历算法对上述示例图进行遍历，并记录遍历的顺序和时间开销。
西安交通大学数据结构课程设计课程名称：图的遍历和生成树求解实现学院：信息科学学院班级：计算机科学（1）班设计者：李想学号：3210.设计时间：2010-06-22目录第一章需求分析 (2)第二章详细设计 (3)第三章源程序 (11)第四章运行结果及调试分析 (19)第五章使用说明 (22)第六章课设体会及总结 (22)参考文献 (22)第一章：需求分析1：设计要求：(1) 先任意创建一个图；(2) 图的DFS,BFS的递归和非递归算法的实现(3) 最小生成树（两个算法）的实现，求连通分量的实现(4) 要求用邻接矩阵、邻接表、十字链表等多种结构存储实现2：所作题目的意义：图是一种较线性表和树更为复杂的数据结构。
在图形结构中结点的关系可以是任意的，图中任意两个数据元素之间都可能相关，因此，图的应用极为广泛，特别是近几年来的迅速发展，已深入到诸如语言学、逻辑学、物理、化学、计算机科学以及数学的其他分支中。
图的遍历通常有两条路径：深度优先搜索和广度优先搜索。
此次课程设计，可以让我对图这个概念有进一步的了解。
3：本人所做的工作：和小组成员一起完成本次程序的编写，查过大量关于这方面的资料。
经过多次的修改和调试后，终于把程序运行了出来。
至于文档是自己独立完成的。
4：系统的主要功能：先创建一个图，用两种搜索方式实现图的遍历，并求得图的最小生成树以及连通分量，用多种存储结构实现。
第二章：详细设计定义九个结构体变量:arcalgraphArcCellarcnodeclosedgelinkqueueMgraph_Lqnodevnode主要的函数：void main()int localvex(MGraph_L G,char v)int creatMGraph_L(MGraph_L &G)void ljjzprint(MGraph_L G)int creatadj(algraph &gra,MGraph_L G)void adjprint(algraph gra)int firstadjvex(algraph gra,vnode v)int nextadjvex(algraph gra,vnode v,int w)int initqueue(linkqueue &q)int enqueue(linkqueue &q,int e)int dequeue(linkqueue &q,int &e)int queueempty(linkqueue q)void bfstra(algraph gra)int dfstra(algraph gra)int dfs(algraph gra,int i)int bfstra_fen(algraph gra)int minispantree(MGraph_L G,char u)int minimum(closedge *p)int prim(int c[][max],int n)int find(int acrvisited[],int f)void kruscal_arc(MGraph_L G,algraph gra)void main()主函数主要是调用各个函数，显示菜单如下：0、显示该图的邻接矩阵;1、显示该图的邻接表2、广度优先遍历3、深度优先遍历4、最小生成树PRIM算法5、最小生成树KRUSCAL算法6、该图的连通分量7、退出程序用户输入自己的选择，就可以对图进行各种运算了int creatMGraph_L(MGraph_L &G)创建一个无向图，用邻接矩阵表示。
数据结构课程设计设计说明书图的遍历的实现学生姓名周朝学号********** 班级网络1101班成绩指导教师申静数学与计算机科学学院2014年1 月4日课程设计任务书2013—2014学年第一学期课程设计名称：数据结构课程设计课程设计题目：图的遍历实现完成期限：自2013年12 月23日至2014年 1 月4 日共 2 周设计内容：1. 任务说明(1) 采用邻接表存储结构创建一个图；(2) 编程实现图的深度优先搜索（或广度优先搜索）遍历算法；(3) 输出遍历结果；(4) 给定具体数据调试程序。
2. 要求1）问题分析和任务定义：根据设计题目的要求，充分地分析和理解问题，明确问题要求做什么？2）逻辑设计：写出抽象数据类型的定义，各个主要模块的算法，并画出模块之间的调用关系图；3）详细设计：定义相应的存储结构并写出各函数的伪码算法。
4）程序编码：把详细设计的结果进一步求精为程序设计语言程序。
5）程序调试与测试：采用自底向上，分模块进行，即先调试低层函数。
6）结果分析：程序运行结果包括正确的输入及其输出结果和含有错误的输入及其输出结果。
算法的时间、空间复杂性分析；7）编写课程设计报告。
3. 参考资料指导教师：申静教研室负责人：余冬梅课程设计评阅摘要本课程设计主要目的在于更深一步的了解图的遍历的问题，以无向图为例分别实现了广度优先遍历和深度优先遍历，在课程设计中，程序设计设计语言采用Visual C，程序运行平台为Windows 98/2000/XP。
在程序设计中我主要是解决的是给出一个图如何用多种方法完成图的遍历的问题。
程序最终通过调试运行，实现了设计目标。
关键词:程序设计；数据结构；无向图目录一课题描述 (1)二设计目的与任务 (2)2.1课程设计的目的 (2)2.2课程设计的任务 (2)三设计方案和实施 (3)3.1总体设计 (3)3.2基本操作 (3)3.3详细设计 (4)四运行调试结果 (6)五结论与致谢 (9)六附录 (10)一课题描述图是一种较为复杂且重要的数据结构，其特殊性在于图形结构中结点之间的关系可以是任意的，图中任意两个数据元素之间都有可能相关。
目录一、课题的主要功能 (2)1.1设计内容 (2)1.2对课程设计功能的需求分析 (2)二、课题的功能模块的划分 (2)2.1模块划分 (2)2.2系统的概要设计 (3)三、主要功能的实现 (4)3.1算法思想 (4)1.图的邻接矩阵的建立 (4)2.图的遍历的实现 (4)3.2数据结构 (4)3.3主函数流程图 (5)3.4深度优先遍历流程图 (6)3.5深度优先遍历递归 (7)3.6深度优先遍历流程图 (9)3.7广度优先遍历递归流程图 (10)四、程序调试 (11)4.1程序的调试分析 (11)4.2程序的测试结果 (11)五、总结 (15)六、附件 (16)6.1源程序一、课题的主要功能1.1设计内容演示图的深度优先, 广度优先遍历过程，并输出原图结构及遍历结果。
要求图的结点数不能少于6个。
可以由系统随机生成图，也可以由用户手动输入图。
报告中要写出画图的思路；画出图的结构，有兴趣的同学可以进一步改进图的效果。
1.2对课程设计功能的需求分析图的遍历并不需要是一个过于复杂的工作环境，一般来说：最合适的才是最好的。
软件设计必须符合我们使用实际情况的需要。
根据要求，图的遍历主要功能如下：1.用户可以随时建立一个有向图或无向图；2.用户可以根据自己的需要，对图进行深度遍历或广度遍历；3.用户可以根据自己的需要对图进行修改；4.在整个程序中,用户可以不断的按照不同的方式对图进行遍历,若不继续,用户也可以随时跳出程序,同时,如果用户输入的序号错误,程序会提示用户重新输入序号；二、课题的功能模块的划分2.1模块划分1.队列的初始化、进队、出队、队列空、队列满的函数void InitQueue(CirQueue *Q) //初始化队列int QueueEmpty(CirQueue *Q)//队列是否为空int QueueFull(CirQueue *Q)//队列满Void EnQueue(CirQueue *Q,int x)//将队员进队int DeQueue(CirQueue *Q)//将队员出队2.创建图的函数void CreateMGraph(MGraph *G)//根据用户需要创建一个图3.图的深度优先遍历递归void DFSM(MGraph *G,int i)/*含有输出已访问的顶点的语句*/4.图的广度优先遍历递归void BFSM(MGraph *G,int k) /*含有输出已访问的顶点的语句*/5.深度优先遍历void DFSTraverseM(MGraph *G)/*调用DFSM函数*/6.广度优先遍历void BFSTraverseM(MGraph *G) /*调用BFSM函数*/7.主函数main() /*包含一些调用和控制语句*/2.2系统的概要设计三、主要功能的实现3.1算法思想本课题所采用的是邻接矩阵的方式存储图，实现图的深度、广度两种遍历，并将每种遍历结果输出来。
*******************实践教学*******************兰州理工大学计算机与通信学院2012年春季学期算法与数据结构课程设计题目：______________专业班级：_______________姓名：_______________学号：指导教师：李睿成绩：_______________目录摘要 (2)1．采用类C语言定义相关数据类型 (2)2．各模块流程图及伪码算法 (3)3．函数的调用关系图 (10)4．调试分析 (11)5．测试结果 (12)6.源程序（见附录） (18)设计总结 (19)参考文献 (20)致谢 (20)附件Ⅰ任务一源程序代码 (21)摘要很多涉及图上操作的算法都是以图的遍历操作为基础的，该设计要求写一个程序，演示出图遍历的过程，并给出图的生成树（网的最小代价生成树）。
通过该题目的设计过程，可以加深理解图数据结构及队列的逻辑结构、存储结构及图的深度优先和广度优先遍历过程，掌握图数据据结构上基本运算的实现，进一步理解和熟练掌握课本中所学的各种数据结构，学会如何把学到的知识用于解决实际问题，培养动手能力。
关键字：图；深度优先遍历；广度优先遍历；生成树1．采用类C语言定义相关数据类型图存储结构的定义：1）顺序存储（邻接矩阵）#define MAX_VERTEX_NUM 30 //最大顶点个数Typedef enum{DG,DN,UDG,UDN} GraphKind; //图的种类：有向图、有向网、无向图、无向网ArcTypeAdjMtrix[MAX_VERTEX_NUM][MAX_VERTEX_NUM]; //ArcType 是顶点关系类型，对无权图，用0和1表示是否相邻，对于网，则为权值类型typedef struct {VertexType vex[MAX_VERTEX_NUM]; //顶点数组AdjMtrix arc; //邻接矩阵int vexnum,arcnum; //图中的顶点数和边数GraphKind kind; //图的种类}GraphMtrix;（2）邻接表的存储#define MAX_VERTEX_NUM 30 //最大顶点个数typedef struct EdgeNode{ //表结点int adjvex; //边或弧依赖的顶点序号InfType *info; //弧或边的相关信息，在网中则为权值struct EdgeNode *next;}EdgeNode;typedef struct VexNode{ //顶点元素VertexType vextex;EdgeNode *link;}VexNode,AdjList[MAX_VERTEX_NUM];typedef struct{ //邻接表AdjList vertices;int vexnum,arcnum; //图中的顶点数和边数GraphKind kind; //图的种类} AdjListGrap2．各模块流程图及伪码算法(1) 遍历算法a.深度优先遍历void DFS(AdjListGraph G,int v)//图G采用邻接表存储结构，v是遍历起始点在邻接表中的下标值，其下标从0开始{visited[v]=1; //置已访问标志visite(G.vertices[v].vextex); //访问顶点for (p = G.vertices[v].link; p; p = p->next)if (!visited[p->adjvex])DFS(G,p->adjvex);//当前顶点未访问，继续深度优先遍历} // DFSb.广度优先遍历void BFS(AdjListGrap G,intv)//图G采用邻接表存储结构，v是遍历起始点在邻接表中的下标，邻接表中下标从0开始，以队列作为基本辅助数据结构{InitQueue(Q); //初始化队列Qvisited[v]=1; //置已访问标志visite(G.vertices[v]. vextex); //访问顶点EnQueue(Q,v); //被访问顶点入队while (!QueueEmpty(Q)){DeQueue(Q,v); //出队列for (p = G.vertices[v].link; p; p = p->next) //找所有和v相邻接的顶点if (!visited[p->adjvex]){visited[p->adjvex]=1;visite(G.vertices [p->adjvex].vextex);EnQueue(Q,p->adjvex);} //if} //while} // BFS(2)流程图a.深度优先遍历dfstrab.广度优先遍历Bfstrac.Prim算法(3) 程序的伪代码算法：a.广度优先遍历：void dfstra (MGraph *G，int i){ /*以vi为出发点对邻接矩阵表示的图G进行DFS搜索，设邻接矩阵是0,l矩阵*/整型 j；打印 ("visit vertex：％c"，G->vexs[i])；/*访问顶点vi*/ visited[i]=TRUE；for(j=0；j<G->n；j++) /*依次搜索vi的邻接点*/if(G->edges[i][j]==1&&!visited[j])DFSM(G，j)/*(vi ，vj)∈E，且vj未访问过，故vj为新出发点}DFSM*/说明：对于具有n个顶点和e条边的无向图或有向图，遍历算法DFSTraverse对图中每顶点至多调用一次DFS或DFSM。
图的遍历和生成树求解实现（邻接矩阵、邻接表―图的深度广度遍历算法的实现和最小生成树PRIM和KRUSCAL算法的实现）图的遍历和生成树求解实现（邻接矩阵、邻接表―图的深度广度遍历算法的实现和最小生成树PRIM和KRUSCAL算法的实现）#inc lude <iostream>#inc lude <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];AdjMatr ix arcs;int vexnum,arcnum;}MGraph_L;//^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^int localvex(MGraph_L G,char v)//返回V的位置{int i=0;w hile(G.vexs[i]!=v){++i;}return i;}int creatMGr aph_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 vis ited[max];//访问标记int w e;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 w eight;//弧的权}edg;int creatadj(algraph &gra,MGr aph_L G)//用邻接表存储图{int i=0,j=0;arcnode *arc,*tem,*p;for(i=0;i!=G.vexnum;++i){gra.vertices[i].data=G.vexs[i];gra.vertices[i].firstarc=NULL;}for(i=0;i!=G.vexnum;++i){for(j=0;j!=G.vexnum;++j){if(gra.vertices[i].firstarc==NULL){if(G.arcs[i][j].adj!=int_max&&j!=G.vexnum){arc=(arcnode *)malloc(sizeof(arcnode));arc->adjvex=j;gra.vertices[i].firstarc=arc;arc->nextarc=NULL;p=arc;++j;w hile(G.arcs[i][j].adj!=int_max&&j!=G.vexnum) {tem=(arcnode *)malloc(sizeof(arcnode));tem->adjvex=j;gra.vertices[i].firstarc=tem;tem->nextarc=arc;arc=tem;++j;}--j;}}else{if(G.arcs[i][j].adj!=int_max&&j!=G.vexnum){arc=(arcnode *)malloc(sizeof(arcnode));arc->adjvex=j;p->nextarc=arc;arc->nextarc=NULL;p=arc;}}}}gra.vexnum=G.vexnum;gra.arcnum=G.arcnum;/*for(i=0;i!=gra.vexnum;++i){arcnode *p;cout<<i<<" ";p=gra.vertices[i].firstarc;w hile(p!=NULL){cout<<p->adjvex;p=p->nextarc;}cout<<endl;}*/cout<<"图G邻接表创建成功！"<<endl;return 1;}void adjpr int(algraph gra){int i;for(i=0;i!=gra.vexnum;++i){arcnode *p;cout<<i<<" ";p=gra.vertices[i].firstarc;w hile(p!=NULL){cout<<p->adjvex;p=p->nextarc;}cout<<endl;}}int firstadjvex(algraph gra,vnode v)//返回依附顶点V的第一个点 //即以V为尾的第一个结点{if(v.firstarc!=NULL)return v.firstarc->adjvex;int nextadjvex(algraph gra,vnode v,int w)//返回依附顶点V的相对于W的下一个顶点{arcnode *p;p=v.firstarc;w hile(p!=NULL&&p->adjvex!=w){p=p->nextarc;}if(p->adjvex==w&&p->nextarc!=NULL){p=p->nextarc;return p->adjvex;}if(p->adjvex==w&&p->nextarc==NULL)return -10;}int initqueue(linkqueue &q)//初始化队列{q.rear=(queueptr)malloc(sizeof(qnode));q.front=q.rear;if(!q.front)return 0;q.front->next=NULL;return 1;}int enqueue(linkqueue &q,int e)//入队{queueptr p;p=(queueptr)malloc(sizeof(qnode));if(!p)return 0;p->data=e;p->next=NULL;q.rear->next=p;q.rear=p;return 1;}int dequeue(linkqueue &q,int &e)//出队{queueptr p;if(q.front==q.r ear)return 0;p=q.front->next;e=p->data;q.front->next=p->next;if(q.rear==p)q.rear=q.front;free(p);return 1;}int queueempty(linkqueue q)//判断队为空{if(q.front==q.r ear)return 1;return 0;}void bfstra(algraph gra)//广度优先遍历{int i,e;linkqueue q;for(i=0;i!=gra.vexnum;++i)visited[i]=0;initqueue(q);for(i=0;i!=gra.vexnum;++i)if(!visited[i]){ visited[i]=1;cout<<gr a.vertices[i].data;enqueue(q,i);w hile(!queueempty(q)){dequeue(q,e);// cout<<" "<<e<<" ";for(w e=firstadjvex(gra,gra.vertices[e]);w e>=0;w e=nextadjvex(gra,gra.vertices[e],w e)) {if(!v isited[w e]){visited[w e]=1;cout<<gra.vertices[w e].data;enqueue(q,w e);}}}}}int dfs(algraph gra,int i);//声明DFSint dfstra(algraph gra){int i,j;for(i=0;i!=gra.vexnum;++i){visited[i]=0;}for(j=0;j!=gra.vexnum;++j){if(visited[j]==0)dfs(gra,j);}return 0;}int dfs(algraph gra,int i){visited[i]=1;int w e1;// cout<<i<<visited[i]<<endl;cout<<gra.vertices[i].data;// cout<<endl;for(w e=firstadjvex(gra,gra.vertices[i]);w e>=0;w e=nextadjvex(gra,gra.vertices[i],w e)) {// cout<<w e<<visited[w e]<<endl;w e1=w e;// cout<<nextadjvex(gra,gra.vertices[i],w e)<<endl;if(visited[w e]==0)// cout<<dfs(gra,w e);//<<endl;// cout<<i<<w e1<<endl;w e=w e1;// cout<<nextadjvex(gra,gra.vertices[i],w e)<<endl;}return 12;}int bfstra_fen(algr aph gra)//求连通分量{int i,j;for(i=0;i!=gra.vexnum;++i){visited[i]=0;}for(j=0;j!=gra.vexnum;++j){if(visited[j]==0){dfs(gra,j);cout<<endl;}}return 0;}typedef struct{int adjvex;int low cost;}closedge;/*int minimum(c losedge *p);int minispantree(MGraph_L G,char u){int k,j,i;closedge closedge_a[20];k=localvex(G,u);// cout<<k<<endl;for(j=0;j!=G.vexnum;++j){if(j!=k){closedge_a[j].adjvex=u;closedge_a[j].low cost=G.arcs[k][j].adj;}for(i=1;i!=G.vexnum;++i){k=minimum(closedge_a);cout<<k;cout<<closedge_a[k].adjvex<<" "<<G.vexs[k]<<endl; closedge_a[k].low cost=0;for(j=0;j!=G.vexnum;++j)if(G.arcs[k][j].adj<closedge_a[j].low cost){closedge_a[j].adjvex=G.vexs[k];closedge_a[j].low cost=G.arcs[k][j].adj;}}}return 0;}int minimum(closedge *p){int s=10000;for(;p!=NULL;++p){if(s>p->lowcost)s=p->low cost;}return s;}*/int pr im(int g[][max],int n) //最小生成树PRIM算法{int low cost[max],prevex[max]; //LOWCOST[]存储当前集合U分别到剩余结点的最短路径 //prevex[]存储最短路径在U中的结点int i,j,k,min;for(i=2;i<=n;i++) //n个顶点，n-1条边{low cost[i]=g[1][i]; //初始化prevex[i]=1; //顶点未加入到最小生成树中}low cost[1]=0; //标志顶点1加入U集合for(i=2;i<=n;i++) //形成n-1条边的生成树{min=inf;k=0;for(j=2;j<=n;j++) //寻找满足边的一个顶点在U,另一个顶点在V的最小边if((lowcost[j]<min)&&(low cost[j]!=0)){min=low cost[j];k=j;}printf("(%d,%d)%d\t",prevex[k]-1,k-1,min);low cost[k]=0; //顶点k加入Ufor(j=2;j<=n;j++) //修改由顶点k到其他顶点边的权值if(g[k][j]<low cost[j]){low cost[j]=g[k][j];prevex[j]=k;}printf("\n");}return 0;}int acrvisited[100];//kruscal弧标记数组int find(int acrvisited[],int f){w hile(acrvisited[f]>0)f=acrvisited[f];return f;}void kruscal_arc(MGraph_L G,algraph gra) {edg edgs[20];int i,j,k=0;for(i=0;i!=G.vexnum;++i)for(j=i;j!=G.vexnum;++j){if(G.arcs[i][j].adj!=10000){edgs[k].pre=i;edgs[k].bak=j;edgs[k].w eight=G.arcs[i][j].adj;++k;}}int x,y,m,n;int buf,edf;for(i=0;i!=gra.arcnum;++i)acrvisited[i]=0;for(j=0;j!=G.arcnum;++j){m=10000;for(i=0;i!=G.arcnum;++i){if(edgs[i].w eight<m){m=edgs[i].w eight;x=edgs[i].pre;y=edgs[i].bak;n=i;}}// cout<<x<<y<<m;// cout<<endl;buf=find(acrvisited,x);edf=find(acrvisited,y);// cout<<buf<<" "<<edf<<endl;edgs[n].w eight=10000;if(buf!=edf){acrvisited[buf]=edf;cout<<"("<<x<<","<<y<<")"<<m;cout<<endl;}}}void main(){algraph gr a;MGraph_L G;int i,d,g[20][20];char a='a';d=creatMGr aph_L(G);creatadj(gra,G);vnode v;cout<<endl<<"……####注意：若该图为非强连通图(含有多个连通分量)时"<<endl <<" 最小生成树不存在,则显示为非法值。
合肥学院计算机科学与技术系课程设计报告20 11～20 12 学年第二学期课程数据结构与算法课程设计名称图遍历的演示学生姓名汪青松学号1004031010专业班级网络工程1班指导教师吕刚、陈圣兵2011 年 6 月图遍历的演示一、问题分析和任务定义很多涉及图上操作的算法都是以图的遍历操作为基础的。
试写一个程序，演示在连通的无向图上访问全部结点的操作。
将每个结点看做一个地名，如合肥。
然后任选国内的城市，起点未合肥，忽略城市间的里程。
设图的结点20-30个，每个结点用一个编号表示(如果一个图有n个结点，则它们的编号分别为1，2，…，n)。
通过输入图的全部边(存于数据文件中，从文件读写)输入一个图，每个边为一个数对，可以对边的输入顺序作出某种限制。
注意，生成树的边是有向边，端点顺序不能颠倒。
二、数据结构的选择和概要设计城市与城市之间的关系使没有方向的，无向图采用邻近多重表来实现，主要要表示无向图中的各个结点和边，在多重表中边是采用两个结点来表示的。
在邻接表中Edgenode表示邻接表中的结点类型，其中含有访问标记mark，一条边所依附的两个结点的序号ivex和jvex，以及分别指向依附于ivex和jvex 的顶点边的链域ilink和jlink。
其中，邻接表中的表头结点用Vexnode表示，包含了顶点信息data和指向第一个边结点的firstedge。
用AMLGraph表示整个无向图，包含了图的顶点vexnum和边数edgenum。
结点坐标信息：struct loc //结点坐标信息{int v; //结点序号int x; //x坐标int y; //y坐标};边结点数据结构：struct Edgenode //边结点{int mark;//标志域，指示该边是否被访问过(0:没有1:有)int ivex,jvex;//该边关联的两个顶点的位置Edgenode *ilink,*jlink;//分别指向关联这两个顶点的下一条边};顶点结点：struct Vexnode //顶点结点{int data; //顶点名称,用数字表示城市Edgenode *firstedge;//指向第一条关联该结点的边};AMLGraph类：三、详细设计和编码程序主体部分主要包括两大部分，一是遍历算法部分；另一部分是对演示图的处理。
中北大学数据结构课程设计说明书2011年12月19日1设计目的：《数据结构》课程主要介绍最常用的数据结构，阐明各种数据结构内在的逻辑关系，讨论其在计算机中的存储表示，以及在其上进行各种运算时的实现算法，并对算法的效率进行简单的分析和讨论。
进行数据结构课程设计要达到以下目的：⏹了解并掌握数据结构与算法的设计方法，具备初步的独立分析和设计能力；⏹初步掌握软件开发过程的问题分析、系统设计、程序编码、测试等基本方法和技能；⏹提高综合运用所学的理论知识和方法独立分析和解决问题的能力；训练用系统的观点和软件开发一般规范进行软件开发，培养软件工作者所应具备的科学的工作方法和作风。
2设计内容和要求设计内容：(1)采用合适的存储结构来创建图，并实现图的遍历；（2）计算图的最小生成树，求联通分量设计要求：（1）先任意创建一个图；（2) 图的DFS,BFS的递归和非递归算法的实现（3) 最小生成树（两个算法）的实现，求连通分量的实现（4) 要求用邻接矩阵、邻接表、十字链表多种结构存储实现3．本设计所采用的数据结构：本程序是采用邻接矩阵、邻接表、十字链表等多种结构存储来实现对图的存储。
对图的遍历分别采用了广度优先遍历和深度优先遍历。
4.1 详细设计思想这次课程设计我们主要是应用以前学习的数据结构与面向对象程序设计知识，结合起来才完成了这个程序。
因为图是一种较线形表和树更为复杂的数据结构。
在线形表中，数据元素之间仅有线性关系，每个元素只有一个直接前驱和一个直接后继，并且在图形结构中，节点之间的关系可以是任意的，图中任意两个数据元素之间都可能相关。
因此，本程序是采用邻接矩阵、邻接表、十字链表等多种结构存储来实现对图的存储。
采用邻接矩阵即为数组表示法，邻接表和十字链表都是图的一种链式存储结构。
对图的遍历分别采用了广度优先遍历和深度优先遍历。
4.3 核心代码#include <iostream> #include <malloc.h> using namespace std;开始创建图G表存储图IfNY显示图的邻接矩阵KRUSCAL算法显示图的邻接表深度优先遍历广度优先遍历最小生成树PRIM输入字母If结束NY图的连通分量输入一个数2013456#define int_max 10000#define inf 9999#define max 20//…………………………………………邻接矩阵定义……………………typedef struct ArcCell22{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(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;//弧尾相同的下一条弧}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 i=0,j=0;arcnode *arc,*tem,*p;for(i=0;i!=G.vexnum;++i){ gra.vertices[i].data=G.vexs[i];gra.vertices[i].firstarc=NULL;}for(i=0;i!=G.vexnum;++i){ for(j=0;j!=G.vexnum;++j){ if(gra.vertices[i].firstarc==NULL){ if(G.arcs[i][j].adj!=int_max&&j!=G.vexnum) { arc=(arcnode *)malloc(sizeof(arcnode));arc->adjvex=j;gra.vertices[i].firstarc=arc;arc->nextarc=NULL;p=arc;++j;while(G.arcs[i][j].adj!=int_max&&j!=G.vexnum) { tem=(arcnode *)malloc(sizeof(arcnode));tem->adjvex=j;gra.vertices[i].firstarc=tem;tem->nextarc=arc;arc=tem;++j;}--j;}}else{ if(G.arcs[i][j].adj!=int_max&&j!=G.vexnum)arc=(arcnode *)malloc(sizeof(arcnode)); arc->adjvex=j;p->nextarc=arc;arc->nextarc=NULL;p=arc;}}}}gra.vexnum=G.vexnum;gra.arcnum=G.arcnum;/*for(i=0;i!=gra.vexnum;++i){ arcnode *p;cout<<i<<" ";p=gra.vertices[i].firstarc;while(p!=NULL){ cout<<p->adjvex;p=p->nextarc;}cout<<endl;}*/cout<<"图G邻接表创建成功！"<<endl;return 1;}void adjprint(algraph gra){ int i;for(i=0;i!=gra.vexnum;++i){ arcnode *p;cout<<i<<" ";while(p!=NULL){ cout<<p->adjvex;p=p->nextarc;}cout<<endl;}}int firstadjvex(algraph gra,vnode v)//返回依附顶点V的第一个点//即以V为尾的第一个结点{ if(v.firstarc!=NULL)return v.firstarc->adjvex;}int nextadjvex(algraph gra,vnode v,int w)//返回依附顶点V的相对于W的下一个顶点{ arcnode *p;p=v.firstarc;while(p!=NULL&&p->adjvex!=w){ p=p->nextarc;}if(p->adjvex==w&&p->nextarc!=NULL){ p=p->nextarc;return p->adjvex;}if(p->adjvex==w&&p->nextarc==NULL)return -10;}int initqueue(linkqueue &q)//初始化队列{ q.rear=(queueptr)malloc(sizeof(qnode));q.front=q.rear;if(!q.front)q.front->next=NULL;return 1;}int enqueue(linkqueue &q,int e)//入队{ queueptr p;p=(queueptr)malloc(sizeof(qnode));if(!p)return 0;p->data=e;p->next=NULL;q.rear->next=p;q.rear=p;return 1;}int dequeue(linkqueue &q,int &e)//出队{ queueptr p;if(q.front==q.rear)return 0;p=q.front->next;e=p->data;q.front->next=p->next;if(q.rear==p)q.rear=q.front;free(p);return 1;}int queueempty(linkqueue q)//判断队为空{ if(q.front==q.rear)return 1;}void bfstra(algraph gra)//广度优先遍历{ int i,e;linkqueue q;for(i=0;i!=gra.vexnum;++i)visited[i]=0;initqueue(q);for(i=0;i!=gra.vexnum;++i)if(!visited[i]){ visited[i]=1;cout<<gra.vertices[i].data;enqueue(q,i);while(!queueempty(q)){ dequeue(q,e);// cout<<" "<<e<<" ";for(we=firstadjvex(gra,gra.vertices[e]);we>=0;we=nextadjvex(gra,gra.vertices[e],we)) { if(!visited[we]){visited[we]=1;cout<<gra.vertices[we].data;enqueue(q,we);}}}}}int dfs(algraph gra,int i);//声明DFSint dfstra(algraph gra){ int i,j;{ visited[i]=0;}for(j=0;j!=gra.vexnum;++j){ if(visited[j]==0)dfs(gra,j);}return 0;}int dfs(algraph gra,int i){ visited[i]=1;int we1;// cout<<i<<visited[i]<<endl;cout<<gra.vertices[i].data;// cout<<endl;for(we=firstadjvex(gra,gra.vertices[i]);we>=0;we=nextadjvex(gra,gra.vertices[i],we)) {// cout<<we<<visited[we]<<endl;we1=we;// cout<<nextadjvex(gra,gra.vertices[i],we)<<endl;if(visited[we]==0)// cout<<dfs(gra,we);//<<endl;// cout<<i<<we1<<endl;we=we1;// cout<<nextadjvex(gra,gra.vertices[i],we)<<endl;}return 12;}int bfstra_fen(algraph gra)//求连通分量for(i=0;i!=gra.vexnum;++i){ visited[i]=0;}for(j=0;j!=gra.vexnum;++j){ if(visited[j]==0){dfs(gra,j);cout<<endl;}}return 0;}typedef struct{ int adjvex;int lowcost;}closedge;/*int minimum(closedge *p);int minispantree(MGraph_L G,char u){ int k,j,i;closedge closedge_a[20];k=localvex(G,u);// cout<<k<<endl;for(j=0;j!=G.vexnum;++j){ if(j!=k){ closedge_a[j].adjvex=u;closedge_a[j].lowcost=G.arcs[k][j].adj; }for(i=1;i!=G.vexnum;++i){ k=minimum(closedge_a);cout<<closedge_a[k].adjvex<<" "<<G.vexs[k]<<endl;closedge_a[k].lowcost=0;for(j=0;j!=G.vexnum;++j)if(G.arcs[k][j].adj<closedge_a[j].lowcost){ closedge_a[j].adjvex=G.vexs[k];closedge_a[j].lowcost=G.arcs[k][j].adj;}}}return 0;}int minimum(closedge *p){ int s=10000;for(;p!=NULL;++p){ if(s>p->lowcost)s=p->lowcost;}return s;}*/int prim(int g[][max],int n) //最小生成树PRIM算法{ int lowcost[max],prevex[max]; //LOWCOST[]存储当前集合U分别到剩余结点的最短路径 //prevex[]存储最短路径在U中的结点int i,j,k,min;for(i=2;i<=n;i++) //n个顶点，n-1条边{ lowcost[i]=g[1][i]; //初始化prevex[i]=1; //顶点未加入到最小生成树中}lowcost[1]=0; //标志顶点1加入U集合for(i=2;i<=n;i++) //形成n-1条边的生成树k=0;for(j=2;j<=n;j++) //寻找满足边的一个顶点在U,另一个顶点在V的最小边 if((lowcost[j]<min)&&(lowcost[j]!=0)){min=lowcost[j];k=j;}printf("(%d,%d)%d\t",prevex[k]-1,k-1,min);lowcost[k]=0; //顶点k加入Ufor(j=2;j<=n;j++) //修改由顶点k到其他顶点边的权值if(g[k][j]<lowcost[j]){lowcost[j]=g[k][j];prevex[j]=k;}printf("\n");}return 0;}int acrvisited[100];//kruscal弧标记数组int find(int acrvisited[],int f){while(acrvisited[f]>0)f=acrvisited[f];return f;}void kruscal_arc(MGraph_L G,algraph gra){ edg edgs[20];int i,j,k=0;for(i=0;i!=G.vexnum;++i)for(j=i;j!=G.vexnum;++j){if(G.arcs[i][j].adj!=10000)edgs[k].bak=j;edgs[k].weight=G.arcs[i][j].adj; ++k;}}int x,y,m,n;int buf,edf;for(i=0;i!=gra.arcnum;++i)acrvisited[i]=0;for(j=0;j!=G.arcnum;++j){m=10000;for(i=0;i!=G.arcnum;++i){if(edgs[i].weight<m){ m=edgs[i].weight;x=edgs[i].pre;y=edgs[i].bak;n=i;}}// cout<<x<<y<<m;// cout<<endl;buf=find(acrvisited,x);edf=find(acrvisited,y);// cout<<buf<<" "<<edf<<endl;edgs[n].weight=10000;if(buf!=edf){acrvisited[buf]=edf;cout<<"("<<x<<","<<y<<")"<<m;cout<<endl;}}void main(){ algraph gra;MGraph_L G;int i,d,g[20][20];char a='a';d=creatMGraph_L(G);creatadj(gra,G);vnode v;cout<<endl<<"……####注意：若该图为非强连通图(含有多个连通分量)时"<<endl <<" 最小生成树不存在,则显示为非法值。
