dfsl.c

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

//图的深度优先遍历算法（利用邻接表）。
//
//            A ----------- H
//          /             /  \
//        /             /      \
//      /             /          \
//    B ----------- I              G
//     \             \            /|
//       \             \        /  |
//         \             \    /    |
//           C ------------ F      |
//          /                \     |
//        /                    \   |
//      /                        \ |
//    D -------------------------- E
//
//
#define N  9  //图的顶点数
#define M  4  //图的度数

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

//邻接表:
int GRA[N][M+1] ={{1,7,-1,-1,-1},
		{0,2,8,-1,-1},
		{1,3,5,-1,-1},
		{2,4,-1,-1,-1},
		{3,5,6,-1,-1},
		{2,4,6,8,-1},
		{4,5,7,-1,-1},
		{0,6,8,-1,-1},
		{1,5,7,-1,-1}};
		
void DFSL (int i)  reentrant //从顶点i出发，深度优先搜索遍历连通图	
{
	int j,k; 		
	OUT [++OUT[0]] = DOT[i];//先访问该顶点（输出该顶点信息）
	visited[i] = 1 ; 	//作已访问标记
	for (j=0;j<=M;j++) {	//从顶点i出发，扫描所有相邻顶点
		k=GRA[i][j];	//读取顶点序号
		if (k==-1) break;//如果该顶点的邻接顶点处理完毕
		if ( !visited[k] ) DFSL (k) ; //如果未访问过,从顶点j出发按深度优先继续搜索
		}
}

//出发点序号为0时的遍历顺序：ABCDEFGHI
//出发点序号为1时的遍历顺序：BAHGEDCFI
//出发点序号为2时的遍历顺序：CBAHGEDFI
//出发点序号为3时的遍历顺序：DCBAHGEFI
//出发点序号为4时的遍历顺序：EDCBAHGFI
//出发点序号为5时的遍历顺序：FCBAHGEDI
//出发点序号为6时的遍历顺序：GEDBCAHIF
//出发点序号为7时的遍历顺序：HABCDEFGI
//出发点序号为8时的遍历顺序：IBAHGEDCF

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