#include<stdio.h>
#include<stdlib.h>
#define MAX 20
int visited[MAX+1];
typedef struct node
{
int adjvex;
struct node *next;
int info;
} EdgeNode;
typedef struct
{
int vertex;
EdgeNode *firstedge;
} VertexNode;
typedef VertexNode AdjList[MAX+1];
typedef struct
{
AdjList adjlist;
int n,e;
} ALGraph;
void CreatesAdjList(ALGraph *g,int n,int e)
{
EdgeNode *ptr;
int k,v1,v2;
g->n=n;
g->e=e;
for(k=1; k<=g->n; k++)
{
g->adjlist[k].vertex=k;
g->adjlist[k].firstedge=NULL;
}
for(k=1; k<=g->e; k++)
{
printf("请输入边的两个节点:");
scanf("%d%d",&v1,&v2);
ptr=(EdgeNode*)malloc(sizeof(EdgeNode));
ptr->adjvex=v2;
int num;
printf("请输入这条边的权值:");
scanf("%d",&num);
ptr->info=num;
ptr->next=g->adjlist[v1].firstedge;
g->adjlist[v1].firstedge=ptr;
ptr=(EdgeNode*)malloc(sizeof(EdgeNode));
ptr->adjvex=v1;
ptr->next=g->adjlist[v2].firstedge;
g->adjlist[v2].firstedge=ptr;
}
}
void DFS(ALGraph *g,int i)
{
EdgeNode *p;
printf("%3d",g->adjlist[i].vertex);
visited[i]=1;
for(p=g->adjlist[i].firstedge; p!=NULL; p=p->next)
if(!visited[p->adjvex])
DFS(g,p->adjvex);
}
void DFSTraverse(ALGraph *g)
{
int i;
for(i=1; i<=g->n; i++)
visited[i]=0;
for(i=1; i<=g->n; i++)
if(!visited[i])
DFS(g,i);
}
int main()
{
int n,m,i=1;
printf("请输入顶点数和边数:");
scanf("%d%d",&n,&m);
ALGraph *g;
CreatesAdjList(g,n,m);
DFS(g,i);
DFSTraverse(g);
system("pause");
return 0;
}