DFS

    从图中某个顶点V0 出发，访问此顶点，然后依次从V0的各个未被访问的邻接点出发深度优先搜索遍历图，直至图中所有和V0有路径相通的顶点都被访问到(使用堆栈).

//使用邻接矩阵存储的无向图的深度优先遍历template 
     
      void Graph
      
       ::DFS(){    stack
       
         iStack;    showVertex(0);    vertexList[0]->wasVisted = true;    iStack.push(0);    while (!iStack.empty())    {        int top = iStack.top();        int v = getAdjUnvisitedVertex(top);        if (v == -1)        {            iStack.pop();        }        else        {            showVertex(v);            vertexList[v]->wasVisted = true;            iStack.push(v);        }    }    //使其还可以再深/广度优先搜索    for (int i = 0; i < nVerts; ++i)        vertexList[i]->wasVisted = false;}
       
      
     

BFS

   从图中的某个顶点V0出发，并在访问此顶点之后依次访问V0的所有未被访问过的邻接点，之后按这些顶点被访问的先后次序依次访问它们的邻接点，直至图中所有和V0有路径相通的顶点都被访问到.

  若此时图中尚有顶点未被访问，则另选图中一个未曾被访问的顶点作起始点，重复上述过程，直至图中所有顶点都被访问到为止(使用队列)。

//使用邻接矩阵存储的无向图的广度优先遍历template 
     
      void Graph
      
       ::BFS(){    queue
       
         iQueue;    showVertex(0);    vertexList[0]->wasVisted = true;    iQueue.push(0);    while (!iQueue.empty())    {        int front = iQueue.front();        iQueue.pop();        int v = getAdjUnvisitedVertex(front);        while (v != -1)        {            showVertex(v);            vertexList[v]->wasVisted = true;            iQueue.push(v);            v = getAdjUnvisitedVertex(front);        }    }    for (int i = 0; i < nVerts; ++i)        vertexList[i]->wasVisted = false;}
       
      
     

附-完整代码

const int MAX_VERTS = 20;//顶点template 
     
      class Vertex{public:    Vertex(const Type &_node = Type())        : node(_node), wasVisted(false) {}public:    bool wasVisted;	//增加一个访问位    Type node;};//图template 
      
       class Graph{public:    Graph();    ~Graph();    void addVertex(const Type &vertex);    void addEdge(int start, int end);    void printMatrix();    void showVertex(int v);    void DFS();    void BFS();private:    int getAdjUnvisitedVertex(int v);private:    Vertex
       
        * vertexList[MAX_VERTS];    int nVerts;    int adjMatrix[MAX_VERTS][MAX_VERTS];};template 
        
         void Graph
         
          ::DFS(){    stack
          
            iStack; showVertex(0); vertexList[0]->wasVisted = true; iStack.push(0); while (!iStack.empty()) { int top = iStack.top(); int v = getAdjUnvisitedVertex(top); if (v == -1) { iStack.pop(); } else { showVertex(v); vertexList[v]->wasVisted = true; iStack.push(v); } } //使其还可以再深度优先搜索 for (int i = 0; i < nVerts; ++i) vertexList[i]->wasVisted = false;}template 
           
            void Graph
            
             ::BFS(){ queue
             
               iQueue; showVertex(0); vertexList[0]->wasVisted = true; iQueue.push(0); while (!iQueue.empty()) { int front = iQueue.front(); iQueue.pop(); int v = getAdjUnvisitedVertex(front); while (v != -1) { showVertex(v); vertexList[v]->wasVisted = true; iQueue.push(v); v = getAdjUnvisitedVertex(front); } } for (int i = 0; i < nVerts; ++i) vertexList[i]->wasVisted = false;}//获取下一个尚未访问的连通节点template 
              
               int Graph
               
                ::getAdjUnvisitedVertex(int v){ for (int j = 0; j < nVerts; ++j) { //首先是邻接的, 并且是未访问过的 if ((adjMatrix[v][j] == 1) && (vertexList[j]->wasVisted == false)) return j; } return -1;}//打印节点信息template 
                
                 void Graph
                 
                  ::showVertex(int v){ cout << vertexList[v]->node << ' ';}template 
                  
                   Graph
                   
                    ::Graph():nVerts(0){ for (int i = 0; i < MAX_VERTS; ++i) for (int j = 0; j < MAX_VERTS; ++j) adjMatrix[i][j] = 0;}template 
                    
                     Graph
                     
                      ::~Graph(){ for (int i = 0; i < nVerts; ++i) delete vertexList[i];}template 
                      
                       void Graph
                       
                        ::addVertex(const Type &vertex){ vertexList[nVerts ++] = new Vertex
                        
                         (vertex);}template 
                         
                          void Graph
                          
                           ::addEdge(int start, int end){ //无向图 adjMatrix[start][end] = 1; adjMatrix[end][start] = 1;}template 
                           
                            void Graph
                            
                             ::printMatrix(){ for (int i = 0; i < nVerts; ++i) { for (int j = 0; j < nVerts; ++j) cout << adjMatrix[i][j] << ' '; cout << endl; }}//测试代码int main(){ Graph
                             
                               g; g.addVertex('A'); //0 g.addVertex('B'); //1 g.addVertex('C'); //2 g.addVertex('D'); //3 g.addVertex('E'); //4 g.addEdge(0, 1); //A-B g.addEdge(0, 3); //A-D g.addEdge(1, 0); //B-A g.addEdge(1, 4); //B-E g.addEdge(2, 4); //C-E g.addEdge(3, 0); //D-A g.addEdge(3, 4); //D-E g.addEdge(4, 1); //E-B g.addEdge(4, 2); //E-C g.addEdge(4, 3); //E-D g.printMatrix(); cout << "DFS: "; g.DFS(); cout << "\nBFS: "; g.BFS(); return 0;}