dfs.c

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

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

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

void DFS (int i)  reentrant //从顶点i出发，深度优先搜索遍历连通图	
{
	int j; 		
	OUT [++OUT[0]] = DOT[i];//先访问该顶点（输出该顶点信息）
	visited[i] = 1 ; 	//作已访问标记
	for (j=0;j<N;j++)	//从顶点i出发，扫描所有相邻顶点
	 if ( GRA[i][j] == 1 && !visited[j] ) //如果未访问过
		DFS (j) ; //从顶点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;//初始化访问标志
		DFS (i) ; //从序号为i的顶点出发进行深度优先遍历
		}
	while (1) ; //在这一行设置断点,中止程序运行,以便观察程序运行的结果 
}