#include<stdio.h>
#include"malloc.h"
#define MAX_VERTEX_NUM 30
#define n 8
#define e 9
#define TRUE 1
#define FALSE 0

int visited[MAX_VERTEX_NUM];

typedef struct edgenode
{int adjvex;
 edgenode * nextedge;
} edgenode;

typedef struct vexnode
{char data;
 edgenode * firstedge;
}vexnode;

vexnode AdjList[MAX_VERTEX_NUM];

typedef struct
{vexnode vertices;
 int vexnum,edgenum;
}ALGraph;

//构造算法
void creatgraph(ALGraph &G)
{int i,j,k;
 edgenode * s;
 printf("以编号为顺序输入顶点信息:（每个顶点占两位）：");
  for(i=0;i<n;i++)
   {scanf("%2d",&AdjList[i].data);
    AdjList[i].firstedge=FALSE;
    }
  printf("输入组成边的点对:(如：边为（1，2），则输入1 2)\n");
 for(k=1;k<=e;k++)       
 {printf("第%d条边的点对：",k);
     scanf("%d%d",&i,&j);
       s=(edgenode*)malloc(sizeof(edgenode));
       s->adjvex=j;
       s->nextedge= AdjList[i].firstedge;
        AdjList[i].firstedge=s;
        s=(edgenode*)malloc(sizeof(edgenode));
        s->adjvex=i;
        s->nextedge=AdjList[j].firstedge;
        AdjList[j].firstedge=s;}
}
//打印领结表
void show(ALGraph &G)
{
    int i;
    edgenode *s;
    for(i=0;i<n;i++)
    {
        printf("%9d:->",AdjList[i].data);
        if(AdjList[i].firstedge!=FALSE)
        {
            s=AdjList[i].firstedge;
            while(s!=FALSE)
            {
                printf("%5d->",s->adjvex);
                s=s->nextedge;
            }
        }
        printf("\n");
    }
}

//DFS遍历算法
void dfs(ALGraph &G,int i)
{static int visited[MAX_VERTEX_NUM];
 edgenode *p;
 printf("%d->",AdjList[i].data);
 visited[i]=TRUE;
p=AdjList[i].firstedge;

while(p!=FALSE)
{if(! visited[p->adjvex])
 dfs(G,p->adjvex);
 p=p->nextedge;
}
}

void dfstravers(ALGraph &G)
{int i;
 for(i=0;i<n;i++) 
     visited[i]=FALSE;
 for(i=0;i<n;i++) 
  if(!visited[i])
   dfs(G,i);
}

void main()
{
    int x;
    ALGraph G;
    creatgraph(G);
    printf("输出如下的邻接表：\n");
    show(G);
    printf("\n输入访问出发点的顶点编号：\n");
    scanf("%d",&x);
    printf("\n该图的深度优先搜索遍历序列为：\n\t");
    dfs(G,x);
    printf("\b\b");
    printf("\n");
}