C++算法-图算法-04

第2章 图搜索

主要是深度优先搜索（DFS）和广度优先搜索（BFS）。

2.1 探索迷宫

用迷宫来代替图、用隧道来代替边、并用交叉点来代替顶点，这将有助于使我们对这个问题有直观的认识。

探索迷宫而不至于迷路的技巧就是难着一个线团并在身后留下线。这些线总能帮助我们找到一个出口，不过，我们还关心确实能够探索到迷宫的每一个部分，而且除非迫不得已，我们并不希望走回头路。

 

假设在每个交叉点都有灯，而且开始时这些灯都是关着的，另外在每个通道的尽头都有门，开始时也是关着的。进一步假设这些门有窗户，而且灯光足够强，另外通道足够直，从而使我们可以通过打开通道某一端的门就能确定另一端交叉点处的等是否打开（即使另一段的门是关闭的）。我们的目标是打开所有的灯和所有的门。

迷宫探索策略：

1.如果当前交叉点没有关闭的门，转向3。否则，对于指向当前交叉点的任何通道，打开任何关闭的门（并令这扇门一直打开）。

2.如果可以看到通道另一端的交叉点上已经开灯，则尝试当前交叉点的另一个门（1）。否则（如果看到通道另一端的交叉点上没有开灯），则沿着通道走到该交叉点，在走的过程中放线绳，打开灯后再转向第1步。

3.如果当前交叉点的所有门都是打开的，则检查是否回到了起始点。如果是，就停止。否则利用线绳再沿着某条通道（第一次正是沿着此通道来到此交叉点）走回去，在回去的途中将相应的线绳卷起，并寻找另一扇关闭的门（也就是说，回到1）。

采用Tremaux迷宫探索方法时，可以打开迷宫中所有的灯，并打开所有的门，最后回到起始位置。

2.2 深度优先搜索

 

 

#include <vector>
template <class Graph> class cDFS
{
    int cnt;
    const Graph $G;
    vector <int> ord;
    void searchC(int v)
    {
        ord[v]=cnt++;
        typename Graph::adjIterator A(G,v);
        for(int t=A.beg();!A.end();t=A.nxt())
            if(ord[t]==-1) searchC(t);
    }
public:
    cDFS(const Graph &G,int v=0):
        G(G),cnt(0),ord(G.V(),-1)
    {
        searchC(v);
    }
    int count() const {return cnt;}
    int operator[](int v) const {return ord[v];}
}


2.3 图搜索ADT函数

图搜索

下面的基类用于处理可能不连通的图。

#include <vector>
template <class Graph> class SEARCH
{
protected:
    int cnt;
    const Graph $G;
    vector <int> ord;
    virtual void searchC(Edge)=0;
    void search()
    {
        for(int v=0;v<G.V();v++)
            if(ord[t]==-1) searchC(Edge(v,v));
    }
public:
    SEARCH(const Graph &G):G(G),cnt(0),ord(G.V(),-1){}
    int operator[](int v) const {return ord[v];}
}


我们向搜索函数传递了一条边（对于每个连通分量，第一次调用时使用一个虚拟的自环）作为参数，而非传递其目标顶点，因为边可以告诉我们如何指向该顶点。