算法7-5：圖的周遊——深度優先搜尋

http://www.dotcpp.com/oj/problem1702.html

題目描述

深度優先搜尋周遊類似于樹的先根周遊，是樹的先根周遊的推廣。其過程為：假設初始狀态是圖中所有頂點未曾被通路，則深度優先搜尋可以從圖中的某個頂點v出發，通路此頂點，然後依次從v的未被通路的鄰接點出發深度優先周遊圖，直至圖中所有和v有路徑相通的頂點都被通路到；若此時圖中尚有頂點未被通路，則另選圖中一個未曾被通路的頂點作為起始點，重複上述過程，直至圖中所有頂點都被通路到為止。

其算法可以描述如下：

在本題中，讀入一個無向圖的鄰接矩陣（即數組表示），建立無向圖并按照以上描述中的算法周遊所有頂點，輸出周遊頂點的順序。

輸入

輸入的第一行包含一個正整數n，表示圖中共有n個頂點。其中n不超過50。

以後的n行中每行有n個用空格隔開的整數0或1，對于第i行的第j個0或1，1表示第i個頂點和第j個頂點有直接連接配接，0表示沒有直接連接配接。當i和j相等的時候，保證對應的整數為0。

輸入保證鄰接矩陣為對稱矩陣，即輸入的圖一定是無向圖。

輸出

隻有一行，包含n個整數，表示按照題目描述中的深度優先周遊算法周遊整個圖的通路頂點順序。每個整數後輸出一個空格，并請注意行尾輸出換行。

樣例輸入

4
0 1 0 1
1 0 0 0
0 0 0 1
1 0 1 0
           

樣例輸出

0 1 3 2 
           

#include<stdio.h>
#include<string.h>
#define N 55
int a[N][N],n,temp[N][N],book[N];
void dfs(int i)
{
	int j;
	printf("%d ",i);
	book[i]=1;
	for(j=0;j<n;j++)
	{
		if(a[i][j]==1&&book[j]==0)
			dfs(j);
	}
	return ;
}
int main()
{
	int i,j;
	while(scanf("%d",&n)!=EOF)
	{
		memset(temp,0,sizeof(temp));
		memset(book,0,sizeof(book));
		for(i=0;i<n;i++)
			for(j=0;j<n;j++)
				scanf("%d",&a[i][j]);
		dfs(0);
		printf("\n");
	}
	return 0;
}