Problem 1. (10 pts) Develop an efficient algorithm to find the length of the lon
ID: 3870498 • Letter: P
Question
Problem 1. (10 pts) Develop an efficient algorithm to find the length of the longest path in a directed graph G = (V, E). Hint: 1. First, observe that if the graph G has a directed cycle, then the maximum path length is infinite, since you can construct a path that keeps going around this cycle forever: Therefore, first devise an algorithm to test whether G contains a directed cycle (and output oo if it does). Prove the correctness of your algorithm for this step. 2 If G contains no cycles, it must be a DAG. Provide an efficient algorithm to output the maximum path length in a DAG. Prove the correctness of your algorithm for this step 3. Analyze the overall running time of your algorithm.Explanation / Answer
1.
#include<iostream>
#include <list>
#include <limits.h>
using namespace std;
class Graph
{
int V;
list<int> *adj;
bool isCyclicUtil(int v, bool visited[], bool *rs); // used by isCyclic()
public:
Graph(int V);
void addEdge(int v, int w);
bool isCyclic();
};
Graph::Graph(int V)
{
this->V = V;
adj = new list<int>[V];
}
void Graph::addEdge(int v, int w)
{
adj[v].push_back(w);
}
bool Graph::isCyclicUtil(int v, bool visited[], bool *recStack)
{
if(visited[v] == false)
{
visited[v] = true;
recStack[v] = true;
list<int>::iterator i;
for(i = adj[v].begin(); i != adj[v].end(); ++i)
{
if ( !visited[*i] && isCyclicUtil(*i, visited, recStack) )
return true;
else if (recStack[*i])
return true;
}
}
recStack[v] = false;
return false;
}
bool Graph::isCyclic()
{
bool *visited = new bool[V];
bool *recStack = new bool[V];
for(int i = 0; i < V; i++)
{
visited[i] = false;
recStack[i] = false;
}
for(int i = 0; i < V; i++)
if (isCyclicUtil(i, visited, recStack))
return true;
return false;
}
int main()
{
Graph g(4);
g.addEdge(0, 1);
g.addEdge(0, 2);
g.addEdge(1, 2);
g.addEdge(2, 0);
g.addEdge(2, 3);
g.addEdge(3, 3);
if(g.isCyclic())
cout << "Graph contains cycle";
else
cout << "Graph doesn't contain cycle";
return 0;
}
Time Complexity of this method is same as time complexity of DFS traversalwhich is O(V+E).
2.
#include <iostream>
#include <list>
#include <stack>
#include <limits.h>
#define NINF INT_MIN
using namespace std;
class AdjListNode
{
int v;
int weight;
public:
AdjListNode(int _v, int _w) { v = _v; weight = _w;}
int getV() { return v; }
int getWeight() { return weight; }
};
class Graph
{
int V;
list<AdjListNode> *adj
void topologicalSortUtil(int v, bool visited[], stack<int> &Stack);
public:
Graph(int V);
void addEdge(int u, int v, int weight);
void longestPath(int s);
};
Graph::Graph(int V)
{
this->V = V;
adj = new list<AdjListNode>[V];
}
void Graph::addEdge(int u, int v, int weight)
{
AdjListNode node(v, weight);
adj[u].push_back(node);
}
void Graph::topologicalSortUtil(int v, bool visited[], stack<int> &Stack)
{
visited[v] = true;
list<AdjListNode>::iterator i;
for (i = adj[v].begin(); i != adj[v].end(); ++i)
{
AdjListNode node = *i;
if (!visited[node.getV()])
topologicalSortUtil(node.getV(), visited, Stack);
}
Stack.push(v);
}
void Graph::longestPath(int s)
{
stack<int> Stack;
int dist[V];
bool *visited = new bool[V];
for (int i = 0; i < V; i++)
visited[i] = false;
for (int i = 0; i < V; i++)
if (visited[i] == false)
topologicalSortUtil(i, visited, Stack);
for (int i = 0; i < V; i++)
dist[i] = NINF;
dist[s] = 0;
while (Stack.empty() == false)
{
int u = Stack.top();
Stack.pop();
list<AdjListNode>::iterator i;
if (dist[u] != NINF)
{
for (i = adj[u].begin(); i != adj[u].end(); ++i)
if (dist[i->getV()] < dist[u] + i->getWeight())
dist[i->getV()] = dist[u] + i->getWeight();
}
}
for (int i = 0; i < V; i++)
(dist[i] == NINF)? cout << "INF ": cout << dist[i] << " ";
}
int main()
{
Graph g(6);
g.addEdge(0, 1, 5);
g.addEdge(0, 2, 3);
g.addEdge(1, 3, 6);
g.addEdge(1, 2, 2);
g.addEdge(2, 4, 4);
g.addEdge(2, 5, 2);
g.addEdge(2, 3, 7);
g.addEdge(3, 5, 1);
g.addEdge(3, 4, -1);
g.addEdge(4, 5, -2);
int s = 1;
cout << "Following are longest distances from source vertex " << s <<" ";
g.longestPath(s);
return 0;
}
3.
Time complexity of topological sorting is O(V+E). After finding topological order, the algorithm process all vertices and for every vertex, it runs a loop for all adjacent vertices. Total adjacent vertices in a graph is O(E). So the inner loop runs O(V+E) times. Therefore, overall time complexity of this algorithm is O(V+E).
#include<iostream>
#include <list>
#include <limits.h>
using namespace std;
class Graph
{
int V;
list<int> *adj;
bool isCyclicUtil(int v, bool visited[], bool *rs); // used by isCyclic()
public:
Graph(int V);
void addEdge(int v, int w);
bool isCyclic();
};
Graph::Graph(int V)
{
this->V = V;
adj = new list<int>[V];
}
void Graph::addEdge(int v, int w)
{
adj[v].push_back(w);
}
bool Graph::isCyclicUtil(int v, bool visited[], bool *recStack)
{
if(visited[v] == false)
{
visited[v] = true;
recStack[v] = true;
list<int>::iterator i;
for(i = adj[v].begin(); i != adj[v].end(); ++i)
{
if ( !visited[*i] && isCyclicUtil(*i, visited, recStack) )
return true;
else if (recStack[*i])
return true;
}
}
recStack[v] = false;
return false;
}
bool Graph::isCyclic()
{
bool *visited = new bool[V];
bool *recStack = new bool[V];
for(int i = 0; i < V; i++)
{
visited[i] = false;
recStack[i] = false;
}
for(int i = 0; i < V; i++)
if (isCyclicUtil(i, visited, recStack))
return true;
return false;
}
int main()
{
Graph g(4);
g.addEdge(0, 1);
g.addEdge(0, 2);
g.addEdge(1, 2);
g.addEdge(2, 0);
g.addEdge(2, 3);
g.addEdge(3, 3);
if(g.isCyclic())
cout << "Graph contains cycle";
else
cout << "Graph doesn't contain cycle";
return 0;
}
Time Complexity of this method is same as time complexity of DFS traversalwhich is O(V+E).
2.
#include <iostream>
#include <list>
#include <stack>
#include <limits.h>
#define NINF INT_MIN
using namespace std;
class AdjListNode
{
int v;
int weight;
public:
AdjListNode(int _v, int _w) { v = _v; weight = _w;}
int getV() { return v; }
int getWeight() { return weight; }
};
class Graph
{
int V;
list<AdjListNode> *adj
void topologicalSortUtil(int v, bool visited[], stack<int> &Stack);
public:
Graph(int V);
void addEdge(int u, int v, int weight);
void longestPath(int s);
};
Graph::Graph(int V)
{
this->V = V;
adj = new list<AdjListNode>[V];
}
void Graph::addEdge(int u, int v, int weight)
{
AdjListNode node(v, weight);
adj[u].push_back(node);
}
void Graph::topologicalSortUtil(int v, bool visited[], stack<int> &Stack)
{
visited[v] = true;
list<AdjListNode>::iterator i;
for (i = adj[v].begin(); i != adj[v].end(); ++i)
{
AdjListNode node = *i;
if (!visited[node.getV()])
topologicalSortUtil(node.getV(), visited, Stack);
}
Stack.push(v);
}
void Graph::longestPath(int s)
{
stack<int> Stack;
int dist[V];
bool *visited = new bool[V];
for (int i = 0; i < V; i++)
visited[i] = false;
for (int i = 0; i < V; i++)
if (visited[i] == false)
topologicalSortUtil(i, visited, Stack);
for (int i = 0; i < V; i++)
dist[i] = NINF;
dist[s] = 0;
while (Stack.empty() == false)
{
int u = Stack.top();
Stack.pop();
list<AdjListNode>::iterator i;
if (dist[u] != NINF)
{
for (i = adj[u].begin(); i != adj[u].end(); ++i)
if (dist[i->getV()] < dist[u] + i->getWeight())
dist[i->getV()] = dist[u] + i->getWeight();
}
}
for (int i = 0; i < V; i++)
(dist[i] == NINF)? cout << "INF ": cout << dist[i] << " ";
}
int main()
{
Graph g(6);
g.addEdge(0, 1, 5);
g.addEdge(0, 2, 3);
g.addEdge(1, 3, 6);
g.addEdge(1, 2, 2);
g.addEdge(2, 4, 4);
g.addEdge(2, 5, 2);
g.addEdge(2, 3, 7);
g.addEdge(3, 5, 1);
g.addEdge(3, 4, -1);
g.addEdge(4, 5, -2);
int s = 1;
cout << "Following are longest distances from source vertex " << s <<" ";
g.longestPath(s);
return 0;
}
3.
Time complexity of topological sorting is O(V+E). After finding topological order, the algorithm process all vertices and for every vertex, it runs a loop for all adjacent vertices. Total adjacent vertices in a graph is O(E). So the inner loop runs O(V+E) times. Therefore, overall time complexity of this algorithm is O(V+E).
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.