算法导论第22章22.2广度优先搜索-白红宇

算法导论第22章22.2广度优先搜索

阅读量：4307 次

发布时间：2019-06-06

本文共 5686 字，大约阅读时间需要 18 分钟。

/* * IA_22.2BreadthFirstSearch.h * *  Created on: Feb 13, 2015 *      Author: sunyj */#ifndef IA_22_2BREADTHFIRSTSEARCH_H_#define IA_22_2BREADTHFIRSTSEARCH_H_#include 
    
     #include 
     #include "IA_10.1queue.h"#include "IA_10.2LinkedLists.h"#include 
      
       using std::map;using std::vector;using std::pair;using std::cout;using std::endl;enum Color { white, grey, black };class NodeData {public:    // use INT64_MAX must include 
       
         and using compiler g++ 4.7.0    // and then g++ -std=c++11, be carefull not c++0x in the centos 64bit operating system    NodeData() : color(white), par(nullptr), depth(INT64_MAX) { }    NodeData(Color const c) : color(c), par(nullptr), depth(INT64_MAX) { }    NodeData(const NodeData& nd)    {        color = nd.color;        par   = nd.par;        depth = nd.depth;    }private:public:    Color    color;    void*    par;    int64_t  depth;};// BFS(G, s)// for each vertex u belongs to G.V - {s}//     u.color = white//     u.d = INT64_MAX//     u.par = NIL// s.color = grey// s.d     = 0// s.par   = NIL// Q = empty// ENQUEUE(Q, s)// while(Q != empty)//     u = DEQUEUE(Q);//     for each v belongs to G.Adj[u]//         if v.color == white//             v.color = grey//             v.d = u.d + 1//             v.par = u//             ENQUEUE(Q, v)//     u.color = black// PRINT-PATH(G, s, v)// if v == s//     print s// elseif v.par == NIL//     print "no path from" s "to" v "exists"// else PRINT-PATH(G, s, v.par)//     print vtemplate 
        
          class Graph {public:	typedef Node
         
          * PVertex; bool PrintPath(PVertex s, PVertex v) { if (s == v) { cout << s->key << " "; return true; } else if (nullptr == v->data.par) { cout << "no path from s to v exists" << endl; return false; } else { if (PrintPath(s, static_cast
          
           (v->data.par))) { cout << v->key << " "; return true; } else { return false; } } } // Type: int, charactor // T: the data that the Node carry void DFS(PVertex s) { s->data.color = grey; s->data.depth = 0; QueueDFS.enqueue(s); while (!QueueDFS.empty()) { PVertex u; QueueDFS.dequeue(u); typename map
           
            * >::iterator iter = MapAdj.find(u->key); if (MapAdj.end() != iter) // { Node
            
             * pNil = iter->second->GetNil(); Node
             
              * x = pNil->next; while (pNil != x) { // cout << x->key << " "; if (white == (*x->data).data.color) { (*x->data).data.color = grey; (*x->data).data.depth += u->data.depth + 1; (*x->data).data.par = u; QueueDFS.enqueue(x->data); cout << "node " << (*x->data).key << " is grey now" << endl; } x = x->next; } u->data.color = black; cout << "node " << u->key << " is black now" << endl; } } return ; } Graph(int const n) : MaxCount(n), QueueDFS(MaxCount) { }// assume the graphic has less than 100 vertex void InsertVertex(Node
              
               * v) { MapVertex.insert(pair
               
                (v->key, v)); LinkedList
                
                 * pLinkedList = new LinkedList
                 
                  ; MapAdj.insert(pair
                  
                   * >(v->key, pLinkedList)); } void InsertEdge(PVertex v1, PVertex v2) { typename map
                   
                    ::const_iterator VIter = MapVertex.find(v1->key); if (MapVertex.end() == VIter) { cout << "v1 is not a vertex of graphic" << endl; return ; } VIter = MapVertex.find(v2->key); if (MapVertex.end() == VIter) { cout << "v2 is not a vertex of graphic" << endl; return ; } typename map
                    
                     * >::iterator iter = MapAdj.find(v1->key); if (MapAdj.end() != iter) // should be found, otherwise program logic is wrong { if (nullptr == iter->second->search(v2->key)) { // Node
                     
                       is a Type, and the type is for Vertex of Graph // Type is a Type, and the type is for the key of the Node(Vertex), key is the attr and diff one // node(Vertex) to another. // T is a Type, and the type is for other information of the Node(Vertex), something like color, etc. Node
                      
                       * pNode = new Node
                       
                        ; pNode->data = v2; pNode->key = v2->key; iter->second->insert(pNode); } else { cout << "edge has already exist" << endl; } } } void PrintAdj(Node
                        
                         * p) { typename map
                         
                          * >::iterator iter = MapAdj.find(p->key); if (MapAdj.end() != iter) { Node
                          
                           * pNil = iter->second->GetNil(); Node
                           
                            * x = pNil->next; while (pNil != x) { cout << x->key << " "; // cout << (*x->data).key << " " ; x = x->next; } cout << endl; } }private: map
                            
                              MapVertex; // vertex map
                             
                              * > MapAdj; // adjacency list int const MaxCount; queue
                              
                                QueueDFS;};#endif /* IA_22_2BREADTHFIRSTSEARCH_H_ */

/* * IA_22.2BreadthFirstSearch.cpp * *  Created on: Feb 13, 2015 *      Author: sunyj */#include "IA_22.2BreadthFirstSearch.h"int main(){    Graph
    
      g(1000); // 1000 vertex at most    Node
     
       r('r');    Node
      
        s('s');    Node
       
         t('t');    Node
        
          u('u');    Node
         
           v('v'); Node
          
            w('w'); Node
           
             x('x'); Node
            
              y('y'); g.InsertVertex(&r); g.InsertVertex(&s); g.InsertVertex(&t); g.InsertVertex(&u); g.InsertVertex(&v); g.InsertVertex(&w); g.InsertVertex(&x); g.InsertVertex(&y); g.InsertEdge(&r, &s); g.InsertEdge(&r, &v); g.InsertEdge(&s, &r); g.InsertEdge(&s, &w); g.InsertEdge(&w, &x); g.InsertEdge(&w, &t); g.InsertEdge(&t, &x); g.InsertEdge(&t, &u); g.InsertEdge(&x, &y); g.InsertEdge(&x, &u); g.InsertEdge(&u, &y); g.InsertEdge(&v, &r); g.InsertEdge(&w, &s); g.InsertEdge(&t, &w); g.InsertEdge(&x, &w); g.InsertEdge(&x, &t); g.InsertEdge(&u, &t); g.InsertEdge(&y, &x); g.InsertEdge(&u, &x); g.InsertEdge(&y, &u); g.PrintAdj(&r); g.PrintAdj(&s); g.PrintAdj(&t); g.PrintAdj(&u); g.PrintAdj(&v); g.PrintAdj(&w); g.PrintAdj(&x); g.PrintAdj(&y); g.DFS(&s); g.PrintPath(&r, &v); cout << endl; g.PrintPath(&s, &v); cout << endl; g.PrintPath(&s, &t); cout << endl; g.PrintPath(&s, &x); cout << endl; g.PrintPath(&s, &y); cout << endl; g.PrintPath(&r, &x); cout << endl; return 0;}