算法導論 第22章 深度優先周遊

         深度優先周遊的作用主要是對邊，點的分類，如拓撲排序，找強連通分量等應用。

         深度優先搜尋的政策是隻要有可能就盡量深入。也就是說每發現一個新的點就立馬對其搜尋，直到與該點所連接配接的所有點都被搜尋完全，則傳回了，傳回該點的前驅。

         由于深度優先搜尋一般都是被其他算法所用，是以它要提供有效的資訊，每個點儲存一個d值和f值，d值是剛發現的時間，f值為結束對該點鄰接點掃描的時間。 比如一個孤立點，發現時間為 p，則結束時間為p+1， 另外還儲存一種顔色，白色為還未被發現，灰色為還未對該點搜尋完，黑色該點已經被搜尋完了。

#include<iostream>
#include<fstream>
#include<queue>

 using namespace std;


 class node
 {
  public:
      node():adjvex(0),nextvex(NULL){}
     int  adjvex;
     node *nextvex;

 };

class vex
{
public:

  char color;
  int predecessor;

  int d; //發現時間
  int f; //完成時間
};

typedef node *  adjnode;


 class Graph
{
 public:
    int n;//頂點個數
    adjnode *Adj;
    vex * vexs;
 };



void CreateGraph(Graph &g)
{
    ifstream  infile("graph22-6.txt");

    cin.rdbuf(infile.rdbuf());
 if(g.Adj==NULL)cout<<1<<endl;
 cout<<"請輸入頂點數"<<endl;
 int n,x;
 cin>>n;

 g.Adj=new adjnode[n+1];// 0号不用
 g.vexs=new vex[n+1];
 g.n=n;

cout<<"依次輸入與每個頂點相鄰的頂點号，以0為結束"<<endl;

for(int i=1;i!=n+1;++i){
 g.Adj[i]=new node;
  adjnode ne=g.Adj[i];

  int ex=0;
  while(true){
    cin>>x;
    if(x==0)
        break;
  else
   if(ex!=0){
    ne->nextvex=new node;
    ne=ne->nextvex;
   }
   ++ex;
    ne->adjvex=x;
  }//while
}
}



void printGraph(Graph g)
{
   for(int i=1;i!=g.n+1;++i){
      adjnode p=g.Adj[i];
      while(p!=NULL){
        cout<<p->adjvex<<"  ";
        p=p->nextvex;
      }
      cout<<endl;
   }
}

int time=0;  //全局變量 初始化為0

void Dfs_visit(Graph &g,int u)    //對某個白色的點進行深度搜尋
{
   time++; //從上個點到這個點 時間+1

   g.vexs[u].d=time;      //發現時間
   g.vexs[u].color='G';          //變為灰色，表示還未完成對點u的深度搜尋

 for(adjnode p=g.Adj[u];p!=NULL;p = p->nextvex)  //對u點連接配接的點進行單個深度搜尋
    {
        int tem=p->adjvex;
            if(g.vexs[tem].color=='W'){  //發現還未被發現的點
                g.vexs[tem].predecessor=u;
                Dfs_visit(g,tem);   //遞歸調用
            }
}

g.vexs[u].color='B';  //完成對u點的搜尋    用黑色表示
++time; //時間加1  從搜尋點傳回到u
g.vexs[u].f=time; //完成時間指派
}




void DepthFisrtSreach(Graph g)  //深度優先搜尋， O（V+E ）   。 盡可能的深入
{

 for(int i=1;i!=g.n+1;++i){   //初始化 是以點都白色，，還未被發現
    g.vexs[i].color='W';
    g.vexs[i].predecessor=i;
   }

 for(int i=1;i!=g.n+1;++i){   //對每個還未發現的點調用Dfs_visit
      if(g.vexs[i].color=='W'){
             Dfs_visit(g,i);
      }
 }


cout<<"         前驅       "<<"d值"<<"       f值"<<endl;
for(int i=1;i!=g.n+1;++i){
      cout<<"結點"<<i<<":     "<<g.vexs[i].predecessor <<"       "<<g.vexs[i].d<<"           "<<g.vexs[i].f <<endl;
   }

}


 int main()
 {

 Graph G;
 CreateGraph( G);
 printGraph(G);

DepthFisrtSreach(G);

 return 0;}