数据结构课程设计图的邻接矩阵

1、数据结构课程设计报告设计题目：图的邻接矩阵存储结构院 系 计算机学院 年 级x 级 学 生xxxx学 号xxxxxxxxxx指导教师 xxxxxxxxx起止时间 10-6/10-102013年10月10日目 录 1 需求分析42 概要设计42.1 ADT描述42.2程序模块结构52.3各功能模块63详细设计73.1类的定义73.2 初始化83.3 图的构建操作83.4 输出操作93.5 get操作93.6 插入操作103.7 删除操作103.8 求顶点的度操作113.9 深度遍历作.113.10 判断连通操作123.11 主函数134 调试分析164.1调试问题164.2算法时间复杂度165用

2、户手册165.1主界面165.2创建图175.3插入节点175.4深度优先遍历175.5求各顶点的度185.6输出图185.7判断是否连通195.8求边的权值195.9插入边195.10删除边20结论20参考文献.20摘 要 随着计算机的普及，涉及计算机相关的科目也越来越普遍，其中数据结构是计算机专业重要的专业基础课程与核心课程之一，为适应我国计算机科学技术的发展和应用，学好数据结构非常必要，然而要掌握数据结构的知识非常难，所以对“数据结构”的课程设计比不可少。本说明书是对“无向图的邻接矩阵存储结构”课程设计的说明。首先是对需求分析的简要阐述，说明系统要完成的任务和相应的分析，并给出测试数据。

3、其次是概要设计，说明所有抽象数据类型的定义、主程序的流程以及各程序模块之间的层次关系，以及ADT描述。然后是详细设计，描述实现概要设计中定义的基本功操作和所有数据类型，以及函数的功能及代码实现。再次是对系统的调试分析说明，以及遇到的问题和解决问题的方法。然后是用户使用说明书的阐述，然后是测试的数据和结果的分析，最后是对本次课程设计的结论。关键词：网络化；计算机；对策；图；储存。1需求分析随着计算机的普及,信息的存储逐渐和我们的日常生活变得密切起来，而数据的存储方式也多种多样，比如树、链表、数组、图等等。为了充分体现图的矩阵储存结构的优势与功能，要求本系统应达到以下要求：1. 图是无向带权图2.

4、 能从键盘上输入各条边和边上的权值；3. 构造图的邻接矩阵和顶点集。4. 输出图的各顶点和邻接矩阵5. 插入一条边6. 删除一条边7. 求出各顶点的度8. 判断该图是否是连通图，若是，返回1；否则返回0.9. 使用深度遍历算法，输出遍历序列。2 概要设计2.1 ADT描述 ADT Glist VR=图的顶点和边VR=<v,w> | v,wV, <v,w>表示顶点v和w间的边；基本操作：初始化空图；输入建立图；深度优先遍历图；确定图中的顶点数目；确定图中边的数目；在图中插入一个顶点；在图中插入一条边；删除图中一个顶点删除图中的一条边；求顶点的度；求最小生成树； ADT G

5、raph;2.2程序模块结构图2.1：模块结构2.2.1结构体定义本系统未采用结构体方法，类的定义如下：定义顶点: nodecount，edgecount 边：已经分别存放顶点和边的两个数组： aMaxNode和 bMaxNodeMaxNode;其余成员函数均以public形式声明。在邻接矩阵表示的图中，顶点信息用一维数组表示a。在简单情况下可省略，仅以下标值代表顶点序号。若需要，顶点信息更加丰富。边（或弧）信息用二维数组表示b ，这也是邻接矩阵。包含边的权值。在类中数据成员有4个，重要的是邻接矩阵Edge 、总边数edgecount和顶点数nodecount。class Graph1 pri

6、vate: int nodecount;/节点 int edgecount;/边 int aMaxNode;/顶点信息组 /set<int> a; int bMaxNodeMaxNode;/权值信息组public: Graph1(int);/构造函数 int getNodeCount();/当前的节点数 int getEdgeCount();/当前的边数 void insertNode(int);/插入一个节点 void isertEdge(int ,int ,int);/插入一条边 void deleteEdge(int,int);/删除一条边 bool isliantong()

7、;/判断是否连通 int getWeight(int,int);/获得某条边的权值 int Depth(int );/深度遍历准备，用于建立顶点访问数组和记录所访问顶点个数void Depth(int v,int visited,int &n);/深度遍历void outDu(Graph1 G);/输出节点个数void PrintOut(Graph1 G) ;/输出图void CreatG(int n,int e);/建立图;2.3各功能模块以下将以注释形式为每个函数的功能进行声明：构造函数：Graph1(int) 用于初始化图get函数：int getNodeCount();得到当前

8、的节点数get函数：int getWeight(int,int);获得某条边的权值get函数：int getEdgeCount();得到当前的边数插入函数：void insertNode(int);插入一个节点插入函数：void isertEdge(int ,int ,int);插入一条边删除函数：void deleteEdge(int,int);删除一条边判断函数：bool isliantong();判断是否连通遍历函数1：int Depth(int );/深度遍历准备，用于建立顶点访问数组和记录所访问顶点个数遍历函数2：void Depth(int v,int visited,int &a

9、mp;n);/深度遍历求度函数：void outDu(Graph1 G);输出节点个数输出函数：void PrintOut(Graph1 G) ;输出图构建函数：void CreatG(int n,int e);建立图3详细设计3.1类的定义class Graph1 private: int nodecount;/节点 int edgecount;/边 int aMaxNode;/顶点信息组 /set<int> a; int bMaxNodeMaxNode;/权值信息组public: Graph1(int);/构造函数 int getNodeCount();/当前的节点数 int

10、getEdgeCount();/当前的边数 void insertNode(int);/插入一个节点 void isertEdge(int ,int ,int);/插入一条边 void deleteEdge(int,int);/删除一条边 void prim(int);/生成最小树 bool isliantong();/判断是否连通 int getWeight(int,int);/获得某条边的权值 int Depth(int );/深度遍历准备，用于建立顶点访问数组和记录所访问顶点个数void Depth(int v,int visited,int &n);/深度遍历void outD

11、u(Graph1 G);/输出节点个数void PrintOut(Graph1 G) ;/输出图void CreatG(int n,int e);/建立图;3.2 初始化初始化邻接矩阵以及有关参数，通过for循环将数组的值都初始化为0，使之成为一个空图。Graph1:Graph1(int s=MaxNode)/构造函数 for(int i=0;i<=s-1;i+) for(int j=0;j<=s-1;j+) bij=0; nodecount=0; for(int k=0;k<=s-1;k+) ak=-1; 3.3 图的构建操作在主函数中要求输入需要构建的图的顶点数和边数，调

12、用构建函数，分别用两个for语句来构建图（即输入顶点的值和边的权值），此处要求输入有一定的顺序，不能随意输入。void Graph1:CreatG(int n,int e) int i,vi,vj,w; edgecount=e; nodecount=n; cout<<endl<<" 输入顶点的信息（暂设为整型）：" ; for ( i=0; i<nodecount; i+ ) cout<<"n "<<i+1<<": " cin>>ai; for ( i=0;

13、 i<edgecount; i+ ) /输入两个顶点编号和边权值 cout<<endl<<" 输入边的信息（vi,vj,w）："<<endl; cin>>vi>>vj>>w; bvi-1vj-1=w; bvj-1vi-1=w; 3.4 输出操作本函数通过传过来的对象G得到相关数组，通过for循环来分别输出顶点数组和边的权值数组（邻接矩阵）。void Graph1:PrintOut(Graph1 G) int i; cout<<"n 输出顶点的信息："<<

14、endl; for ( i=0; i<G.getNodeCount(); i+ ) cout<<G.ai<<" " cout<<endl<<"n 输出邻接矩阵：" ; for ( i=0; i<G.getNodeCount(); i+ ) cout<<endl<<i+1<<": " for ( int j=0; j<G.getNodeCount() ;j+ ) cout<<G.bij<<" "

15、; cout<<endl; 3.5 get操作用于得到图的顶点数、边数、权值int Graph1:getNodeCount()/当前的节点数 return nodecount; int Graph1:getEdgeCount()/当前的边数 return edgecount; int Graph1:getWeight(int x,int y)/获得某条边的权值 return bx-1y-1;3.6 插入操作插入顶点：通过将传来的值（顶点值）赋到一个当前顶点数下一个的数组元素中实现插入功能，此时顶点树加1。插入边：原理与插入顶点相同，通过传过来的两个顶点信息与权值进行相应赋值，不过此

16、时应该注意表示同一条边的两个数组都该赋值。void Graph1:insertNode(int it)/插入一个节点 anodecount+=it; cout<<"当前节点数为："<<nodecount<<endl; void Graph1:isertEdge(int x,int y,int w)/插入一条边 bx-1y-1=w; by-1x-1=w; cout<<"该边插入成功! "<<endl; edgecount+; 3.7 删除操作将相应的数组值赋为0从而达到删除目的。void Grap

17、h1:deleteEdge(int x ,int y)/删除一条边 bx-1y-1=0; by-1x-1=0; cout<<"边("<<x<<","<<y<<")已经成功删除!" edgecount-; 3.8 求顶点的度操作通过两个for循环来查找各顶点，判断其是否有边（权值），有边的话又有几条边，每找到一条边则度数加一，记录到存放顶点的度数的数组M中，搜索完成后输出各顶点的度。void Graph1:outDu(Graph1 G)/输出各点的度 int mMax=0,k,

18、i; for(k=0;k<G.getNodeCount();k+) for(i=0;i<G.getNodeCount();i+) if(G.bki!=0) mk+; cout<<"各点的度："<<endl; for(i=0;i<G.getNodeCount();i+) cout<<"顶点"<<i<<"的度："<<mi<<endl; 3.9 深度遍历操作图的深度优先遍历DFS算法是沿着某初始顶点出发的一条路径，尽可能深入地前进，即每次在

19、访问完当前顶点后，首先访问当前顶点的一个未被访问过的邻接顶点，然后去访问这个邻接点的一个未被访问过的邻接点，这是一个递归算法。其中第一个遍历函数Depth(int node)其主要作用是构建访问数组intv，以及调用核心遍历函数Depth(int v,int visited,int &n)，其中的n是用来记录访问的顶点数目，用于判断图的连通性。int Graph1:Depth(int node) int n=0;int vMaxNode; for(int i=0;i<=nodecount-1;i+) vi=0; Depth(node,v,n); return n;/n记录访问节点

20、数，用于判断是否连通 void Graph1:Depth(int v,int visited,int &n) cout<<" "<<v+1<<" " ;/访问顶点v visitedv=1; /标记顶点v已访问n+;/n记录访问节点数 for (int col=0; col<nodecount; col+) if (bvcol=0|bvcol=Max) continue; /找v一个邻接点col if (!visitedcol) Depth(col, visited,n); /调用深度递归遍历 3.10 判

21、断连通操作通过调用遍历函数得到所能访问的顶点数n，然后判断n与当前顶点数是否相等来确认是否连通。bool Graph1:isliantong()/判断是否连通 int n=0; n=Depth(0); cout<<"该图的总节点数为:"<<nodecount<<"!"<<endl; cout<<"其中一个连通分量连通的节点数为:"<<n<<"!"<<endl; if(n=nodecount)/访问到的节点数与顶点数是否相

22、等 return 1; else return 0; 3.11 主函数主函数的主要功能是引导构建新图的邻接矩阵存储结构，并且制作菜单、调用各个相应的功能函数。int main()system("cls");system("color 1f");system("mode con: cols=78 lines=35");cout<<" n"cout<<" 必做题：无向图的邻接矩阵存储结构 n"cout<<" 姓名：xxxxn"cout<&

23、lt;" 学号：xxxxxxxxxn"cout<<" n"cout<<">>>>>>n"Graph1 G(10);int x,y,w;int node; cout<<"你好,请依次输入图的节点数n和边数e:"<<endl;int n,e;cin>>n>>e;G.CreatG(n,e);cout<<"恭喜你!你的图已经建立成功!"<<endl;system("

24、;pause");while(true)cout<<endl;cout<<"n"cout<<" 欢迎进入图的邻接矩阵存储结构演示系统 n"cout<<" - n"cout<<" 请选择您要的操作： n"cout<<" 1.输出图 2.判断图是否连通 n"cout<<" 3.深度优先搜索 4.求各顶点的度 n"cout<<" 5.插入新节点 6.删除边 n&quo

25、t;cout<<" 7.求边的权值 8.插入新的边 n"cout<<" 0.退出系统 n"cout<<"n"int choice;cout<<endl;cout<<"请你做出选择!"<<endl;cin>>choice;switch(choice)case 1: G.PrintOut(G);break;case 2:if(G.isliantong()cout<<"该图是连通的!"<<end

26、l;elsecout<<"该图不是连通的!"<<endl;break;case 3:int node;cout<<"请输入你选择的起始节点!"<<endl;cin>>node;cout<<"深度优先搜索结果为:"<<endl;G.Depth(node-1);cout<<endl;break;case 4: G.outDu(G);break;case 5:cout<<"请输入你要插入的新节点!"<<

27、endl;cin>>node;G.insertNode(node);cout<<endl;break;case 6:cout<<"请输入你要删除的边!"<<endl;cin>>x>>y;G.deleteEdge(x,y);cout<<endl;break;case 7:cout<<"请输入你要查询的边的两个顶点"<<endl;cin>>x>>y;cout<<G.getWeight(x,y)<<endl;break;case 8:cout<<"请输入你要添加的"<<e<<"条边以及边上对应的权值!"<<endl;cin>>x>>y>>w;G.