图的设计作业

1、 1 / 10 课程设计题目和内容 一.图的基本操作的实现 1)自选存储结构,输入含n个顶点（用字符表示顶点）和e条边的图G； (2)求每个顶点的度,输出结果； (3)指定任意顶点x为初始顶点,对图G作DFS遍历,输出DFS顶点序列(提示: 使用一个栈实现DFS)； (4)指定任意顶点x为初始顶点,对图G作BFS遍历,输出BFS顶点序列(提示: 使用一个队列实现BFS)； (5)输入顶点x,查找图G: 若存在含x的顶点,则删除该结点及与之相关连的边,并作DFS遍历(执行操作3)；否则输出信息“无x”； (6)判断图G是否是连通图，输出信息“YES”/“NO”； (7)如果选用的存储结构是邻接矩

2、阵,则用邻接矩阵的信息生成图G的邻接表,即复制图G,然再执行操作 (2)；反之亦然。 二.程序中所采用的数据结构及存储结构的说明1邻接矩阵： 适用于图中边或弧的数目比较多的情况，压缩存储方式结构。邻接矩阵是表示顶点之间相邻关系的矩阵。若图有n个顶点，则邻接矩阵是一个n*n阶的方阵，结构唯一。邻接矩阵A的元素规定为： 用邻接矩阵存储网时只需要将矩阵中的1换为相应的权值，将0用一个不可能存在的权值代替即可。当图用邻接矩阵表示后图的某些操作的实现是很方便的，如求某一顶点v i的第一邻接点，只需在第i行找到第1个非零元即可。若求某一顶点v 2 / 10 i的度，对于无向图来说，只须统计第i行的非零元个

3、数或第i列的非零元个数（无向图的邻接矩阵是对称的）；当图中顶点数确定，插入一条边（v i,v j）只须将矩阵中第i行j列和第j行i列的元素分别改为1或相应的权值；插入一条弧i,v j>只须将矩阵中第i行j列的元素改为1或相应的权值即可。 2邻接表： 一种链式存储结构 在邻接表中对图的每个顶点建立一个单链表，第i个单链表中包含第i个顶点的所有邻接点，每一个单链表包含两种结点，头结点和表结点。 在图的邻接表中，可以比较方便地查找一个顶点的边（出边）或邻接点（出边邻接点），这只要首先从表头向量中取出对应的表头指针，然后从表头指针出发进行查找即可。邻接表则是以一数组(结构体数组)的元素作为头指针

4、,后面链接和它相邻的结点. 3邻接矩阵表示法与邻接表表示法的比较：1）邻接矩阵是唯一的，邻接表不唯一； 2）存储稀疏图用邻接表，存储稠密图用邻接矩阵；3）求无向图顶点的度都容易，求有向图顶点的度邻接矩阵较方便； 4）判断是否是图中的边，邻接矩阵容易，邻接表最坏时间为O(n)； 5）求边数e，邻接矩阵耗时为O(n2)，与e无关，邻接表的耗时 三.算法的设计思想 1邻接矩阵存储图的基本思路： 图用邻接矩阵表示后图的某些操作的实现是很方便的，如求某一顶点v 3 / 10 i的第一邻接点，只需在第i行找到第1个非零元即可。若求某一顶点v i的度，对于无向图来说，只须统计第i行的非零元个数或第i列的非零

5、元个数（无向图的邻接矩阵是对称的）；对于有向图来说，第i行的非零元个数为该顶点的出度，第i列的非零元个数为该顶点的入度，两者相加为该顶点的度。当图中顶点数确定，插入一条边（v i,v j）只须将矩阵中第i行j列和第j行i列的元素分别改为1或相应的权值；插入一条弧i,v j>只须将矩阵中第i行j列的元素改为1或相应的权值即可。 2邻接表存储图的基本思路： 若无向图中有n个顶点e条边，则邻接表需要n个头结点和2e个表结点。在边稀疏的情况下，采用邻接表比采用邻接矩阵节省存储空间。 在无向图的邻接表中，顶点v i的度恰好为第i个链表中的表结点数。 若有向图中有n个顶点e条弧，则邻接表需要n个头结

6、点和e个表结点。在有向图的邻接表中，第i个链表中的结点数为顶点v i的出度。为求顶点v i的入度，需要遍历整个邻接表，在所有链表中其邻接点域的值为i的结点个数为顶点v i的入度。在邻接表中，容易找到任意一顶点的第一邻接点和下一个邻接点，但要判断任意两个顶点v i和v j之间是否有边相连，则须搜索第i或j个链表，因此，不及邻接矩阵方便。3深度优先遍历图的基本思路是： 4 / 10 （1）访问图中的指定起始点v 0； （2）从v 0出发，访问一个与v 0邻接的顶点w 1后，再从w 1出发，访问与w 1邻接的且未访问的顶点w 2。然后从w 2出发，重复上述过程，直到找不到未被访问的顶点为止。 （3）

7、回退到尚有未被访问过的邻接点的顶点，从该顶点出发，重复上面的步骤，直到所有被访问过的顶点的邻接点都已访问为止。 4xx优先遍历是图的实现思路是： （1）访问图中的指定起始点v 0； （2）从v 0出发，依次访问v 0的未被访问的邻接点w 1,w 2,w 3,w 5 / 10 n。然后依次访问w 1,w 2,w 3,w n的未被访问的邻接点。 （3）重复上面的第二步，直到所有顶点的邻接点都已访问为止。 四.程序清单 #include<stdio.h> #include<stdlib.h> #define NULL 0 #define maxsize 10 typedef

8、struct nodeint data; struct node *next; dnode; typedef struct int vex; dnode *first; Node; typedef structNode arrymaxsize; int num; graph; 6 / 10 int visitmaxsize; graph creat()/创建邻接表graph a; dnode *p; int i,x,y,e; printf(输入顶点数和边数（以空格分割）： );scanf(%d%d,&a.num,&e); for(i=1;i<=a.num;i+)a.arr

9、yi.first=NULL; a.arryi.vex=i;for(i=1;i<=e;i+)printf(输入第%d个顶点的边: ,i); scanf(%d%d,&x,&y); p=(dnode*)malloc(sizeof(dnode); p->data=y; p->next=a.arryx.first; a.arryx.first=p; p=(dnode*)malloc(sizeof(dnode); p->data=x; p->next=a.arryy.first ; a.arryy.first=p;return a;void copy(grap

10、h b,int vmaxsize)/邻接矩阵与邻接表转换int i,j; dnode *p; for(i=1;i<=b.num;i+) for(j=1;j<=b.num;j+) 7 / 10 vij=0; for(i=1;i<=b.num;i+)p=(dnode*)malloc(sizeof(dnode); p=b.arryi.first; while(p)vip->data=1; p=p->next ; for(i=1;i<=b.num;i+)for(j=1;j<=b.num;j+) printf(%d,vij); printf(n); void v

11、exdu(graph a)/求度数dnode *p; int i,count; for(i=1;i<=a.num;i+)p=a.arryi.first; count=0; while(p)count+; p=p->next ;printf(%d的度数: %dn,a.arryi.vex,count); void clr()int i; for(i=1;i<=maxsize;i+) visiti=0;void dfs(graph a,int v)dnode *p; if(a.arryv.vex!=0) printf(%d,a.arryv.vex); visitv=1; 8 / 1

12、0 p=a.arryv.first ; while(p)if(!visitp->data) dfs(a,p->data ); p=p->next; void find1(graph a)int v; clr(); printf(输入开始搜索节点： ); scanf(%d,&v); dfs(a,v); printf(n);void find2(graph a)int x,i; dnode *p,*q; clr(); printf(输入要查找删除的点： scanf(%d,&x); for(i=1;i<=a.num;i+) if(a.arryi.vex=x)b

13、reak; if(i>a.num)printf(没找到！n); return; ); elseprintf(找到！n); 9 / 10 q=p=a.arryi.first ; a.arryi.vex=0; if(p->data=x)p=p->next; else while(p)if(p->data=x)q->next=p->next; break;q=p; p=p->next; dfs(a,x); printf(n);void find3(graph a)int i; clr(); dfs(a,1); for(i=1;i<a.num;i+) if(v