数据结构与算法课程设计报告---图的算法实现

数据结构与算法实验——图的基本操作图的基本操作实验报告图的基本操作实验报告实验名称图的基本操作实验目的1.掌握图的各种存储结构，特别要熟练掌握邻接矩阵和邻接表的存储结构；2.遍历是图各种应用的算法的基础，要熟练掌握图的深度优先遍历和广度优先遍历的算法，复习栈和队列的应用；3.掌握以邻接矩阵作为存储结构的生成图的最小生成树的普利姆算法；实验内容编制一个演示图的邻接表的创建、深度遍历、广度遍历操作的程序。

问题描述用数据结构相关知识，实现邻接表的定义和操作。

该程序包括图的邻接表的结点类型定义以及对图操作的具体的函数定义（包括：建立图的邻接表、深度优先遍历图、广度优先遍历图）。

问题分析该实验是基于C语言和数据结构知识基础的对图的基本操作的检验，无需设计复杂的算法，程序语句也相对简单。

因此，我直接按要求定义了对图操作的具体函数，并于主函数中实现对应的功能调用。

实验步骤1．需求分析本演示程序用VC++编写，完成图的邻接表的生成、遍历基本操作。

输入的形式和输入值的范围：在输入邻接表顶点信息前，必须先确定该信息能正确创建邻接表。

②输出的形式：在所有三种操作中都显示操作是否正确以及操作后图的内容。

③程序所能达到的功能：完成图的邻接表的生成、深度优先遍历、广度优先遍历基本操作。

④测试数据：创建操作中依次输入7,7作为顶点数和边数，以（0,1）（0,2）（1,3）（1,5）（3,4）（3,6）（4,5）作为各顶点信息生成一个邻接表。

2．概要设计1）为了实现上述程序功能，需要定义二叉树的抽象数据类型：ADT Graph {数据对象：顶点的有穷非空集合和边的集合数据关系：结点具有相同的数据类型及层次结构基本操作：Void InitGraph(ALGraph *G)初始条件：无操作结果：初始化图Void DFSTraverse(ALGraph *G)初始条件：图Graph已存在操作结果：按深度优先遍历图的邻接表Void BFSTraverse(ALGraph *G)初始条件：图Graph已存在操作结果：按广度优先遍历图的邻接表2）本程序包含7个函数：①主函数main() ②建立一个图的邻接表函数CreateGraphAL ()③深度优先遍历图 DFS ()④广度优先遍历 BFS()函数说明#include <stdio.h>#include <stdlib.h>#define MaxVertexNum 100#define QueueSize 30typedef enum{FALSE,TRUE}Boolean;Boolean visited[MaxVertexNum];typedef char VertexType;typedef int EdgeType;typedef struct node //边表结点{int adjvex; //邻接点域struct node *next; //域链//若是要表示边上的权,则应增加一个数据域}EdgeNode;typedef struct vnode //顶点边结点{VertexType vertex; //顶点域EdgeNode *firstedge;//边表头指针}VertexNode;typedef VertexNode AdjList[MaxVertexNum];//AdjList是邻接表类型typedef struct{AdjList adjlist; //邻接表int n,e; //图中当前顶点数和边数}ALGraph;void CreateGraphAL (ALGraph *G){int i,j,k;EdgeNode * s;printf("请输入顶点数和边数(输入格式为:顶点数,边数)：\n");scanf("%d,%d",&(G->n),&(G->e));// 读入顶点数和边数printf("请输入顶点信息(输入格式为:顶点号<CR>)每个顶点以回车作为结束:\n");for (i=0;i<G->n;i++) //立有n个顶点的顶点表{scanf("\n%c",&(G->adjlist[i].vertex)); //读入顶点信息G->adjlist[i].firstedge=NULL; // 点的边表头指针设为空}printf("请输入边的信息(输入格式为:i,j)：\n");for (k=0;k<G->e;k++) // 建立边表{scanf("\n%d,%d",&i,&j); // 读入边<Vi,Vj>的顶点对应序号s=new EdgeNode; // 生成新边表结点ss->adjvex=j; // 邻接点序号为js->next=G->adjlist[i].firstedge; // 将新边表结点s插入到顶点Vi的边表头部 G->adjlist[i].firstedge=s;s=new EdgeNode;s->adjvex=i;s->next=G->adjlist[j].firstedge;G->adjlist[j].firstedge=s;}}/**************************************** ********************************//* 深度优先遍历*//**************************************** ********************************/void DFS(ALGraph *G,int i){//以vi为出发点对邻接表表示的图G进行深度优先搜索EdgeNode *p;printf("visitvertex:%c\n",G->adjlist[i].vertex); // 访问顶点vivisited[i]=TRUE; //标记vi已访问p=G->adjlist[i].firstedge; //取vi 边表的头指针while(p){ //依次搜索vi的邻接点vj，这里j=p->adjvexif (!visited[p->adjvex]) //若vi尚未被访问DFS(G,p->adjvex); //则以Vj为出发点向纵深搜索p=p->next; //找vi的下一邻接点}}void DFSTraverseM(ALGraph *G){int i;for(i=0;i<G->n;i++)visited[i]=FALSE;for(i=0;i<G->n;i++)if(!visited[i])DFS(G,i);}/**************************************** ********************************//* 广度优先遍历*//**************************************** ********************************/ typedef struct{int front;int rear;int count;int data[QueueSize];}CirQueue;void InitQueue(CirQueue *Q){Q->front=Q->rear=0;Q->count=0;}int QueueEmpty(CirQueue *Q){return Q->front==Q->rear;}int QueueFull(CirQueue *Q){return(Q->rear+1)%QueueSize==Q->front; }void EnQueue(CirQueue *Q,int x) {if (QueueFull(Q))printf("Queue overflow"); else{Q->count++;Q->data[Q->rear]=x;Q->rear=(Q->rear+1)%QueueSize; }}int DeQueue(CirQueue *Q){int temp;if(QueueEmpty(Q)){printf("Queue underflow");return false;}else{temp=Q->data[Q->front];Q->count--;Q->front=(Q->front+1)%QueueSize; return temp;}}void BFS(ALGraph*G,int k){ // 以vk为源点对用邻接表表示的图G进行广度优先搜索int i;CirQueue Q; //须将队列定义中DataType改为intEdgeNode *p;InitQueue(&Q); //队列初始化printf("visitvertex:%c\n",G->adjlist[k].vertex); //访问源点vkvisited[k]=TRUE;EnQueue(&Q,k); //vk已访问，将其人队。

数据结构实验报告目的要求１．掌握图的存储思想及其存储实现..２．掌握图的深度、广度优先遍历算法思想及其程序实现..３．掌握图的常见应用算法的思想及其程序实现..实验内容１．键盘输入数据;建立一个有向图的邻接表..２．输出该邻接表..3．在有向图的邻接表的基础上计算各顶点的度;并输出..4．以有向图的邻接表为基础实现输出它的拓扑排序序列..5．采用邻接表存储实现无向图的深度优先递归遍历..6．采用邻接表存储实现无向图的广度优先遍历..7．在主函数中设计一个简单的菜单;分别调试上述算法..源程序：主程序的头文件：队列#include <stdio.h>#include <stdlib.h>#define TRUE 1#define FALSE 0#define OK 1#define ERROR 0#define OVERFLOW -2typedef int QElemType;typedef struct QNode{ //队的操作QElemType data;struct QNode *next;}QNode;*QueuePtr;typedef struct {QueuePtr front;QueuePtr rear;}LinkQueue;void InitQueueLinkQueue &Q{ //初始化队列Q.front =Q.rear =QueuePtrmallocsizeofQNode;ifQ.front exitOVERFLOW; //存储分配失败Q.front ->next =NULL;}int EnQueueLinkQueue &Q;QElemType e //插入元素e为Q的新的队尾元素{QueuePtr p;p=QueuePtrmallocsizeofQNode;ifp exitOVERFLOW;p->data=e;p->next=NULL;Q.rear->next=p;Q.rear =p;return OK;}int DeQueueLinkQueue &Q;QElemType &e //删除Q的队头元素;用e返回其值{ ifQ.front ==Q.rear return ERROR;QueuePtr p;p=Q.front ->next;e=p->data;Q.front->next=p->next ;ifQ.rear==p Q.rear =Q.front ;freep;return OK;}主程序：#include <stdio.h>#include<stdlib.h>#include"duilie.h"#define TRUE 1#define FALSE 0#define Status int#define MAX_VERTEX_NUM 8 /*顶点最大个数*/#define VertexType char /*顶点元素类型*/enum BOOlean {False;True};BOOlean visitedMAX_VERTEX_NUM; //全局变量——访问标志数组typedef struct ArcNode{int adjvex;struct ArcNode *nextarc;int weight; /*边的权*/}ArcNode; /*表结点*/typedef struct VNode{ int degree;indegree;/*顶点的度;入度*/V ertexType data;ArcNode *firstarc;}VNode/*头结点*/;AdjListMAX_VERTEX_NUM;typedef struct{ AdjList vertices;int vexnum;arcnum;/*顶点的实际数;边的实际数*/}ALGraph;//建立图的邻接表void creat_linkALGraph *G{ int i;j;ArcNode *s;printf"请依次输入顶点数、边数：";scanf"%d%d";&G->vexnum;&G->arcnum;for i=0;i<G->vexnum;i++{ G->verticesi.data='A'+i;G->verticesi.firstarc=NULL;}for i=0;i<G->vexnum;{ printf"请输入顶点的数组坐标若退出;请输入-1：";scanf"%d";&i;ifi==-1 break;printf"请输入顶点所指向下一个顶点的数组坐标：";scanf"%d";&j;s=ArcNode *mallocsizeofArcNode;s->adjvex=j;s->nextarc=G->verticesi.firstarc;G->verticesi.firstarc=s;}}// 输出邻接表void visitALGraph G{ int i;ArcNode *p;printf"%4s%6s%18s\n";"NO";"data";"adjvexs of arcs";for i=0;i<G.vexnum;i++{printf"%4d%5c ";i;G.verticesi.data;forp=G.verticesi.firstarc;p;p=p->nextarcprintf"%3d";p->adjvex;printf"\n";}}// 计算各顶点的度及入度void cacuALGraph *G{ArcNode *p;int i;for i=0;i<G->vexnum;i++{G->verticesi.degree=0;G->verticesi.indegree=0;}//度与初度初始化为零for i=0;i<G->vexnum;i++forp=G->verticesi.firstarc;p;p=p->nextarc{G->verticesi.degree++;G->verticesp->adjvex.degree++;G->verticesp->adjvex.indegree++;}}void print_degreeALGraph G{int i;printf"\n Nom data degree indegree\n";for i=0;i<G.vexnum;i++printf"\n%4d%5c%7d%8d";i;G.verticesi.data;G.verticesi.degree;G.verticesi.indegree;printf"\n";}// 拓扑排序Status TopologiSortALGraph G{int i;count;top=0;stack50;ArcNode *p;cacu&G;print_degreeG;printf"\nTopologiSort is \n";fori=0;i<G.vexnum;i++ifG.verticesi.indegree stacktop++=i;count=0;whiletop=0{i=stack--top;if count==0 printf"%c";G.verticesi.data;else printf"-->%c";G.verticesi.data;count++;forp=G.verticesi.firstarc;p;p=p->nextarcif --G.verticesp->adjvex.indegreestacktop++=p->adjvex;}if count<G.vexnumreturnFALSE; else returnTRUE;}//在图G中寻找第v个顶点的第一个邻接顶点int FirstAdjVexALGraph G;int v{ifG.verticesv.firstarc return 0;else returnG.verticesv.firstarc->adjvex;}//在图G中寻找第v个顶点的相对于u的下一个邻接顶点int NextAdjVexALGraph G;int v;int u{ArcNode *p;p=G.verticesv.firstarc;whilep->adjvex=u p=p->nextarc; //在顶点v的弧链中找到顶点u ifp->nextarc==NULL return 0; //若已是最后一个顶点;返回0else returnp->nextarc->adjvex; //返回下一个邻接顶点的序号}//采用邻接表存储实现无向图的深度优先递归遍历void DFSALGraph G;int i{ int w;visitedi=True; //访问第i个顶点printf"%d->";i;forw=FirstAdjVexG;i;w;w=NextAdjVexG;i;wifvisitedw DFSG;w; //对尚未访问的邻接顶点w调用DFS}void DFSTraverseALGraph G{ int i;printf"DFSTraverse:";fori=0;i<G.vexnum;i++ visitedi=False; //访问标志数组初始化fori=0;i<G.vexnum;i++ifvisitedi DFSG;i; //对尚未访问的顶点调用DFS}//按广度优先非递归的遍历图G;使用辅助队列Q和访问标志数组visited void BFSTraverseALGraph G{int i;u;w;LinkQueue Q;printf"BFSTreverse:";fori=0;i<G.vexnum;i++ visitedi=False; //访问标志数组初始化InitQueueQ; //初始化队列fori=0;i<G.vexnum;i++ifvisitedi{visitedi=True; //访问顶点iprintf"%d->";i;EnQueueQ;i; //将序号i入队列whileQ.front ==Q.rear //若队列不空;继续{DeQueueQ;u; //将队头元素出队列并置为uforw=FirstAdjVexG;u;w;w=NextAdjV exG;u;wifvisitedw //对u的尚未访问的邻接顶点w进行访问并入队列{ visitedw=True;printf"%d->";w;EnQueueQ;w;}}}}void main{ALGraph G;int select;printf" 图的有关操作实验\n ";do{printf"\n1 创建一个有向图的邻接表 2 输出该邻接表\n";printf"3.输出该有向图的度和入度 4.输出该有向图拓扑排序序列\n";printf"5.创建一个无向图的邻接表 6.深度优先递归遍历该无向图\n";printf"7.广度优先遍历该无向图0.退出\n";printf"请输入选择：";scanf"%d";&select;switchselect{case 1:printf"\n创建一个有向图的邻接表：\n";creat_link&G;break;case 2:printf"\n输出该邻接表：\n";visitG;break;case 3:printf"\n输出该有向图的度和入度：\n";cacu&G;print_degreeG;break;case 4:printf"\n输出该有向图拓扑排序序列：\n";ifTopologiSortGprintf"Toposort is not success";break;case 5:printf"\n创建一个无向图的邻接表: \n";creat_link&G;break;case 6:printf"\n深度优先递归遍历该无向图: \n";DFSTraverseG;break;case 7:printf"\n广度优先遍历该无向图：\n";BFSTraverseG;break;case 0:break;default:printf"输入选项错误重新输入\n";}}whileselect;}运行结果截图：1.主菜单界面：2.创建一个有向图的领接表3.输出该邻接表4. 在有向图的邻接表的基础上计算各顶点的度;并输出..5. 输出它的拓扑排序序列6. 输出所建无向图的邻接表7. 深度优先递归遍历该无向图8. 广度优先遍历该无向图说明：本实验用的有向图是课本182页图7.28;无向图为课本168页图a实验总结这次的图的操作实验;与树的操作类似;但又比树复杂;包含更多的存储结构和遍历方法的操作;而且图的遍历需要沿着弧进行;以便输出弧上的信息..本实验中图的遍历采用邻接表的存储结构;在输入图的信息时;首先要画出图的邻接表信息..图有两种遍历的形式;一种为深度优先搜索;另一种为广度优先搜索..由于能力有限;没能实现图的深度非递归优先搜索;而是实现了图的深度递归优先搜索..本实验基本完成了图的操作;也学到了很多关于图的知识和算法..。

数据结构实验报告--图【数据结构实验报告--图】【一、实验目的】本实验旨在掌握图的基本概念、存储结构以及相关操作，并通过实验加深对图的理解。

【二、实验环境】操作系统：Windows 10编程语言：C++开发工具：Dev-C++ 5.11【三、实验内容】1.图的定义与基本概念1.1 图的定义：有向图、无向图1.2 图的基本概念：顶点、边、路径、路径长度2.图的存储结构2.1 邻接矩阵表示法2.2 邻接表表示法3.图的操作3.1 图的创建①手动输入图的顶点和边②从文件中读取图的顶点和边3.2 图的遍历①深度优先遍历（DFS）②广度优先遍历（BFS）3.3 图的最小树① Prim算法② Kruskal算法3.4 图的最短路径① Dijkstra算法② Floyd算法4.实验结果分析4.1 图的创建结果4.2 图的遍历结果4.3 图的最小树结果4.4 图的最短路径结果【四、实验步骤】1.定义图的数据结构和相关操作的函数原型。

2.实现图的存储结构和相关操作的函数实现。

3.开发主程序，包括菜单、用户输入、调用图操作函数等。

4.运行程序，测试各个功能是否正常进行。

5.根据运行结果分析，进行必要的调试和优化。

【五、实验结果】1.图的创建结果：●手动输入图的顶点和边：●顶点数.10●边数.15●从文件中读取图的顶点和边：●顶点数.8●边数.122.图的遍历结果：●深度优先遍历：●遍历路径.1 -> 2 -> 4 -> 5 -> 3●广度优先遍历：●遍历路径.1 -> 2 -> 3 -> 4 -> 53.图的最小树结果：●Prim算法：●最小树顶点集合：{1, 2, 4, 5}●最小树边集合：{(1, 2), (2, 4), (2, 5)}●Kruskal算法：●最小树边集合：{(1, 2), (2, 4), (2, 5)}4.图的最短路径结果：●Dijkstra算法：●从顶点1到其他顶点的最短路径长度：●1 -> 2、2●1 -> 3、5●1 -> 4、4●1 -> 5、6●Floyd算法：●图的最短路径邻接矩阵：●0 2 5 4 6●2 0 3 1 3●5 3 0 5 4●4 1 5 0 2●6 3 4 2 0【附件】无【法律名词及注释】1.顶点：图中的一个节点，可以表示实体或事件。

《数据结构与算法分析》课程实验报告【实验目的】1. 理解图形结构的逻辑和存储特点。

2. 掌握图形结构遍历递归算法。

【实验内容】1. 用邻接矩阵或者邻接表存储一个图形结构。

2. 采用深度或者广度优先搜索算法，遍历一个图，并输出遍历结果。

【实验方式】个人实验。

【实验设备与环境】PC机，Windows XP操作系统，VC++6.0开发环境。

【数据结构及函数定义】（1）类的定义：类的数据成员，成员函数．．．．．．．．．．．．．．．．．．．（2）主函数main（）实现初始化操作，完成对子函数的调用．．．．．．．．．．．．．．．．．．．（3）子函数．．．．．．．．．．．．．．．．．．．。

【测试数据与实验结果】（请用截图的方式展示实验结果，并辅以必要的文字说明）【源程序清单】（请附上源程序）#include<iostream>using namespace std;#include<string.h>class Graph{public:c har Vtx[20];d ouble AdjMtx[20][20];i nt CurrentVnum;i nt CurrentEnum;G raph(){CurrentVnum=CurrentEnum=0;} i nt first_adj(int v);i nt next_adj(int v1,int v2);v oid visite(int v);v oid DFS();v oid DFS(int v,int visited[]);~Graph(){}};int Graph::first_adj(int v){f or(int v1=0;v1<CurrentVnum;v1++)if(AdjMtx[v][v1]>0)return v1;return -1;}int Graph::next_adj(int v1,int v2) {f or(int vn=v2+1;vn<CurrentVnum;vn++)if(AdjMtx[v1][vn]>0)return vn;return -1;}void Graph::visite(int v){c out<<Vtx[v]<<" ";}void Graph::DFS(){i nt *visited=new int[CurrentVnum];f or(int i=0;i<CurrentVnum;i++)visited[i]=0;f or(i=0;i<CurrentVnum;i++){if(visited[i]==0)DFS(i,visited);}d elete[] visited;}void Graph::DFS(int v,int visited[]) {v isite(v);v isited[v]=1;i nt w=first_adj(v);w hile(w!=-1){if(!visited[w])DFS(w,visited);w=next_adj(v,w);}}int LocateVex(Graph G,char u){i nt i;f or(i=0;i<G.CurrentVnum;i++)if(u==G.Vtx[i])return i;return -1;}void creat(Graph &G){i nt i,j,k;c har va,vb;c out<<"请输入图的顶点数,弧数:";c in>>G.CurrentVnum>>G.CurrentEnum;c out<<"请输入"<<G.CurrentVnum<<"个顶点的值:";f or(i=0;i<G.CurrentVnum;i++)cin>>G.Vtx[i];f or(i=0;i<G.CurrentVnum;i++)for(j=0;j<G.CurrentVnum;j++)G.AdjMtx[i][j]=0;c out<<"请输入"<<G.CurrentEnum<<"条弧的弧尾,弧头(以空格作为间隔):\n";f or(k=0;k<G.CurrentEnum;k++){cin>>va>>vb;i=LocateVex(G,va);j=LocateVex(G,vb);if(i!=j){G.AdjMtx[i][j]=1;G.AdjMtx[j][i]=1;}else G.AdjMtx[i][j]=1;}}void main(){G raph G;c reat(G);c out<<"深度优先搜索序列:"<<endl;G.DFS();c out<<endl;。

数据结构课程设计报告设计题目：图的算法实现班级：学号：姓名：数据结构课程设计报告内容一．课程设计题目图的算法实现【基本要求】（1）建立一文件，将图的信息存在此文件中；（2）从此文件读入图的信息，建立邻接矩阵和邻接表；（3）实现Prim、Kruskal、Dijkstra和拓扑排序算法。

二．算法设计思想（1）图的存储结构：邻接矩阵：用两个数组分别存储数据元素（顶点）的信息和数据元素之间的关系（边或弧）的信息。

邻接表：对图中的每个顶点建立一个单链表，第i个单链表中的结点表示依附于顶点Vi的边（对有向图是以顶点Vi为尾的弧）。

每个结点由3个域组成，其中邻接点域指示与顶点Vi邻接的点在图中的位置，链域指示下一条边或弧的结点；数据域存储和边或弧相关的信息。

每个链表上附设一个表头结点。

在表头结点中，除了设有链域指向链表中第一个结点之外，还设有存储顶点Vi的名或其他相关信息的数据域。

（2）prim算法是一种求图的最小生成树的算法。

假设N=（V，{E}）是连通网，TE是N上最小生成树中边的集合。

算法从U＝{u0}（u0∈V）、TE＝{}开始。

重复执行下列操作：在所有u∈U，v∈V－U的边(u，v)∈E中找一条权值最小的边(u0,v0)并入集合TE中，同时v0并入U，直到V＝U为止。

此时，TE中必有n-1条边，T=(V，TE)为G 的最小生成树。

Prim算法的核心:始终保持TE中的边集构成一棵生成树。

（3）Kruskal算法Kruskal算法是另一种求最小生成树的算法他的基本思想是以边为主导地位，始终选择当前可用（所选的边不能构成回路）的最小权植边。

所以Kruskal算法的第一步是给所有的边按照从小到大的顺序排序。

具体实现过程如下：<1> 设一个有n个顶点的连通网络为G（V,E），最初先构造一个只有n个顶点，没有边的非连通图T={V,空}，图中每个顶点自成一格连通分量。

<2> 在Ｅ中选择一条具有最小权植的边时，若该边的两个顶点落在不同的连通分量上，则将此边加入到Ｔ中；否则，即这条边的两个顶点落到同一连通分量上，则将此边舍去（此后永不选用这条边），重新选择一条权植最小的边。

数据结构实验报告--图
数据结构实验报告--图
1、实验目的
本实验主要旨在通过实践操作，深入理解图这种数据结构的基本概念、性质和基本操作，掌握图的存储结构与常见算法。

2、实验环境
本次实验使用编程语言C++，在Windows平台下进行开发和运行。

3、实验内容
3.1 图的定义与基本概念
在本章中，我们将介绍图的基本概念，包括有向图与无向图、顶点与边、度与入度出度、连通性等。

3.2 图的存储结构
在本章中，我们将介绍图的几种存储结构，包括邻接矩阵、邻接表和十字链表，以及它们的优缺点和适用场景。

3.3 图的遍历
在本章中，我们将介绍图的两种常用的遍历算法，即深度优先搜索（DFS）和广度优先搜索（BFS），并分别给出它们的实现代码和应用场景。

3.4 最短路径
在本章中，我们将介绍图的最短路径问题，包括单源最短路径和全源最短路径。

我们将使用Dijkstra算法和Floyd-Warshall算法来解决这些问题，并给出它们的实现代码和应用场景。

3.5 最小树
在本章中，我们将介绍图的最小树问题，即找到一棵树使得树上的边的权值之和最小。

我们将使用Prim算法和Kruskal算法来解决这个问题，并给出它们的实现代码和应用场景。

4、实验步骤和结果
在本章中，我们将详细介绍实验的具体步骤，并给出实验结果的详细分析和说明。

5、实验总结
在本章中，我们将对整个实验进行总结，总结实验中遇到的问题、解决方案和经验教训。

6、附件
本实验报告所涉及的附件包括实验代码和运行结果的截图。

7、法律名词及注释
本文所涉及的法律名词和注释详见附件中的相关文件。

淮北师范大学数据结构课程设计图的相关算法----无向图相关算法学院计算机科学与技术专业计算机科学与技术(师范)学号 20091201016学生姓名 ***指导教师姓名 ***2011年04月13日一、设计目的与内容：（1）实验目的●进一步巩固和复习数据结构理论知识。

●培养学生结构化程序、模块化程序设计的方法和能力。

●提高学生调试程序的技巧和软件设计的能力。

●提高分析问题、解决问题以及综合利用各种数据结构的能力。

●了解软件的编制过程。

（2）实验内容实现从文件中读入图的信息，能够根据信息建立有向图和无向图，并分别用邻接矩阵和邻接表存储。

在此基础上，实现Prim、Kruskal、Dijkstra和拓扑排序算法。

程序应具有以下基本功能：图的建立和存储:根据文件中的信息，建立图并采用合适结构存储：无向图的邻接矩阵和邻接表、有向图的邻接矩阵和邻接表。

分别实现Prim、Kruskal、Dijkstra和拓扑排序算法。

使用菜单方式进行各功能选择。

1、实现的任务：从文件中读入图的信息，建立图的邻接矩阵和邻接表，实现Prim、Kruskal、Dijkstra和拓扑排序算法。

2、本系统涉及的知识点Prim、Kruskal、Dijkstra、拓扑排序、邻接矩阵和邻接表存储。

3、功能要求1．不同的功能使用不同的函数实现（模块化），对每个函数的功能和调用接口要注释清楚。

对程序其它部分也进行必要的注释。

2．对系统进行功能模块分析、画出总流程图和各模块流程图。

3．用户接口要求使用方便、简洁明了、美观大方、格式统一。

4．通过命令行相应选项能直接进入某个相应菜单选项的功能模块。

5．所有程序需调试通过。

二、功能设计：1、流程图（Prim算法找出最小生成树）2、程序无向图相关算法的基本功能本部分程序可以对图的相关信息：顶点、边以及顶点与边的指向关系建立无向图的邻接矩阵进行拓扑排序。

3、程序代码设计1．文件保存函数（void getin_1()）建立一个名为record_1.txt的文件保存数据，保存的数据包括顶点的个数、边的条数、顶点与边之间的关系。

《算法与数据结构》课程实验报告一、实验目的1.实现图的存储结构;2.通过图的相关算法实现，掌握其算法思想。

二、实验内容及要求1.无向带权图的存储结构(邻接矩阵、邻接表等自选)2.实现图的相关算法(1)计算指定顶点的度(2)图的深度优先遍历和广度优先遍历算法(3)分别使用Kruskal和Prim算法求解该图的最小生成树三、系统分析（1）数据方面：定义图的模板基类，在模板类定义中的数据类型参数表<class T,class E>中，T是定点数据的类型，E是边上所附数据的类型。

这个模板基类是按照带权无向图来定义的。

在该实验中定点的数据的类型为char型，边上所附数据的类型为int型。

且图的创建为无向图。

（2）功能方面：1.能够实现图的创建以及图的输出。

2.能够返回顶点在图中位置以及图中位置对应顶点的值。

3.返回当前图中的边数与顶点数。

4.返回输入边的权值。

5.能够插入一个顶点或插入顶点与之相关联的边。

6.删除边或删除顶点与之相关联的边。

7.计算顶点的度。

8.实现深度优先搜索、广度优先搜索遍历。

9.Kruskal算法、Prim算法生成最小生成树。

四、系统设计（1）设计的主要思路根据实验要求，首先确定图的存储结构，在根据存储结构编写模板类，并将需要实现的功能代码完善，再写出实现各个功能的菜单并进行调试。

由于在编写由图生成最小生成树中采用了最小堆以及并查集的算法，故需要将这两个个类的代码完成并进行调试。

最后将此次实验所涉及的类全部整理完全后，通过之前编写的菜单对功能进行依次调试，完成此次实验。

（2）数据结构的设计图是非线性结构，它的每一个顶点可以与多个其他顶点相关联，各顶点之间的关系是任意的。

可以用很多方法来存储图结构。

在此采用邻接矩阵来存储图结构。

首先将所有顶点的信息组织成一个顶点表，然后利用一个矩阵来表示各顶点之间的邻接关系，称为邻接矩阵。

下面针对带权无向图的邻接矩阵作出说明。

其中有一个类型为顺序表的顶点表向量VerticesList，用以存储顶点的信息，还有一个作为邻接矩阵使用的二维数组Edge，用以存储图中的边，其矩阵元素个数取决于顶点个数，与边数无关。

数据结构与算法课程设计报告课程设计题目：图的算法实现专业班级：信息与计算科学1002班目录摘要 (1)1、引言 (1)2、需求分析 (1)3、概要设计 (2)4、详细设计 (4)5、程序设计 (10)6、运行结果 (18)7、总结体会 (19)摘要(题目): 图的算法实现实验内容图的算法实现问题描述：（1）将图的信息建立文件；（2）从文件读入图的信息，建立邻接矩阵和邻接表；（3）实现Prim、Kruskal、Dijkstra和拓扑排序算法。

关键字:邻接矩阵、Dijkstra和拓扑排序算法1.引言本次数据结构课程设计共完成图的存储结构的建立、Prim、Kruskal、Dijkstra 和拓扑排序算法等问题。

通过本次课程设计，可以巩固和加深对数据结构的理解，通过上机和程序调试，加深对课本知识的理解和熟练实践操作。

（1）通过本课程的学习，能够熟练掌握数据结构中图的几种基本操作；（2）能针对给定题目，选择相应的数据结构，分析并设计算法，进而给出问题的正确求解过程并编写代码实现。

使用语言：CPrim算法思想：从连通网N={V,E}中的某一顶点v0出发，选择与它关联的具有最小权值的边(v0,v)，将其顶点加入到生成树的顶点集合V中。

以后每一步从一个顶点在V中，而另一个顶点不在V中的各条边中选择权值最小的边(u,v),把它的顶点加入到集合V中。

如此继续下去，直到网中的所有顶点都加入到生成树顶点集合V中为止。

拓扑排序算法思想：1、从有向图中选取一个没有前驱的顶点，并输出之；2、从有向图中删去此顶点以及所有以它为尾的弧；重复上述两步，直至图空，或者图不空但找不到无前驱的顶点为止。

没有前驱-- 入度为零，删除顶点及以它为尾的弧-- 弧头顶点的入度减1。

2.需求分析1、通过键盘输入建立一个新的有向带权图，建立相应的文件；2、对建立的有向带权图进行处理，要求具有如下功能：（1）用邻接矩阵和邻接表的存储结构输出该有向带权图，并生成相应的输出结果；（2）用Prim、Kruskal算法实现对图的最小生成树的求解，并输出相应的输出结果；（3）用Dijkstra算法实现对图中从某个源点到其余各顶点的最短路径的求解，并输出相应的输出结果；（4）实现该图的拓扑排序算法。

数据结构与算法课程设计报告题目两两相连的房间问题：一所奇怪的房子，这所房子里有n个房间，每个房间里有一些门通向别的房间，可是这些门十分奇怪，它们只能从房间a开向房间b，也就是说，一扇从a开向b的门是不能让一个人从b房间走到a房间的。

你能计算一下任意两个房间之间都互相相通吗？问题分析此程序需要完成如下要求：在这所房子里，从任意一个房间开始，按照开门的方向，均能够找到一个合适的路线，使得一个人能够不重复的到达其他的每一个房间，所以，需以每一个房间都为一次起始点来走向其他的房间，以此来判断这所房子里的任意两个房间之间是否互相相通。

实现本程序需要解决以下问题：1.如何表示每一个房间，即存储房间的信息，并且还要确定这所房子里的各个房间的位置。

2.各个房间之间的门，以及门是从哪个房间开向哪个房间的该如何表示和存储的。

3.从某一个房间开始，如何走到其他各个房间，即如何对房间进行遍历。

4.为了在遍历过程中，不重复的遍历每一个房间，该如何标记已被遍历过的房间，从而只访问未走过的房间。

5.最后通过什么的遍历方式才能判断各个房间之间是否互相相通。

数据结构的选择和概要设计通过对题目要求的理解，我们可以用图来表示这所房子，而房子中的各个房间就相当于图中的各个结点，由于房间的门是有方向的，一扇从a开向b的门是不能让一个人从b房间走到a 房间的，从而可知该图为有向图，那么门就相当于有向图中的弧，从一个门开向另一个门即代表有向图中弧的起始点和终止点。

对于图的存储，我采用邻接表的形式来存储，并将每一个房间进行编号，对于邻接表，则需要定义一个邻接表结点类型、邻接表表头结点类型，通过表头与结点的连接而将有向图中弧的信息存储起来。

那么人从任意一个房间走向另一个房间，即相当于有向图中从一个结点按照弧的信息访问其他的结点，可以采用深度优先搜索遍历。

如果从每一个结点以起始点开始一次遍历就都能访问到其他结点的话则说明有向图是连通图，即该房子里的各个房间能够互相相通。