图的广度遍历.cpp

c++算法的很经典的一些小练习 看了 觉得还可以 给大家分享一下！

#include"stdlib.h"
#include"stdio.h"

#define max 10
#define null 0
typedef enum{FALSE,TRUE} boolean;
typedef struct node{
	 int adjvex;
	 struct node *next;
	 }edgenode;
typedef struct vnode{
	 int vextex;
	 edgenode *firstedge;
	 }vertexnode;
typedef struct{
	 vertexnode adjlist[max];
	 int n,e;
	 }algraph;

boolean visited[max];
void createalgraph(algraph *g);
void bfs(algraph *g,int k);

main(){ 
	algraph *g= (algraph *)malloc(sizeof( algraph)); int v;
	createalgraph(g);
	for(v=0;v<g->n;v++)
		visited[v]=FALSE;
	for(v=0;v<g->n;v++)
		if(!visited[v])
			bfs(g,v);
}

void createalgraph(algraph *g){  
	edgenode *s;
	int i,j,k1,m,i1,j1;
	printf("input n and e:");
   scanf("%d%d",&g->n ,&g->e);
   for(i=0;i<g->n ;i++){
	   g->adjlist[i].vextex=i;
	   g->adjlist[i].firstedge=null;
   }
   for(k1=0;k1<g->e;k1++){
		printf("输入边的端点的编码！\n");
		scanf("%d%d",&i1,&j1);
		s=(edgenode *)malloc(sizeof(edgenode));
		s->adjvex=j1;
		s->next=g->adjlist[i1].firstedge;
		g->adjlist[i1].firstedge=s;
		s=(edgenode *)malloc(sizeof(edgenode));
		s->adjvex=i1;
		s->next=g->adjlist[j1].firstedge;
		g->adjlist[j1].firstedge=s;
   }
}
void bfs(algraph *g,int k){
	edgenode *p;
	int i,q[max],front,rear;
	front=rear=0;
	printf("%d",g->adjlist[k].vextex);
	visited[k]=TRUE;
	rear=(rear+1)%max;
	q[rear]=k;
	while(front!=rear){
		front=(front+1)%max;
		i=q[front];
		p=g->adjlist[i].firstedge;
		while(p){
			if(!visited[p->adjvex]){
				printf("%d",g->adjlist[p->adjvex].vextex);
				visited[p->adjvex]=TRUE;
				rear=(rear+1)%max;
				q[rear]=p->adjvex;
			}
			p=p->next;
		}
	}
}