#include <stdio.h> #include <stdlib.h> #define maxvertextnum 100 #define queuesize 10 #define null 0 typedef int vertextype; typedef struct{ int count,front,rear,data[maxvertextnum]; }myqueue; typedef struct node{ int adjvex; struct node *next; }edgenode; typedef struct{ vertextype vertex; edgenode *firstedge; }vertexnode; typedef vertexnode vexlist[maxvertextnum]; typedef struct{ vexlist vertics; int vexnum; int arcnum; }algraph; bool visited[100]; algraph* createalgraph() {//建立图g的邻接表表示 algraph *g=(algraph*)malloc(sizeof(algraph)); int i,j,k; int flag; edgenode *s; printf(" creat: ");//选择建立有向图或无向图 printf("digraph--0 "); printf("undigraph--1 "); scanf("%d",&flag); printf("input n,e "); scanf("%d%d",&g->vexnum,&g->arcnum);//输入图g的顶点数和边数 printf("input nodes: "); for(i=0;i<g->vexnum;i++){//构造一个只含n个顶点,边数为0的图 scanf("%d",&(g->vertics[i].vertex)); //输入顶点的数据域(为了简单起见,输入为整数) g->vertics[i].firstedge=null;//将顶点结点的firstedge域置为空 }//end for for(k=0;k<g->arcnum;k++){ printf("input i,j(0~n-1): "); scanf("%d%d",&i,&j);//输入对应于一条边的顶点序号序偶对,要求顶点序号为0~n-1 s=(edgenode *)malloc(sizeof(edgenode));//申请一个边结点*s s->adjvex=j;//将序号j放入边结点*s的adjvex域 s->next=g->vertics[i].firstedge; //将边结点*s作为第一个邻接点插入到序号为i的顶点的边表中 g->vertics[i].firstedge=s; if (flag){//若要建立无向图 s=(edgenode *)malloc(sizeof(edgenode));//申请一个边结点*s s->adjvex=i;//将序号i放入边结点*s的adjvex域 s->next=g->vertics[j].firstedge; //将边结点*s作为第一个邻接点插入到序号为j的顶点的边表中 g->vertics[j].firstedge=s; } //end of if }//end of for return g; }//end of creatalgraph void dfs(algraph *g,int i){ edgenode *p; printf("visit node%d ",i); visited[i]=true; p=g->vertics[i].firstedge; while(p){ if(!visited[p->adjvex]) dfs(g,p->adjvex); p=p->next; } } void dfstraver(algraph *g){ int i; for(i=0;i<g->vexnum;++i){ visited[i]=false; } for(i=0;i<g->vexnum;++i){ if(!visited[i]) dfs(g,i); } } void bfs(algraph *g,int k){ int i=0,j=0; myqueue *q=null; edgenode *p=null; q=(myqueue*)malloc(sizeof(myqueue)); q->front=q->rear=q->count=0; p=(edgenode*)malloc(sizeof(edgenode)); q->data[q->rear]=k;q->rear=(q->rear++)%queuesize;q->count++; printf("visit node %d ",k); visited[k]=true; while(q->count){ i=q->data[q->front];q->front=(q->front++)%queuesize;q->count--; p=g->vertics[i].firstedge; while(p){ if(!visited[p->adjvex]){ printf("visit node %d ",p->adjvex); visited[p->adjvex]=true; q->data[q->rear]=p->adjvex;q->rear=(q->rear++)%queuesize;q->count++; } p=p->next; } } } void bfstraver(algraph *g){ int i; for(i=0;i<g->vexnum;++i){ visited[i]=false; } for(i=0;i<g->vexnum;++i){ if(!visited[i]) bfs(g,i); } } void main(){ algraph *g=createalgraph(); dfstraver(g); printf(" "); bfstraver(g); }