#include<stdio.h>
#include<stdlib.h>
#define MAX 20
typedef int DataType;
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;
typedef struct
{
DataType Qdata[MAX+1];
int front,rear;
} SeqQueue;
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);
}
void InitQueue(SeqQueue *q)
{
q->front=q->rear=0;
}
int QueueEmpty(SeqQueue *q)
{
if(q->front==q->rear)
return 1;
else
return 0;
}
int EnQueue(SeqQueue *q,DataType x)
{
if(q->rear==MAX+1)
{
printf("队列已满!");
return 0;
}
else
{
q->Qdata[q->rear]=x;
q->rear++;
return 1;
}
}
int DeQueue(SeqQueue *q,DataType *x)
{
if(q->rear==q->front)
{
printf("队列已空!");
return 0;
}
else
{
*x=q->Qdata[q->front];
q->front++;
return 1;
}
}
int GetQueue(SeqQueue *q,DataType *x)
{
if(q->rear==q->front)
{
printf("队列已空!");
return 0;
}
else
{
*x=q->Qdata[q->front];
return 1;
}
}
void BFS(ALGraph *g,int v)
{
SeqQueue q;
EdgeNode *p;
InitQueue(&q);
visit(v);
visited[v]=1;
EnQueue(&q,v);
while(!QueueEmpty(&q))
{
DeQueue(&q,&v);
p=g->adjlist[v].firstedge;
while(p!=NULL)
{
if(!visited[p->adjvex])
{
visit(p->adjvex);
visited[p->adjvex]=1;
EnQueue(&q,p->adjvex);
}
p=p->next;
}
}
}
void visit(int v)
{
}
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");
/*
CreatGraph(&g);
for(int x=0;x<g->n;x++)
visited[i]=0;
for(int x=1;x<g->n;x++)
if(visited[i]==0)
BFS(&G,i);
*/
return 0;
}