dfs.rar_Vc_dfs

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