掌握图的结构特征,掌握图的建立及遍历运算的实现

1、洛阳理工学院实验报告系部计算机系班级B110505学号B11050516姓名李满意课程名称数据结构实验日期2013.05.01实验名称图的遍历成绩实验目的：掌握图的结构特征，掌握图的建立及遍历运算的实现。实验条件：电脑一台，VC+6.0软件。实验内容与算法思想：内容： 矩阵和邻接表实现图的深度优先遍历和广度优先遍历。算法思想：该程序中的深度优先搜索的基本过程是这样的：1，访问第一个出发点；2，依次以第一个出发点的未被访问的邻接点为出发点，深度优先搜索图，直至图中所有与第一个出发点有路径相通的顶点都被访问。若是非连通图，则图中一定还有顶点未被访问，需要从图中另选一个未被访问的顶点作为起始点，重复

2、上述深度优先搜索过程，直至图中所有顶点均被访问过为止；广度优先搜索的基本过程是：1；从图中某个顶点v出发，首先访问v；2，依次访问v的各个未被访问的邻接点。3，分别从这些邻接点出发，依次访问它们的各个未被访问的邻接点。访问时应为：如果第i个结点和第k个结点为当前端接点，且第i个结点和第k个结点之前被被访问，则第i个结点的所有未被访问的邻接点应在第k个结点的所有未被访问的邻接点之前访问。重复3，直到所有端接点均没有未被访问的邻接点为止。若此时还有顶点未被访问，则选一个未被访问的顶点作为起始点，重复上述过程，直至所有顶点均被访问过为止。运行结果：实验总结：经过这次实验对图的基本知识很熟悉了，通过对

3、深度优先遍历及广度优先遍历，对邻接矩阵及邻接表的使用也更加熟练了，所以以后还是要多加上机啊，复习以往的知识，巩固已学习的知识，还可以增强实际操作能力，提高实战能力。另外，在这次实验中感受到图这一章还是很有难度的，以后应该多加练习。学好数据结构这门课程。附：源程序：#include <stdio.h>#include <malloc.h>#define MAX_VERTEX_NUM 20#define INFINITY 32768#define True 1#define False 0#define Error -1#define OK 1typedef enumDG,

4、DN,UDG,UDNGraphKind;typedef char VertexData;typedef int AdjType;typedef int OtherInfo;typedef struct ArcNodeAdjType adj;OtherInfo info;ArcNode;typedef struct VertexData vertexMAX_VERTEX_NUM;ArcNode arcsMAX_VERTEX_NUMMAX_VERTEX_NUM;int vexnum;int arcnum;GraphKind kind;AdjMatrix;typedef struct ArcNode

5、2int adjvex;struct ArcNode2 *nextarc;OtherInfo info;ArcNode2;typedef struct VertexNodeVertexData data;ArcNode2 *firstarc;VertexNode;typedef structVertexNode vertexMAX_VERTEX_NUM;int vernum2,arcnum2;GraphKind kind2;AdjList;typedef struct Nodeint data;struct Node *next;QueueNode;typedef structQueueNod

6、e *front;QueueNode *rear;LinkQueue;int visitedMAX_VERTEX_NUM;VertexData aMAX_VERTEX_NUM;VertexData bMAX_VERTEX_NUM;int InitQueue(LinkQueue *Q)Q->front=(QueueNode *)malloc(sizeof(QueueNode);if(Q->front!=NULL)Q->front->next=NULL;Q->rear=Q->front;return True;elsereturn False;int Enter

7、Queue(LinkQueue *Q,int x)QueueNode *p;p=(QueueNode *)malloc(sizeof(QueueNode);if(p!=NULL)p->data=x;p->next=NULL;Q->rear->next=p;Q->rear=p;return True;elsereturn False;int DeleQueue(LinkQueue *Q,int *x)QueueNode *p;p=Q->front->next;if(p!=NULL)Q->front->next=p->next;*x=p-

8、>data;free(p);if(p=Q->rear)Q->rear=Q->front;return True;elsereturn False;int IsEmpty(LinkQueue *Q)if(Q->front=Q->rear)return True;elsereturn False;int LocateVertex(AdjMatrix *G,VertexData v)int j=Error;int k;for(k=0;k<G->vexnum;k+)if(G->vertexk=v)j=k;break;return j;int Cre

9、ateDN(AdjMatrix *G)VertexData v1,v2;int i,j,k,weight;printf("请输入图的顶点数及弧数:n");scanf("%d,%d",&G->vexnum,&G->arcnum);getchar();for(i=0;i<G->vexnum;i+)for(j=0;j<G->vexnum;j+)G->arcsij.adj=INFINITY;printf("请输入图的顶点:n");for(i=0;i<G->vexnum;i+

10、)scanf("%c",&G->vertexi);getchar();printf("请输入一条弧的两个顶点及权值:n");for(k=0;k<G->arcnum;k+)scanf("%c,%c,%d",&v1,&v2,&weight);getchar();i=LocateVertex(G,v1);j=LocateVertex(G,v2);G->arcsij.adj=weight;ak=v1;bk=v2;return OK;void DepthFirstSearch(AdjMat

11、rix *G,int v0)int vj;printf("%c ",G->vertexv0);visitedv0=True;for(vj=0;vj<G->vexnum;vj+)if(!visitedvj&&G->arcsv0vj.adj!=INFINITY)DepthFirstSearch(G,vj);void BreadthFirstSearch(AdjMatrix *G,int v0)int vi,vj;LinkQueue Q;InitQueue(&Q);visitedv0=True;EnterQueue(&Q,v

12、0);while(!IsEmpty(&Q)DeleQueue(&Q,&vi);printf("%c ",G->vertexvi);for(vj=0;vj<G->vexnum;vj+)if(!visitedvj)&&(G->arcsvivj.adj!=INFINITY)visitedvj=True;EnterQueue(&Q,vj);void TraverseGraph(AdjMatrix *G)int vi;for(vi=0;vi<G->vexnum;vi+)visitedvi=False;

13、printf("邻接矩阵法深度优先遍历序列：");for(vi=0;vi<G->vexnum;vi+)if(!visitedvi)DepthFirstSearch(G,vi);printf("n");for(vi=0;vi<G->vexnum;vi+)visitedvi=False;printf("邻接矩阵法广度优先遍历序列：");for(vi=0;vi<G->vexnum;vi+)if(!visitedvi)BreadthFirstSearch(G,vi);printf("n"

14、);int LocateVertex2(AdjList *g,VertexData v)int k,j=Error;for(k=0;k<g->vernum2;k+)if(g->vertexk.data=v)j=k;break;return(j);int CreateDN2(AdjMatrix *G,AdjList *g)int i,j,k;ArcNode2 *p;ArcNode2 *r;g->vernum2=G->vexnum;g->arcnum2=G->arcnum;for(i=0;i<G->vexnum;i+)g->vertexi

15、.data=G->vertexi;g->vertexi.firstarc=NULL;for(k=0;k<g->arcnum2;k+)i=LocateVertex2(g,ak);j=LocateVertex2(g,bk);if(g->vertexi.firstarc=NULL)p=(ArcNode2 *)malloc(sizeof(ArcNode2);if(p=NULL)return False;p->adjvex=j;g->vertexi.firstarc=p;p->nextarc=NULL;elser=g->vertexi.firstar

16、c;while(r->nextarc!=NULL)r=r->nextarc;p=(ArcNode2 *)malloc(sizeof(ArcNode2);if(p=NULL)return False;p->adjvex=j;r->nextarc=p;p->nextarc=NULL;return True;void DepthFirstSearch2(AdjList *g,int v0)ArcNode2 *p;printf("%c ",g->vertexv0.data);visitedv0=True;p=g->vertexv0.firs

17、tarc;while(p!=NULL)if(!visitedp->adjvex)DepthFirstSearch2(g,p->adjvex);p=p->nextarc;void BreadthFirstSearch2(AdjList *g,int v0)int vi;ArcNode2 *p;LinkQueue Q;InitQueue(&Q);visitedv0=True;EnterQueue(&Q,v0);while(!IsEmpty(&Q)DeleQueue(&Q,&vi);printf("%c ",g->v

18、ertexvi.data);p=g->vertexvi.firstarc;while(p!=NULL)if(!visitedp->adjvex)visitedp->adjvex=True;EnterQueue(&Q,p->adjvex);p=p->nextarc;void TraverseGraph2(AdjList *g)int vi;for(vi=0;vi<g->vernum2;vi+)visitedvi=False;printf("邻接表法深度优先遍历序列：");for(vi=0;vi<g->vernum2;vi+)if(!visitedvi)DepthFirstSearch2(g,vi); printf("n");for(vi=0;v