数据结构专题--图的路径

1、7.22判断是否存在从u到v的路径基本思想：从u出发深度或广度搜索，找到v就有，找不到就没有intvisitedMAXSIZE;intexist_path_DFS(ALGraphG,inti,intj)(if(i=j)return1;else(visitedi=1;for(p=G.verticesi.firstarc;p;p=p->nextarc)(k=p->adjvex;if(!visitedk&&exit_path_DFS(G,k,j)return1;7.23intexist_path_BFS(ALGraphG,inti,intj)/三件事情，定访问数组，初始化

2、队列，起点进队intvisitedMAXSIZE;InitQueue(Q);EnQueue(Q,i);while(!QueueEmpty(Q)DeQueue(Q,u);/出队并访问visitedu=1;for(p=G.verticesu.firstarc;p;p=p->nextarc)k=p->adjvex;if(k=j)return1;if(!visitedk)EnQueue(Q,k);7.27判断u到v是否存在长度k的简单路径intvisitedMAXSIZE;intexist_path_len(ALGraphG,inti,intj,intk)if(i=j&&k

3、=0)return1;elseif(k>0)visitedi=1;for(p=G.verticesi.firstarc;p;p=p->nextarc)(l=p->adjvex;if(!visitedl)if(exit_path_len(G,l,j,k-1)return1;visitedi=0;/如果该点的邻接点中没找到，将该点退出/以便在别的路径中访问return0;7.28求u到v所有简单路径intpathMAXSIZE,visitedMAXSIZE;intFind_All_Path(ALGraphG,intu,intv,intk)(pathk=u;visitedu=1;i

4、f(u=v)(printf("Foundonepath!n");for(i=0;pathi;i+)printf("%d",pathi);elsefor(p=G.vertices.u.firstarc;p;p=p->nextarc)(l=p->adjvex;if(!visitedl)Find_All_Path(G,l,v,k+1);visitedi=0;pathk=0;7.29求i至Uj的不含回路的，长度为k的路径条数intGetPathNum_Len(ALGraphG,inti,intj,intlen)(if(i=j&&len

5、=0)return1;elseif(len>0)(sum=0;/表示通过本结点的路径数visitedi=1;for(p=G.verticesi.firstarc;p;p=p->nextarc)(l=p->adjvex;if(!visitedl)sum+=GetPathNum_Len(G,l,j,len-1);visitedi=0;returnsum;7.30求有向图中所有简单回路intvisitedMAXSIZE;intpathMAXSIZE;intcyclesMAXSIZEMAXSIZE;intthiscycleMAXSIZE;intcyount=0;/以发现的回路个数vo

6、idGetAllCycle(ALGraphG)(for(v=0;v<G.vexnum;v+)visitedv=0;for(v=0;v<G.vexnum;v+)if(!visitedi)DFS(G,v,0);voidDFS(ALGraphG,intv,intk)(visitedv=1;pathk=v;for(p=G.verticesv.firstarc;p;p=p->next)(w=p->adjvex;if(!visitedw)DFS(G,w,k+1);else/出现已经访问过的结点，发现回路(for(i=0;pathi!=w;i+);/找回路起点for(j=0;path

7、i+j;i+)thiscyclej=pathi+j;if(!exist_cycle()cyclescycount+=thiscycle;for(i=0;i<G.vexnum;i+)thiscyclei=0;pathk=0;visitedk=0;/注意只有当前路经结点上的visited为真。因此一旦发现当前结点visited为真/即发现了一条回路intexsit_cycle()(inttempMAXSIZE;for(i=0;i<cycount;i+)tempm=cyclesik+m;for()7.36每个顶点增加一个MPL域存放由他出发的最长路径的长度voidFill_MPL(ALG

8、raph&G)(FindIndegree(G,indegree);MPLMfor(i=0;i<G.vexnum;i+)(if(!indegreei)Get_MPL(G,i);/从零入度顶点出发构建)intGet_MPL(ALGraph&G,inti)(if(!G.verticesi.firstarc)(G.verticesi.MPL=0;return0;)else(max=0;for(p=G.verticesi.firstarc;p;p=p->nextarc)(j=p->adjvex;if(G.verticesj.MPL=0)k=Get_MPL(G,j);if

9、(k>max)max=k;)G.verticesi=max+1;returnmax+1;7.37求有向无环图中最长路径的算法intmaxlen,pathMAXSIZE;intmlpMAXSIZE;/存储已发现的最长路径voidGet_Longest_Path(ALGraphG)maxlen=0;FindIndegree(G,indegree);for(i=0;i<G.vexnum;i+)for(j=0;j<G.vexnum;j+)visitedj=0;if(!indegreei)DFS(G,i,0);/从每一个入度为0的开始深度优先printf("LongestPa

10、th:");for(i=0;mlpi;i+)printf("%d",mlpi);voidDFS(ALGraphG,inti,intlen)/这就是一个找路径递归程序,len是路径点序列visitedi=1;pathlen=i;if(len>maxlen&&!G.verticesi.firstarc)/如果路径长度大于最大路径，而且没有邻接点了for(j=0;j<=len;j+)mlpj=pathj;maxlen=len;elsefor(p=G.verticesi.firstarc;p;p=p->nextarc)j=p->ad

11、jvex;if(!visitedj)DFS(G,i,len+1);pathi=0;visitedi=0;7.28求u出发的简单回路intpathMAXSIZE,visitedMAXSIZE;intFind_All_Path(ALGraphG,intu,intv,intk)for(p=G.vertices.u.firstarc;p;p=p->nextarc)(pathk=p;visitedp=1;if(u=v)(printf("Foundonepath!n");for(i=0;pathi;i+)printf("%d",pathi);elsefor(q

12、=G.vertices.p.firstarc;q;q=p->nextarc)(l=q->adjvex;if(!visitedl)Find_All_Path(G,l,v,k+1);visitedi=0;pathk=0;例3.判断有向图中是否存在回路基本思想：如果访问过的顶点，后来又出现在别的点的邻接点中，出现回路intCycle(ALGraphG,intu,bool&has)(ArcNode*p;visitedu=1;for(p=G.verticesu.firstarc;p;p=p->nextarc)(w=p->adjvex;if(!visitedi)return

13、(Cycle(G,w);elsereturn1;例4.不带权无向连通图G中距离v最远的一个顶点基本思想：广度优先搜索，最后一个到达的顶点为所求intMaxdist(AGraphG,intv)/三件事情，定访问数组，初始化队列，起点进队intvisitedMAXSIZE;InitQueue(Q);EnQueue(Q,i);while(!QueueEmpty(Q)(DeQueue(Q,u);/出队并访问visitedu=1;for(p=G.verticesu.firstarc;p;p=p->nextarc)(k=p->adjvex;if(!visitedk)EnQueue(Q,k);r

14、eturnu;严蔚敏老师上课讲的算法例2.广度有优先遍历求u到v的最短路径基本思想：广度优先本来就是由近到远，首先找到v的就是最短路径。修改出入队操作：出队时，front后移但是不删除元素，进队时要有一个前驱指针指向刚刚出队的元素.typedefDuLinkListQueuePtr;voidInitQueue(LinkQueue&Q)(Q.front=Q.rear=(QueuePtr)malloc(sizeof(QNode);Q.front->next=Q.rear->priou=NULL;voidEnQueue(LinkQueue&Q,QelemTypee)(p=

15、(QueuePtr)malloc(sizeof(QNode);p->data=e;p->next=NULL;p->priou=front;/为了找回路径Q.rear->next=p;voidDeQueue(LinkQueue&Q,QelemType&e)/依然是先移动指针在出列Q.front=Q.front->next;e=Q.front->data;voidGet_Route(Q)/从队尾指针沿着前驱过去就是路径QueuePrep;for(p=Q.rear;p;p=p->priou)printf("%d",p->data);voidBFS(