《TDPL.CPP图的深度优先搜索和广度优先搜索》由会员分享，可在线阅读，更多相关《TDPL.CPP图的深度优先搜索和广度优先搜索（7页珍藏版）》请在金锄头文库上搜索。
1、0以邻接表形式存储的图深度优先搜索和广度优先搜索程序及运行结果如下，请完成： 1、不修改程序，只修改边输入的顺序，使得深度优先搜索和广度优先搜索的结果与 136 页和 138 页的结果一样。 2、不修改边输入的顺序，修改程序（链表从表尾插入） ，使得深度优先搜索和广度优 先搜索的结果与 136 页和 138 页的结果一样。 3、以所给的程序为样板，编写一个以邻接矩阵形式存储的图深度优先搜索和广度优先 搜索程序。 4、编写一个菜单程序，能实现如下功能： 1. 建立一个以邻接表形式存储的图 2. 建立一个以邻接矩阵形式存储的图 3. 以邻接表形式存储的图深度优先搜索 4. 以邻接表形式存储的图广度
2、优先搜索 5. 以邻接矩阵形式存储的图深度优先搜索 6. 以邻接矩阵形式存储的图广度优先搜索 7. 退出/TDPL.CPP 图(以邻接表形式存储)的深度优先搜索和广度优先搜索 2014.4.16#include #include #define Max_vertex 20 /*最大顶点数*/ typedef int elemtype; /*元素类型*/ typedef struct QNode /* 队列元素类型*/ elemtype data;struct QNode *next; QNode,*QNodeptr;typedef struct QueueNode QNodeptr front
3、;QNodeptr rear; LinkQueue; /*队列类型*/typedef enumFALSE,TRUEBoolean; Boolean visitedMax_vertex; /*标志数组，下标与顶点序号对应，访问过的顶点置为 1，未访问过的结点为 0*/ typedef char vertextypeMax_vertex; /顶点类型typedef struct ArcNode int adjvex; /*adjvex 通常存放的是邻接点的序号*/struct ArcNode *nextarc; ArcNode; /*边结点类型*/typedef struct VNode vert
4、extype data;ArcNode *firstarc; VNode,AdjListMax_vertex;/*链表顶点类型*/1typedef struct AdjList adjlist; /adjlist 是一个有 20 个 VNode 类型数据的数组int vexnum,arcnum; / vexnum 是顶点数变量，arcnum 是边数变量 Graph;/*定义图的类型*/int locate(Graph G,vertextype p)/*确定顶点的邻接点位置*/ int i;for(i=0;iG.vexnumG.arcnum; /*输入顶点数和边数*/coutG.adjlisti
5、.data; /*输入各顶点，如 v1 v2 v3 v4 v5 v6 v7 v8*/G.adjlisti.firstarc=NULL; /*各头结点赋初值空指针*/coutmn; /*输入各边，如输入 v1 v2 代表 v1 与 v2 之间有一条边*/i=locate(G,m); j=locate(G,n); /*寻找顶点 m 和 n 在顶点向量表中的下标*/s=new ArcNode; /*申请一个边结点存储空间*/if(!s) coutadjvex=j; /*插入一个边结点*/s-nextarc=G.adjlisti.firstarc;G.adjlisti.firstarc=s; /*在各
6、链表的前面插入*/s=new ArcNode;if(!s) coutadjvex=i;/*插入另一个对称的边结点，如 v1 到 v2 是一条边，则 v2 到 v1 也是一条边*/s-nextarc=G.adjlistj.firstarc;G.adjlistj.firstarc=s; void DFS(Graph G,int i) /*深度优先搜索函数*/ ArcNode *p;coutadjvex)DFS(G,p-adjvex); /*递归调用*/p=p-nextarc; /*指向下一邻接点*/ void DFSTraverse(Graph G)/*对图的深度优先搜索*/ int v;for(
7、v=0;vnext=NULL; int emptyQueue(LinkQueue Q) /*判断队列是否为空*/ return Q.front=Q.rear; void enQueue(LinkQueue p=new QNode;p-data=e; p-next=NULL;Q.rear-next=p;Q.rear=p; 3void deQueue(LinkQueue if(Q.front=Q.rear) coutnext;e=p-data;Q.front-next=p-next;if(Q.rear=p) Q.rear=Q.front;delete p; int firstadjvex(Grap
8、h G,int u) /*第一个邻接点的位置*/ return G.adjlistu.firstarc-adjvex; int nextadjvex(Graph G,int u) /*找下一个邻接点的位置*/ int c;ArcNode *p;p=G.adjlistu.firstarc; /p 指向第一个边结点c=G.adjlistu.firstarc-adjvex; /c 是第一个邻接点的序号while(visitedc /*指向下一邻接点*/if(p) c=p-adjvex; /邻接点序号赋给 C 变量if(p) return c; /*找到了返回序号*/else return -1; /
9、*没找到返回-1*/void BFSTraverse(Graph G)/*对图的广度优先搜索*/ elemtype u=0,v,w;LinkQueue L; /初始化队列for(v=0;v=0;w=nextadjvex(G,u)if(!visitedw) visitedw=TRUE;4cout“visit:“G.adjlistw.dataendl;enQueue(L,w); void main() /* 主函数*/ Graph create; /create 为图变量名createGraphic(create); /建立图cout“n DFST visit:n“;DFSTraverse(cre
10、ate); /调用图的深度优先遍历函数cout“n BFST visit:n“;BFSTraverse(create); /调用图的广度优先遍历函数输入：please input the vertexs number and Edges number: 8 9 please input the vertexs information. V1 v2 v3 v4 v5 v6 v7 v8 please input the nodes(double): v1 v2 v2 v4 v4 v8 v8 v5 v5 v2 v1 v3 v3 v6 v6 v7 v7 v3 输出： DFST visit:深度优先遍历
11、visitvertex: v1 visitvertex: v3/2 visitvertex: v7/4 visitvertex: v6/8 visitvertex: v2/5 visitvertex: v5/3 visitvertex: v8/6 visitvertex: v4/75BFST visit:广度优先遍历visit: v1 visit: v3 visit: v2 visit: v7 visit: v6 visit: v5 visit: v4 visit: v8上图的邻接表60 v1 1 v22 v33 v44 v55 v66 v77 v8 2 1 4 3 0 6 5 0 7 1 1 7 6 2 2 5 4 3
