#include "stdio.h"
#include "stdlib.h"
#include"string.h"
#define MAX_VERTEX_NUM 20
#define MAXNAME 10
#define MAXQSIZE 100
typedef char VertexType[MAXNAME];
typedef struct ArcNode
{
int adjvex;
struct ArcNode *nextarc;
}ArcNode;
typedef struct VNode
{
VertexType data;
ArcNode *firstarc;
}VNode,AdjList[MAX_VERTEX_NUM];
typedef struct
{
AdjList vertices;
int vexnum,arcnum;
}ALGraph;
typedef enum{ FALSE, TRUE }Boolean;
Boolean visited[MAX_VERTEX_NUM];
void CreateGraph(ALGraph *G)
{
int i=0;
char ch;
ArcNode *p, *q;
printf("请输入顶点数和边数(用空格隔开)：\n");
scanf("%d %d",&G->vexnum,&G->arcnum);
printf("请输入图的顶点:\n");
for(i=0;ivexnum;i++)
{
scanf("%c", &G->vertices[i].data);
G->vertices[i].firstarc=NULL;
}
for( i=0; ivexnum; i++ )
{ //存储图的边信息
printf("请输入顶点 %c 的邻接顶点:\n",G->vertices[i].data );
scanf("%c", &ch);
while( '\n' != ch )
{
p = (ArcNode *)malloc(sizeof(ArcNode));
p->adjvex = ch;
q->nextarc = p;
q = p;
q->nextarc = NULL;
scanf("%c", &ch);
}
}
}
int FirstAdjVex(ALGraph *G,int v)
{
if(G->vertices[v].firstarc)
return G->vertices[v].firstarc->adjvex;
else
return -1;
}
int NextAdjVex(ALGraph *G,int v,int w)
{
ArcNode *p=G->vertices[v].firstarc;
while(p->adjvex!=w)
p=p->nextarc;
if(p->nextarc)
return p->nextarc->adjvex;
else
return -1;
}
void DFS(ALGraph *G,int v)
{
int w;
visited[v]=TRUE;
printf("%c",G->vertices[v].data);
for(w=FirstAdjVex(G,v);w>=0;w=NextAdjVex(G,v,w))
if(!visited[w])
DFS(G,w);
}
void DFSGrahp(ALGraph *G)
{
int v;
for(v=0;vvexnum;v++)
visited[v]=FALSE;
for(v=0;vvexnum;v++)
if(!visited[v])
DFS(G,v);
printf("\n");
}
struct QNode
{
int data;
struct QNode *next;
};
typedef struct
{
QNode *front;
QNode *rear;
}LinkQueue;
int QueueEmpty(LinkQueue Q)
{
if(Q.front->next==NULL)
return 1;
else
return 0;
}
void EnQueue(LinkQueue Q, int k)
{
QNode * p=(QNode *)malloc(sizeof(QNode));
if(!p)
exit(0);
p->data=k;
p->next=NULL;
Q.rear->next=p;
Q.rear=p;
}
void DeQueue(LinkQueue &Q,int &e)
{
QNode * p;
if(Q.front==Q.rear)
return ;
p=Q.front->next;
e=p->data;
}
void BFSGrahp(ALGraph *G)
{
int v,u,w;
LinkQueue Q;
for(v=0;vvexnum;v++)
visited[v]=FALSE;
for(v=0;vvexnum;v++)
if(!visited[v])
{
visited[v]=TRUE;
printf("%c",G->vertices[v].data);
EnQueue(Q,v);
while(!QueueEmpty(Q))
{
DeQueue(Q,u);
for(w=FirstAdjVex(G,u);w!=0;w=NextAdjVex(G,u,w))
if(!visited[w])
{
visited[w]=TRUE;
printf("%c",G->vertices[w].data);
EnQueue(Q,w);
}
}
}
}
void print(ALGraph *G)
{
int v;
for(v=0;vvexnum;v++)
{
printf("%c ",G->vertices[v].data);
}
}
void menu()
{
int num;
ALGraph G=(ALGraph)malloc(sizeof(ALGraph));
while(1)
{
printf("\t\t\t 图的遍历\n\n");
printf("\t\t\t1 图的建立\n");
printf("\t\t\t2 深度优先遍历图\n");
printf("\t\t\t3 广度优先遍历图\n");
printf("\t\t\t4 显示顶点\n");
printf("\t\t\t5 结束:\n\n");
printf("\t\t 请选择1-5： ");
scanf("%d",&num);
switch(num)
{
case 1:
CreateGraph(G);
break;
case 2:
DFSGrahp(G);
break;
case 3:
BFSGrahp(G);
break;
case 4:
print(G);
break;
case 5:
exit(0);
default:
printf("请输入1-5之间的数字");
}
}
}
void main()
{
menu();
}
