Desktop Programming > C/C++ & Visual C++
Directed Graphs (digraph) and Weighted Directed Graphs (wdigraph) ...
David:
Update: FREE homework help NOW available ...
You can contact me via:
http://sites.google.com/site/andeveryeyeshallseehim/home/he-comes
http://developers-heaven.net/forum/index.php/board,9.0.html
The subject of Graphs, Directed Graphs and Weighted Directed Graphs can be quite daunting (especially at first) ...
This site will feature some simple beginning steps ... and a collation of example code, that was recently found on the web ... but here it is all together ... edited, fixed and polished some ... to help make it all ... work for YOU!
Here is a little C++ example, to get you started ... that uses an adjacency list ...(Google it) ...
Check it out.
It simply tests and reports if a target vertex is reachable from some start vertex.
An example might be ... can one get from one place ... in a maze ... to some other?
--- Code: ---// a_isReachable.cpp // // 2014-12-08 //
// a DiGraph (Directed Graph) using an adjacency list //
/*
Edited/augmented & fixed memory leaks
now uses STL vector containers, etc (instead of new arrays, etc)
Idea and original code found at:
http://www.sanfoundry.com/cpp-program-find-shortest-path-between-two-vertices-using-dijkstras-algorithm/
This program simply tells if a node 'd', (the destination),
is 'reachable' from 's', (the start),
(the node from which we start the search to see if
there exists any 'reachable path')
The 'digraph' here is unweighted ...
The program stops and reports 'reachable' at the first
'reachable' path encountered as it traverses the 'graph'
*/
#include <iostream>
#include <vector>
#include <list>
#include <string> // re. more() ...
#include <cctype> // re. tolower(..)
#include <algorithm> // re. swap
using namespace std;
// This class represents a directed graph
// (a simple un-weighted digraph)
// using an adjacency list representation ... //
class Graph
{
vector< list< int > > adj;
public:
// ctor... v is number of Verticies (Nodes)
Graph( int v );
// function to add an edge to graph
void addEdge( int p, int q ) ;
// returns true if there is a path from s to d, other wise returns false
bool isReachable( int s, int d );
// a wrapper function to return size 'vector< list< int > > adj'
size_t size() const { return adj.size() ; }
friend ostream& operator << ( ostream&, const Graph& );
} ;
// def'ns
ostream& operator << ( ostream& os, const Graph& g )
{
int size = g.adj.size();
if( size )
{
list< int >::const_iterator it;
for( int i = 0; i < size; ++ i )
{
for( it = g.adj[i].begin(); it != g.adj[i].end(); ++ it )
os << '(' << i << ','<< *it << ") ";
os << '\n';
}
}
return os;
}
Graph::Graph( int v ) // ctor...
{
adj.resize( v );
}
void Graph::addEdge( int v, int w )
{
adj[v].push_back( w ) ; // Add w to v’s list.
}
// A BFS (Breadth First Search) based function ...
// to check whether d is reachable from s.
// Note the use of a queue (a list < int > here)... FIFO //
bool Graph::isReachable( int s, int d )
{
// Base case ...
if( s == d )
return true;
// construct & (initial) all the vertices as not yet visited ...
vector< bool > visited ( this->size(), false );
// construct an empty queue (a list of int) for BFS ...
list< int > queue;
// set the current node as visited and enqueue it
visited[s] = true;
queue.push_back(s);
while( !queue.empty() )
{
// Dequeue a vertex from queue ...
s = queue.front();
queue.pop_front();
// iterator 'it' will be used to get all the
// adjacent vertices of a vertex ...
list< int >::iterator it;
// Get all adjacent vertices of the dequeued vertex s
// If an adjacent has not been visited, then mark it visited
// and enqueue it
for( it = adj[s].begin(); it != adj[s].end(); ++it )
{
// If this adjacent node is the destination node, then return true
if ( *it == d )
return true;
// Else, continue to do BFS
if( !visited[*it] )
{
visited[*it] = true;
queue.push_back(*it);
}
}
}
return false;
}
// utiliites to facilitate valid input in a loop ... //
int takeInChr( const std::string& msg = "" )
{
std::cout << msg << flush;
std::string reply;
getline( cin, reply );
if( reply.size() )
return reply[0];
// else ...
return 0;
}
bool more()
{
if( tolower( takeInChr( "\n\nMore (y/n) ? " )) == 'n' )
return false;
// else ...
return true;
}
bool uvOkRange( int u, int v, int topVal )
{
bool goodData = true;
if( u < 0 || u > topVal )
{ cout << '\n' << u << " NOT in range 0.."
<< topVal << '\n'; goodData = false; }
if( v < 0 || v > topVal )
{ cout << '\n' << v << " NOT in range 0.."
<< topVal << '\n'; goodData = false; }
return goodData;
}
// Driver program to test methods of graph class
int main()
{
// construct an empty graph to hold 5 Verticies (5 Nodes) ..
Graph g(5);
// get adjacent nodes for each node in graph ...
g.addEdge(0, 1); // 1 'is reachable' from 0
g.addEdge(0, 2); // 2 'is reachable' from 0
g.addEdge(1, 3); // 3 'is reachable' from 1
g.addEdge(2, 1);
g.addEdge(2, 3);
g.addEdge(2, 4);
g.addEdge(3, 4);
g.addEdge(4, 4);
do
{
cout << "The graph g: \n"<< g ;
cout << "\nEnter 2 int's separated by a space ..."
<< "\nthe source and destination vertices, in range 0..4 : ";
int u, v;
if( cin >> u >> v && cin.get() == '\n' && uvOkRange( u, v, 4 ) )
{
int count = 2;
while( count-- )
{
cout << "\nThere is "
<< (g.isReachable(u, v) ? "a " : "NO ")
<< "path from " << u << " to " << v;
swap( u, v );
}
}
else
{
cin.clear();
cin.sync();
cout << "\nData entry error ...\n";
}
}
while( more() );
}
--- End code ---
For a easy way to download all these example programs, see ...
http://www.4shared.com/folder/WUykX6-t/DiGraphsAndWDiGraphs.html
Addendum:
This subject ... of how to reach a place ... leads to ... a much BIGGER context !!!
After several days of many hours each ... I suddenly was impressed ... that the structure and the meaning of any notation ... is so important!
Abstract symbols have meaning only in pre-defined (real) context.
For example:
What do I mean when I say (two, to, too, ... ) ?
The same sound has several spellings to help differentiate the meaning provided by different contexts ...
It's really quite amazing what a bird's eye look/see ...
by any of God's seeing creation ... can do!
In terms of reach-ability ...
How can (fleshly/finite) man, (ever) see/reach the (invisible infinite Spirit), the Creator of this whole large universe?
Well ... firstly, everything created tells much regarding the creator ...
Firstly ... that a Creator exists!
And much more !!!
But ... since we can see, hear, speak, move, love, hate ... so much more our Creator!
So did / does our creator ever re-veal beyond what the created things speak?
Yes ... the history of this ... His-Story ... is well established and preserved ...
passed on by those to whom it was chosen to be entrusted.
There is a steady line drawn from Adam via Seth, to Noah and via Shem, to Abraham and via Isaac, Jacob/Israel, Judah ... to Yeshua the Messiah, who was also fore-named Emmanuel (i.e. the creator El to be with us, the creator who in the beginning, as Elohim, created the heavens and the earth.)
Please continue at:
http://developers-heaven.net/forum/index.php/topic,2587.0.html
David:
This next little example, with imbedded links, is coded in Python 3...
You may like to play with it as you study the link and example code ...
And further read up on:
Breadth First Search (bfs)
vs
Depth First Search (dfs)
--- Code: ---# graph_2.py # # 2014-12-07 # # a simple Python 3 implementation #
'''
See:
http://www.inf.ed.ac.uk/teaching/courses/inf2b/algnotes/slides-full09.pdf
Inf 2B: Graphs, BFS, DFS
Kyriakos Kalorkoti
School of Informatics
University of Edinburgh
'''
Vx = ( 0,1,2,3,4,5,6 )
E = ( (0,2),(0,4),(0,5),(1,0),(2,1),(2,5),(3,1),(3,6),(4,0),(4,5),(6,3),(6,5) )
G = ( Vx, E )
LstAdjLsts = ( (2,4,5),(0,),(1,5),(1,6),(0,5),(),(3,5) )
def showLstAdjLsts():
print( "Showing LstAdjLsts..." )
for i, e in enumerate(LstAdjLsts):
for ee in e:
print( (i, ee), end = ' ' )
print()
def bfsStartAt( v ):
visited = [ False ]*len(Vx)
visited[v] = True
print( v, end = ' ' )
Q = []
Q.append(v)
while( Q ):
v = Q[0]
Q = Q[1:]
for w in LstAdjLsts[v]:
if visited[w] == False:
visited[w] = True
print( w, end = ' ' )
Q.append(w)
print( "\nShowing visited :", visited )
def dfsStartAt( v ):
visited = [ False ]*len(Vx)
Stk = []
Stk.append(v)
while( Stk ):
v = Stk[-1]
Stk = Stk[0:-1]
if visited[v] == False:
visited[v] = True
print( v, end = ' ' )
for w in LstAdjLsts[v]:
Stk.append(w)
print( "\nShowing visited :", visited )
# the recursive part #
def dfs_r( s, visited ):
visited[s] = True
print( s, end = ' ' )
# using reversed order here
# so output will match non_recursive
# (using local stack) call above ...
for w in reversed(LstAdjLsts[s]):
if visited[w] == False:
dfs_r( w, visited )
def dfsStartAt_r( v ):
visited = [ False ]*len(Vx)
dfs_r( v, visited )
print( "\nShowing visited :", visited )
showLstAdjLsts()
loop = 0
while loop < 7 :
print( "\nShowing bfsStartAt(", loop, ") : ", end = '' )
bfsStartAt( loop )
print( "\nShowing dfsStartAt(", loop, ") : ", end = '' )
dfsStartAt( loop )
print( "Showing dfsStartAt_r(", loop, ") : ", end = '' )
dfsStartAt_r( loop )
loop += 1
if loop < 7:
input( "Press 'Enter' to continue ... " )
else:
input( "\n\n\n*** Press 'Enter' to EXIT *** " )
--- End code ---
David:
Now we will jump to C ...
this similar demo ...
(as the Python one above, but in C, and using a MATRIX, instead of an adjacency list)
bfs
vs
dfs (recursive and non-recursive)
You will first need to get a copy of file Clist.h ... as it needs to be included.
It is available here:
http://developers-heaven.net/forum/index.php/topic,2582.0.html
Note: we need a stack (a Clist) and a queue (a Clist) to push and pop data ...
--- Code: ---/* c_reachable_dfsVSbfs_matrix_c.c */ /* rev. 2014-12-08 */
/* using some globals here to keep code similar...
to related (coded in Python) example ... */
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <limits.h> /* re. INT_MAX */
/**********************************************************
*** re. using Clist.h for stack and queue *** */
typedef struct ClistOfInt
{
int val;
struct ClistOfInt* next;
} List ; /* i.e. ... a node/element/record in the list ...*/
typedef List* pList;
void clearLrec( pList p )
{
/* no dynamic Cstrings, etc... to free here ... */
}
#ifndef dwMYASSERT
#define dwMYASSERT
void myAssert( int condition, const char text[] )
{
if( !condition )
{
fprintf(stderr, "%s\n", text );
fputs( "Press 'Enter' to exit program ... ", stderr );
getchar();
exit(1);
}
}
#endif
/**********************************************************/
/* above needed by Clist.h */
#include "Clist.h" /* to use ClistOfInt as stack and queue */
/* using some globals here for simpler code ... */
#define N 9 /* N is no of vertices in Graph */
const int G[N][N] = /* Create an example graph ... */
{
{ 0, 4, 0, 0, 0, 0, 0, 8, 0 },
{ 4, 0, 8, 0, 0, 0, 0,11, 0 },
{ 0, 8, 0, 7, 0, 4, 0, 0, 2 },
{ 0, 0, 7, 0, 9,14, 0, 0, 0 },
{ 0, 0, 0, 9, 0,10, 0, 0, 0 },
{ 0, 0, 4, 0,10, 0, 2, 0, 0 },
{ 0, 0, 0,14, 0, 2, 0, 1, 6 },
{ 8,11, 0, 0, 0, 0, 1, 0, 7 },
{ 0, 0, 2, 0, 0, 0, 6, 7, 0 }
} ;
int VISITED[N]; /* graph is stored in matrix G[N][N ] */
void dfs_r( int, int );
void isReachable_dfs( int s, int d );
void showGraph( const int g[N][N] );
/* coded for this added function is at bottom here ...
so can use as stack (with push_front) and queue (with push_back) */
int popClist( Clist* pLst ) ;
void isReachable_dfs_non_recursive( int s, int d );
void isReachable_bfs( int s, int d );
int main()
{
int j, k;
puts( "Showing Graph ... " );
showGraph( G );
putchar( '\n' );
for( j = 0; j < N; ++ j )
{
printf( "Showing isReachable_dfs(s=%d,d=%d) : ", 3, j );
isReachable_dfs( 3, j ); /* begin at 3 */
putchar( '\n' );
}
printf( "\nPress 'Enter' to continue ... " );
while( getchar() != '\n' ) ;
for( j = 0; j < N; ++ j )
{
printf( "Showing isReachable_dfs(s=%d,d=%d) : ", j, 3 );
isReachable_dfs( j, 3 ); /* begin at 3 */
putchar( '\n' );
}
printf( "\nPress 'Enter' to continue ... " );
while( getchar() != '\n' ) ;
for( j = 0; j < N; ++ j )
{
for( k = 0; k < N; ++ k )
{
if( j != k )
{
printf( "now doing 'is reachable_dfs(%15d, %d)' : ", j, k ) ;
isReachable_dfs( j, k );
putchar( '\n' );
printf( "now doing 'is reachable_dfs_non_recursive(%d, %d)' : ", j, k ) ;
isReachable_dfs_non_recursive( j, k );
putchar( '\n' );
printf( "now doing 'is reachable_bfs(%15d, %d)' : ", j, k ) ;
isReachable_bfs( j, k );
puts( "\n" );
}
}
printf( "\nPress 'Enter' to continue ... " );
while( getchar() != '\n' ) ;
}
printf( "\nPress 'Enter' to EXIT ... " ); fflush( stdout );
while( getchar() != '\n' );
return 0;
}
/* ... just to call recursive drf_r... */
void isReachable_dfs( int s, int d )
{
int j;
for( j = 0; j < N; ++j ) /* initial all 'visited' to zero */
VISITED[j] = 0; /* using GLOBAL array here ... */
dfs_r( s, d );
}
/* begin recursive ... starting from i */
void dfs_r( int i, int d )
{
int j;
VISITED[i] = 1; /* Now mark this 'i' as visited ... */
printf( "%d ", i ); /* show 'i' here at top ... */
if( i == d )
{
printf( "found " );
return;
}
/* push in reversed order here, so ...
output will match non-recursive calls. */
for( j = N-1; j >= 0; --j )
if( !VISITED[j] && G [i][j] ) /* if NOT visited and reachable */
dfs_r( j, d );
}
void isReachable_dfs_non_recursive( int s, int d )
{
int j;
Clist stk;
List lst;
lst.val = s;
initClist( &stk );
for( j = 0; j < N; ++j ) /* initial all 'visited' to zero */
VISITED[j] = 0; /* using GLOBAL array here ... */
push_frontClist( &stk, &lst );
while( stk.size )
{
int cur = popClist( &stk );
if( !VISITED[cur] )
{
/* Now mark this 'i' as visited ... */
VISITED[cur] = 1;
printf( "%d ", cur ); /* show 'cur' here at top */
if( cur == d )
{
printf( "found " );
break;
}
/* for all j reachable from cur ... */
for( j = 0; j < N; ++j )
{
if( G[cur][j] )
{
lst.val = j;
push_frontClist( &stk, &lst );
}
}
}
}
clearClist( &stk ); /* make sure to free any dynamic memory */
}
void isReachable_bfs( int s, int d )
{
int j;
Clist que;
List lst;
lst.val = s;
initClist( &que );
for( j = 0; j < N; ++j ) /* initial all 'visited' to zero */
VISITED[j] = 0; /* using GLOBAL array here ... */
VISITED[j] = 1;
printf( "%d ", s );
if( s == d )
{
printf( "found " );
return;
}
push_backClist( &que, &lst );
while( que.size )
{
int cur = popClist( &que );
/* for all (not-visited) j reachable from cur ... */
for( j = 0; j < N; ++ j )
{
if( !VISITED[j] && G[cur][j] )
{
VISITED[j] = 1;
printf( "%d ", j );
if( j == d )
{
printf( "found " );
break;
}
lst.val = j;
push_backClist( &que, &lst );
}
}
}
clearClist( &que ); /* make sure to free any dynamic memory */
}
void showGraph( const int g[N][N] )
{
int i, j;
for( i = 0; i < N; ++ i )
{
for( j = 0; j < N; ++ j )
printf( "%3d ", g[i][j] );
putchar( '\n' );
}
}
int popClist( Clist* pLst )
{
if( pLst->size )
{
pList cur = pLst->start;
int tmp = cur->val;
pLst->start = cur->next;
free( cur );
--pLst->size;
if( pLst->size < 2 )
{
pLst->isSorted = 1;
pLst->end = pLst->start;
}
return tmp;
}
return INT_MAX;
}
--- End code ---
David:
Back to C++ ...
And adjacency lists ...
This simple example is very similar to the first, that just searches for a vertex ... to indicate if it IS reachable?.
(But it demos the use of a set to track the nodes already visited, and not an array or vector.)
See if you can find the very few edits here to go from the first example program that used a STL vector?
--- Code: ---// a_isReachable_visitedSET.cpp // // 2014-12-08 //
// a DiGraph (Directed Graph) using an adjacency list //
#include <iostream>
#include <vector>
#include <list>
#include <set> // re. tracking visted ... //
#include <string> // re. more() ...
#include <cctype> // re. tolower(..)
#include <algorithm> // re. swap
using namespace std;
/*
Edited/augmented & fixed memory leaks
now uses STL vector containers, etc (instead of new arrays, etc)
Idea and original code found at:
http://www.sanfoundry.com/cpp-program-find-shortest-path-between-two-vertices-using-dijkstras-algorithm/
This program simply tells if a node 'd', (the destination),
is 'reachable' from 's', (the start),
(the node from which we start the search to see if
there exists any 'reachable path')
The 'digraph' here is unweighted ...
The program stops and reports 'reachable' at the first
'reachable' path encountered as it traverses the 'graph'
*/
// This class represents a directed graph
// (a simple un-weighted digraph)
// using an adjacency list representation ... //
class Graph
{
vector< list< int > > adj;
public:
// ctor... v is number of Verticies (Nodes)
Graph( int v );
// function to add an edge to graph
void addEdge( int p, int q ) ;
// returns true if there is a path from s to d, other wise returns false
bool isReachable( int s, int d );
// a wrapper function to return size 'vector< list< int > > adj'
size_t size() const { return adj.size() ; }
friend ostream& operator << ( ostream&, const Graph& );
} ;
// def'ns
ostream& operator << ( ostream& os, const Graph& g )
{
int size = g.adj.size();
if( size )
{
list< int >::const_iterator it;
for( int i = 0; i < size; ++ i )
{
for( it = g.adj[i].begin(); it != g.adj[i].end(); ++ it )
os << '(' << i << ','<< *it << ") ";
os << '\n';
}
}
return os;
}
Graph::Graph( int v ) // ctor...
{
adj.resize( v );
}
void Graph::addEdge( int v, int w )
{
adj[v].push_back( w ) ; // Add w to v’s list.
}
// A BFS (Breadth First Search) based function ...
// to check whether d is reachable from s.
// Note the use of a queue ... FIFO ... //
bool Graph::isReachable( int s, int d )
{
// Base case ...
if( s == d )
return true;
// to hold verticied that habe been visited ...
set< int > visited;
// construct an empty queue (a list of int) for BFS ...
list< int > queue;
// set the current node as visited and enqueue it
visited.insert(s);
queue.push_back(s);
while( !queue.empty() )
{
// Dequeue a vertex from queue ...
s = queue.front();
queue.pop_front();
// iterator 'it' will be used to get all the
// adjacent vertices of a vertex ...
list< int >::iterator it;
// Get all adjacent vertices of the dequeued vertex s
// If an adjacent has not been visited, then mark it visited
// and enqueue it
for( it = adj[s].begin(); it != adj[s].end(); ++it )
{
// If this adjacent node is the destination node, then return true
if ( *it == d )
return true;
// Else, continue to do BFS
if( !visited.count(*it) )
{
visited.insert(*it);
queue.push_back(*it);
}
}
}
return false;
}
// utiliites to facilitate valid input in a loop ... //
int takeInChr( const std::string& msg = "" )
{
std::cout << msg << flush;
std::string reply;
getline( cin, reply );
if( reply.size() )
return reply[0];
// else ...
return 0;
}
bool more()
{
if( tolower( takeInChr( "\n\nMore (y/n) ? " )) == 'n' )
return false;
// else ...
return true;
}
bool uvOkRange( int u, int v, int topVal )
{
bool goodData = true;
if( u < 0 || u > topVal )
{ cout << '\n' << u << " NOT in range 0.."
<< topVal << '\n'; goodData = false; }
if( v < 0 || v > topVal )
{ cout << '\n' << v << " NOT in range 0.."
<< topVal << '\n'; goodData = false; }
return goodData;
}
// Driver program to test methods of graph class
int main()
{
// construct an empty graph to hold 5 Verticies (5 Nodes) ..
Graph g(5);
// get adjacent nodes for each node in graph ...
g.addEdge(0, 1); // 1 'is reachable' from 0
g.addEdge(0, 2); // 2 'is reachable' from 0
g.addEdge(1, 3); // 3 'is reachable' from 1
g.addEdge(2, 1);
g.addEdge(2, 3);
g.addEdge(2, 4);
g.addEdge(3, 4);
g.addEdge(4, 4);
do
{
cout << "The graph g: \n"<< g ;
cout << "\nEnter 2 int's separated by a space ..."
<< "\nthe source and destination vertices, in range 0..4 : ";
int u, v;
if( cin >> u >> v && cin.get() == '\n' && uvOkRange( u, v, 4 ) )
{
int count = 2;
while( count-- )
{
cout << "\nThere is "
<< (g.isReachable(u, v) ? "a " : "NO ")
<< "path from " << u << " to " << v;
swap( u, v );
}
}
else
{
cin.clear();
cin.sync();
cout << "\nData entry error ...\n";
}
}
while( more() );
}
--- End code ---
David:
More C++ ... Note that this example program needs a C++11 compiler.
More ... and you may like to NOTE the embedded comments in the program here and also the comments at the embedded links ... in the program.
bfs
vs
dfs
Note the C examples above used a Matrix ... whereas ... this C++ example uses an adjacency list.
--- Code: ---// bfs_vs_dfs.cpp // // 2014-12-06 // // use a C++11 compiler //
// Note: this program is an attempt to demo what was said at link below ... //
// using globals here to keep 'match' simple and close to given code ... //
#include <iostream>
#include <vector>
#include <list>
#include <set>
using namespace std;
/*
http://www.ics.uci.edu/~eppstein/161/960215.html
With a little care it is possible to make BFS and DFS look almost
the same as each other ...
(as similar as, say, Prim's and Dijkstra's algorithms are to each other):
(1)
bfs(G)
{
list L = empty
tree T = empty
choose a starting vertex x
search(x)
while(L nonempty)
remove edge (v,w) from start of L
if w not yet visited
{
add (v,w) to T
search(w)
}
}
vs
(2)
dfs(G)
{
list L = empty
tree T = empty
choose a starting vertex x
search(x)
while(L nonempty)
remove edge (v,w) from end of L
if w not yet visited
{
add (v,w) to T
search(w)
}
}
search(vertex v)
{
visit(v);
for each edge (v,w)
add edge (v,w) to end of L
}
Both of these search algorithms now keep a list of edges to explore;
the only difference between the two is that,
while both algorithms adds items to the end of L,
BFS removes them from the beginning,
(which results in maintaining the list as a queue),
while DFS removes them from the end,
(maintaining the list as a stack).
*/
typedef vector< list < int > > Graph;
// globals used here ... (to keep code closer match to given example)
// construct an empty graph g, (to hold 5 Verticies (5 Nodes) )
Graph G;
list< int > L; // the adjancey list ...
set < int > T; // the (red-black?) Tree (set) to track visited Nodes ... //
ostream& operator << ( ostream& os, const Graph& g )
{
int size = g.size();
if( size )
{
for( int i = 0; i < size; ++ i )
{
for( auto e : g[i] )
os << '(' << i << ','<< e << ") ";
os << '\n';
}
}
return os;
}
void search( int v )
{
// visit(v);
cout << v << ' ';
T.insert(v);
for( auto e: G[v] ) L.push_back( e );
}
void bfs( int s )
{
L.clear(); // list L = empty
T.clear(); // tree T = empty
// choose a starting vertex x ... passed in s at top
search(s);
while( !L.empty() ) // while(L not empty)
{
// remove edge (v,w) from *START* of L
int target = L.front();
L.pop_front();
if( !T.count(target) ) // if w not yet visited
{
T.insert(target); //add (v,w) to T
search(target);
}
}
}
void dfs( int s )
{
L.clear(); // list L = empty,
T.clear(); // tree T = empty
// choose a starting vertex x ... passed in s at top
search(s) ;
while( !L.empty() ) // while(L not empty)
{
// remove edge (v,w) from *END* of L
int target = L.back();
L.pop_back();
if( !T.count(target) ) // if w not yet visited
{
T.insert(target); //add (v,w) to T
search(target);
}
}
}
int main()
{
G.resize(5);
// get adjacent nodes for each node in graph ...
G[0].push_back(1); // 1 'is reachable' from 0
G[0].push_back(2); // 2 'is reachable' from 0
G[1].push_back(3); // 3 'is reachable' from 1
G[2].push_back(1);
G[2].push_back(3);
G[2].push_back(4);
G[3].push_back(4);
G[4].push_back(4);
cout << "Showing Graph G : \n" << G;
for( int i = 0; i < 5; ++ i )
{
cout << "\nShowing bfs(" << i << ") : ";
bfs( i );
cout << "\nShowing dfs(" << i << ") : ";
dfs( i );
cout << "\n";
}
cout << "\nPress 'Enter' to continue/exit ... " << flush;
cin.get();
}
--- End code ---
Navigation
[0] Message Index
[#] Next page
Go to full version