全路径.docx

全路径 问题描述 本实验是要找出一个有向图中任意两节点间的所有路径，可以查找到任意两节点间的所有路径。 设计思路 本算法首先将两点之间有直接路径的求出，再根据已经求出的路径，找到在任意给定的两点之间是否可以通过不同于这两点的某个节点，如果可以有路径，那么将产生一条新的路径，如果没有，接着寻找。 代码 #include stdio.h #include math.h #include stdlib.h #define N 10 int flag=0; struct AllPath { int Onepath[N]; //用于存放i-j的一条路径所经过的节点 struct AllPath *next; //如果 从 i-j有很多路径，就用 链表 连接起来 }; typedef struct AllPath allpath; int main() //有向图 { int a[N][N]={0,1,1,0,1,0,1,0,1,0, 1,0,1,0,0,1,0,1,0,0, 0,1,0,1,1,1,0,1,0,1, 0,1,1,0,1,1,0,0,1,0, 0,1,1,0,0,1,1,0,1,1, 0,0,1,0,0,0,1,1,0,1, 1,0,1,0,1,0,0,1,1,0, 1,0,1,1,0,0,1,0,1,0, 1,1,1,0,1,1,0,0,0,1, 1,0,1,1,0,0,0,0,0,0 }; //有向图，为1时表示 行(i)所代表的节点到列(j)所代表的节点之间有边， allpath path[N][N];// 第一维表示起始节点，第二维表示结束节点， allpath *q; allpath *p; //主要用于记录到达的位置 int i=0,j=0;//i表示行(起始节点) j表示列(终止节点) int ij=0; for(i=0;iN;i++) //对path[][]的初始化 { for(j=0;jN;j++) { for(ij=0;ijN;ij++) { path[i][j].Onepath[ij]=-1; } path[i][j].next=NULL; } } for(i=0;iN;i++) { for(j=0;jN;j++) { if(a[i][j]!=0) { p = (allpath *)malloc(sizeof (allpath)); p-Onepath[0]=j;//直接记录一步就可到达的节点 （i-j 只需一步） 只记录了i-j之间的就直接的一条路径 for(ij=1;ijN;ij++) p-Onepath[ij]=-1; p-next =NULL; //下一个节点为空 path[i][j].next=p; //将(i-j 的)第一条路径存放到 path[i][j] } } } //************************以下是找出i,j之间的其他路径 int k =0; allpath *pp; allpath *ipath,*jpath; int noden=0; //对节点计数 int inode[N]={-1},jnode[N]={-1}; int node,t;//t表示 inode 中非-1的个数 int d=0; for(k=0;kN;k++) { for(i=0;iN;i++) { if(i!=k) { for(j=0;jN;j++) { if(j!=kj!=i) { q=path[i][j]; while(q!=NULLq-next!=NULL) //如果不是空（以防止一开始就没有后继节点），而且不是最后一个节点 一直往后走 ；目的是找到最后一个节点的位置 { q=q-next; }//此时q-next 为空 q是存在的节点 if(path[i][k].next!=NULLpath[k][j].next!=NULL) //表示在i,k和k,j之间都有路径 { ipath=path[i][k].next; //找出i,k所有的路径 while(ipath!=NULL) {