youxiangtu.txt

已知有向图和图中两个顶点u和v

已知有向图和图中两个顶点u和v，试编写算法求
有向图中从u到v的所有简单路径。
实现下列函数：
void AllPath(ALGraph g, VertexType sv, VertexType tv,
             StrARR &path, int &i);
/* Get all the paths from vertex sv to tv, save them */
/* into Array path which contains string components. */
/* Return the number of path using i                 */

图的邻接表以及相关类型、函数和辅助变量定义如下：
Status visited[MAX_VERTEX_NUM];
typedef char StrARR[100][MAX_VERTEX_NUM+1];
typedef char VertexType;
typedef struct ArcNode {
    int adjvex;
    struct ArcNode *nextarc;
} ArcNode;

typedef struct VNode {
    VertexType data;
    ArcNode  *firstarc;
} VNode, AdjList[MAX_VERTEX_NUM];

typedef struct {
    AdjList vertices;
    int vexnum, arcnum;
} ALGraph;

int LocateVex(Graph g, VertexType v);
void inpath(char *path, VertexType v);
 /* Add vertex 'v' to 'path' */
void depath(char *path, VertexType v);
 /* Remove vertex 'v' from 'path' */
int k=0,q=0;
void AllPath(ALGraph g, VertexType sv, VertexType tv,
             StrARR &path, int &i)
/* Get all the paths from vertex sv to tv, save them */
/* into Array path which contains string components. */
/* Return the number of path using i                 */
{int m,n,j,l;
 ArcNode *p;
 if(!q)
 {for(j=0;j<20;j++)
   for(l=0;l<=20;l++)
    path[j][l]=0;
  q=1;
 }   
 m=LocateVex(g,sv);
 n=LocateVex(g,tv); 
 path[i][k]=sv; //加入当前路径中
 visited[m]=1;
 if(m==n) //找到了一条简单路径
  {i++;
   j=k;
   for(;j>=0;j--)path[i][j]=path[i-1][j];   
   visited[m]=0;
   path[i][k--]=0;
  }
  else
   {for(p=g.vertices[m].firstarc;p;p=p->nextarc)
    {l=p->adjvex;
     if(!visited[l]){k++;AllPath(g,g.vertices[l].data,tv,path,i);}//继续寻找
    }
    visited[m]=0;
    path[i][k--]=0; //回溯    
   }
 if(k<0)
 {j=k+1;
  if(!path[i][j]){k=0;q=0;}
 } 
}