#include<stdio.h>
#include<stdlib.h>
#define Max_vertex 20
typedef int elemtype;             /*最大顶点数*/
typedef struct QNode        /* 队列元素类型*/
{
elemtype data;
struct QNode *next;
}QNode,*QNodeptr;
typedef struct QueueNode
{
QNodeptr front ;
QNodeptr rear;
}Queue;                          /*队列类型*/
Queue *L;         /*建立队列*/
typedef enum
{
FALSE,
TRUE
}Boolean;
Boolean visited[Max_vertex];/*联合体类型数组*/
typedef char vertextype[Max_vertex];/*顶点类型*/
typedef struct edgenode
{
int adjvex;
struct edgenode *next;
}EdgeNode;    /*边类型*/
typedef struct vertexnode
{
vertextype vertex;
EdgeNode *firstedge;
}VertexNode;/*链表顶点类型*/
typedef VertexNode AdjList[Max_vertex];
typedef struct ALGraph
{
AdjList adjlist;
int n,e;
}Graphic;/*定义图的类型*/
int locate(Graphic *H,vertextype p)/*确定顶点的邻接点位置*/
{
int i;
for(i=0;i<H->e;i++)
{
  if(strcmp(H->adjlist[i].vertex,p)==0)
return i;
}
return 0;
}
void createGraphic(Graphic *G)/*用邻接表创建图*/
{
int i,j,k;
vertextype m,n;
EdgeNode *s;
printf("please input the vertexs' number and Edges' number:\n");
fflush(stdin);
scanf("%d%d",&G->n,&G->e);
getchar();
printf("please input the vertexs' information.\n");
for(i=0;i<G->n;i++)
{
fflush(stdin);
gets(G->adjlist[i].vertex);
G->adjlist[i].
firstedge=NULL;
}
printf("please input the nodes(double):\n");
for(k=0;k<G->e;k++)
{
scanf("%s%s",&m,&n);
i=locate(G,m);
j=locate(G,n);
s=(EdgeNode *)malloc(sizeof(EdgeNode));
if(!s)
{
printf("overflow!");
exit(0);
}
else
{
s->adjvex=j;
s->next=G->adjlist[i].firstedge;
G->adjlist[i].firstedge=s;
s=(EdgeNode *)malloc(sizeof(EdgeNode));
   if(!s)
    {
     printf("overflow!");
     exit(0);
   }
   else
      {
    s->adjvex=i;
        s->next=G->adjlist[j].firstedge;
        G->adjlist[j].firstedge=s;
      }
   }
}
}
void DFS(Graphic *G,int i)
{
EdgeNode *p;
printf("visitvertex:%s",&G->adjlist[i].vertex);
printf("\n");
visited[i]=TRUE;
p=G->adjlist[i].firstedge;
while(p)
{
if(!visited[p->adjvex])
DFS(G,p->adjvex);
p=p->next;
}
}
void DFSTraverse(Graphic *G)/*对图的深度优先搜索*/
{
int i;
for(i=0;i<G->n;i++)
visited[i]=FALSE;
for(i=0;i<G->n;i++)
if(!visited[i])
  DFS(G,i);
}
void initalQueue(Queue *S)/*初始化队列*/
{
S->rear=S->front=(QNode *)malloc(sizeof(QNode));
if(!S->front)
{
printf("overflow!");
exit(0);
}
S->front->next=NULL;
}
int emptyQueue(Queue *S)/*判断队列是否为空*/
{
return S->front==S->rear;
}
void enQueue(Queue *S,elemtype x)/*将x插入为队列的队尾元素*/
{
QNodeptr new;
new=(QNode *)malloc(sizeof(QNode));
new->data=x;
S->rear=new;
S->rear->next=NULL;
}
void deQueue(Queue *S,elemtype m)/*删除队列的队头元素,并返回值m */
{
QNodeptr p;
if(S->front==S->rear)
{
printf("the Queue is empty!\n");
exit(0);
}
p=S->front->next;
m=p->data;
S->front->next=p->next;
if(S->rear==p)
S->rear=S->front;
free(p);
return m
}
void printnode(Graphic *Q,int x)/*显示路径函数*/
{
printf("visit:%s",&Q->adjlist[x].vertex);
printf("\n");
}
int firstadjvex(Graphic *M,int u)/*第一个邻接点的位置*/
{
return M->adjlist[u].firstedge->adjvex;
}
int nextadjvex(Graphic *H,int u)/*下一个邻接点的位置*/
{
int c;
c=H->adjlist[u].firstedge->adjvex;
while(visited[c]&&H->adjlist[u].firstedge->next)
    c=H->adjlist[u].firstedge->next->adjvex;
return c;
}
void BFSTraverse(Graphic *H,void(*visit)(Graphic *Q,int x))/*对图的广度优先搜索*/
{
elemtype u=0,v,w,x;
visit=printnode;
for(v=0;v<H->n;v++)
visited[v]=FALSE;
initalQueue(L);
for(v=0;v<H->n;v++)
if(!visited[v])
  {
    visited[v]=TRUE;
   visit(H,v);
  enQueue(L,v);
  while(!emptyQueue(L))
        {
     deQueue(L,u);
         for(w=firstadjvex(H,u);w>=0;w=nextadjvex(H,u))
               if(!visited[w])
                 {
                    visited[w]=TRUE;
                    visit(H,w);
                    enQueue(L,w);
                 }
        }

   }
}


void main(void) /*  主函数*/
{
Graphic create;
clrscr();
createGraphic(&create);
printf("\n DFST visit:\n");
DFSTraverse(&create);
printf("\n BFST visit:\n");
BFSTraverse(&create,printnode);
}









评论