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

7.22

判断是否存在从

u

< br>到

v

的路径

< br>基本思想：从

u

出发深度或广度搜索，找到

v

就有，找不到就没有

int visited[MAXSIZE];

int exist_path_DFS(ALGraph G,int i,int j)

{

if(i==j) return 1;

else

{

visited[i]=1;

for(p=es[i].firstarc;p;p=p->nextarc)

{

k=p->adjvex;

if(!visited[k]&&exit_path_DFS(G,k,j)) return 1;

}

}

}

7.23

int exist_path_BFS(ALGraph G,int i,int j)

{ //

三件事情，定访问数组，初始化队列，起点进队

int visited[MAXSIZE];

InitQueue(Q);

EnQueue(Q,i);

while(!QueueEmpty(Q))

{

De Queue(Q,u);//

出队并访问

visited[u]=1;

for(p=es[u].firstarc;p;p=p->nextarc)

{

k=p->adjvex;

if(k==j) return 1;

if(!visited[k]) EnQueue(Q,k);

}

}

}

7.27

判断

u

到

v

是否存在长度

k

的简单路径

int visited[MAXSIZE];

int exist_path_len(ALGraph G,int i,int j,int k)

{

if(i==j&&k==0) return 1;

else if(k>0)

{

visited[i]=1;

for(p=es[i].firstarc;p;p=p->nextarc)

{

l=p->adjvex;

if(!visited[l])

if(exit_path_len(G,l,j,k-1)) return 1;

}

visited[i]=0;//

如 果该点的邻接点中没找到，将该点退出

}

//

以便在别的路径中访问

return 0;

}

7.28

求

u

到

v

所有简单路径

int path[MAXSIZE],visited[MAXSIZE];

int Find_All_Path(ALGraph G,int u,int v,int k)

{

path[k]=u;

visited[u]=1;

if(u==v)

{

printf(

for(i=0;path[i];i++) printf(

}

else

for(p=es.[u].firstarc;p;p=p->nextarc)

{

l=p->adjvex;

if(!visited[l]) Find_All_Path(G,l,v,k+1);

}

visited[i]=0;

path[k]=0;

}

7.29

求

i

到

j

的不含回路的，长度为

k

的路径条数

int GetPathNum_Len(ALGraph G,int i,int j,int len)

{

if(i==j&&len==0) return 1;

else if(len>0)

{

sum=0;//

表示通过本结点的路径数

visited[i]=1;

for(p=es[i].firstarc;p;p=p->nextarc)

{

l=p->adjvex;

if(!visited[l])

sum+=GetPathNum_Len(G,l,j,len-1);

}

visited[i]=0;

}

return sum;

}

7.30

求有向图中所有简单回路

int visited[MAXSIZE];

int path[MAXSIZE];

int cycles[MAXSIZE][MAXSIZE];

int thiscycle[MAXSIZE];

int cyount=0;//

以发现的回路个数

void GetAllCycle(ALGraph G)

{

for(v=0;v<;v++) visited[v]=0;

for(v=0;v<;v++)

if(!visited[i]) DFS(G,v,0);

}

void DFS(ALGraph G,int v,int k)

{

visited[v]=1;

path[k]=v;

for(p=es[v].firstarc;p;p=p->next)

{

w=p->adjvex;

if(!visited[w]) DFS(G,w,k+1);

else //

出现已经访问过的结点，发现回路

{

for(i=0;path[i] !=w;i++);//

找回路起点

for(j=0;path[i+j];i++) thiscycle[j]=path[i+j];

if(!exist_cycle()) cycles[cycount++]=thiscycle;

for(i=0;i<;i++) thiscycle[i]=0;

}

}

path[k]=0;

visit ed[k]=0;//

注意只有当前路经结点上的

visite d

为真。因此一旦发现当前结点

visited

为真

//

即发现了一条回路

}

int exsit_cycle()

{

int temp[MAXSIZE];

for(i=0;i

temp[m]=cycles[i][k+m];

for()

}

7.36

每个顶点增加一个

MPL

域存放由他出发的最长路径的长度

void Fill_MPL(ALGraph &G)

{

FindIndegree(G,indegree);

for(i=0;i<;i++)

{

if(!indegree[i]) Get_MPL(G,i);//

从零入度顶点出发构建

MPL

域

}

}

int Get_MPL(ALGraph &G,int i)

{

if(!es[i].firstarc)

{

es[i].MPL=0;

return 0;

}

else

{

max=0;

for(p=es[i].firstarc;p;p=p->nextarc)

{

j=p->adjvex;

if(es[j].MPL==0) k=Get_MPL(G,j);

if(k>max) max=k;

}

es[i]=max+1;

return max+1;

}

}