实验三、图的遍历操作.doc

实验三、图的遍历操作一、 目的掌握有向图和无向图的概念；掌握邻接矩阵和邻接链表建立图的存储结构；掌握DFS及BFS对图的遍历操作；了解图结构在人工智能、工程等领域的广泛应用。二、 要求采用邻接矩阵和邻接链表作为图的存储结构，完成有向图和无向图的DFS和BFS操作。三、 DFS和BFS 的基本思想深度优先搜索法DFS的基本思想：从图G中某个顶点Vo出发，首先访问Vo，然后选择一个与Vo相邻且没被访问过的顶点Vi访问，再从Vi出发选择一个与Vi相邻且没被访问过的顶点Vj访问，依次继续。如果当前被访问过的顶点的所有邻接顶点都已被访问，则回退到已被访问的顶点序列中最后一个拥有未被访问的相邻顶点的顶点W，从W出发按同样方法向前遍历。直到图中所有的顶点都被访问。广度优先算法BFS的基本思想：从图G中某个顶点Vo出发，首先访问Vo，然后访问与Vo相邻的所有未被访问过的顶点V1，V2，Vt；再依次访问与V1，V2，Vt相邻的起且未被访问过的的所有顶点。如此继续，直到访问完图中的所有顶点。四、 实验内容1、 示例程序1分析：图的DFS遍历可通过递归调用或用栈来实现。其思想是：只要当前结点未访问过，就访问该结点，沿着其一条分支深入下去，每深入一个未访问过的结点，就访问这个结点，然后从这个结点继续进行DFS遍历。在这一过程中，若深入时遇到一个已访问过的结点，则查找是否有与这个结点相邻的下一个未访问过的结点。若有则继续深人，否则将退回到这个结点的前一个结点，再找下一个相邻的本访问过的结点，如此进行下去，直到所有的结点都被访问过。BFS遍历可利用队列来帮助实现，也可以用栈。实现方法与二叉树的层次遍历类似。V6V4V5V7V2V3V1V0Vo图G的示例示例程序2：分析：以邻接表为存储结构的图的DFS和BFS算法的实现思想与以邻接矩阵为存储结构的实现是一样的。只是由于图的存储形式不同。而具体到取第一个邻接点和下一个邻接点的语句表示上有所差别而已。V6V4V5V7V2V3V1V0Vo图G的示例3附录：#define MaxVertexNum 10 /设最大顶点数为10#include #include typedef char VertexType;typedef int EdgeType;typedef structchar vexs10;int edges1010;int n,e;MGraph;#define FALSE 0#define TRUE 1#define Error printfint visited10;void CreateMGraph(MGraph *G);void DFSTraverseM(MGraph *G);void BFSTraverseM(MGraph *G);void DFSM(MGraph *G,int i);void BFSM(MGraph *G,int i);#define QueueSize 30 /*假定预分配的队列空间最多为30*/typedef int DataType; /*队列中的元素类型为字符型*/typedef structint front; /*队头指针，队非空时指向队头元素*/int rear; /*队尾指针，队非空时指向队尾元素的下一位置*/int count; /*计数器，记录队中元素总数*/DataType dataQueueSize;CirQueue;void InitQueue(CirQueue *Q) /*初始队列*/Q-front=Q-rear=0;Q-count=0;int QueueEmpty(CirQueue *Q) /*判队空*/return Q-count=0;int QueueFull(CirQueue *Q) /*判队满*/return Q-count=QueueSize;void EnQueue(CirQueue *Q,DataType x) /*入队*/if (QueueFull(Q)Error(Queue overflow); /*队满上溢*/else Q-count+; /*队列元素个数加1*/Q-dataQ-rear=x; /*新元素插入队列*/Q-rear=(Q-rear+1)%QueueSize; /*循环队列的尾指针加1*/DataType DeQueue(CirQueue *Q) /*出队*/DataType temp;if (QueueEmpty(Q)Error(Queue underflow); /*队空下溢*/else temp=Q-dataQ-front;Q-count-; /*队列元素个数减1*/Q-front=(Q-front+1)%QueueSize; /*循环队列的头指针加1*/return temp;main()MGraph *G; /*定义一个以邻接矩阵为存储类型的图G*/char ch1,ch2;G= (MGraph *)malloc(sizeof(MGraph);printf(create graph(adjoining matrix ):n); /*创建图G的存储*/CreateMGraph(G);printf(create graph success 。n);ch1=y;while(ch1=y | ch1=Y)printf(select:n);printf(nb-Degree First search );printf(nc-breadth First search );printf(nd-exitn);scanf(n%c,&ch2);switch (ch2)case B:case b:DFSTraverseM(G);break;case C:case c:BFSTraverseM(G);break;case D:case d:ch1=n;break;default:ch1=n;void CreateMGraph(MGraph *G)/*建立有向图G的邻接矩阵存储*/int i,j,k,w;char ch;printf(input vertex number and edge number(input format:vn,en):n);/*输入顶点数和边数,输入格式：顶点数，边数*/scanf(%d,%d,&(G-n),&(G-e);printf(input vertex(input format:serial number):n);/*输入顶点信息，建立顶点表，输入格式为:顶点号)/*/for (i=0;in;i+)scanf(n%c,&(G-vexsi);printf(input edge(format:i,j):n);/*输入e条边，输入格式为:i,j*/for (k=0;ke;k+)scanf(n%d,%d,&i,&j); /*输入e条边，建立邻接矩阵*/G-edgesij=1;/*CreateMGraph*/void DFSTraverseM(MGraph *G) /*深度优先遍历以邻接矩阵存储的图G*/ int i; printf(Degree First searchn); for(i=0;in;i+)visitedi=FALSE; for(i=0;in;i+)if(!visitedi)DFSM(G,i); /*DFSTraverse*/void DFSM(MGraph *G,int i)/*以Vi为出发点，对邻接矩阵存储的图G进行DFS搜索*/ int j; printf( edge:v%cn,G-vexsi); visitedi=TRUE; for(j=0;jn;j+)if(G-edgesij=1&!visitedj) DFSM(G,j); /*DFSM*/void BFSTraverseM(MGraph *G)/*广度优先遍历邻接矩阵存储的图G*/int i;printf(breadth First searchn);for (i=0;in;i+)visitedi=FALSE; /*标志向量初始化*/for (i=0;in;i+)if (!visitedi) BFSM(G,i);/*Vi未访问过，以Vi为原点开始BFS搜索*/*BFSTraverseM*/void BFSM(MGraph *G,int k)/*以Vi为出发点，对邻接矩阵存储的图G进行BFS搜索*/int i,j;CirQueue Q;InitQueue(&Q);printf(vertex:v%cn,G-vexsk);visitedk=TRUE;EnQueue(&Q,k); /*原点Vk入