数据机构实验六 图的邻接表存储及遍历.doc

实验六 图的邻接表存储及遍历一、实验学时 2学时二、背景知识1图的邻接表存储结构 在图的邻接表中，图中每个顶点都建立一个单链表，第i个单链表中的结点数为顶点i的出度。(逆邻接表中，第i个单链表中的结点数为顶点i的入度) 邻接表的数据结构描述为： struct node int vertex; struct node *nextnode;typedef struct node *graph;struct node headvertexnum; 2.图的遍历深度优先遍历（DFS）法：算法步骤：1）初始化： （1）置所有顶点“未访问”标志； （2）打印起始顶点； （3）置起始顶点“已访问”标志； （4）起始顶点进栈。2）当栈非空时重复做： （1）取栈顶点； （2）如栈顶顶点存在被访问过的邻接顶点，则选择一个顶点做： 打印该顶点； 置顶点为“已访问”标志； 该顶点进栈；否则，当前栈顶顶点退栈。3）结束。 广度优先遍历（BFS）法：算法步骤：1) 初始化： （1）置所有顶点“未访问”标志； （2）打印起始顶点； （3）置起始顶点“已访问”标志； （4）起始顶点入队。2）当队列非空时重复做： （1）取队首顶点； （2）对与队首顶点邻接的所有未被访问的顶点依次做： 打印该顶点； 置顶点为“已访问”标志； 该顶点入队；否则，当前队首顶点出队。3) 结束。三、目的要求 1掌握图的基本存储方法；2掌握有关图的操作算法并用高级语言实现；3熟练掌握图的两种搜索路径的遍历方法。四、实验内容1 编写程序实现下图的邻接表表示及其基础上的深度和广度优先遍历。五、程序实例图的邻接表表示法的C语言描述：#include #include struct node /* 图形顶点结构定义 */ int vertex; /* 顶点 */ struct node *nextnode; /* 指下一顶点的指针 */;typedef struct node *graph; /* 图形的结构重定义 */struct node head6; /* 图形顶点结构数组 */*-建立图形-*/void creategraph(int *node,int num) graph newnode; /* 新顶点指针 */ graph ptr; int from; /* 边线的起点 */ int to; /* 边线的终点 */ int i; for ( i = 0; i vertex = to; /* 建立顶点内容 */ newnode-nextnode = NULL; /* 设定指针初值 */ ptr = &(headfrom); /* 顶点位置 */ while ( ptr-nextnode != NULL ) /* 遍历至链表尾 */ ptr = ptr-nextnode; /* 下一个顶点 */ ptr-nextnode = newnode; /* 插入结尾 */ /*-主程序: 建立图形后,将邻接链表输出-*/void main() graph ptr; int node122 = 1, 2, 2, 1, /* 边线数组 */ 1, 3, 3, 1, 2, 3, 3, 2, 2, 4, 4, 2, 3, 5, 5, 3, 4, 5, 5, 4 ; int i; for ( i = 1; i = 5; i+ ) headi.vertex = i; /* 设定顶点值 */ headi.nextnode = NULL; /* 清除图形指针 */ creategraph(*node,12); /* 建立图形 */ printf(图形的邻接链表内容:n); for ( i = 1; i ,headi.vertex);/* 顶点值 */ ptr = headi.nextnode; /* 顶点位置 */ while ( ptr != NULL ) /* 遍历至链表尾 */ printf( %d ,ptr-vertex); /* 输出顶点内容 */ ptr = ptr-nextnode; /* 下一个顶点 */ printf(n); /* 换行 */ 深度和广度优先遍历#include#include#include#define MAX_VERTEX_MUN 20int visited20;typedef struct ArcNode int adjvex;struct ArcNode *nextarc;char *info;ArcNode;typedef struct VNodechar data;ArcNode *firstarc;VNode,AdjList20;typedef structAdjList vertices;int vexnum,arcnum;ALGragh;typedef struct QNodeint data;struct QNode *next;QNode,*QueuePtr;typedef structQueuePtr front;QueuePtr rear;LinkQueue;int InitQueue(LinkQueue &Q)Q.front=Q.rear=(QueuePtr)malloc(sizeof(QNode);if(!Q.front)exit(0);Q.front-next=NULL;return 1;int EnQueue(LinkQueue &Q,int e)QueuePtr p;p=(QueuePtr)malloc(sizeof(QNode);if(!p)exit(0);p-next=NULL;p-data=e;Q.rear-next=p;Q.rear=p;return 1;int DeQueue(LinkQueue &Q,int e)QueuePtr p;if(Q.front=Q.rear)exit(0);p=Q.front-next;e=p-data;Q.front-next=p-next;if(Q.rear=p)Q.rear=Q.front;free(p);return 1;int EmptyQueue(LinkQueue Q)if(Q.front=Q.rear)return 1;return 0;int LocateVex(ALGragh G,char v) int i;for(i=0;iadjvex;elsereturn -1;int NextAdjVex(ALGragh G,char v,char w)int i,j;ArcNode *p,*q;i=LocateVex(G,v);j=LocateVex(G,w);if(i=-1|j=-1|i=j)return -1;p=G.verticesi.firstarc;while(p-nextarc&p-adjvex!=j)p=p-nextarc;if(p-nextarc)q=p-nextarc;return q-adjvex;else return -1;int Visit(char v)printf(%c,v);return 1;/构造无向图int CreateDG(ALGragh &G)int v,e,i,j,t;ArcNode *p,*q;char tail,head;printf(input the number of the vertices:);scanf(%d,&v);if(v0)return 0;G.vexnum=v;printf(input the number of the arcs:);scanf(%d,&e);if(e0)return 0;G.arcnum=e;printf(build the Dg G:n);for(t=0;tG.vexnum;t+) fflush(stdin);printf(input the vertice %d s information,t+1);scanf(%c,&G.verticest.data);G.verticest.firstarc=NULL;for(t=0;tadjvex=j;p-info=NULL;p-nextarc=NULL;if(!G.verticesi.firstarc)G.verticesi.firstarc=p;else/for(q=G.verticesi.firstarc;q-nextarc;q=q-nextarc);q-nextarc=p;return 1;int BFSTraverse(ALGragh G,int(*Visit)(char v)LinkQueue Q;int v,w,u;for(v=0;vG.vexnum;v+)visitedv=0;InitQueue(Q);for(v=0;v=0;w=NextAdjVex(G, G.verticesu.data,G.verticesw.data)if(!visitedw)visitedw=1;Visit(G.verticesw.data);EnQueue(Q,w);return 1;int DFS(ALGragh G,int v)int w;visitedv=1;printf(%c,G.verticesv.data);w=FirstAdjVex(G, G.verticesv.data);for(;w=0;w=NextAdjVex(G, G.verticesv.data, G.verticesw.data)if(!visitedw)DFS(G,w);return 1;int DFSTraverse(ALGragh G)int v;for(v=0;vG.vexnum;v+)visitedv=0;for(v=0;vG.vexnum;v+)if(!visitedv)DF