/*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
}
