假设图G采用邻接表存储,设计一个算法,输出图G中从顶点u到v的所有简单路径.

网友回答

#include stdio.h
#define MAX 5
typedef struct ArcNode
{\x09/*单链表中的结点的类型*/
\x09int adjvex; /*该边指向的顶点在顺序表中的位置*/
\x09struct ArcNode *next; /*下一条边*/
}ArcNode;
typedef struct VNode
{\x09/*顶点类型*/
\x09int data; /*顶点中的数据信息*/
\x09ArcNode *firstarc; /*指向单链表,即指向第一条边*/
}VNode;
int visited[5]={0,0,0,0,0};\x09//标记数组
//先创建顶点,再创建指向
CreatGraph(int n ,VNode G[] )
{\x09int i,e;
\x09ArcNode *p ,*q;
\x09printf(Input the information of the vertex\n);
\x09for(i=0;iadjvex = e;
\x09\x09\x09if(G[i].firstarc == NULL)
\x09\x09\x09\x09G[i].firstarc = p; /*i结点的第一条边*/
\x09\x09\x09else
\x09\x09\x09\x09q->next = p; /*下一条边*/
\x09\x09\x09q = p;
\x09\x09\x09scanf(%d,&e);
\x09\x09}
\x09}}int FirstAdj(VNode G[],int v)
{\x09if(G[v].firstarc != NULL)
\x09\x09return (G[v].firstarc)->adjvex;
\x09return -1;
}int NextAdj(VNode G[],int v)
{\x09ArcNode *p;
\x09\x09p = G[v].firstarc;
\x09while( p!= NULL)
\x09{\x09\x09if(visited[p->adjvex]) //如果访问过了就继续找下一个结点
\x09\x09\x09p = p->next;\x09\x09else
\x09\x09\x09return p->adjvex;\x09//如果找到未访问过的就返回
\x09}\x09return -1;
}void DFS(VNode G[],int v)
{\x09int w;
\x09\x09printf(%d ,G[v].data); /*访问当前顶点,打印出该顶点中的数据信息*/
\x09visited[v] = 1; /*将顶点v对应的访问标记置1*/
\x09w = FirstAdj(G,v); /*找到顶点v的第一个邻接点,如果无邻接点,返回-1*/
\x09while(w != -1)\x09{//退出递归条件有二：一是直到某节点无指向,二是该深度没有可以访问的顶点\x09\x09if(visited[w] == 0) /*该顶点未被访问*/\x09\x09\x09DFS(G,w); /*递归地进行深度优先搜索*/\x09\x09w = NextAdj(G,v);