太原理工大学数据结构实验三.doc

《太原理工大学数据结构实验三.doc》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、本科实验报告课程名称：数据结构（C语言版）实验项目：实验三图实验地点：软件楼110专业班级：计科1402学号：学生姓名：陈志棚指导教师：孟亮2015年12月29日一、[问题描述]1.采用邻接表存储结构，编写一个求无向图的连通分量个数的算法。二、[输入]图顶点的个数，和以各个顶点为弧尾的所有弧，并以-1结束输入。三、[输出]连通分量的个数。四、[存储结构]图采用邻接矩阵的方式存储。五、[算法的基本思想]用到深度优先搜索，先从任意一个顶点开始进行深度优先搜索，搜索完后，连通分量个数增1。然后再从没有遍历过的顶点找一个出来进行深度优先搜

2、索，搜索完后，连通分量个数增1。一直到所有的顶点都被遍历过。六、[源程序]#include#includeintn;structVNode//顶点{intposition;structVNode*next;};structArcNode//弧{intmark;structVNode*first;};voidDFS(structArcNode*v,structArcNode*w)//深度优先搜索{structVNode*L;w->mark=1;L=w->first;while(L!=NULL){

3、if((v+(L->position))->mark==0)//递归调用{DFS(v,(v+L->position));}L=L->next;}}intmain(){inti,j,k;intnum=0;structArcNode*p;structVNode*temp;structVNode*flag;printf("请输入顶点个数n：");scanf("%d",&n);while(n<1){printf("你输入的值不合理，请重新输入：");scanf("%d",&n);}p=(structArcNode*)malloc(

4、n*sizeof(structArcNode));/*说明：1.Vi表示第i个顶点，它在表中的位置为i-1，如V3在表中的位置为2;2.如果输入以V1为弧尾的所有弧(假设存在弧和)则输入：21-1(只需输入弧头的位置，并用-1表示结束)*/for(i=0;i

5、uctVNode*)malloc(sizeof(structVNode));temp->position=k;temp->next=NULL;p[i].first=temp;p[i].mark=0;flag=temp;scanf("%d",&k);while(k!=-1){temp=(structVNode*)malloc(sizeof(structVNode));temp->position=k;temp->next=NULL;flag->next=temp;flag=temp;scanf("%d",&k);}}}i=0;whi

6、le(p[i].mark==0){//计算连通分量的个数DFS(p,(p+i));num++;i=0;while(p[i].mark!=0&&i

7、作，能够熟练的进行图的建立、遍历。在编写程序时，有很多不明白的地方，在得到同学的鼎立相助后，基本解决了这些问题。一、[问题描述]1.试基于图的深度优先搜索策略编写一程序，判别以邻接表方式存储的有向图中是否存在有顶点Vi到Vj顶点的路径(i≠j)。二、[输入]输入图的顶点数，并按邻接表方式依次输入各顶点的关系以回车作为结束标志创建一个图，输入需要判别路径的顶点Vi和Vj三、[输出]输出Vi到Vj是否有路径四、[存储结构]图采用邻接表的方式存储。五、[算法的基本思想]首先按照邻接表方式建立一个图，当输入需要判断是否有路径的两个顶点Vi

8、和Vj时，通过深度优先搜索Vi到Vj之间是否有路径。六、[源程序]#include"stdio.h"#include"malloc.h"#include"conio.h"typedefstructArcNode{intadjvex;//该弧指向的顶