#include <iostream.h>
const int nmax=100;
typedef struct
{
int data[nmax+1];
int adjmat[nmax+1][nmax+1];
int n,e;
}mat_graph;
typedef struct node * pointer;
struct node
{
int no;
pointer next;
};
typedef struct
{
int data;
pointer first;
}headtype;
typedef struct
{
headtype adjlist[nmax+1];
int n,e;
}lk_graph;
int pathdetect (lk_graph *gl,int i,int j);
void main()
{
mat_graph ga;
int i,j;
ga.n=4;
ga.e=4;
ga.adjmat[1][2]=1;
ga.adjmat[2][3]=1;
ga.adjmat[3][1]=1;
ga.adjmat[1][4]=1;
lk_graph gl;
pointer p;
gl.n=ga.n;
gl.e=ga.e;
for(i=1;i<=gl.n;i++) gl.adjlist[i].first=NULL;
for(i=1;i<=ga.n;i++)
for(j=ga.n;j>=i;j--)
{
if(ga.adjmat[i][j]==0) continue;
p=new node;
p->no=j;
p->next=gl.adjlist[i].first;
gl.adjlist[i].first=p;
}
pathdetect(&gl,1,2);
}
int pathdetect (lk_graph *gl,int i,int j)
{
int S[nmax];
pointer p;
int top=-1;
int k;
int visited[100];
visited[i]=1;
S[++top]=i;
do
{
p=gl->adjlist[S[top]].first;
while(p!=NULL && visited[p->no])
p=p->next;
if(p==NULL) top--;
else
{
visited[p->no]=1;
S[++top]=p->no;
if(p->no==j)
{
cout<<"发现路径:"<<endl;
for(k=0;k<=top;k++)
cout<<S[k]<<" ";
return 1;
}
}
}while(top!=-1);
cout<<"没有路径"<<endl;
return 0;
}