18.2 Graph Search
template <class Graph > class SEARCH
{
protected:
const Graph &G;
int cnt;
vector<int> ord;
virtual void search (Edge) = 0;
void search(){
for(int v = 0; v<G.V(); v++)
if(ord[v] == -1) searchC(Edge(v,v));
}
public:
SEARCH(const Graph &G): G(G),
ord(G.V(),-1), cnt(0) {}
int operator[](int v) const {return ord[v];}
};
We typically use graph-search function that performs these steps until all of the vertices of the graph have been marked as having been visited:
**Program 18.3 Derived class for depth-first search for computing a spanning forest from SEARCH base class of 18.2 **
private vector st here holds a parent-link representation of tree that we initialize in the constructor. So basically this allows anyone know the parent of any vertex easily.
template <class Graph>
class DFS : public SEARCH<Graph>
{
vector<int> st;
void searchC(Edge e)
{
int w = e.w;
ord[w] = cnt++; st[e.w] = e.v;
typename Graph::adjIterator A(G,w);
for(int t = A.beg(); !A.end(); t = A.nxt())
if(ord[t] == -1) searchC(Edge(w,t));
}
public :
DFS(const Graph &G) : SEARCH<Graph> (G),
st(G.V(), -1) { search(); }
int ST(int v) const {return st[v];}
};
Property 18.2 A graph-search function checks each edge and marks each vertex in a graph if an only if the search function that it uses marks each vertex and checks each edge in the connected component that contains the start vertex.
Proof : By induction on the number of connected components.
Property 18.3 DFS of a graph represented with an adjacency matrix requires time proportional to
Property 18.4 DFS of a graph represented with adjacency lists requires time proportional to
18.3 and 18.4 implies that search is linear in size of data structure used to represent the graph.
If time per vertex is bounded by some function