#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); } 

评论