bfs.c

在定时器中断中做LED的PWM输出 AT89C2051实现A/D转换的C51程序 单片机开发系统 指令系统 程序设计 定时与中断 系统扩展 接口技术 串行口

//图的广度优先遍历算法（利用邻接矩阵）。
//
//            A ----------- H
//          /             /  \
//        /             /      \
//      /             /          \
//    B ----------- I              G
//     \             \            /|
//       \             \        /  |
//         \             \    /    |
//           C ------------ F      |
//          /                \     |
//        /                    \   |
//      /                        \ |
//    D -------------------------- E
//
//
#define N  9  //图的顶点数
#define maxsize 16	//定义队列的容量
struct  sequeue
{	int d[maxsize] ; //用数组作为队列的储存空间
	int  front,rear ; 	//指示队头位置和队尾位置的指针
} Q ; 				//定义一个全程队列变量

char DOT[N]={'A','B','C','D','E','F','G','H','I'};//存放顶点信息的数组
char OUT[N+1];	//存放被访问顶点信息顺序的数组,OUT[0]保存已访问顶点总数
char visited[N];	//存放顶点被访问标志

//邻接矩阵:
int GRA[N][N] ={{0,1,0,0,0,0,0,1,0},
		{1,0,1,0,0,0,0,0,1},
   		{0,1,0,1,0,1,0,0,0},
		{0,0,1,0,1,0,0,0,0},
		{0,0,0,1,0,1,1,0,0},
		{0,0,1,0,1,0,1,0,1},
		{0,0,0,0,1,1,0,1,0},
		{1,0,0,0,0,0,1,0,1},
		{0,1,0,0,0,1,0,1,0}};

int ENQUEUE ( int x ) //数据入队算法
{	if ( Q.front == (Q.rear+1) % maxsize ) 
		return 0; 	//队列否已满,入队失败	
	else {
		Q.rear = (Q.rear+1) % maxsize ; //调整队尾指针
		Q.d[Q.rear] = x ;    //数据成功入队
		return 1 ; 
		}
}

void BFS (int k)   //从顶点i出发，广度优先搜索遍历连通图
{
	int i,j;	//定义辅助变量
	Q.front = Q.rear = maxsize -1;	//初始化空队
	OUT [++OUT[0]] = DOT[k];//先访问该顶点（输出该顶点信息）
	visited[k] = 1 ; 	//作已访问标记
	ENQUEUE (k); 		//将访问过的出发顶点入队
	while ( Q.front != Q.rear) {//只要队列不空
		Q.front = ( Q.front+1) % maxsize ; //调整队首指针
		i = Q.d[Q.front] ;  //队首顶点出队
		for (j=0;j<N;j++)//访问它的所有邻接顶点
			if ( GRA[i][j] == 1 && !visited[j] ) {//如果该顶点邻接且未访问
			OUT [++OUT[0]] = DOT[j];//访问该顶点（输出该顶点信息）
			visited[j] = 1; //作已访问标志
			ENQUEUE (j); //将访问过的顶点入队
			}
		}
}

//出发点序号为0时的遍历顺序：ABHCIGDFE
//出发点序号为1时的遍历顺序：BACIHDFGE
//出发点序号为2时的遍历顺序：CBDFAIEGH
//出发点序号为3时的遍历顺序：DCEBFGAIH
//出发点序号为4时的遍历顺序：EDFGCIHBA
//出发点序号为5时的遍历顺序：FCEGIBDHA
//出发点序号为6时的遍历顺序：GEFHDCIAB
//出发点序号为7时的遍历顺序：HAGIBEFCD
//出发点序号为8时的遍历顺序：IBFHACEGD

main ( )
{
	int  i,j;
	for (i=0;i<N;i++) {
		OUT[0]=0;	//初始化已访问顶点数
		for (j=0;j<N;j++) visited[j]=0;//初始化访问标志
		BFS (i) ; //从序号为i的顶点出发进行广度优先遍历
		}
	while (1) ; //在这一行设置断点,中止程序运行,以便观察程序运行的结果 
}