#include<stdio.h>
#include<malloc.h>

typedef int InfoType;
#define  MAXV 100
#define  INF  32767
typedef struct
{     int no;
      InfoType info;
}VertexType;
typedef  struct
{    int  edges[MAXV][MAXV];
     int  n,e;
     VertexType vexs[MAXV];
}MGraph;
typedef  struct  ANode
{      int  adjvex;
       struct  ANode  * nextarc;
       InfoType info;
}ArcNode;
typedef  int  Vertex;
typedef  struct  Vnode
{    Vertex  data;
     ArcNode  *firstarc;
}VNode;
typedef  VNode AdjList[MAXV];
typedef struct
{     AdjList adjlist;
      int n,e;
}ALGraph;

void MatToList(MGraph g ,ALGraph *&G)
{    int i,j;
      ArcNode * p;
      G=(ALGraph  *)malloc(sizeof(ALGraph));
      for(i=0;i<g.n;i++)
          G->adjlist[i].firstarc=NULL;
      for(i=0;i<g.n;i++)
          for(j=g.n-1;j>=0;j--)
              if(g.edges[i][j]!=0&&g.edges[i][j]!=INF)
              {   p=(ArcNode *)malloc(sizeof(ArcNode));
                  p->adjvex=j;
                 
                  p->nextarc=G->adjlist[i].firstarc;
                  G->adjlist[i].firstarc=p;
              }
    G->n=g.n;G->e=g.e;
}
void DispAdj(ALGraph *G)
{    int i;
     ArcNode *p;
     for(i=0;i<G->n;i++)
     {   p=G->adjlist[i].firstarc;
     printf("%3d:",i);
     while(p!=NULL)
     {     printf("\n");
     }
     }
}
int visited[MAXV];
    void PathAll1(ALGraph  *G,int u,int v,int path[],int i)
    {    ArcNode  *p;
         int j,n;
         visited[u]=1;
         p=G->adjlist[u].firstarc;
         while(p!=NULL)
         {    n=p->adjvex;
              if(n==v)
              {   path[i+1]=v;
                  for(j=0;j<=i+1;j++)
                      printf("%3d",path[j]);
                  printf("\n");
              }
              else if(visited[n]==0)
              {    path[i+1]=n;
                   PathAll1(G,n,v,path,i+1);
              }
              p=p->nextarc;
         }
         visited[u]=0;
    }
    void  BFS(ALGraph  *G,int v)
    {     ArcNode *p;
          int queue[MAXV],front=0,rear=0;
          int  visited[MAXV];
          int w,i;
          for(i=0;i<G->n;i++)visited[i]=0;
          printf("%3d",v);
          visited[v]=1;
          rear=(rear+1)%MAXV;
          queue[rear]=v;
          while(front!=rear)
          {    front=(front+1)%MAXV;
               w=queue[front];
               p=G->adjlist[w].firstarc;
               while(p!=NULL)
               {    if(visited[p->adjvex]==0)
               {    printf("3d",p->adjvex);
                    visited[p->adjvex]=1;
                    rear=(rear+1)%MAXV;
                    queue[rear]=p->adjvex;
               }
               p=p->nextarc;
               }
          }
          printf("\n");
    }
    void main()
    {    int i,j;
         int u=5,v=2,d=3;
         int path[MAXV];
         MGraph g;
         ALGraph  *G;
         int A[MAXV][6]={{0,1,0,1,0,0},{0,0,1,0,0,0},{1,0,0,0,0,1},{0,0,1,0,0,1},{0,0,0,1,0,0},{1,1,0,1,1,0}};
         g.n=6;g.e=10;
         for(i=0;i<g.n;i++)
             for(j=0;j<g.n;j++)
                 g.edges[i][j]=A[i][j];
             G=(ALGraph  *)malloc(sizeof(ALGraph));
             MatToList(g,G);
             printf("图G的领接表:\n");
             DispAdj(G);
             for(i=0;i<g.n;i++)
                 visited[i]=0;
             printf("从顶点%d到%d的所有路径:\n",u,v);
             path[0]=u;visited[u]=1;
             PathAll1(G,u,v,path,0);
             BFS(G,0);printf("\n");
    }