DS4-图的操作
- 格式：doc
- 大小：57.50 KB
- 文档页数：7
《数据结构与算法分析》课程实验报告【实验目的】1. 理解图形结构的逻辑和存储特点。
2. 掌握图形结构遍历递归算法。
【实验内容】1. 用邻接矩阵或者邻接表存储一个图形结构。
2. 采用深度或者广度优先搜索算法，遍历一个图，并输出遍历结果。
【实验方式】个人实验。
【实验设备与环境】PC机，Windows XP操作系统，VC++6.0开发环境。
【数据结构及函数定义】（1）主函数main（）实现初始化操作，完成对子函数的调用（2）子函数int LocateVex(MGraph &G,int v) //确定v在G中的位置 void CreateUDG(MGraph &G) //采用邻接矩阵的表示法，构造无向图Gvoid VisiteFunc(MGraph &G,int v) //调用函数输出第v个顶点int FirstAdjVex(MGraph &G,int v) //返回v的第一个邻接顶点int NextAdjVex(MGraph &G,int v,int w) //返回v的（相对于w的）下一个邻接顶点void DFS(MGraph &G,int v) //从第v个顶点出发递归地深度优先遍历图Gvoid DFSTraverse(MGraph &G,int v) //对图G进行深度优先遍历void InitQueue(LinkQueue &Q) //构造一个空队列Qvoid EnQueue(LinkQueue &Q,int e) //插入e为Q的新的队尾元素int QueueEmpty(LinkQueue &Q) //若队列为空，则返回1，否则返回0 int DeQueue(LinkQueue &Q,int &e) //若队列不空，则删除Q的队头元素，用e返回其值，并返回1void BFSTraverse(MGraph &G,int v) //按广度优先非递归遍历图G 【测试数据与实验结果】测试数据：图的顶点数和边数分别为5和6顶点向量为1,2,3,4,5相邻的顶点分别为：1和2,1和4,3和4,3和2，3和5,2和5图的形状为：1 234 5实验结果：对图进行深度优先搜索的结果为：1 2 3 4 5 对图进行广度优先搜索的结果为：1 2 4 3 5【源程序清单】#include <stdio.h>#include <stdlib.h>#define MAX_VERTEX_NUM 20#define TRUE 1#define FLASE 0int w;int visited[MAX_VERTEX_NUM];typedef struct{int vexs[MAX_VERTEX_NUM];int arcs[MAX_VERTEX_NUM][MAX_VERTEX_NUM];int vexnum,arcnum;}MGraph;int LocateVex(MGraph &G,int v){int i;for(i=0;i<G.vexnum;i++){if(v==G.vexs[i])return i;}return 0;}void CreateUDG(MGraph &G){int i,j,k;char v1,v2;printf("请输入图的顶点数和边数(逗号隔开)：");scanf("%d,%d",&G.vexnum,&G.arcnum);printf("请输入顶点向量：");for(i=0;i<G.vexnum;i++)scanf("%d",&G.vexs[i]);G.vexs[i]='\0';for(i=0;i<G.vexnum;i++)for(j=0;j<G.vexnum;j++)G.arcs[i][j]=0;printf("请输入%d条边相邻的两个顶点(逗号隔开):",G.arcnum);for(k=0;k<G.arcnum;k++){scanf("%d,%d",&v1,&v2);i=LocateVex(G,v1);j=LocateVex(G,v2);G.arcs[i][j]=1;G.arcs[j][i]=G.arcs[i][j];}}void VisiteFunc(MGraph &G,int v){printf("%2d",G.vexs[v]);}int FirstAdjVex(MGraph &G,int v){int i;for(i=1;i<G.vexnum;i++)if(G.arcs[v][i])return i;return 0;}int NextAdjVex(MGraph &G,int v,int w){int j;for(j=w+1;j<G.vexnum;j++)if(G.arcs[v][j])return j;return 0;}void DFS(MGraph &G,int v){visited[v]=TRUE;VisiteFunc(G,v);for(w=FirstAdjVex(G,v);w;w=NextAdjVex(G,v,w)) if(!visited[w])DFS(G,w);}void DFSTraverse(MGraph &G,int v){for(v=0;v<G.vexnum;v++)visited[v]=FLASE;for(v=0;v<G.vexnum;v++)if(!visited[v])DFS(G,v);}typedef struct QNode{int data;struct QNode *next;}QNode,*QueuePtr;typedef struct{QueuePtr front;QueuePtr rear;}LinkQueue;void InitQueue(LinkQueue &Q){Q.front=Q.rear=(QueuePtr)malloc(sizeof(QNode));if(!Q.front)exit(-2);Q.front->next=NULL;}void EnQueue(LinkQueue &Q,int e){QueuePtr p;p=(QueuePtr)malloc(sizeof(QNode));if(!p)exit(-2);p->data=e;p->next=NULL;Q.rear->next=p;Q.rear=p;}int QueueEmpty(LinkQueue &Q){if(Q.front==Q.rear)return 1;elsereturn 0;}int DeQueue(LinkQueue &Q,int &e){QueuePtr p;if(Q.front==Q.rear)return 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;}void BFSTraverse(MGraph &G,int v){LinkQueue Q;int u;for(v=0;v<G.vexnum;v++)visited[v]=FLASE;InitQueue(Q);for(v=0;v<G.vexnum;v++)if(!visited[v]){visited[v]=TRUE;VisiteFunc(G,v);EnQueue(Q,v);while(!QueueEmpty(Q)){DeQueue(Q,u);for(w=FirstAdjVex(G,u);w;w=NextAdjVex(G,u,w))if(!visited[w]){visited[w]=TRUE;VisiteFunc(G,w);EnQueue(Q,w);}}}}void main(){int i,j;MGraph G;CreateUDG(G);printf("\n");printf("输出的邻接矩阵为：");printf("\n");for(i=0;i<G.vexnum;++i){for(j=0;j<G.vexnum;++j)printf("%2d",G.arcs[i][j]);printf("\n");}printf("对图进行深度优先搜索的结果为：");DFSTraverse(G,i);printf("\n");printf("对图进行广度优先搜索的结果为：");BFSTraverse(G,i);printf("\n");}。
