Suppose that G is a directed graph. In class we discussed an algorithm that will
ID: 3805498 • Letter: S
Question
Suppose that G is a directed graph. In class we discussed an algorithm that will determine whether a given vertex can reach every other vertex in the graph (this is the 1-to-many reachability problem). Consider the following similar problem: given graph G, is there any node in G that can reach every other node in G? Such a node is called a "source node". We want to know whether any node of G is a source node. A trivial algorithm for this is to execute DFS n times, using each node in G as the start node of the DFS. But the total time for this algorithm is O(n* (n+m)) Describe a linear time algorithm for this "does di-graph G have a source node problem
Explanation / Answer
The Source Node from which all nodes are reachable can be found in O(V+E) time where V=no. of vertices and E=no.of edges. It is based on idea of Kosaraju’s Strongly Connected Component Algorithm.
If there exist such source node then one of the such node is the last finished vertex in DFS. A node is finished in DFS if recursive call for it is over which means all descendants of the vertex have been visited.
Algorithm :
Implementation in C++:
#include <bits/stdc++.h>
using namespace std;
class Graph
{
int V; // No. of vertices
list<int> *adj; // adjacency lists
// A recursive function to print DFS starting from v
void DFSUtil(int v, vector<bool> &visited);
public:
Graph(int V);
void addEdge(int v, int w);
int findSource();
};
Graph::Graph(int V)
{
this->V = V;
adj = new list<int>[V];
}
// A recursive function to print DFS starting from v
void Graph::DFSUtil(int v, vector<bool> &visited)
{
// Mark the current node as visited and print it
visited[v] = true;
// Recur for all the vertices adjacent to this vertex
list<int>::iterator i;
for (i = adj[v].begin(); i != adj[v].end(); ++i)
if (!visited[*i])
DFSUtil(*i, visited);
}
void Graph::addEdge(int v, int w)
{
adj[v].push_back(w); // Add w to v’s list.
}
// Returns a mother vertex if exists. Otherwise returns -1
int Graph::findSource()
{
// visited[] is used for DFS. Initially all are
// initialized as not visited
vector <bool> visited(V, false);
// To store last finished vertex (or mother vertex)
int v = 0;
// Do a DFS traversal and find the last finished
// vertex
for (int i = 0; i < V; i++)
{
if (visited[i] == false)
{
DFSUtil(i, visited);
v = i;
}
}
// If there exist mother vertex (or vetices) in given
// graph, then v must be one (or one of them)
// Now check if v is actually a mother vertex (or graph
// has a mother vertex). We basically check if every vertex
// is reachable from v or not.
// Reset all values in visited[] as false and do
// DFS beginning from v to check if all vertices are
// reachable from it or not.
fill(visited.begin(), visited.end(), false);
DFSUtil(v, visited);
for (int i=0; i<V; i++)
if (visited[i] == false)
return -1;
return v;
}
#include <bits/stdc++.h>
using namespace std;
class Graph
{
int V; // No. of vertices
list<int> *adj; // adjacency lists
// A recursive function to print DFS starting from v
void DFSUtil(int v, vector<bool> &visited);
public:
Graph(int V);
void addEdge(int v, int w);
int findSource();
};
Graph::Graph(int V)
{
this->V = V;
adj = new list<int>[V];
}
// A recursive function to print DFS starting from v
void Graph::DFSUtil(int v, vector<bool> &visited)
{
// Mark the current node as visited and print it
visited[v] = true;
// Recur for all the vertices adjacent to this vertex
list<int>::iterator i;
for (i = adj[v].begin(); i != adj[v].end(); ++i)
if (!visited[*i])
DFSUtil(*i, visited);
}
void Graph::addEdge(int v, int w)
{
adj[v].push_back(w); // Add w to v’s list.
}
// Returns a mother vertex if exists. Otherwise returns -1
int Graph::findSource()
{
// visited[] is used for DFS. Initially all are
// initialized as not visited
vector <bool> visited(V, false);
// To store last finished vertex (or mother vertex)
int v = 0;
// Do a DFS traversal and find the last finished
// vertex
for (int i = 0; i < V; i++)
{
if (visited[i] == false)
{
DFSUtil(i, visited);
v = i;
}
}
// If there exist mother vertex (or vetices) in given
// graph, then v must be one (or one of them)
// Now check if v is actually a mother vertex (or graph
// has a mother vertex). We basically check if every vertex
// is reachable from v or not.
// Reset all values in visited[] as false and do
// DFS beginning from v to check if all vertices are
// reachable from it or not.
fill(visited.begin(), visited.end(), false);
DFSUtil(v, visited);
for (int i=0; i<V; i++)
if (visited[i] == false)
return -1;
return v;
}