8-1实验八报告(图的相关操作)

课程名称：《数据结构》班级：软件二班学号：123745姓名：胡文凯实验名称：图的相关操作

实验目的：1、进一步掌握图的基本概念及其存储结构。

2、进一步掌握图的深度优先遍历和广度优先遍历的方法和算法的实

现。

实验原理（预习内容）：

1、图的概念、基本相关术语；

2、图的矩阵和邻接表存储结构的描述方法；3、图的遍历和其他各种操作实现。实验器材（软件）：Computer，WindowsOS，VC++

实验过程记录：

1、图的基本操作

（1）请选择用邻接矩阵存储方式或邻接表的存储方式创建图（图的种类可自行选择）。可以考虑建立一个无向有权图

（2）求出所创建图中某一顶点的度（如果创建的是有向图，分别求出出度和入度）。

（3）实现所创建图的深度优先和广度优先遍历。（4）判断任一图是否连通。实验源码：#include\"stdio.h\"#include\"stdlib.h\"typedefcharelemtype;

typedefstructarc{

intadjvertex;//存放结点后的相邻点的数据intweight;

structarc*nextarc;}Arc,*Arctype;typedefstruct{

elemtypevertex;Arc*firstarc;}vertextype;

//存放结点的空间

typedefstruct{

vertextypevertices[30];//申请空间存放图

intvexnum,arcnum;}ALGraph;Arctype

p,q;

//节点数，和边数

Creat_G(ALGraph*G){

inti,j,k,w;charv1,v2;

printf(\"请输入结点数：\");scanf(\"%d\getchar();

for(i=1;i<=G->vexnum;i++){

scanf(\"%c\G->vertices[i].firstarc=NULL;}

printf(\"请输入边数：\");scanf(\"%d\getchar();

for(i=1;i<=G->arcnum;i++){

scanf(\"%c%c%d\getchar();

for(j=1;j<=G->vexnum;j++)//查找结点在表中的位置if(v1==G->vertices[j].vertex)break;for(k=1;k<=G->vexnum;k++)

if(v2==G->vertices[k].vertex)break;//同上p=(Arctype)malloc(sizeof(Arc));//申请一个邻接点空间，存放它的邻接

点的数据

p->adjvertex=k;p->weight=w;

p->nextarc=G->vertices[j].firstarc;G->vertices[j].firstarc=p;

q=(Arctype)malloc(sizeof(Arc));q->adjvertex=j;q->weight=w;

q->nextarc=G->vertices[k].firstarc;G->vertices[k].firstarc=q;}}

//计算图顶点的度

voidDegree_G(ALGraphG,charch){

inti,count=0;

for(i=1;i<=G.vexnum;i++)

if(ch==G.vertices[i].vertex)break;p=G.vertices[i].firstarc;while(p){

count++;

p=p->nextarc;}

printf(\"%c顶点的度为%d：\\n\system(\"pause\");}

//深度遍历图，从顶点n开始voidDFS_G(ALGraphG,intn){

intw;Arctyper;//r不能为全局变量，因为每访问一个邻接点的时候，要存下他

的信息，以便递归调用完后好返回起始调用的位置

staticintvisited[20]={0};

visited[n]=1;//标志起点n已经被访问printf(\"%5c\r=G.vertices[n].firstarc;//访问下一个将被访问的结点while(r){

w=r->adjvertex;//记录下一个结点的位置if(visited[w]==0)//判断该结点是否被访问过DFS_G(G,w);r=r->nextarc;}}

//深度遍历非递归算法，栈结构intSt[20];inttop=0;

voidZDFS_G(ALGraphG,charch){

intvisited[20]={0};inti;

for(i=1;i<=G.vexnum;i++)

if(ch==G.vertices[i].vertex)break;St[++top]=i;printf(\"%5c\visited[i]=1;while(top){

p=G.vertices[i].firstarc;while(p){

if(visited[p->adjvertex]==0){

visited[p->adjvertex]=1;St[++top]=p->adjvertex;

printf(\"%5c\p=G.vertices[p->adjvertex].firstarc;}else

p=p->nextarc;

}

i=St[--top];

}

}

printf(\"\\n\");

system(\"pause\");

//广度遍历图

voidBFS_G(ALGraphG,charch){

intSqueue[20];//队列intfront=0,rear=0;inti,w;

intV[20]={0};//标记数组for(i=1;i<=G.vexnum;i++)

if(ch==G.vertices[i].vertex)break;Squeue[rear++]=i;//将该元素的下标存入队列V[i]=1;//标记为已访问printf(\"%5c\

p=G.vertices[i].firstarc;while(front!=rear)//当队列为空时，也就遍历结束了{

w=Squeue[front++];

p=G.vertices[w].firstarc;while(p)//此while循环是找当前结点的所有邻接点，

并将其下标存入数组中

{

if(V[p->adjvertex]==0){

V[p->adjvertex]=1;

printf(\"%5c\Squeue[rear++]=p->adjvertex;}

p=p->nextarc;}}

printf(\"\\n\");

system(\"pause\");}

//判断图的连通性intVis[10];

voidDFSTraverse(ALGraphG){

inti,count=0;

for(i=1;i<=G.vexnum;i++)

Vis[i]=0;

for(i=1;i<=G.vexnum;i++)

if(!Vis[i]){

DFS_G(G,i);//如果能只进行一次遍历，就遍历完了图，那么就说明

图是连通的

count++;//遍历次数的计数}

if(count==1)printf(\"\\n该图是连通图!\");elseprintf(\"\\n该图非连通!\");system(\"pause\");}

//显示图的邻接表结构voidPrint_G(ALGraphG){

inti;

for(i=1;i<=G.vexnum;i++){

printf(\"%c\p=G.vertices[i].firstarc;

}

}

system(\"pause\");

while(p){

printf(\"-->│%d<%d>│\p=p->nextarc;}

printf(\"\\n\");

printf(\"─────────────────\\n\");

main(){

charch;intn;

ALGraphG;

printf(\"开始创建图！\\n\");Creat_G(&G);while(1){

system(\"cls\");

printf(\"───────────────────\\n\");printf(\"1、计算顶点的度2、显示邻接表\\n\");printf(\"3、深度递归遍历图4、深度非递归遍历\\n\");printf(\"5、广度遍历图6、判断图的连通性\\n\");printf(\"0、退出\\n\");printf(\"───────────────────\\n\");printf(\"请选择操作：\");switch(n=getchar()){

case'1':getchar();

printf(\"请输入一个顶点：\");ch=getchar();Degree_G(G,ch);break;

case'2':

printf(\"显示图的邻接表结构：\\n\");Print_G(G);break;

case'3':printf(\"从第几个顶点开始：\");

scanf(\"%d\DFS_G(G,n);printf(\"\\n\");

system(\"pause\");

}

结果截图：

break;

case'4':printf(\"请输入起始顶点：\");

getchar();

scanf(\"%c\ZDFS_G(G,ch);break;

case'5':getchar();

printf(\"请输入一个顶点：\");ch=getchar();BFS_G(G,ch);break;

case'6':DFSTraverse(G);

break;

case'0':exit(0);

break;

default:printf(\"选择错误，请重新输入！\\n\");

break;

}}

实验结果分析与小结：

对于此章图的学习，感觉其图的构造比较复杂，理解上有点困难，需仔细认真的去想，其次是图的遍历算法，我个人感觉需先弄懂其算法思路，多在纸上画画，这是必要的，凭空想象是不可能理会算法的含义的，按照算法步骤一步一步的去做，去想。就容易理解了。