图的建立与输出

1、数据结构课程设计目录一、需求分析1二、概要设计1三、算法设计的思想 2邻接矩阵表示法2四、算法的流程图 3五、算法设计分析 45.1无向网邻接矩阵的建立算法 45.2无向图邻接矩阵的建立算法 4六、源代码5七、调试测试11八、总结 14一、需求分析问题重述：建立图的存储结构（图的类型可以是有向图、无向图），能够输入图的顶点和边的信息，并存储到相应存储结构中，而后输出图的邻接矩阵。应用环境设定给定某类图的顶点和边的相关信息，要求输出该图的邻接矩阵。用户界面命令行界面，用户选择所要建立的图的类型，输入相关顶点和边的信息，然后输出该图的邻接矩阵。输入方式首先输入所要建立的图形类型的代码，然后输入顶点

2、vexnum和边的数量arcnum，再输入顶点信息，边的2个端点v1和v2，如果建立的是网则还要输入权值w。输出方式输出的是一个邻接矩阵，采用for循环嵌套，输出该图的邻接矩阵。数据存储方式全部在内存存放，不使用硬盘上的文件或其他数据源，程序执行过程中和结束后不保存数据。程序功能1. 输入图的类型；2. 输入相应的图的顶点和边的相关信息； 3. 得到图的邻接矩阵。 二、概要设计基本操作：CreateGraph(MGraph &G) 初始条件：图G未创建。 操作结果：创建一个图G。 CreateUDG(MGraph &G); 初始条件：无向图G未创建。 操作结果：创建一个无向图并求出其邻接矩阵。

3、 CreateDG(MGraph &G); 初始条件：有向图G未创建。 操作结果：创建一个有向图并求出其邻接矩阵。 CreateDN(MGraph &G); 初始条件：有向网G未创建。 操作结果：创建一个有向网并求出其邻接矩阵。CreateUDN(MGraph &G); 初始条件：有无向网G未创建。 操作结果：创建一个无向网并求出其邻接矩阵。D Display(MGraph G)。 初始条件：图G已创建。 操作结果：输出图G的邻接矩阵。三、算法设计的思想邻接矩阵表示法:设G=(V,E)是一个图，其中V=V1,V2,V3,Vn。G的邻接矩阵是一个具有下述性质的n阶方阵：若(Vi,Vj)E或者E，

4、则Ai,j=1反之为0；图5-2中有向图G1和无向图G2的邻接矩阵分别为 M1和 M2:M1= 0 1 0 1 1 0 1 0 1 0 0 1 0 0 0 0 M2= 0 1 1 1 1 0 1 0 1 1 0 1 1 0 1 0 注意无向图的邻接是一个对称矩阵，例如 M2。用邻接矩阵表示法来表示一个具有n个顶点的图时，除了用邻接矩阵中的n*n个元素存储顶点间相邻关系外，往往还需要另设一个向量存储n个顶点的信息。因此其类型定义如下：VertexType vertexMAX_VERTEX_NUM; / 顶点向量 AdjMatrix arcs; / 邻接矩阵 int vexnum, arcnum;

5、 / 图的当前顶点数和弧(边)数 GraphKind kind; / 图的种类标志 若图中每个顶点只含一个编号i(1ivnum)，则只需一个二维数组表示图的邻接矩阵。此时存储结构可简单说明如下： type adjmatrix=array1.vnum,1.vnumof adj;利用邻接矩阵很容易判定任意两个顶点之间是否有边（或弧）相联，并容易求得各个顶点的度。对于无向图，顶点Vi的度是邻接矩阵中第i行元素之和，即nD(Vi)Ai,j j=1 对于有向图，顶点Vi的出度OD(Vi)为邻接矩阵第i行元素之和，顶点Vi的入度ID(Vi)为第i列元素之和。即 nnOD(Vi)Ai,j， ID(Vi)Aj

6、,i） j=1j=1用邻接矩阵也可以表示带权图，只要令 Wij, 若(Vi,Vj)或者E其中Wij为或(Vi,Vj)上的权值。Ai,j0 , 否则。四、算法的流程图开始开始输入vexnum，arcnumIncInfo选择图的类型构造图ii+1输入顶点ivexnumY输出该图的邻接矩阵jj+1N结束初始化邻接矩阵ivexnumYjvexnumNYii+1N主程序流程图karcnumkk+1设置邻接矩阵YN结束图的构造流程图五、算法设计分析1、无向图邻接矩阵的建立算法如下：procedure build-graph; 建立无向图的邻接矩阵beginfor i:=1 to n do read(G.v

7、ertexi)； 读入n个顶点的信息for i:=1 to n dofor j:=1 to e doG.arcsij =0；将邻接矩阵的每个元素初始化成0 for k:=1 to e do e为边的数目 read(i,j,w) 读入边和权G.arcsij:=wG.arcsijG.arcsii置对称弧 end；该算法的执行时间是O(n+n2+e),其中消耗在邻接矩阵初始化操作上的时间是O(n2),而en2，所以上述算法的时间复杂度是O(n2)。 2、有向图邻接矩阵的建立算法如下：procedure build-graph; 建立有向图的邻接矩阵beginfor i:=1 to n do read

8、(G.vertexi)； 读入n个顶点的信息for i:=1 to n dofor j:=1 to e doG.arcsij =0；将邻接矩阵的每个元素初始化成0 for k:=1 to e do e为边的数目 read(i,j,w) 读入边和权G.arcsij:=wG.arcsijG.arcsii置对称弧 end；该算法的执行时间是O(n+n2+e),其中消耗在邻接矩阵初始化操作上的时间是O(n2),而en2，所以上述算法的时间复杂度是O(n2)。六、源代码#include #include #include #include #include#define ERROR 0#define O

9、K 1#define MAX_VERTEX_NUM 20 /定义最大值#define INFINITY 32768 /定义极大值#define MAX_INFO 20typedef int VrType; /定义新的类型typedef int InfoType;typedef char VertexType;typedef enum DG,DN,UDG,UDNGraphKind;/有向图,有向网,无向图,无向网typedef struct ArcCell VrType adj; / 顶点关系类型。对无权图，用1或0表示相邻否；对带权图，则为权值类型。 InfoType *info; / 该弧相

10、关信息的指针 ArcCell, AdjMatrixMAX_VERTEX_NUMMAX_VERTEX_NUM;typedef struct VertexType vertexMAX_VERTEX_NUM; / 顶点向量 AdjMatrix arcs; / 邻接矩阵 int vexnum, arcnum; / 图的当前顶点数和弧(边)数 GraphKind kind; / 图的种类标志 MGraph;void CreateDG(MGraph &G) / 采用数组(邻接矩阵)表示法,构造有向图 int i,j,k; /i，j，k为计数器 VertexType v1,v2; /用于放置输入的弧的两个顶

11、点 printf(请输入有向图G的顶点数(不超过20个):n); scanf(%d,&G.vexnum); printf(请输入有向图G的边数:n); scanf(%d,&G.arcnum); printf(_请输入%d个顶点的值:n,G.vexnum); for(i=0;iG.vexnum|G.vertexi1) printf(-_- Sorry!您输入的顶点值错误,请重新输入第%d个顶点的值:n,i+1); scanf(%d,&G.vertexi); for(i=0;iG.vexnum;+i) / 初始化邻接矩阵 for(j=0;jG.vexnum;+j) G.arcsij.adj=0;

12、G.=NULL; for(k=0;kG.vexnum)|(v2G.vexnum)printf(+) 对不起!您输入的边信息错误,请重新输入第%d条边的始点和终点:n,k+1); scanf(%d %d,&v1,&v2); i=v1-1; j=v2-1; G.arcsij.adj=1; /CreateDG void CreateDN(MGraph &G) / 采用数组(邻接矩阵)表示法,构造有向网 int i,j,k,w; /i，j，k为计数器，w用于放置权值 int v1,v2; /用于放置输入的弧的两个顶点 printf(请输入有向网G的顶点数:n); scanf(%d

13、,&G.vexnum); printf(请输入有向网G的边数:n); scanf(%d,&G.arcnum); printf(_请输入%d个顶点的值:n,G.vexnum); for(i=0;iG.vexnum|G.vertexi1) printf(-_- Sorry!您输入的顶点值错误,请重新输入第%d个顶点的值:n,i+1); scanf(%d,&G.vertexi); for(i=0;iG.vexnum;+i) / 初始化邻接矩阵 for(j=0;jG.vexnum;+j) G.arcsij.adj=0; G.=NULL; /adj,info for(k=0;kG.

14、vexnum)|(v2G.vexnum)printf(+) 对不起!您输入的边信息错误,请重新输入第%d条边的始点和终点:n,k+1); scanf(%d %d %d,&v1,&v2,&w); i=v1-1; j=v2-1; G.arcsij.adj=w; /CreateDNvoid CreateUDG(MGraph &G) / 采用数组(邻接矩阵)表示法,构造无向图 int i,j,k; /i，j，k为计数器 int v1,v2; /用于放置输入的弧的两个顶点 printf(请输入无向图G的顶点数:n); scanf(%d,&G.vexnum); printf(请输入无向图G的边数:n);

15、scanf(%d,&G.arcnum); printf(_请输入%d个顶点的值:n,G.vexnum); for(i=0;iG.vexnum|G.vertexi1) printf(-_- Sorry!您输入的顶点值错误,请重新输入第%d个顶点的值:n,i+1); scanf(%d,&G.vertexi); for(i=0;iG.vexnum;+i) / 初始化邻接矩阵 for(j=0;jG.vexnum;+j) G.arcsij.adj=0; G.=NULL; for(k=0;kG.vexnum)|(v2G.vexnum)printf(+) 对不起!您输入的边信息错误,请

16、重新输入第%d条边的始点和终点:n,k+1); scanf(%d %d,&v1,&v2); i=v1-1; j=v2-1; G.arcsij.adj=G.arcsji.adj=1; / 置的对称弧 /CreateUDG void CreateUDN(MGraph &G) / 采用数组(邻接矩阵)表示法,构造无向网 int i,j,k,w; /i，j，k为计数器，w用于放置权值 int v1,v2; /用于放置输入的弧的两个顶点 printf(请输入无向网G的顶点数:n); scanf(%d,&G.vexnum); printf(请输入无向网G的边数:n); scanf(%d,&G.arcnum

17、); printf(_请输入%d个顶点的值:n,G.vexnum); for(i=0;iG.vexnum|G.vertexi1) printf(-_- Sorry!您输入的顶点值错误,请重新输入第%d个顶点的值:n,i+1); scanf(%d,&G.vertexi); for(i=0;iG.vexnum;+i) / 初始化邻接矩阵 for(j=0;jG.vexnum;+j) G.arcsij.adj=0; G.=NULL; /adj,info for(k=0;kG.vexnum)|(v2G.vexnum)printf(+) 对不起!您输入的边信息错误,请重新输入第%d条

18、边的始点和终点:n,k+1); scanf(%d %d %d,&v1,&v2,&w); i=v1-1; j=v2-1; G.arcsij.adj=G.arcsji.adj=w; / 置的对称弧 /CreateUDNint CreateGraph(MGraph &G) /构造图printf(请输入要构造的图的类型(1.有向图,2.有向网,3.无向图,4.无向网):n);scanf (%d,&G.kind);switch(G.kind) case 1: CreateDG(G);break;case 2: CreateDN(G);break;case 3: CreateUDG(G);break;ca

19、se 4: CreateUDN(G);break;default: return ERROR;/CreateGraphvoid Display(MGraph G)/输出图的邻接矩阵int i,j; printf(该图的邻接矩阵为：n);for(i=0;iG.vexnum;+i) for(j=0;jG.vexnum;j+) printf(%5d,G.arcsij.adj); printf(n); void main() MGraph G; CreateGraph(G); Display(G);七、调试测试1、程序开始运行时输出：请输入要构造的图的类型(1.有向图,2.有向网,3.无向图,4.无向网): 为了测试输入为：3显示：请输入无向图G的顶点数:输入：5显示：请输入无向图G的边数:输入：6显示：_请输入5个顶点的值:输入：1 2 3 4 5显示：(o)请输入第1条边的2个端点(以空格作为间隔):输入：1 2显示：(o)请输入第2条边的2个端点(以空格作为间隔):输入：1 4显示：(o)请输入第3条边的2个端点(以空格作为间隔):输入：2 6显示：(+) 对不起!您输入的边信息错误,请重新输入第3条边的2个端点(以空格作为间