dfs.txt

DFS的程序 VC++编写的 保存为TXT格式

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