/*DFS深度優先搜索*/


#include<iostream.h>
#define maxv 100    /*最大頂點數*/


void main(void)
{
    int n;
    //int (*A)[maxv],*visit,*visited;
	int *visit,*visited;
    cout<<"請輸入圖中的節點個數：";
    cin>>n;
   // A=(int(*)[maxv])new int[maxv];   /*鄰接矩陣*/
    visit=new int[n];  /*存儲按順序訪問到的節點的序號*/
    visited=new int[n];/*記錄每個節點的訪問標志位:0—未訪問，1—已訪問*/

    cout<<"請輸入鄰接矩陣：\n";
    int A[8][8]={{0,1,1,0,0,0,0,0},{1,0,0,1,1,0,0,0},{1,0,0,0,0,1,1,0},{0,1,0,0,0,0,0,1},{0,1,0,0,0,0,0,1},{0,0,1,0,0,0,1,0},{0,0,1,0,0,1,0,0},{0,0,0,1,1,0,0,0}};
    for(int i=0;i<n;i++)
    {
       for (int j=0;j<n;j++)
          cout<<A[i][j]<<'\t';
	   cout<<'\n';
       visit[i]=-1;  
       visited[i]=0; //置每個節點的初始訪問標志位為0，表明該節點未被訪問
     }

    int start;
    cout<<"請輸入查找的初始節點的序號（1，2,...):\n";
    cin>>start;
	cout<<"初始節點為:"<<start<<'\n';

    if(start<1||start>n)
       cout<<"節點序號超出范圍!\n";
    else
    { 
		 start=start-1;
		 cout<<"start="<<start<<'\n';
         visited[start]=1;   //說明節點start已經被訪問
         visit[0]=start;     //節點start是第一個被訪問的節點

        int count=1;         //置節點計數器為1，因為初始節點已經被訪問
        while(count<=8)
        {

            for(int j=start+1;j<n;j++) /*查找與節點start相接并且未被訪問過的節點*/
            {
                  if(A[start][j]==1 && visited[j]==0)
                  {
				     cout<<"已經找到!\n";
                     visited[j]=1;        /*第j個節點已經被訪問,置其訪問標志位為1*/
                     visit[count]=j;      /*第j個節點已經被訪問*/
				     count++;
                     start=j;
                     break;
                  }
				  else continue;
			}//for

            if(j==n)  /*說明沒有符合條件的節點，此時需要回搠到一個未被訪問過的節點*/
			{
                 if(start==visit[0])
                     cout<<"該圖不連通!\n";
                  else 
				     start=visit[count-2];
			}
			
		}//while 
		
        cout<<"遍歷次序為：\n";
        for(int j=0;j<n;j++)
           cout<<visit[j]+1<<'\t';
        cout<<'\n';
	}//else
}