Graphs
Graphs
Graphs
1
10 Longest Path in a Directed Acyclic Graph 53
Source . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 56
11 Topological Sorting 57
Source . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 61
2
22 Dijkstra’s Algorithm for Adjacency List Representation 125
Source . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 136
3
34 Given a sorted dictionary of an alien language, find order of
characters 200
Source . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 204
4
46 Eulerian path and circuit for undirected graph 265
Source . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 271
5
58 Travelling Salesman Problem | Set 2 (Approximate using MST)334
Source . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 337
6
69 Karger’s algorithm for Minimum Cut | Set 2 (Analysis and
Applications) 396
Source . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 399
7
Chapter 1
8
Following two are the most commonly used representations of graph.
1. Adjacency Matrix
2. Adjacency List
There are other representations also like, Incidence Matrix and Incidence List.
The choice of the graph representation is situation specific. It totally depends
on the type of operations to be performed and ease of use.
Adjacency Matrix:
Adjacency Matrix is a 2D array of size V x V where V is the number of vertices
in a graph. Let the 2D array be adj[][], a slot adj[i][j] = 1 indicates that there
is an edge from vertex i to vertex j. Adjacency matrix for undirected graph is
always symmetric. Adjacency Matrix is also used to represent weighted graphs.
If adj[i][j] = w, then there is an edge from vertex i to vertex j with weight w.
The adjacency matrix for the above example graph is:
9
Adjacency List Representation of the above Graph
Below is C code for adjacency list representation of an undirected graph:
#include <stdio.h>
#include <stdlib.h>
10
(struct AdjListNode*) malloc(sizeof(struct AdjListNode));
newNode->dest = dest;
newNode->next = NULL;
return newNode;
}
return graph;
}
11
while (pCrawl)
{
printf("-> %d", pCrawl->dest);
pCrawl = pCrawl->next;
}
printf("\n");
}
}
return 0;
}
Output:
12
Adjacency list of vertex 4
head -> 3-> 1-> 0
Pros: Saves space O(|V|+|E|) . In the worst case, there can be C(V, 2) number
of edges in a graph thus consuming O(Vˆ2) space. Adding a vertex is easier.
Cons: Queries like whether there is an edge from vertex u to vertex v are not
efficient and can be done O(V).
Reference:
http://en.wikipedia.org/wiki/Graph_%28abstract_data_type%29
This article is compiled by Aashish Barnwal and reviewed by GeeksforGeeks
team. Please write comments if you find anything incorrect, or you want to
share more information about the topic discussed above.
Source
http://www.geeksforgeeks.org/graph-and-its-representations/
13
Chapter 2
Breadth First Traversal (or Search) for a graph is similar to Breadth First
Traversal of a tree (See mthod 2 of this post). The only catch here is, unlike
trees, graphs may contain cycles, so we may come to the same node again. To
avoid processing a node more than once, we use a boolean visited array. For
simplicity, it is assumed that all vertices are reachable from the starting vertex.
For example, in the following graph, we start traversal from vertex 2. When we
come to vertex 0, we look for all adjacent vertices of it. 2 is also an adjacent
vertex of 0. If we don’t mark visited vertices, then 2 will be processed again
and it will become a non-terminating process. A Breadth First Traversal of the
following graph is 2, 0, 3, 1.
Following are C++ and Java implementations of simple Breadth First Traversal
14
from a given source.
The C++ implementation uses adjacency list representation of graphs. STL‘s
list container is used to store lists of adjacent nodes and queue of nodes needed
for BFS traversal.
C++
Graph::Graph(int V)
{
this->V = V;
adj = new list<int>[V];
}
void Graph::BFS(int s)
{
// Mark all the vertices as not visited
bool *visited = new bool[V];
for(int i = 0; i < V; i++)
visited[i] = false;
15
// Mark the current node as visited and enqueue it
visited[s] = true;
queue.push_back(s);
while(!queue.empty())
{
// Dequeue a vertex from queue and print it
s = queue.front();
cout << s << " ";
queue.pop_front();
cout << "Following is Breadth First Traversal (starting from vertex 2) \n";
g.BFS(2);
return 0;
}
16
Java
// Constructor
Graph(int v)
{
V = v;
adj = new LinkedList[v];
for (int i=0; i<v; ++i)
adj[i] = new LinkedList();
}
17
queue.add(s);
while (queue.size() != 0)
{
// Dequeue a vertex from queue and print it
s = queue.poll();
System.out.print(s+" ");
// Driver method to
public static void main(String args[])
{
Graph g = new Graph(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);
g.BFS(2);
}
}
// This code is contributed by Aakash Hasija
18
Output:
Note that the above code traverses only the vertices reachable from a given
source vertex. All the vertices may not be reachable from a given vertex (ex-
ample Disconnected graph). To print all the vertices, we can modify the BFS
function to do traversal starting from all nodes one by one (Like the DFS mod-
ified version) .
Time Complexity: O(V+E) where V is number of vertices in the graph and E
is number of edges in the graph.
Also see Depth First Traversal
Please write comments if you find anything incorrect, or you want to share more
information about the topic discussed above.
Source
http://www.geeksforgeeks.org/breadth-first-traversal-for-a-graph/
19
Chapter 3
Applications of Breadth
First Traversal
20
Search is preferred over Depth First Search because of better locality of refer-
ence:
8)Cycle detection in undirected graph: In undirected graphs, either
Breadth First Search or Depth First Search can be used to detect cycle. In
directed graph, only depth first search can be used.
9) Ford–Fulkerson algorithm In Ford-Fulkerson algorithm, we can either
use Breadth First or Depth First Traversal to find the maximum flow. Breadth
First Traversal is preferred as it reduces worst case time complexity to O(VE2 ).
10)To test if a graph is Bipartite We can either use Breadth First or Depth
First Traversal.
11) Path Finding We can either use Breadth First or Depth First Traversal
to find if there is a path between two vertices.
12) Finding all nodes within one connected component: We can either
use Breadth First or Depth First Traversal to find all nodes reachable from a
given node.
Many algorithms like Prim’s Minimum Spanning Tree and Dijkstra’s Single
Source Shortest Path use structure similar to Breadth First Search.
There can be many more applications as Breadth First Search is one of the core
algorithm for Graphs.
This article is contributed by Neeraj Jain. Please write comments if you
find anything incorrect, or you want to share more information about the topic
discussed above
Source
http://www.geeksforgeeks.org/applications-of-breadth-first-traversal/
21
Chapter 4
Depth First Traversal (or Search) for a graph is similar to Depth First Traversal
of a tree. The only catch here is, unlike trees, graphs may contain cycles, so we
may come to the same node again. To avoid processing a node more than once,
we use a boolean visited array.
For example, in the following graph, we start traversal from vertex 2. When we
come to vertex 0, we look for all adjacent vertices of it. 2 is also an adjacent
vertex of 0. If we don’t mark visited vertices, then 2 will be processed again
and it will become a non-terminating process. A Depth First Traversal of the
following graph is 2, 0, 1, 3.
22
C++
// C++ program to print DFS traversal from a given vertex in a given graph
#include<iostream>
#include <list>
Graph::Graph(int V)
{
this->V = V;
adj = new list<int>[V];
}
23
// DFS traversal of the vertices reachable from v. It uses recursive DFSUtil()
void Graph::DFS(int v)
{
// Mark all the vertices as not visited
bool *visited = new bool[V];
for (int i = 0; i < V; i++)
visited[i] = false;
int main()
{
// Create a graph given in the above diagram
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);
cout << "Following is Depth First Traversal (starting from vertex 2) \n";
g.DFS(2);
return 0;
}
Java
24
// Array of lists for Adjacency List Representation
private LinkedList<Integer> adj[];
// Constructor
Graph(int v)
{
V = v;
adj = new LinkedList[v];
for (int i=0; i<v; ++i)
adj[i] = new LinkedList();
}
25
public static void main(String args[])
{
Graph g = new Graph(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);
g.DFS(2);
}
}
// This code is contributed by Aakash Hasija
Output:
Note that the above code traverses only the vertices reachable from a given
source vertex. All the vertices may not be reachable from a given vertex
(example Disconnected graph). To do complete DFS traversal of such graphs,
we must call DFSUtil() for every vertex. Also, before calling DFSUtil(), we
should check if it is already printed by some other call of DFSUtil(). Following
implementation does the complete graph traversal even if the nodes are
unreachable. The differences from the above code are highlighted in the below
code.
C++
26
using namespace std;
class Graph
{
int V; // No. of vertices
list<int> *adj; // Pointer to an array containing adjacency lists
void DFSUtil(int v, bool visited[]); // A function used by DFS
public:
Graph(int V); // Constructor
void addEdge(int v, int w); // function to add an edge to graph
void DFS(); // prints DFS traversal of the complete graph
};
Graph::Graph(int V)
{
this->V = V;
adj = new list<int>[V];
}
27
// starting from all vertices one by one
for (int i = 0; i < V; i++)
if (visited[i] == false)
DFSUtil(i, visited);
}
int main()
{
// Create a graph given in the above diagram
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);
return 0;
}
Java
// Constructor
Graph(int v)
{
V = v;
28
adj = new LinkedList[v];
for (int i=0; i<v; ++i)
adj[i] = new LinkedList();
}
29
g.addEdge(0, 1);
g.addEdge(0, 2);
g.addEdge(1, 2);
g.addEdge(2, 0);
g.addEdge(2, 3);
g.addEdge(3, 3);
g.DFS();
}
}
// This code is contributed by Aakash Hasija
Output:
Source
http://www.geeksforgeeks.org/depth-first-traversal-for-a-graph/
30
Chapter 5
31
6) Finding Strongly Connected Components of a graph A directed
graph is called strongly connected if there is a path from each vertex in the
graph to every other vertex. (See thisfor DFS based algo for finding Strongly
Connected Components)
Sources:
http://www8.cs.umu.se/kurser/TDBAfl/VT06/algorithms/LEC/LECTUR16/
NODE16.HTM
http://en.wikipedia.org/wiki/Depth-first_search
http://www.personal.kent.edu/~rmuhamma/Algorithms/MyAlgorithms/
GraphAlgor/depthSearch.htm
http://ww3.algorithmdesign.net/handouts/DFS.pdf
Source
http://www.geeksforgeeks.org/applications-of-depth-first-search/
32
Chapter 6
Depth First Traversal (or Search) for a graph is similar to Depth First Traversal
(DFS) of a tree. The only catch here is, unlike trees, graphs may contain cycles,
so we may come to the same node again. To avoid processing a node more than
once, we use a boolean visited array.
For example, a DFS of below graph is “0 3 4 2 1�, other possible DFS is “0 2 1
3 4�.
33
Below is C++ implementation of Iterative DFS. The implementation is sim-
ilar to BFS, the only difference is queue is replaced by stack.
Graph::Graph(int V)
{
this->V = V;
adj = new list<int>[V];
}
34
visited[s] = true;
stack.push(s);
while (!stack.empty())
{
// Pop a vertex from stack and print it
s = stack.top();
cout << s << " ";
stack.pop();
return 0;
}
35
Output:
Note that the above implementation prints only vertices that are reachable from
a given vertex. For example, if we remove edges 0-3 and 0-2, the above program
would only print 0. To print all vertices of a graph, we need to call DFS for
every vertex. Below is C++ implementation for the same.
Graph::Graph(int V)
{
this->V = V;
adj = new list<int>[V];
}
36
adj[v].push_back(w); // Add w to v’s list.
}
while (!stack.empty())
{
// Pop a vertex from stack and print it
s = stack.top();
cout << s << " ";
stack.pop();
37
for (int i = 0; i < V; i++)
if (!visited[i])
DFSUtil(i, visited);
}
return 0;
}
Output:
Source
http://www.geeksforgeeks.org/iterative-depth-first-traversal/
Category: Graph Stack Tags: stack, Stack-Queue
Post navigation
38
← Number of paths with exactly k coins Works Applications Interview Experi-
ence | Set 3 →
Writing code in comment? Please use code.geeksforgeeks.org, generate link and
share the link here.
39
Chapter 7
Given a directed graph, check whether the graph contains a cycle or not. Your
function should return true if the given graph contains at least one cycle, else
return false. For example, the following graph contains three cycles 0->2->0,
0->1->2->0 and 3->3, so your function must return true.
Solution
Depth First Traversal can be used to detect cycle in a Graph. DFS for a
connected graph produces a tree. There is a cycle in a graph only if there is
a back edge present in the graph. A back edge is an edge that is from a node
to itself (selfloop) or one of its ancestor in the tree produced by DFS. In the
following graph, there are 3 back edges, marked with cross sign. We can observe
that these 3 back edges indicate 3 cycles present in the graph.
For a disconnected graph, we get the DFS forrest as output. To detect cycle,
we can check for cycle in individual trees by checking back edges.
40
To detect a back edge, we can keep track of vertices currently in recursion stack
of function for DFS traversal. If we reach a vertex that is already in the recursion
stack, then there is a cycle in the tree. The edge that connects current vertex
to the vertex in the recursion stack is back edge. We have used recStack[] array
to keep track of vertices in the recursion stack.
class Graph
{
int V; // No. of vertices
list<int> *adj; // Pointer to an array containing adjacency lists
bool isCyclicUtil(int v, bool visited[], bool *rs); // used by isCyclic()
public:
Graph(int V); // Constructor
void addEdge(int v, int w); // to add an edge to graph
bool isCyclic(); // returns true if there is a cycle in this graph
};
Graph::Graph(int V)
{
this->V = V;
adj = new list<int>[V];
}
41
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; // remove the vertex from recursion stack
return false;
}
return false;
}
int main()
{
// Create a graph given in the above diagram
Graph g(4);
g.addEdge(0, 1);
g.addEdge(0, 2);
g.addEdge(1, 2);
g.addEdge(2, 0);
g.addEdge(2, 3);
42
g.addEdge(3, 3);
if(g.isCyclic())
cout << "Graph contains cycle";
else
cout << "Graph doesn't contain cycle";
return 0;
}
Output:
Source
http://www.geeksforgeeks.org/detect-cycle-in-a-graph/
Category: Graph Tags: Graph
43
Chapter 8
0
| \
| \
1-----2
44
For each edge, make subsets using both the vertices of the edge. If both the
vertices are in the same subset, a cycle is found.
Initially, all slots of parent array are initialized to -1 (means there is only one
item in every subset).
0 1 2
-1 -1 -1
0 1 2
Edge 1-2: 1 is in subset 1 and 2 is in subset 2. So, take union.
0 1 2
Edge 0-2: 0 is in subset 2 and 2 is also in subset 2. Hence, including this edge forms a cycle.
How subset of 0 is same as 2?
45
// graph is represented as an array of edges
struct Edge* edge;
};
return graph;
}
// The main function to check whether a given graph contains cycle or not
int isCycle( struct Graph* graph )
{
// Allocate memory for creating V subsets
int *parent = (int*) malloc( graph->V * sizeof(int) );
46
{
int x = find(parent, graph->edge[i].src);
int y = find(parent, graph->edge[i].dest);
if (x == y)
return 1;
Union(parent, x, y);
}
return 0;
}
if (isCycle(graph))
printf( "Graph contains cycle" );
else
printf( "Graph doesn't contain cycle" );
return 0;
}
Output:
47
Graph contains cycle
Note that the implementation of union() and find() is naive and takes O(n)
time in worst case. These methods can be improved to O(Logn) using Union by
Rank or Height. We will soon be discussing Union by Rank in a separate post.
This article is compiled by Aashish Barnwal and reviewed by GeeksforGeeks
team. Please write comments if you find anything incorrect, or you want to
share more information about the topic discussed above.
Source
http://www.geeksforgeeks.org/union-find/
48
Chapter 9
Detect cycle in an
undirected graph
Given an undirected graph, how to check if there is a cycle in the graph? For
example, the following graph has a cycle 1-0-2-1.
We have discussed cycle detection for directed graph. We have also discussed
a union-find algorithm for cycle detection in undirected graphs. The time com-
plexity of the union-find algorithm is O(ELogV). Like directed graphs, we can
use DFSto detect cycle in an undirected graph in O(V+E) time. We do a DFS
traversal of the given graph. For every visited vertex ‘v’, if there is an adjacent
‘u’ such that u is already visited and u is not parent of v, then there is a cycle
in graph. If we don’t find such an adjacent for any vertex, we say that there is
no cycle. The assumption of this approach is that there are no parallel edges
between any two vertices.
49
#include<iostream>
#include <list>
#include <limits.h>
using namespace std;
Graph::Graph(int V)
{
this->V = V;
adj = new list<int>[V];
}
50
// If an adjacent is visited and not parent of current vertex,
// then there is a cycle.
else if (*i != parent)
return true;
}
return false;
}
return false;
}
Graph g2(3);
g2.addEdge(0, 1);
g2.addEdge(1, 2);
g2.isCyclic()? cout << "Graph contains cycle\n":
cout << "Graph doesn't contain cycle\n";
51
return 0;
}
Output:
Time Complexity: The program does a simple DFS Traversal of graph and
graph is represented using adjacency list. So the time complexity is O(V+E)
Exercise: Can we use BFS to detect cycle in an undirected graph in O(V+E)
time? What about directed graphs?
Please write comments if you find anything incorrect, or you want to share more
information about the topic discussed above
Source
http://www.geeksforgeeks.org/detect-cycle-undirected-graph/
Category: Graph Tags: Graph
52
Chapter 10
Given a Weighted Directed Acyclic Graph (DAG) and a source vertex s in it,
find the longest distances from s to all other vertices in the given graph.
The longest path problem for a general graph is not as easy as the shortest path
problem because the longest path problem doesn’t have optimal substructure
property. In fact, the Longest Path problem is NP-Hard for a general graph.
However, the longest path problem has a linear time solution for directed acyclic
graphs. The idea is similar to linear time solution for shortest path in a directed
acyclic graph., we use Tological Sorting.
We initialize distances to all vertices as minus infinite and distance to source
as 0, then we find a topological sorting of the graph. Topological Sorting of
a graph represents a linear ordering of the graph (See below, figure (b) is a
linear representation of figure (a) ). Once we have topological order (or linear
representation), we one by one process all vertices in topological order. For
every vertex being processed, we update distances of its adjacent using distance
of current vertex.
Following figure shows step by step process of finding longest paths.
53
Following is complete algorithm for finding longest distances.
1) Initialize dist[] = {NINF, NINF, ….} and dist[s] = 0 where s is the source
vertex. Here NINF means negative infinite.
2) Create a toplogical order of all vertices.
3) Do following for every vertex u in topological order.
………..Do following for every adjacent vertex v of u
………………if (dist[v] // A C++ program to find single source longest distances
in a DAG #include <iostream> #include <list> #include <stack> #include
<limits.h> #define NINF INT_MIN using namespace std; // Graph is repre-
sented using adjacency list. Every node of adjacency list // contains vertex
number of the vertex to which edge connects. It also // contains weight of
the edge 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 to represent a graph using adjacency list rep-
resentation class Graph { int V; // No. of vertices’ // Pointer to an ar-
ray containing adjacency lists list<AdjListNode> *adj; // A function used by
longestPath void topologicalSortUtil(int v, bool visited[], stack<int> &Stack);
54
public: Graph(int V); // Constructor // function to add an edge to graph
void addEdge(int u, int v, int weight); // Finds longest distances from given
source vertex void longestPath(int s); }; Graph::Graph(int V) // Constructor
{ 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);
// Add v to u’s list } // A recursive function used by longestPath. See be-
low link for details // http://www.geeksforgeeks.org/topological-sorting/ void
Graph::topologicalSortUtil(int v, bool visited[], stack<int> &Stack) { // Mark
the current node as visited visited[v] = true; // Recur for all the vertices ad-
jacent to this vertex list<AdjListNode>::iterator i; for (i = adj[v].begin(); i !=
adj[v].end(); ++i) { AdjListNode node = *i; if (!visited[node.getV()]) topologi-
calSortUtil(node.getV(), visited, Stack); } // Push current vertex to stack which
stores topological sort Stack.push(v); } // The function to find longest distances
from a given vertex. It uses // recursive topologicalSortUtil() to get topologi-
cal sorting. void Graph::longestPath(int s) { stack<int> Stack; int dist[V]; //
Mark all the vertices as not visited bool *visited = new bool[V]; for (int i =
0; i < V; i++) visited[i] = false; // Call the recursive helper function to store
Topological Sort // starting from all vertices one by one for (int i = 0; i < V;
i++) if (visited[i] == false) topologicalSortUtil(i, visited, Stack); // Initialize
distances to all vertices as infinite and distance // to source as 0 for (int i = 0;
i < V; i++) dist[i] = NINF; dist[s] = 0; // Process vertices in topological order
while (Stack.empty() == false) { // Get the next vertex from topological order
int u = Stack.top(); Stack.pop(); // Update distances of all adjacent vertices
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(); } } // Print the calculated longest distances for (int
i = 0; i < V; i++) (dist[i] == NINF)? cout << “INF ”: cout << dist[i] << ” “;
} // Driver program to test above functions int main() { // Create a graph given
in the above diagram. Here vertex numbers are // 0, 1, 2, 3, 4, 5 with following
mappings: // 0=r, 1=s, 2=t, 3=x, 4=y, 5=z 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 <<” \n”; g.longestPath(s); return 0; }
Output:
55
Exercise: The above solution print longest distances, extend the code to print
paths also.
Please write comments if you find anything incorrect, or you want to share more
information about the topic discussed above
Source
http://www.geeksforgeeks.org/find-longest-path-directed-acyclic-graph/
56
Chapter 11
Topological Sorting
57
Topological Sorting vs Depth First Traversal (DFS):
In DFS, we print a vertex and then recursively call DFS for its adjacent vertices.
In topological sorting, we need to print a vertex before its adjacent vertices. For
example, in the given graph, the vertex ‘5’ should be printed before vertex
‘0’, but unlike DFS, the vertex ‘4’ should also be printed before vertex ‘0’. So
Topological sorting is different from DFS. For example, a DFS of the above
graph is “5 2 3 1 0 4�, but it is not a topological sorting
Algorithm to find Topological Sorting:
We recommend to first see implementation of DFS here. We can modify DFSto
find Topological Sorting of a graph. In DFS, we start from a vertex, we first
print it and then recursively call DFS for its adjacent vertices. In topological
sorting, we use a temporary stack. We don’t print the vertex immediately, we
first recursively call topological sorting for all its adjacent vertices, then push
it to a stack. Finally, print contents of stack. Note that a vertex is pushed to
stack only when all of its adjacent vertices (and their adjacent vertices and so
on) are already in stack.
Following is C++ implementation of topological sorting. Please see the code
for Depth First Traversal for a disconnected Graph and note the differences
between the second code given there and the below code.
58
};
Graph::Graph(int V)
{
this->V = V;
adj = new list<int>[V];
}
59
while (Stack.empty() == false)
{
cout << Stack.top() << " ";
Stack.pop();
}
}
return 0;
}
Output:
Time Complexity: The above algorithm is simply DFS with an extra stack.
So time complexity is same as DFS which is O(V+E).
Applications:
Topological Sorting is mainly used for scheduling jobs from the given depen-
dencies among jobs. In computer science, applications of this type arise in
instruction scheduling, ordering of formula cell evaluation when recomputing
formula values in spreadsheets, logic synthesis, determining the order of com-
pilation tasks to perform in makefiles, data serialization, and resolving symbol
dependencies in linkers [2].
References:
60
http://www.personal.kent.edu/~rmuhamma/Algorithms/MyAlgorithms/
GraphAlgor/topoSort.htm
http://en.wikipedia.org/wiki/Topological_sorting
Please write comments if you find anything incorrect, or you want to share more
information about the topic discussed above
Source
http://www.geeksforgeeks.org/topological-sorting/
61
Chapter 12
A Bipartite Graph is a graph whose vertices can be divided into two independent
sets, U and V such that every edge (u, v) either connects a vertex from U to V
or a vertex from V to U. In other words, for every edge (u, v), either u belongs
to U and v to V, or u belongs to V and v to U. We can also say that there is
no edge that connects vertices of same set.
62
A bipartite graph is possible if the graph coloring is possible using two colors
such that vertices in a set are colored with the same color. Note that it is
possible to color a cycle graph with even cycle using two colors. For example,
see the following graph.
It is not possible to color a cycle graph with odd cycle using two colors.
63
Algorithm to check if a graph is Bipartite:
One approach is to check whether the graph is 2-colorable or not using back-
tracking algorithm m coloring problem.
Following is a simple algorithm to find out whether a given graph is Birpartite
or not using Breadth First Search (BFS).
1. Assign RED color to the source vertex (putting into set U).
2. Color all the neighbors with BLUE color (putting into set V).
3. Color all neighbor’s neighbor with RED color (putting into set U).
4. This way, assign color to all vertices such that it satisfies all the constraints
of m way coloring problem where m = 2.
5. While assigning colors, if we find a neighbor which is colored with same color
as current vertex, then the graph cannot be colored with 2 vertices (or graph is
not Bipartite)
C++
64
colorArr[i] = -1;
65
{1, 0, 1, 0}
};
Java
class Bipartite
{
final static int V = 4; // No. of Vertices
66
// Dequeue a vertex from queue
int u = q.poll();
67
Output:
Yes
Source
http://www.geeksforgeeks.org/bipartite-graph/
68
Chapter 13
Given a snake and ladder board, find the minimum number of dice throws
required to reach the destination or last cell from source or 1st cell. Basically,
the player has total control over outcome of dice throw and wants to find out
minimum number of throws required to reach last cell.
If the player reaches a cell which is base of a ladder, the player has to climb up
that ladder and if reaches a cell is mouth of the snake, has to go down to the
tail of snake without a dice throw.
69
For example consider the board shown on right side (taken from here), the min-
imum number of dice throws required to reach cell 30 from cell 1 is 3. Following
are steps.
a) First throw two on dice to reach cell number 3 and then ladder to reach 22
b) Then throw 6 to reach 28.
c) Finally through 2 to reach 30.
There can be other solutions as well like (2, 2, 6), (2, 4, 4), (2, 3, 5).. etc.
We strongly recommend to minimize the browser and try this yourself
first.
The idea is to consider the given snake and ladder board as a directed graph
with number of vertices equal to the number of cells in the board. The problem
reduces to finding the shortest path in a graph. Every vertex of the graph has
an edge to next six vertices if next 6 vertices do not have a snake or ladder. If
any of the next six vertices has a snake or ladder, then the edge from current
vertex goes to the top of the ladder or tail of the snake. Since all edges are of
equal weight, we can efficiently find shortest path using Breadth First Search of
the graph.
Following is C++ implementation of the above idea. The input is represented
by two things, first is ‘N’ which is number of cells in the given board, second
is an array ‘move[0…N-1]’ of size N. An entry move[i] is -1 if there is no snake
and no ladder from i, otherwise move[i] contains index of destination cell for the
snake or the ladder at i.
70
int getMinDiceThrows(int move[], int N)
{
// The graph has N vertices. Mark all the vertices as
// not visited
bool *visited = new bool[N];
for (int i = 0; i < N; i++)
visited[i] = false;
71
if (move[j] != -1)
a.v = move[j];
else
a.v = j;
q.push(a);
}
}
}
// Ladders
moves[2] = 21;
moves[4] = 7;
moves[10] = 25;
moves[19] = 28;
// Snakes
moves[26] = 0;
moves[20] = 8;
moves[16] = 3;
moves[18] = 6;
cout << "Min Dice throws required is " << getMinDiceThrows(moves, N);
return 0;
}
Output:
72
Time complexity of the above solution is O(N) as every cell is added and removed
only once from queue. And a typical enqueue or dequeue operation takes O(1)
time.
This article is contributed by Siddharth. Please write comments if you find
anything incorrect, or you want to share more information about the topic
discussed above.
Source
http://www.geeksforgeeks.org/snake-ladder-problem-2/
73
Chapter 14
Given a number of friends who have to give or take some amount of money from
one another. Design an algorithm by which the total cash flow among all the
friends is minimized.
Example:
Following diagram shows input debts to be settled.
74
Above debts can be settled in following optimized way
75
minimum of two amounts be x. We pay ‘x’ amount from the maximum debtor
to maximum creditor and settle one person. If x is equal to the maximum debit,
then maximum debtor is settled, else maximum creditor is settled.
The following is detailed algorithm.
Do following for every person Pi where i is from 0 to n-1.
1) Compute the net amount for every person. The net amount for person ‘i’
can be computed be subtracting sum of all debts from sum of all credits.
2) Find the two persons that are maximum creditor and maximum debtor.
Let the maximum amount to be credited maximum creditor be maxCredit and
maximum amount to be debited from maximum debtor be maxDebit. Let the
maximum debtor be Pd and maximum creditor be Pc.
3) Find the minimum of maxDebit and maxCredit. Let minimum of two be x.
Debit ‘x’ from Pd and credit this amount to Pc
4) If x is equal to maxCredit, then remove Pc from set of persons and recur for
remaining (n-1) persons.
76
int maxInd = 0;
for (int i=1; i<N; i++)
if (arr[i] > arr[maxInd])
maxInd = i;
return maxInd;
}
77
// Given a set of persons as graph[] where graph[i][j] indicates
// the amount that person i needs to pay person j, this function
// finds and prints the minimum cash flow to settle all debts.
void minCashFlow(int graph[][N])
{
// Create an array amount[], initialize all value in it as 0.
int amount[N] = {0};
minCashFlowRec(amount);
}
Output:
78
Source
http://www.geeksforgeeks.org/minimize-cash-flow-among-given-set-friends-borrowed-money/
79
Chapter 15
80
We strongly recommend to minimize your browser and try this your-
self first.
The idea is to consider every character as a starting character and find all words
starting with it. All words starting from a character can be found using Depth
First Traversal. We do depth first traversal starting from every cell. We keep
track of visited cells to make sure that a cell is considered only once in a word.
#define M 3
#define N 3
81
return false;
}
82
{
char boggle[M][N] = {{'G','I','Z'},
{'U','E','K'},
{'Q','S','E'}};
Output:
Note that the above solution may print same word multiple times. For example,
if we add “SEEK” to dictionary, it is printed multiple times. To avoid this, we
can use hashing to keep track of all printed words.
This article is contributed by Rishabh. Please write comments if you find
anything incorrect, or you want to share more information about the topic
discussed above.
Source
http://www.geeksforgeeks.org/boggle-find-possible-words-board-characters/
Category: Graph
Post navigation
← Amazon Interview Experience | Set 164 (For SDE I) Synopsys Interview
Experience | Set 2 →
Writing code in comment? Please use code.geeksforgeeks.org, generate link and
share the link here.
83
Chapter 16
Given a graph with both directed and undirected edges. It is given that the
directed edges don’t form cycle. How to assign directions to undirected edges
so that the graph (with all directed edges) remains acyclic even after the assign-
ment?
For example, in the below graph, blue edges don’t have directions.
84
We strongly recommend to minimize your browser and try this your-
self first.
The idea is to use Topological Sorting. Following are two steps used in the
algorithm.
1) Consider the subgraph with directed edges only and find topological sorting
of the subgraph. In the above example, topological sorting is {0, 5, 1, 2, 3, 4}.
Below diagram shows topological sorting for the above example graph.
Source: http://courses.csail.mit.edu/6.006/oldquizzes/solutions/q2-f2009-sol.
pdf
This article is contributed by Aditya Agrawal. Please write comments if you
find anything incorrect, or you want to share more information about the topic
discussed above.
85
Source
http://www.geeksforgeeks.org/assign-directions-to-edges-so-that-the-directed-graph-remains-acyclic/
Category: Graph
86
Chapter 17
87
iterate through all adjacent vertices. For every adjacent vertex v, if weight of
edge u-v is less than the previous key value of v, update the key value as weight
of u-v
The idea of using key values is to pick the minimum weight edge from cut. The
key values are used only for vertices which are not yet included in MST, the key
value for these vertices indicate the minimum weight edges connecting them to
the set of vertices included in MST.
Let us understand with the following example:
The set mstSet is initially empty and keys assigned to vertices are {0, INF, INF,
INF, INF, INF, INF, INF} where INF indicates infinite. Now pick the vertex
with minimum key value. The vertex 0 is picked, include it in mstSet. So mstSet
becomes {0}. After including to mstSet, update key values of adjacent vertices.
Adjacent vertices of 0 are 1 and 7. The key values of 1 and 7 are updated as 4
and 8. Following subgraph shows vertices and their key values, only the vertices
with finite key values are shown. The vertices included in MST are shown in
green color.
Pick the vertex with minimum key value and not already included in MST
(not in mstSET). The vertex 1 is picked and added to mstSet. So mstSet now
becomes {0, 1}. Update the key values of adjacent vertices of 1. The key value
of vertex 2 becomes 8.
88
Pick the vertex with minimum key value and not already included in MST (not
in mstSET). We can either pick vertex 7 or vertex 2, let vertex 7 is picked. So
mstSet now becomes {0, 1, 7}. Update the key values of adjacent vertices of 7.
The key value of vertex 6 and 8 becomes finite (7 and 1 respectively).
Pick the vertex with minimum key value and not already included in MST (not
in mstSET). Vertex 6 is picked. So mstSet now becomes {0, 1, 7, 6}. Update
the key values of adjacent vertices of 6. The key value of vertex 5 and 8 are
updated.
We repeat the above steps until mstSet includes all vertices of given graph.
Finally, we get the following graph.
89
How to implement the above algorithm?
We use a boolean array mstSet[] to represent the set of vertices included in MST.
If a value mstSet[v] is true, then vertex v is included in MST, otherwise not.
Array key[] is used to store key values of all vertices. Another array parent[]
to store indexes of parent nodes in MST. The parent array is the output array
which is used to show the constructed MST.
#include <stdio.h>
#include <limits.h>
// A utility function to find the vertex with minimum key value, from
// the set of vertices not yet included in MST
int minKey(int key[], bool mstSet[])
{
// Initialize min value
int min = INT_MAX, min_index;
return min_index;
}
90
printf("%d - %d %d \n", parent[i], i, graph[i][parent[i]]);
}
// Function to construct and print MST for a graph represented using adjacency
// matrix representation
void primMST(int graph[V][V])
{
int parent[V]; // Array to store constructed MST
int key[V]; // Key values used to pick minimum weight edge in cut
bool mstSet[V]; // To represent set of vertices not yet included in MST
91
// driver program to test above function
int main()
{
/* Let us create the following graph
2 3
(0)--(1)--(2)
| / \ |
6| 8/ \5 |7
| / \ |
(3)-------(4)
9 */
int graph[V][V] = {{0, 2, 0, 6, 0},
{2, 0, 3, 8, 5},
{0, 3, 0, 0, 7},
{6, 8, 0, 0, 9},
{0, 5, 7, 9, 0},
};
return 0;
}
Output:
Edge Weight
0 - 1 2
1 - 2 3
0 - 3 6
1 - 4 5
Time Complexity of the above program is O(Vˆ2). If the input graph is repre-
sented using adjacency list, then the time complexity of Prim’s algorithm can
be reduced to O(E log V) with the help of binary heap. Please see Prim’s MST
for Adjacency List Representation for more details.
Please write comments if you find anything incorrect, or you want to share more
information about the topic discussed above.
92
Source
http://www.geeksforgeeks.org/greedy-algorithms-set-5-prims-minimum-spanning-tree-mst-2/
Category: Graph Tags: Graph, Greedy, Greedy Algorithm, Minimum Spanning
Tree, Prim’s Algorithm
Post navigation
← Amazon Interview | Set 10 Set 6 (Prim’s MST for Adjacency List Represen-
tation) →
Writing code in comment? Please use code.geeksforgeeks.org, generate link and
share the link here.
93
Chapter 18
Applications of Minimum
Spanning Tree Problem
Minimum Spanning Tree (MST) problem: Given connected graph G with posi-
tive edge weights, find a min weight set of edges that connects all of the vertices.
MST is fundamental problem with diverse applications.
Network design.
– telephone, electrical, hydraulic, TV cable, computer, road
The standard application is to a problem like phone network design. You have
a business with several offices; you want to lease phone lines to connect them up
with each other; and the phone company charges different amounts of money
94
to connect different pairs of cities. You want a set of lines that connects all
your offices with a minimum total cost. It should be a spanning tree, since if a
network isn’t a tree you can always remove some edges and save money.
Approximation algorithms for NP-hard problems.
– traveling salesperson problem, Steiner tree
A less obvious application is that the minimum spanning tree can be used to
approximately solve the traveling salesman problem. A convenient formal way
of defining this problem is to find the shortest path that visits each point at
least once.
Note that if you have a path visiting all points exactly once, it’s a special kind
of tree. For instance in the example above, twelve of sixteen spanning trees are
actually paths. If you have a path visiting some vertices more than once, you
can always drop some edges to get a tree. So in general the MST weight is less
than the TSP weight, because it’s a minimization over a strictly larger set.
On the other hand, if you draw a path tracing around the minimum spanning
tree, you trace each edge twice and visit all points, so the TSP weight is less
than twice the MST weight. Therefore this tour is within a factor of two of
optimal.
Indirect applications.
– max bottleneck paths
– LDPC codes for error correction
– image registration with Renyi entropy
– learning salient features for real-time face verification
– reducing data storage in sequencing amino acids in a protein
– model locality of particle interactions in turbulent fluid flows
– autoconfig protocol for Ethernet bridging to avoid cycles in a network
Cluster analysis
k clustering problem can be viewed as finding an MST and deleting the k-1 most
expensive edges.
Sources:
http://www.cs.princeton.edu/courses/archive/spr07/cos226/lectures/mst.pdf
http://www.ics.uci.edu/~eppstein/161/960206.html
Source
http://www.geeksforgeeks.org/applications-of-minimum-spanning-tree/
95
Chapter 19
96
in MST). If v is in Min Heap and its key value is more than weight of u-v, then
update the key value of v as weight of u-v.
Let us understand the above algorithm with the following example:
Initially, key value of first vertex is 0 and INF (infinite) for all other vertices.
So vertex 0 is extracted from Min Heap and key values of vertices adjacent to
0 (1 and 7) are updated. Min Heap contains all vertices except vertex 0.
The vertices in green color are the vertices included in MST.
Since key value of vertex 1 is minimum among all nodes in Min Heap, it is
extracted from Min Heap and key values of vertices adjacent to 1 are updated
(Key is updated if the a vertex is not in Min Heap and previous key value is
greater than the weight of edge from 1 to the adjacent). Min Heap contains all
vertices except vertex 0 and 1.
97
Since key value of vertex 7 is minimum among all nodes in Min Heap, it is
extracted from Min Heap and key values of vertices adjacent to 7 are updated
(Key is updated if the a vertex is not in Min Heap and previous key value is
greater than the weight of edge from 7 to the adjacent). Min Heap contains all
vertices except vertex 0, 1 and 7.
Since key value of vertex 6 is minimum among all nodes in Min Heap, it is
extracted from Min Heap and key values of vertices adjacent to 6 are updated
(Key is updated if the a vertex is not in Min Heap and previous key value is
greater than the weight of edge from 6 to the adjacent). Min Heap contains all
vertices except vertex 0, 1, 7 and 6.
The above steps are repeated for rest of the nodes in Min Heap till Min Heap
becomes empty
98
// C / C++ program for Prim's MST for adjacency list representation of graph
#include <stdio.h>
#include <stdlib.h>
#include <limits.h>
99
newNode->next = NULL;
return newNode;
}
return graph;
}
100
int capacity; // Capacity of min heap
int *pos; // This is needed for decreaseKey()
struct MinHeapNode **array;
};
// A utility function to swap two nodes of min heap. Needed for min heapify
void swapMinHeapNode(struct MinHeapNode** a, struct MinHeapNode** b)
{
struct MinHeapNode* t = *a;
*a = *b;
*b = t;
}
101
if (left < minHeap->size &&
minHeap->array[left]->key < minHeap->array[smallest]->key )
smallest = left;
if (smallest != idx)
{
// The nodes to be swapped in min heap
MinHeapNode *smallestNode = minHeap->array[smallest];
MinHeapNode *idxNode = minHeap->array[idx];
// Swap positions
minHeap->pos[smallestNode->v] = idx;
minHeap->pos[idxNode->v] = smallest;
// Swap nodes
swapMinHeapNode(&minHeap->array[smallest], &minHeap->array[idx]);
minHeapify(minHeap, smallest);
}
}
102
minHeap->pos[lastNode->v] = 0;
return root;
}
103
printf("%d - %d\n", arr[i], i);
}
104
int v = pCrawl->dest;
PrimMST(graph);
return 0;
}
105
Output:
0 - 1
5 - 2
2 - 3
3 - 4
6 - 5
7 - 6
0 - 7
2 - 8
http://en.wikipedia.org/wiki/Prim’s_algorithm
This article is compiled by Aashish Barnwal and reviewed by GeeksforGeeks
team. Please write comments if you find anything incorrect, or you want to
share more information about the topic discussed above.
Source
http://www.geeksforgeeks.org/greedy-algorithms-set-5-prims-mst-for-adjacency-list-representation/
Category: Graph Tags: Graph, Greedy Algorithm
Post navigation
← Set 5 (Prim’s Minimum Spanning Tree (MST)) Construction of Longest
Monotonically Increasing Subsequence (N log N) →
Writing code in comment? Please use code.geeksforgeeks.org, generate link and
share the link here.
106
Chapter 20
Kruskal’s Minimum
Spanning Tree Algorithm
2. Pick the smallest edge. Check if it forms a cycle with the spanning tree
formed so far. If cycle is not formed, include this edge. Else, discard it.
3. Repeat step#2 until there are (V-1) edges in the spanning tree.
107
The step#2 uses Union-Find algorithm to detect cycle. So we recommend to
read following post as a prerequisite.
Union-Find Algorithm | Set 1 (Detect Cycle in a Graph)
The graph contains 9 vertices and 14 edges. So, the minimum spanning tree
formed will be having (9 – 1) = 8 edges.
After sorting:
Weight Src Dest
1 7 6
2 8 2
2 6 5
4 0 1
4 2 5
6 8 6
7 2 3
7 7 8
8 0 7
8 1 2
9 3 4
10 5 4
11 1 7
14 3 5
Now pick all edges one by one from sorted list of edges
108
1. Pick edge 7-6: No cycle is formed, include it.
109
4. Pick edge 0-1: No cycle is formed, include it.
110
6. Pick edge 8-6: Since including this edge results in cycle, discard it.
7. Pick edge 2-3: No cycle is formed, include it.
8. Pick edge 7-8: Since including this edge results in cycle, discard it.
9. Pick edge 0-7: No cycle is formed, include it.
111
10. Pick edge 1-2: Since including this edge results in cycle, discard it.
11. Pick edge 3-4: No cycle is formed, include it.
Since the number of edges included equals (V – 1), the algorithm stops here.
112
int src, dest, weight;
};
return graph;
}
return subsets[i].parent;
}
113
// (uses union by rank)
void Union(struct subset subsets[], int x, int y)
{
int xroot = find(subsets, x);
int yroot = find(subsets, y);
114
(struct subset*) malloc( V * sizeof(struct subset) );
115
2--------3
4 */
int V = 4; // Number of vertices in graph
int E = 5; // Number of edges in graph
struct Graph* graph = createGraph(V, E);
KruskalMST(graph);
return 0;
}
116
time. After sorting, we iterate through all edges and apply find-union algorithm.
The find and union operations can take atmost O(LogV) time. So overall com-
plexity is O(ELogE + ELogV) time. The value of E can be atmost Vˆ2, so
O(LogV) are O(LogE) same. Therefore, overall time complexity is O(ElogE) or
O(ElogV)
References:
http://www.ics.uci.edu/~eppstein/161/960206.html
http://en.wikipedia.org/wiki/Minimum_spanning_tree
This article is compiled by Aashish Barnwal and reviewed by GeeksforGeeks
team. Please write comments if you find anything incorrect, or you want to
share more information about the topic discussed above.
Source
http://www.geeksforgeeks.org/greedy-algorithms-set-2-kruskals-minimum-spanning-tree-mst/
117
Chapter 21
Given a graph and a source vertex in graph, find shortest paths from source to
all vertices in the given graph.
Dijkstra’s algorithm is very similar to Prim’s algorithm for minimum spanning
tree. Like Prim’s MST, we generate a SPT (shortest path tree) with given source
as root. We maintain two sets, one set contains vertices included in shortest
path tree, other set includes vertices not yet included in shortest path tree. At
every step of the algorithm, we find a vertex which is in the other set (set of
not yet included) and has minimum distance from source.
Below are the detailed steps used in Dijkstra’s algorithm to find the shortest
path from a single source vertex to all other vertices in the given graph.
Algorithm
1) Create a set sptSet (shortest path tree set) that keeps track of vertices in-
cluded in shortest path tree, i.e., whose minimum distance from source is calcu-
lated and finalized. Initially, this set is empty.
2) Assign a distance value to all vertices in the input graph. Initialize all dis-
tance values as INFINITE. Assign distance value as 0 for the source vertex so
that it is picked first.
3) While sptSet doesn’t include all vertices
….a) Pick a vertex u which is not there in sptSetand has minimum distance
value.
….b) Include u to sptSet.
….c) Update distance value of all adjacent vertices of u. To update the distance
values, iterate through all adjacent vertices. For every adjacent vertex v, if sum
of distance value of u (from source) and weight of edge u-v, is less than the
distance value of v, then update the distance value of v.
118
Let us understand with the following example:
The set sptSetis initially empty and distances assigned to vertices are {0, INF,
INF, INF, INF, INF, INF, INF} where INF indicates infinite. Now pick the
vertex with minimum distance value. The vertex 0 is picked, include it in sptSet.
So sptSet becomes {0}. After including 0 to sptSet, update distance values of
its adjacent vertices. Adjacent vertices of 0 are 1 and 7. The distance values of
1 and 7 are updated as 4 and 8. Following subgraph shows vertices and their
distance values, only the vertices with finite distance values are shown. The
vertices included in SPT are shown in green color.
Pick the vertex with minimum distance value and not already included in SPT
(not in sptSET). The vertex 1 is picked and added to sptSet. So sptSet now
becomes {0, 1}. Update the distance values of adjacent vertices of 1. The
distance value of vertex 2 becomes 12.
119
Pick the vertex with minimum distance value and not already included in SPT
(not in sptSET). Vertex 7 is picked. So sptSet now becomes {0, 1, 7}. Update
the distance values of adjacent vertices of 7. The distance value of vertex 6 and
8 becomes finite (15 and 9 respectively).
Pick the vertex with minimum distance value and not already included in SPT
(not in sptSET). Vertex 6 is picked. So sptSet now becomes {0, 1, 7, 6}. Update
the distance values of adjacent vertices of 6. The distance value of vertex 5 and
8 are updated.
We repeat the above steps until sptSet doesn’t include all vertices of given graph.
Finally, we get the following Shortest Path Tree (SPT).
120
How to implement the above algorithm?
We use a boolean array sptSet[] to represent the set of vertices included in SPT.
If a value sptSet[v] is true, then vertex v is included in SPT, otherwise not.
Array dist[] is used to store shortest distance values of all vertices.
#include <stdio.h>
#include <limits.h>
// A utility function to find the vertex with minimum distance value, from
// the set of vertices not yet included in shortest path tree
int minDistance(int dist[], bool sptSet[])
{
// Initialize min value
int min = INT_MAX, min_index;
return min_index;
}
121
// Funtion that implements Dijkstra's single source shortest path algorithm
// for a graph represented using adjacency matrix representation
void dijkstra(int graph[V][V], int src)
{
int dist[V]; // The output array. dist[i] will hold the shortest
// distance from src to i
122
/* Let us create the example graph discussed above */
int graph[V][V] = {{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}
};
dijkstra(graph, 0);
return 0;
}
Output:
Notes:
1) The code calculates shortest distance, but doesn’t calculate the path infor-
mation. We can create a parent array, update the parent array when distance
is updated (like prim’s implementation) and use it show the shortest path from
source to different vertices.
2) The code is for undirected graph, same dijekstra function can be used for
directed graphs also.
3) The code finds shortest distances from source to all vertices. If we are
interested only in shortest distance from source to a single target, we can break
the for loop when the picked minimum distance vertex is equal to target (Step
3.a of algorithm).
123
4) Time Complexity of the implementation is O(Vˆ2). If the input graph is
represented using adjacency list, it can be reduced to O(E log V) with the help
of binary heap. Please see
Source
http://www.geeksforgeeks.org/greedy-algorithms-set-6-dijkstras-shortest-path-algorithm/
Category: Graph Tags: Dijkstra, Graph, Greedy Algorithm
Post navigation
← Construction of Longest Monotonically Increasing Subsequence (N log N)
Amazon Interview | Set 11 →
Writing code in comment? Please use code.geeksforgeeks.org, generate link and
share the link here.
124
Chapter 22
125
3) While Min Heap is not empty, do following
…..a) Extract the vertex with minimum distance value node from Min Heap.
Let the extracted vertex be u.
…..b) For every adjacent vertex v of u, check if v is in Min Heap. If v is in Min
Heap and distance value is more than weight of u-v plus distance value of u,
then update the distance value of v.
Let us understand with the following example. Let the given source vertex be 0
Initially, distance value of source vertex is 0 and INF (infinite) for all other
vertices. So source vertex is extracted from Min Heap and distance values of
vertices adjacent to 0 (1 and 7) are updated. Min Heap contains all vertices
except vertex 0.
The vertices in green color are the vertices for which minimum distances are
finalized and are not in Min Heap
Since distance value of vertex 1 is minimum among all nodes in Min Heap, it
is extracted from Min Heap and distance values of vertices adjacent to 1 are
updated (distance is updated if the a vertex is not in Min Heap and distance
through 1 is shorter than the previous distance). Min Heap contains all vertices
except vertex 0 and 1.
126
Pick the vertex with minimum distance value from min heap. Vertex 7 is
picked. So min heap now contains all vertices except 0, 1 and 7. Update the
distance values of adjacent vertices of 7. The distance value of vertex 6 and 8
becomes finite (15 and 9 respectively).
Pick the vertex with minimum distance from min heap. Vertex 6 is picked. So
min heap now contains all vertices except 0, 1, 7 and 6. Update the distance
values of adjacent vertices of 6. The distance value of vertex 5 and 8 are updated.
Above steps are repeated till min heap doesn’t become empty. Finally, we get
the following shortest path tree.
127
// C / C++ program for Dijkstra's shortest path algorithm for adjacency
// list representation of graph
#include <stdio.h>
#include <stdlib.h>
#include <limits.h>
128
newNode->weight = weight;
newNode->next = NULL;
return newNode;
}
return graph;
}
129
int size; // Number of heap nodes present currently
int capacity; // Capacity of min heap
int *pos; // This is needed for decreaseKey()
struct MinHeapNode **array;
};
// A utility function to swap two nodes of min heap. Needed for min heapify
void swapMinHeapNode(struct MinHeapNode** a, struct MinHeapNode** b)
{
struct MinHeapNode* t = *a;
*a = *b;
*b = t;
}
130
if (left < minHeap->size &&
minHeap->array[left]->dist < minHeap->array[smallest]->dist )
smallest = left;
if (smallest != idx)
{
// The nodes to be swapped in min heap
MinHeapNode *smallestNode = minHeap->array[smallest];
MinHeapNode *idxNode = minHeap->array[idx];
// Swap positions
minHeap->pos[smallestNode->v] = idx;
minHeap->pos[idxNode->v] = smallest;
// Swap nodes
swapMinHeapNode(&minHeap->array[smallest], &minHeap->array[idx]);
minHeapify(minHeap, smallest);
}
}
131
minHeap->pos[root->v] = minHeap->size-1;
minHeap->pos[lastNode->v] = 0;
return root;
}
132
printf("Vertex Distance from Source\n");
for (int i = 0; i < n; ++i)
printf("%d \t\t %d\n", i, dist[i]);
}
// The main function that calulates distances of shortest paths from src to all
// vertices. It is a O(ELogV) function
void dijkstra(struct Graph* graph, int src)
{
int V = graph->V;// Get the number of vertices in graph
int dist[V]; // dist values used to pick minimum weight edge in cut
// Initialize min heap with all vertices. dist value of all vertices
for (int v = 0; v < V; ++v)
{
dist[v] = INT_MAX;
minHeap->array[v] = newMinHeapNode(v, dist[v]);
minHeap->pos[v] = v;
}
133
// If shortest distance to v is not finalized yet, and distance to v
// through u is less than its previously calculated distance
if (isInMinHeap(minHeap, v) && dist[u] != INT_MAX &&
pCrawl->weight + dist[u] < dist[v])
{
dist[v] = dist[u] + pCrawl->weight;
dijkstra(graph, 0);
return 0;
}
134
Output:
135
Introduction to Algorithms by Clifford Stein, Thomas H. Cormen, Charles E.
Leiserson, Ronald L.
Algorithms by Sanjoy Dasgupta, Christos Papadimitriou, Umesh Vazirani
Please write comments if you find anything incorrect, or you want to share more
information about the topic discussed above.
Source
http://www.geeksforgeeks.org/greedy-algorithms-set-7-dijkstras-algorithm-for-adjacency-list-representation/
Category: Graph Tags: Dijkstra, Graph, Greedy Algorithm
Post navigation
← Oracle Interview | Set 1 Divide and Conquer | Set 2 (Closest Pair of Points)
→
Writing code in comment? Please use code.geeksforgeeks.org, generate link and
share the link here.
136
Chapter 23
Boruvka’s algorithm
Below is the idea behind above algorithm (The idea is same as Prim’s MST
algorithm).
A spanning tree means all vertices must be connected. So the two disjoint subsets
(discussed above) of vertices must be connected to make a Spanning Tree. And
137
they must be connected with the minimum weight edge to make it a Minimum
Spanning Tree.
Let us understand the algorithm with below example.
For every component, find the cheapest edge that connects it to some other
component.
138
The cheapest edges are highlighted with green color. Now MST becomes {0-1,
2-8, 2-3, 3-4, 5-6, 6-7}.
After above step, components are {{0,1}, {2,3,4,8}, {5,6,7}}. The components
are encircled with blue color.
We again repeat the step, i.e., for every component, find the cheapest edge that
connects it to some other component.
The cheapest edges are highlighted with green color. Now MST becomes {0-1,
2-8, 2-3, 3-4, 5-6, 6-7, 1-2, 2-5}
139
At this stage, there is only one component {0, 1, 2, 3, 4, 5, 6, 7, 8} which has
all edges. Since there is only one component left, we stop and return MST.
Implementation:
Below is C++ implementation of above algorithm. The input graph is repre-
sented as a collection of edges and union-find data structure is used to keep
track of components.
140
int parent;
int rank;
};
141
int set1 = find(subsets, edge[i].src);
int set2 = find(subsets, edge[i].dest);
if (cheapest[set1] == -1 ||
edge[cheapest[set2]].weight > edge[i].weight)
cheapest[set2] = i;
}
}
if (set1 == set2)
continue;
MSTweight += edge[cheapest[i]].weight;
printf("Edge %d-%d included in MST\n",
edge[cheapest[i]].src, edge[cheapest[i]].dest,
edge[cheapest[i]].weight);
142
printf("Weight of MST is %d\n", MSTweight);
return;
}
return subsets[i].parent;
}
143
subsets[yroot].parent = xroot;
subsets[xroot].rank++;
}
}
144
boruvkaMST(graph);
return 0;
}
Output:
Source
http://www.geeksforgeeks.org/greedy-algorithms-set-9-boruvkas-algorithm/
145
Chapter 24
Bellman–Ford Algorithm
Given a graph and a source vertex src in graph, find shortest paths from src to
all vertices in the given graph. The graph may contain negative weight edges.
We have discussed Dijkstra’s algorithm for this problem. Dijksra’s algorithm is a
Greedy algorithm and time complexity is O(VLogV) (with the use of Fibonacci
heap). Dijkstra doesn’t work for Graphs with negative weight edges, Bellman-
Ford works for such graphs. Bellman-Ford is also simpler than Dijkstra and
suites well for distributed systems. But time complexity of Bellman-Ford is
O(VE), which is more than Dijkstra.
Algorithm
Following are the detailed steps.
Input: Graph and a source vertex src
Output: Shortest distance to all vertices from src. If there is a negative weight
cycle, then shortest distances are not calculated, negative weight cycle is re-
ported.
1) This step initializes distances from source to all vertices as infinite and dis-
tance to source itself as 0. Create an array dist[] of size |V| with all values as
infinite except dist[src] where src is source vertex.
2) This step calculates shortest distances. Do following |V|-1 times where |V|
is the number of vertices in given graph.
…..a) Do following for each edge u-v
………………If dist[v] > dist[u] + weight of edge uv, then update dist[v]
………………….dist[v] = dist[u] + weight of edge uv
3) This step reports if there is a negative weight cycle in graph. Do following
for each edge u-v
……If dist[v] > dist[u] + weight of edge uv, then “Graph contains negative weight
cycle”
The idea of step 3 is, step 2 guarantees shortest distances if graph doesn’t contain
146
negative weight cycle. If we iterate through all edges one more time and get a
shorter path for any vertex, then there is a negative weight cycle
How does this work? Like other Dynamic Programming Problems, the al-
gorithm calculate shortest paths in bottom-up manner. It first calculates the
shortest distances for the shortest paths which have at-most one edge in the
path. Then, it calculates shortest paths with at-nost 2 edges, and so on. Af-
ter the ith iteration of outer loop, the shortest paths with at most i edges are
calculated. There can be maximum |V| – 1 edges in any simple path, that is
why the outer loop runs |v| – 1 times. The idea is, assuming that there is no
negative weight cycle, if we have calculated shortest paths with at most i edges,
then an iteration over all edges guarantees to give shortest path with at-most
(i+1) edges (Proof is simple, you can refer this or MIT Video Lecture)
Example
Let us understand the algorithm with following example graph. The images are
taken from thissource.
Let the given source vertex be 0. Initialize all distances as infinite, except the
distance to source itself. Total number of vertices in the graph is 5, so all edges
must be processed 4 times.
Let all edges are processed in following order: (B,E), (D,B), (B,D), (A,B),
(A,C), (D,C), (B,C), (E,D). We get following distances when all edges are
processed first time. The first row in shows initial distances. The second row
shows distances when edges (B,E), (D,B), (B,D) and (A,B) are processed. The
third row shows distances when (A,C) is processed. The fourth row shows
when (D,C), (B,C) and (E,D) are processed.
147
The first iteration guarantees to give all shortest paths which are at most 1 edge
long. We get following distances when all edges are processed second time (The
last row shows final values).
The second iteration guarantees to give all shortest paths which are at most 2
edges long. The algorithm processes all edges 2 more times. The distances are
minimized after the second iteration, so third and fourth iterations don’t update
the distances.
Implementation:
C++
#include <stdio.h>
148
#include <stdlib.h>
#include <string.h>
#include <limits.h>
graph->edge =
(struct Edge*) malloc( graph->E * sizeof( struct Edge ) );
return graph;
}
149
void BellmanFord(struct Graph* graph, int src)
{
int V = graph->V;
int E = graph->E;
int dist[V];
printArr(dist, V);
return;
}
150
int main()
{
/* Let us create the graph given in above example */
int V = 5; // Number of vertices in graph
int E = 8; // Number of edges in graph
struct Graph* graph = createGraph(V, E);
151
BellmanFord(graph, 0);
return 0;
}
Java
int V, E;
Edge edge[];
152
{
int V = graph.V, E = graph.E;
int dist[] = new int[V];
153
for (int i=0; i<V; ++i)
System.out.println(i+"\t\t"+dist[i]);
}
154
// add edge 4-3 (or E-D in above figure)
graph.edge[7].src = 4;
graph.edge[7].dest = 3;
graph.edge[7].weight = -3;
graph.BellmanFord(graph, 0);
}
}
// Contributed by Aakash Hasija
Output:
Notes
1) Negative weights are found in various applications of graphs. For example,
instead of paying cost for a path, we may get some advantage if we follow the
path.
2) Bellman-Ford works better (better than Dijksra’s) for distributed systems.
Unlike Dijksra’s where we need to find minimum value of all vertices, in Bellman-
Ford, edges are considered one by one.
Exercise
1) The standard Bellman-Ford algorithm reports shortest path only if there is
no negative weight cycles. Modify it so that it reports minimum distances even
if there is a negative weight cycle.
2) Can we use Dijksra’s algorithm for shortest paths for graphs with negative
weights – one idea can be, calculate the minimum weight value, add a positive
value (equal to absolute value of minimum weight value) to all weights and run
the Dijksra’s algorithm for the modified graph. Will this algorithm work?
References:
http://www.youtube.com/watch?v=Ttezuzs39nk
http://en.wikipedia.org/wiki/Bellman%E2%80%93Ford_algorithm
http://www.cs.arizona.edu/classes/cs445/spring07/ShortestPath2.prn.pdf
155
Please write comments if you find anything incorrect, or you want to share more
information about the topic discussed above.
Source
http://www.geeksforgeeks.org/dynamic-programming-set-23-bellman-ford-algorithm/
156
Chapter 25
The Floyd Warshall Algorithm is for solving the All Pairs Shortest Path problem.
The problem is to find shortest distances between every pair of vertices in a given
edge weighted directed Graph.
Example:
Input:
graph[][] = { {0, 5, INF, 10},
{INF, 0, 3, INF},
{INF, INF, 0, 1},
{INF, INF, INF, 0} }
which represents the following graph
10
(0)------->(3)
| /|\
5 | |
| | 1
\|/ |
(1)------->(2)
3
Note that the value of graph[i][j] is 0 if i is equal to j
And graph[i][j] is INF (infinite) if there is no edge from vertex i to j.
Output:
Shortest distance matrix
0 5 8 9
INF 0 3 4
INF INF 0 1
INF INF INF 0
157
Floyd Warshall Algorithm
We initialize the solution matrix same as the input graph matrix as a first
step. Then we update the solution matrix by considering all vertices as an
intermediate vertex. The idea is to one by one pick all vertices and update all
shortest paths which include the picked vertex as an intermediate vertex in the
shortest path. When we pick vertex number k as an intermediate vertex, we
already have considered vertices {0, 1, 2, .. k-1} as intermediate vertices. For
every pair (i, j) of source and destination vertices respectively, there are two
possible cases.
1) k is not an intermediate vertex in shortest path from i to j. We keep the
value of dist[i][j] as it is.
2) k is an intermediate vertex in shortest path from i to j. We update the value
of dist[i][j] as dist[i][k] + dist[k][j].
The following figure is taken from the Cormen book. It shows the above optimal
substructure property in the all-pairs shortest path problem.
C/C++
158
// Solves the all-pairs shortest path problem using Floyd Warshall algorithm
void floydWarshell (int graph[][V])
{
/* dist[][] will be the output matrix that will finally have the shortest
distances between every pair of vertices */
int dist[V][V], i, j, k;
159
for (int i = 0; i < V; i++)
{
for (int j = 0; j < V; j++)
{
if (dist[i][j] == INF)
printf("%7s", "INF");
else
printf ("%7d", dist[i][j]);
}
printf("\n");
}
}
Java
160
import java.io.*;
class AllPairShortestPath
{
final static int INF = 99999, V = 4;
161
// Print the shortest distance matrix
printSolution(dist);
}
162
Output:
Following matrix shows the shortest distances between every pair of vertices
0 5 8 9
INF 0 3 4
INF INF 0 1
INF INF INF 0
#include<limits.h>
Please write comments if you find anything incorrect, or you want to share more
information about the topic discussed above
Source
http://www.geeksforgeeks.org/dynamic-programming-set-16-floyd-warshall-algorithm/
163
Chapter 26
The problem is to find shortest paths between every pair of vertices in a given
weighted directed Graph and weights may be negative. We have discussed Floyd
Warshall Algorithm for this problem. Time complexity of Floyd Warshall
Algorithm is Θ(V3 ). Using Johnson’s algorithm, we can find all pair shortest
paths in O(V2 log V + VE) time. Johnson’s algorithm uses both Dijkstra and
Bellman-Ford as subroutines.
If we apply Dijkstra’s Single Source shortest path algorithm for every ver-
tex, considering every vertex as source, we can find all pair shortest paths in
O(V*VLogV) time. So using Dijkstra’s single source shortest path seems to be
a better option than Floyd Warshell, but the problem with Dijkstra’s algorithm
is, it doesn’t work for negative weight edge.
The idea of Johnson’s algorithm is to re-weight all edges and make them all
positive, then apply Dijkstra’s algorithm for every vertex.
How to transform a given graph to a graph with all non-negative
weight edges?
One may think of a simple approach of finding the minimum weight edge and
adding this weight to all edges. Unfortunately, this doesn’t work as there may
be different number of edges in different paths (See this for an example). If there
are multiple paths from a vertex u to v, then all paths must be increased by
same amount, so that the shortest path remains the shortest in the transformed
graph.
The idea of Johnson’s algorithm is to assign a weight to every vertex. Let the
weight assigned to vertex u be h[u]. We reweight edges using vertex weights. For
example, for an edge (u, v) of weight w(u, v), the new weight becomes w(u, v)
+ h[u] – h[v]. The great thing about this reweighting is, all set of paths between
any two vertices are increased by same amount and all negative weights become
164
non-negative. Consider any path between two vertices s and t, weight of every
path is increased by h[s] – h[t], all h[] values of vertices on path from s to t
cancel each other.
How do we calculate h[] values? Bellman-Ford algorithm is used for this purpose.
Following is the complete algorithm. A new vertex is added to the graph and
connected to all existing vertices. The shortest distance values from new vertex
to all existing vertices are h[] values.
Algorithm:
1) Let the given graph be G. Add a new vertex s to the graph, add edges from
new vertex to all vertices of G. Let the modified graph be G’.
2) Run Bellman-Ford algorithm on G’ with s as source. Let the distances
calculated by Bellman-Ford be h[0], h[1], .. h[V-1]. If we find a negative weight
cycle, then return. Note that the negative weight cycle cannot be created by
new vertex s as there is no edge to s. All edges are from s.
3) Reweight the edges of original graph. For each edge (u, v), assign the new
weight as “original weight + h[u] – h[v]”.
4) Remove the added vertex s and run Dijkstra’s algorithm for every vertex.
How does the transformation ensure nonnegative weight edges?
The following property is always true about h[] values as they are shortest
distances.
h[v]
The property simply means, shortest distance from s to v must be smaller than or equal to shorte
We add a source s and add edges from s to all vertices of the original graph. In the following di
We calculate the shortest distances from 4 to all other vertices using Bellman-Ford algorithm.
Since all weights are positive now, we can run Dijkstra's shortest path algorithm for every vert
Time Complexity: The main steps in algorithm are Bellman Ford Algorithm called once and Dijkstr
The time complexity of Johnson's algorithm becomes same as Floyd Warshell when the graphs is com
References:
Introduction to Algorithms 3rd Edition by Clifford Stein, Thomas H. Cormen, Charles E. Leiserso
http://www.youtube.com/watch?v=b6LOHvCzmkI
http://www.youtube.com/watch?v=TV2Z6nbo1ic
165
http://en.wikipedia.org/wiki/Johnson%27s_algorithm
http://www.youtube.com/watch?v=Sygq1e0xWnM
Please write comments if you find anything incorrect, or you want to share more information abou
Source
http://www.geeksforgeeks.org/johnsons-algorithm/
166
Chapter 27
Given a Weighted Directed Acyclic Graph and a source vertex in the graph, find
the shortest paths from given source to all other vertices.
For a general weighted graph, we can calculate single source shortest distances
in O(VE) time using Bellman–Ford Algorithm. For a graph with no negative
weights, we can do better and calculate single source shortest distances in O(E
+ VLogV) time using Dijkstra’s algorithm. Can we do even better for Directed
Acyclic Graph (DAG)? We can calculate single source shortest distances in
O(V+E) time for DAGs. The idea is to use Topological Sorting.
We initialize distances to all vertices as infinite and distance to source as 0, then
we find a topological sorting of the graph. Topological Sorting of a graph rep-
resents a linear ordering of the graph (See below, figure (b) is a linear represen-
tation of figure (a) ). Once we have topological order (or linear representation),
we one by one process all vertices in topological order. For every vertex being
processed, we update distances of its adjacent using distance of current vertex.
Following figure is taken from this source. It shows step by step process of
finding shortest paths.
167
Following is complete algorithm for finding shortest distances.
1) Initialize dist[] = {INF, INF, ….} and dist[s] = 0 where s is the source vertex.
2) Create a toplogical order of all vertices.
3) Do following for every vertex u in topological order.
………..Do following for every adjacent vertex v of u
………………if (dist[v] > dist[u] + weight(u, v))
// A C++ program to find single source shortest paths for Directed Acyclic Graphs
#include<iostream>
#include <list>
#include <stack>
#include <limits.h>
#define INF INT_MAX
using namespace std;
168
// Graph is represented using adjacency list. Every node of adjacency list
// contains vertex number of the vertex to which edge connects. It also
// contains weight of the edge
class AdjListNode
{
int v;
int weight;
public:
AdjListNode(int _v, int _w) { v = _v; weight = _w;}
int getV() { return v; }
int getWeight() { return weight; }
};
Graph::Graph(int V)
{
this->V = V;
adj = new list<AdjListNode>[V];
}
169
// A recursive function used by shortestPath. See below link for details
// http://www.geeksforgeeks.org/topological-sorting/
void Graph::topologicalSortUtil(int v, bool visited[], stack<int> &Stack)
{
// Mark the current node as visited
visited[v] = true;
// The function to find shortest paths from given vertex. It uses recursive
// topologicalSortUtil() to get topological sorting of given graph.
void Graph::shortestPath(int s)
{
stack<int> Stack;
int dist[V];
170
{
// Get the next vertex from topological order
int u = Stack.top();
Stack.pop();
int s = 1;
cout << "Following are shortest distances from source " << s <<" \n";
g.shortestPath(s);
return 0;
}
171
Output:
Source
http://www.geeksforgeeks.org/shortest-path-for-directed-acyclic-graphs/
Category: Graph Tags: Graph
Post navigation
← Topological Sorting Tree Isomorphism Problem →
Writing code in comment? Please use code.geeksforgeeks.org, generate link and
share the link here.
172
Chapter 28
Question 1: Given a directed weighted graph. You are also given the
shortest path from a source vertex ‘s’ to a destination vertex ‘t’. If
weight of every edge is increased by 10 units, does the shortest path
remain same in the modified graph?
The shortest path may change. The reason is, there may be different number of
edges in different paths from s to t. For example, let shortest path be of weight
15 and has 5 edges. Let there be another path with 2 edges and total weight
25. The weight of the shortest path is increased by 5*10 and becomes 15 + 50.
Weight of the other path is increased by 2*10 and becomes 25 + 20. So the
shortest path changes to the other path with weight as 45.
Question 2: This is similar to above question. Does the shortest path
change when weights of all edges are multiplied by 10?
If we multiply all edge weights by 10, the shortest path doesn’t change. The
reason is simple, weights of all paths from s to t get multiplied by same amount.
The number of edges on a path doesn’t matter. It is like changing unit of
weights.
Question 3: Given a directed graph where every edge has weight as
either 1 or 2, find the shortest path from a given source vertex ‘s’ to
a given destination vertex ‘t’. Expected time complexity is O(V+E).
If we apply Dijkstra’s shortest path algorithm, we can get a shortest path in
O(E + VLogV) time. How to do it in O(V+E) time? The idea is to use BFS.
One important observation about BFSis, the path used in BFS always has least
number of edges between any two vertices. So if all edges are of same weight,
we can use BFS to find the shortest path. For this problem, we can modify
the graph and split all edges of weight 2 into two edges of weight 1 each. In
the modified graph, we can use BFS to find the shortest path. How is this
173
approach O(V+E)? In worst case, all edges are of weight 2 and we need to
do O(E) operations to split all edges, so the time complexity becomes O(E) +
O(V+E) which is O(V+E).
Question 4: Given a directed acyclic weighted graph, how to find the
shortest path from a source s to a destination t in O(V+E) time?
See: Shortest Path in Directed Acyclic Graph
More Questions See following links for more questions.
http://algs4.cs.princeton.edu/44sp/
http://geeksquiz.com/graph-shortest-paths/
Please write comments if you find anything incorrect, or you want to share more
information about the topic discussed above.
Source
http://www.geeksforgeeks.org/interesting-shortest-path-questions-set-1/
174
Chapter 29
Given a directed and two vertices ‘u’ and ‘v’ in it, find shortest path from ‘u’
to ‘v’ with exactly k edges on the path.
The graph is given as adjacency matrix representation where value of graph[i][j]
indicates the weight of an edge from vertex i to vertex j and a value INF(infinite)
indicates no edge from i to j.
For example consider the following graph. Let source ‘u’ be vertex 0, destination
‘v’ be 3 and k be 2. There are two walks of length 2, the walks are {0, 2, 3} and
{0, 1, 3}. The shortest among the two is {0, 2, 3} and weight of path is 3+6 =
9.
175
The idea is to browse through all paths of length k from u to v using the
approach discussed in the previous post and return weight of the shortest path.
A simple solution is to start from u, go to all adjacent vertices and recur for
adjacent vertices with k as k-1, source as adjacent vertex and destination as v.
Following is C++ implementation of this simple solution.
// Initialize result
int res = INF;
176
for (int i = 0; i < V; i++)
{
if (graph[u][i] != INF && u != i && v != i)
{
int rec_res = shortestPath(graph, i, v, k-1);
if (rec_res != INF)
res = min(res, graph[u][i] + rec_res);
}
}
return res;
}
Output:
The worst case time complexity of the above function is O(Vk ) where V is
the number of vertices in the given graph. We can simply analyze the time
complexity by drawing recursion tree. The worst occurs for a complete graph. In
worst case, every internal node of recursion tree would have exactly V children.
We can optimize the above solution using Dynamic Programming. The
idea is to build a 3D table where first dimension is source, second dimension is
destination, third dimension is number of edges from source to destination, and
the value is count of walks. Like other Dynamic Programming problems, we fill
the 3D table in bottom up manner.
177
// Dynamic Programming based C++ program to find shortest path with
// exactly k edges
#include <iostream>
#include <climits>
using namespace std;
178
}
}
}
}
return sp[u][v][k];
}
Output:
Time complexity of the above DP based solution is O(V3 K) which is much better
than the naive solution.
This article is contributed by Abhishek. Please write comments if you find
anything incorrect, or you want to share more information about the topic
discussed above
Source
http://www.geeksforgeeks.org/shortest-path-exactly-k-edges-directed-weighted-graph/
Category: Graph Tags: Dynamic Programming
Post navigation
← Connect n ropes with minimum cost Tarjan’s Algorithm to find Strongly
Connected Components →
Writing code in comment? Please use code.geeksforgeeks.org, generate link and
share the link here.
179
Chapter 30
Given a Directed Graph and two vertices in it, check whether there is a path
from the first given vertex to second. For example, in the following graph,
there is a path from vertex 1 to 3. As another example, there is no path from
3 to 0.
We can either use Breadth First Search (BFS) or Depth First Search (DFS) to
find path between two vertices. Take the first vertex as source in BFS (or DFS),
follow the standard BFS (or DFS). If we see the second vertex in our traversal,
then return true. Else return false.
180
Following is C++ code that uses BFS for finding reachability of second vertex
from first vertex.
Graph::Graph(int V)
{
this->V = V;
adj = new list<int>[V];
}
181
// Mark the current node as visited and enqueue it
visited[s] = true;
queue.push_back(s);
while (!queue.empty())
{
// Dequeue a vertex from queue and print it
s = queue.front();
queue.pop_front();
return false;
}
182
int u = 1, v = 3;
if(g.isReachable(u, v))
cout<< "\n There is a path from " << u << " to " << v;
else
cout<< "\n There is no path from " << u << " to " << v;
u = 3, v = 1;
if(g.isReachable(u, v))
cout<< "\n There is a path from " << u << " to " << v;
else
cout<< "\n There is no path from " << u << " to " << v;
return 0;
}
Output:
As an exercise, try an extended version of the problem where the complete path
between two vertices is also needed.
Please write comments if you find anything incorrect, or you want to share more
information about the topic discussed above.
Source
http://www.geeksforgeeks.org/find-if-there-is-a-path-between-two-vertices-in-a-given-graph/
Category: Graph Tags: Graph
183
Chapter 31
Given an array of strings, find if the given strings can be chained to form a circle.
A string X can be put before another string Y in circle if the last character of
X is same as first character of Y.
Examples:
184
The strings can be chained as "aaa", "aab", "bbb"
and "baa"
185
Graph(int V);
~Graph() { delete [] adj; delete [] in; }
Graph getTranspose();
};
Graph::Graph(int V)
{
this->V = V;
adj = new list<int>[V];
in = new int[V];
for (int i = 0; i < V; i++)
in[i] = 0;
}
return true;
}
186
// Mark the current node as visited and print it
visited[v] = true;
187
// If DFS traversal doesn’t visit all vertices, then return false.
for (int i = 0; i < V; i++)
if (adj[i].size() > 0 && visited[i] == false)
return false;
return true;
}
188
// Driver program to test above functions
int main()
{
string arr1[] = {"for", "geek", "rig", "kaf"};
int n1 = sizeof(arr1)/sizeof(arr1[0]);
canBeChained(arr1, n1)? cout << "Can be chained \n" :
cout << "Can't be chained \n";
return 0;
}
Output:
Can be chained
Can't be chained
Source
http://www.geeksforgeeks.org/given-array-strings-find-strings-can-chained-form-circle/
Category: Graph Strings
Post navigation
← Given a sorted dictionary of an alien language, find order of characters Com-
parison of a float with a value in C →
Writing code in comment? Please use code.geeksforgeeks.org, generate link and
share the link here.
189
Chapter 32
Given a list of contacts containing username, email and phone number in any
order. Identify the same contacts (i.e., same person having many different con-
tacts) and output the same contacts together.
Notes:
1) A contact can store its three fields in any order, i.e., phone number can appear
before username or username can appear before phone number.
2) Two contacts are same if they have either same username or email or phone
number.
Example:
Input: contact[] =
{ {"Gaurav", "[email protected]", "[email protected]"},
{ "Lucky", "[email protected]", "+1234567"},
{ "gaurav123", "+5412312", "[email protected]"}.
{ "gaurav1993", "+5412312", "[email protected]"}
}
Output:
0 2 3
1
contact[2] is same as contact[3] because they both have same
contact number.
contact[0] is same as contact[3] because they both have same
e-mail address.
Therefore, contact[0] and contact[2] are also same.
190
We strongly recommend you to minimize your browser and try this
yourself first.
Input is basically an array of structures. A structure contains three fields such
that any field can represent any detail about a contact.
The idea is to first create a graph of contacts using given array. In the graph,
there is an edge between vertex i to vertex j if they both have either same
username or same email or same phone number. Once the graph is constructed,
the task reduces to finding connected components in an undirected graph. We
can find connected components either by doing DFSor BFSstarting from every
unvisited vertex. In below code, DFS is used.
Below is C++ implementation of this idea.
191
arr[i].field1 == arr[j].field2 ||
arr[i].field1 == arr[j].field3 ||
arr[i].field2 == arr[j].field1 ||
arr[i].field2 == arr[j].field2 ||
arr[i].field2 == arr[j].field3 ||
arr[i].field3 == arr[j].field1 ||
arr[i].field3 == arr[j].field2 ||
arr[i].field3 == arr[j].field3)
{
mat[i][j] = 1;
mat[j][i] = 1;
break;
}
}
}
192
// Since, we made a graph with contacts as nodes with fields as links.
// two nodes are linked if they represent the same person.
// so, total number of connected components and nodes in each component
// will be our answer.
for (int i = 0; i < n; i++)
{
if (!visited[i])
{
DFSvisit(i, mat, visited, sol, n);
// Drive program
int main()
{
contact arr[] = {{"Gaurav", "[email protected]", "[email protected]"},
{"Lucky", "[email protected]", "+1234567"},
{"gaurav123", "+5412312", "[email protected]"},
{"gaurav1993", "+5412312", "[email protected]"},
{"raja", "+2231210", "[email protected]"},
{"bahubali", "+878312", "raja"}
};
Output:
0 3 2
1
4 5
193
Time complexity: O(n2 ) where n is number of contacts.
Thanks to Gaurav Ahirwar for above solution.
Please write comments if you find anything incorrect, or you want to share more
information about the topic discussed above
Source
http://www.geeksforgeeks.org/find-same-contacts-in-a-list-of-contacts/
Category: Graph
Post navigation
← Interview with WOW Labz for MEAN Stack Developer EXl Analytics Inter-
view Experience | Set 2 (On-Campus) →
Writing code in comment? Please use code.geeksforgeeks.org, generate link and
share the link here.
194
Chapter 33
There are N stations on route of a train. The train goes from station 0 to N-1.
The ticket cost for all pair of stations (i, j) is given where j is greater than i.
Find the minimum cost to reach the destination.
Consider the following example:
Input:
cost[N][N] = { {0, 15, 80, 90},
{INF, 0, 40, 50},
{INF, INF, 0, 70},
{INF, INF, INF, 0}
};
There are 4 stations and cost[i][j] indicates cost to reach j
from i. The entries where j
We strongly recommend to minimize your browser and try this yourself first.
The minimum cost to reach N-1 from 0 can be recursively written as following:
195
The following is C++ implementation of above recursive formula.
// infinite value
#define INF INT_MAX
// Number of stations
#define N 4
196
// Driver program to test above function
int main()
{
int cost[N][N] = { {0, 15, 80, 90},
{INF, 0, 40, 50},
{INF, INF, 0, 70},
{INF, INF, INF, 0}
};
cout << "The Minimum cost to reach station "
<< N << " is " << minCost(cost);
return 0;
}
Output:
197
3) The min cost for station 2 is minimum of following two.
a) dist[0] + cost[0][2]
b) dist[1] + cost[1][2]
3) The min cost for station 3 is minimum of following three.
a) dist[0] + cost[0][3]
b) dist[1] + cost[1][3]
c) dist[2] + cost[2][3]
Similarly, dist[4], dist[5], … dist[N-1] are calculated.
Below is C++ implementation of above idea.
return dist[N-1];
}
198
int cost[N][N] = { {0, 15, 80, 90},
{INF, 0, 40, 50},
{INF, INF, 0, 70},
{INF, INF, INF, 0}
};
cout << "The Minimum cost to reach station "
<< N << " is " << minCost(cost);
return 0;
}
Output:
Source
http://www.geeksforgeeks.org/find-the-minimum-cost-to-reach-a-destination-where-every-station-is-connecte
Category: Dynamic Programming Graph Tags: Dynamic Programming
Post navigation
← Fiberlink (maas360) Interview | Set 2 (Written Test Question) VMWare
Interview Experience | Set 2 (On-Campus) →
Writing code in comment? Please use code.geeksforgeeks.org, generate link and
share the link here.
199
Chapter 34
200
2) Do following for every pair of adjacent words in given sorted array.
…..a) Let the current pair of words be word1 and word2. One by one compare
characters of both words and find the first mismatching characters.
…..b) Create an edge in g from mismatching character of word1 to that of word2.
3) Print topological sorting of the above created graph.
Following is C++ implementation of the above algorithm.
Graph::Graph(int V)
{
this->V = V;
adj = new list<int>[V];
}
201
// A recursive function used by topologicalSort
void Graph::topologicalSortUtil(int v, bool visited[], stack<int> &Stack)
{
// Mark the current node as visited.
visited[v] = true;
202
// This function fidns and prints order of characer from a sorted
// array of words. n is size of words[]. alpha is set of possible
// alphabets.
// For simplicity, this function is written in a way that only
// first 'alpha' characters can be there in words array. For
// example if alpha is 7, then words[] should have only 'a', 'b',
// 'c' 'd', 'e', 'f', 'g'
void printOrder(string words[], int n, int alpha)
{
// Create a graph with 'aplha' edges
Graph g(alpha);
Output:
203
c a b
Time Complexity: The first step to create a graph takes O(n + alhpa) time
where n is number of given words and alpha is number of characters in given
alphabet. The second step is also topological sorting. Note that there would
be alpha vertices and at-most (n-1) edges in the graph. The time complexity
of topological sorting is O(V+E) which is O(n + aplha) here. So overall time
complexity is O(n + aplha) + O(n + aplha) which is O(n + aplha).
Exercise:
The above code doesn’t work when the input is not valid. For example {“aba”,
“bba”, “aaa”} is not valid, because from first two words, we can deduce ‘a’ should
appear before ‘b’, but from last two words, we can deduce ‘b’ should appear
before ‘a’ which is not possible. Extend the above program to handle invalid
inputs and generate the output as “Not valid”.
This article is contributed by Piyush Gupta. Please write comments if you
find anything incorrect, or you want to share more information about the topic
discussed above.
Source
http://www.geeksforgeeks.org/given-sorted-dictionary-find-precedence-characters/
Category: Graph Strings
Post navigation
← Flipkart Interview | Set 10 (On-Campus For SDE-1) Given an array of strings,
find if the strings can be chained to form a circle →
Writing code in comment? Please use code.geeksforgeeks.org, generate link and
share the link here.
204
Chapter 35
Given a dictionary, and two words ‘start’ and ‘target’ (both of same length).
Find length of the smallest chain from ‘start’ to ‘target’ if it exists, such that
adjacent words in the chain only differ by one character and each word in the
chain is a valid word i.e., it exists in the dictionary. It may be assumed that the
‘target’ word exists in dictionary and length of all dictionary words is same.
Example:
205
#include<bits/stdc++.h>
using namespace std;
206
// Process a dictionary word if it is adjacent to current
// word (or vertex) of BFS
string temp = *it;
if (isadjacent(curr.word, temp))
{
// Add the dictionary word to Q
item.word = temp;
item.len = curr.len + 1;
Q.push(item);
// If we reached target
if (temp == target)
return item.len;
}
}
}
return 0;
}
// Driver program
int main()
{
// make dictionary
set<string> D;
D.insert("poon");
D.insert("plee");
D.insert("same");
D.insert("poie");
D.insert("plie");
D.insert("poin");
Output:
207
Length of shortest chain is: 7
Thanks to Gaurav Ahirwar and Rajnish Kumar Jha for above solution.
Please write comments if you find anything incorrect, or you want to share more
information about the topic discussed above.
Source
http://www.geeksforgeeks.org/length-of-shortest-chain-to-reach-a-target-word/
Category: Graph
208
Chapter 36
Given a matrix of dimension m*n where each cell in the matrix can have values
0, 1 or 2 which has the following meaning:
0: Empty cell
So we have to determine what is the minimum time required so that all the or-
anges become rotten. A rotten orange at index [i,j] can rot other fresh orange at
indexes [i-1,j], [i+1,j], [i,j-1], [i,j+1] (up, down, left and right). If it is impossible
to rot every orange then simply return -1.
Examples:
209
{0, 0, 1, 2, 1},
{1, 0, 0, 2, 1}};
Output:
All oranges cannot be rotten.
1) Create an empty Q.
2) Find all rotten oranges and enqueue them to Q. Also enqueue
a delimiter to indicate beginning of next time frame.
3) While Q is not empty do following
3.a) While delimiter in Q is not reached
(i) Dequeue an orange from queue, rot all adjacent oranges.
While rotting the adjacents, make sure that time frame
is incremented only once. And time frame is not icnremented
if there are no adjacent oranges.
3.b) Dequeue the old delimiter and enqueue a new delimiter. The
oranges rotten in previous time frame lie between the two
delimiters.
210
// structure for storing coordinates of the cell
struct ele {
int x, y;
};
// Store all the cells having rotten orange in first time frame
for (int i=0; i<R; i++)
{
for (int j=0; j<C; j++)
{
if (arr[i][j] == 2)
{
temp.x = i;
temp.y = j;
Q.push(temp);
}
}
}
211
// Separate these rotten oranges from the oranges which will rotten
// due the oranges in first time frame using delimiter which is (-1, -1)
temp.x = -1;
temp.y = -1;
Q.push(temp);
// Process the grid while there are rotten oranges in the Queue
while (!Q.empty())
{
// This flag is used to determine whether even a single fresh
// orange gets rotten due to rotten oranges in current time
// frame so we can increase the count of the required time.
bool flag = false;
212
// Check top adjacent cell that if it can be rotten
if (isvalid(temp.x, temp.y+1) && arr[temp.x][temp.y+1] == 1) {
if (!flag) ans++, flag = true;
arr[temp.x][temp.y+1] = 2;
temp.y++;
Q.push(temp); // Push this cell to Queue
temp.y--;
}
Q.pop();
}
// Drive program
int main()
{
int arr[][C] = { {2, 1, 0, 2, 1},
{1, 0, 1, 2, 1},
{1, 0, 0, 2, 1}};
int ans = rotOranges(arr);
if (ans == -1)
213
cout << "All oranges cannot rot\n";
else
cout << "Time required for all oranges to rot => " << ans << endl;
return 0;
}
Output:
Source
http://www.geeksforgeeks.org/minimum-time-required-so-that-all-oranges-become-rotten/
Category: Graph Matrix Queue Tags: Graph, Matrix
Post navigation
← Flipkart Interview Experience| Set 35 (On-Campus for SDE 1) Morgan Stan-
ley Interview | Set 15 (On-Campus) →
Writing code in comment? Please use code.geeksforgeeks.org, generate link and
share the link here.
214
Chapter 37
A person is determined to finish the book in ‘k’ days but he never wants to stop
a chapter in between. Find the optimal assignment of chapters, such that the
person doesn’t read too many extra/less pages overall.
Example 1:
Input: Number of Days to Finish book = 2
Number of pages in chapters = {10, 5, 5}
Output: Day 1: Chapter 1
Day 2: Chapters 2 and 3
Example 2:
Input: Number of Days to Finish book = 3
Number of pages in chapters = {8, 5, 6, 12}
Output: Day 1: Chapter 1
Day 2: Chapters 2 and 3
Day 2: Chapter 4
The target is to minimize the sum of differences between the pages read on
each day and average number of pages. If the average number of pages is a
non-integer, then it should be rounded to closest integer.
In above example 2, average number of pages is (8 + 5 + 6 + 12)/3 = 31/3 which
is rounded to 10. So the difference between average and number of pages on
215
each day for the output shown above is “abs(8-10) + abs(5+6-10) + abs(12-10)”
which is 5. The value 5 is the optimal value of sum of differences.
We strongly recommend to minimize the browser and try this yourself
first.
Consider the example 2 above where a book has 4 chapters with pages 8, 5, 6
and 12. User wishes to finish it in 3 days. The graphical representation of the
above scenario is,
In the above graph vertex represents the chapter and an edge e(u, v) represents
number of pages to be read to reach ‘v ‘ from ‘u ‘. Sink node is added to
symbolize the end of book.
First, calculate the average number of pages to read in a day (here 31/3 roughly
10). New edge weight e ‘(u, v) would be the mean difference |avg – e(u, v)|.
Modified graph for the above problem would be,
216
Thanks to Armadillofor initiating this thought in a comment.
The idea is to start from chapter 1 and do a DFS to find sink with count of
edges being ‘k ‘. Keep storing the visited vertices in an array say ‘path[]’. If
we reach the destination vertex, and path sum is less than the optimal path
update the optimal assignment optimal_path[]. Note, that the graph is DAG
thus there is no need to take care of cycles during DFS.
Following, is the C++ implementation of the same, adjacency matrix is used to
represent the graph. The following program has mainly 4 phases.
1) Construct a directed acyclic graph.
2) Find the optimal path using DFS.
3) Print the found optimal path.
217
// Graph - Node chapter+1 is the sink described in the
// above graph
int DAG[CHAPTERS+1][CHAPTERS+1];
// This function finds and prints optimal read list. It first creates a
// graph, then calls assignChapters().
void minAssignment(int pages[])
218
{
// 1) ............CONSTRUCT GRAPH.................
// Partial sum array construction S[i] = total pages
// till ith chapter
int avg_pages = 0, sum = 0, S[CHAPTERS+1], path[DAYS+1];
S[0] = 0;
219
{
cout << ch << " ";
ch++;
}
cout << endl;
}
}
return 0;
}
Output:
This article is contributed by Balaji S. Please write comments if you find any-
thing incorrect, or you want to share more information about the topic discussed
above.
Source
http://www.geeksforgeeks.org/optimal-read-list-given-number-days/
220
Chapter 38
Given a directed graph, a source vertex ‘s’ and a destination vertex ‘d’, print
all paths from given ‘s’ to ‘d’.
Consider the following directed graph. Let the s be 2 and d be 3. There are 4
different paths from 2 to 3.
221
Following is C++ implementation of above idea.
public:
Graph(int V); // Constructor
void addEdge(int u, int v);
void printAllPaths(int s, int d);
};
Graph::Graph(int V)
{
this->V = V;
adj = new list<int>[V];
}
222
visited[i] = false;
// Driver program
int main()
{
// Create a graph given in the above diagram
Graph g(4);
g.addEdge(0, 1);
223
g.addEdge(0, 2);
g.addEdge(0, 3);
g.addEdge(2, 0);
g.addEdge(2, 1);
g.addEdge(1, 3);
int s = 2, d = 3;
cout << "Following are all different paths from " << s
<< " to " << d << endl;
g.printAllPaths(s, d);
return 0;
}
Output:
Source
http://www.geeksforgeeks.org/find-paths-given-source-destination/
Category: Graph
Post navigation
← Factorial of a large number Practo Placement Experience →
Writing code in comment? Please use code.geeksforgeeks.org, generate link and
share the link here.
224
Chapter 39
Input: x = 20
Output: 0 1 2 3 4 5 6 7 8 9 10 12
Input: x = 105
Output: 0 1 2 3 4 5 6 7 8 9 10 12
21 23 32 34 43 45 54 56 65
67 76 78 87 89 98 101
225
One Simple Solution is to traverse all numbers from 0 to x. For every traversed
number, check if it is a Jumping number. If yes, then print it. Otherwise ignore
it. Time Complexity of this solution is O(x).
An Efficient Solution can solve this problem in O(k) time where k is number
of Jumping Numbers smaller than or equal to x. The idea is use BFS or DFS.
Assume that we have a graph where the starting node is 0 and we need to
traverse it from the start node to all the reachable nodes.
With the restrictions given in the graph about the jumping numbers, what do
you think should be the restrictions defining the next transitions in the graph.
Start node = 0
From 0, we can move to 1 2 3 4 5 6 7 8 9
[these are not in our range so we don't add it]
226
q.push(num);
if (num <= x)
{
cout << num << " ";
int last_dig = num % 10;
// Driver program
int main()
{
int x = 40;
227
printJumping(x);
return 0;
}
Output:
0 1 10 12 2 21 23 3 32 34 4 5 6 7 8 9
Source
http://www.geeksforgeeks.org/print-all-jumping-numbers-smaller-than-or-equal-to-a-given-value/
228
Chapter 40
Given N men and N women, where each person has ranked all members of the
opposite sex in order of preference, marry the men and women together such
that there are no two people of opposite sex who would both rather have each
other than their current partners. If there are no such people, all the marriages
are “stable” (Source Wiki).
Consider the following example.
Let there be two men m1 and m2 and two women w1 and w2.
Let m1‘s list of preferences be {w1, w2}
Let m2‘s list of preferences be {w1, w2}
Let w1‘s list of preferences be {m1, m2}
Let w2‘s list of preferences be {m1, m2}
The matching { {m1, w2}, {w1, m2} } is not stable because m1 and w1 would
prefer each other over their assigned partners. The matching {m1, w1} and
{m2, w2} is stable because there are no two people of opposite sex that would
prefer each other over their assigned partners.
It is always possible to form stable marriages from lists of preferences (See refer-
ences for proof). Following is Gale–Shapley algorithm to find a stable matching:
The idea is to iterate through all free men while there is any free man available.
Every free man goes to all women in his preference list according to the order.
For every woman he goes to, he checks if the woman is free, if yes, they both
become engaged. If the woman is not free, then the woman chooses either says
no to him or dumps her current engagement according to her preference list. So
an engagement done once can be broken if a woman gets better option.
Following is complete algorithm from Wiki
229
{
w = m's highest ranked such woman to whom he has not yet proposed
if w is free
(m, w) become engaged
else some pair (m', w) already exists
if w prefers m to m'
(m, w) become engaged
m' becomes free
else
(m', w) remain engaged
}
// This function returns true if woman 'w' prefers man 'm1' over man 'm'
bool wPrefersM1OverM(int prefer[2*N][N], int w, int m, int m1)
{
// Check if w prefers m over her current engagment m1
for (int i = 0; i < N; i++)
{
// If m1 comes before m in lisr of w, then w prefers her
// cirrent engagement, don't do anything
if (prefer[w][i] == m1)
return true;
230
}
}
// Prints stable matching for N boys and N girls. Boys are numbered as 0 to
// N-1. Girls are numbereed as N to 2N-1.
void stableMarriage(int prefer[2*N][N])
{
// Stores partner of women. This is our output array that
// stores paing information. The value of wPartner[i]
// indicates the partner assigned to woman N+i. Note that
// the woman numbers between N and 2*N-1. The value -1
// indicates that (N+i)'th woman is free
int wPartner[N];
231
}
return 0;
}
232
Output:
Woman Man
4 2
5 1
6 3
7 0
References:
http://www.csee.wvu.edu/~ksmani/courses/fa01/random/lecnotes/lecture5.
pdf
http://www.youtube.com/watch?v=5RSMLgy06Ew#t=11m4s
Please write comments if you find anything incorrect, or you want to share more
information about the topic discussed above
Source
http://www.geeksforgeeks.org/stable-marriage-problem/
Category: Graph
Post navigation
← Find minimum s-t cut in a flow network Convex Hull | Set 2 (Graham Scan)
→
Writing code in comment? Please use code.geeksforgeeks.org, generate link and
share the link here.
233
Chapter 41
The Steiner Tree Problem is to find the minimum cost Steiner Tree.
See below for an example.
234
Spanning Tree vs Steiner Tree
Minimum Spanning Tree is a minimum weight tree that spans through all ver-
tices.
235
If given subset (or terminal) vertices is equal to set of all vertices in Steiner Tree
problem, then the problem becomes Minimum Spanning Tree problem. And
if the given subset contains only two vertices, then it shortest path problem
between two vertices.
Finding out Minimum Spanning Tree is polynomial time solvable, but Minimum
Steiner Tree problem is NP Hard and related decision problem is NP-Complete.
Applications of Steiner Tree
Any situation where the task is minimize cost of connection among some impor-
tant locations like VLSI Design, Computer Networks, etc.
Shortest Path based Approximate Algorithm
Since Steiner Tree problem is NP-Hard, there are no polynomial time solutions
that always give optimal cost. Therefore, there are approximate algorithms to
solve the same. Below is one simple approximate algorithm.
www.cs.uu.nl/docs/vakken/an/teoud/an-steiner.ppt
This article is contributed by Shivam Gupta. Please write comments if you
find anything incorrect, or you want to share more information about the topic
discussed above
Source
http://www.geeksforgeeks.org/steiner-tree/
236
Chapter 42
Connectivity in a directed
graph
Given a directed graph, find out whether the graph is strongly connected or not.
A directed graph is strongly connected if there is a path between any two pair
of vertices. For example, following is a strongly connected graph.
It is easy for undirected graph, we can just do a BFS and DFS starting from
any vertex. If BFS or DFS visits all vertices, then the given undirected graph
is connected. This approach won’t work for a directed graph. For example,
consider the following graph which is not strongly connected. If we start DFS
(or BFS) from vertex 0, we can reach all vertices, but if we start from any other
vertex, we cannot reach all vertices.
237
How to do for directed graph?
A simple idea is to use a all pair shortest path algorithm like Floyd Warshall
or find Transitive Closure of graph. Time complexity of this method would
be O(v3 ).
We can also do DFSV times starting from every vertex. If any DFS, doesn’t
visit all vertices, then graph is not strongly connected. This algorithm takes
O(V*(V+E)) time which can be same as transitive closure for a dense graph.
A better idea can be Strongly Connected Components (SCC) algorithm.
We can find all SCCs in O(V+E) time. If number of SCCs is one, then graph
is strongly connected. The algorithm for SCC does extra work as it finds all
SCCs.
Following is Kosaraju’s DFS based simple algorithm that does two DFS
traversals of graph:
1) Initialize all vertices as not visited.
2) Do a DFS traversal of graph starting from any arbitrary vertex v. If DFS
traversal doesn’t visit all vertices, then return false.
3) Reverse all arcs (or find transpose or reverse of graph)
4) Mark all vertices as not-visited in reversed graph.
5) Do a DFS traversal of reversed graph starting from same vertex v (Same as
step 2). If DFS traversal doesn’t visit all vertices, then return false. Otherwise
return true.
The idea is, if every node can be reached from a vertex v, and every node can
reach v, then the graph is strongly connected. In step 2, we check if all vertices
are reachable from v. In step 4, we check if all vertices can reach v (In reversed
graph, if all vertices are reachable from v, then all vertices can reach v in original
graph).
Following is C++ implementation of above algorithm.
238
class Graph
{
int V; // No. of vertices
list<int> *adj; // An array of adjacency lists
239
{
g.adj[*i].push_back(v);
}
}
return g;
}
// Step 4: Mark all the vertices as not visited (For second DFS)
for(int i = 0; i < V; i++)
visited[i] = false;
return true;
240
}
Graph g2(4);
g2.addEdge(0, 1);
g2.addEdge(1, 2);
g2.addEdge(2, 3);
g2.isSC()? cout << "Yes\n" : cout << "No\n";
return 0;
}
Output:
Yes
No
241
Source
http://www.geeksforgeeks.org/connectivity-in-a-directed-graph/
242
Chapter 43
243
244
How to find all articulation points in a given graph?
A simple approach is to one by one remove all vertices and see if removal of a
vertex causes disconnected graph. Following are steps of simple approach for
connected graph.
1) For every vertex v, do following
…..a) Remove v from graph
..…b) See if the graph remains connected (We can either use BFS or DFS)
…..c) Add v back to the graph
Time complexity of above method is O(V*(V+E)) for a graph represented using
adjacency list. Can we do better?
A O(V+E) algorithm to find all Articulation Points (APs)
The idea is to use DFS (Depth First Search). In DFS, we follow vertices in tree
form called DFS tree. In DFS tree, a vertex u is parent of another vertex v, if
v is discovered by u (obviously v is an adjacent of u in graph). In DFS tree, a
vertex u is articulation point if one of the following two conditions is true.
1) u is root of DFS tree and it has at least two children.
2) u is not root of DFS tree and it has a child v such that no vertex in subtree
rooted with v has a back edge to one of the ancestors (in DFS tree) of u.
Following figure shows same points as above with one additional point that a
leaf in DFS Tree can never be an articulation point. (Source Ref 2)
We do DFS traversal of given graph with additional code to find out Articulation
Points (APs). In DFS traversal, we maintain a parent[] array where parent[u]
stores parent of vertex u. Among the above mentioned two cases, the first case
is simple to detect. For every vertex, count children. If currently visited vertex
u is root (parent[u] is NIL) and has more than two children, print it.
How to handle second case? The second case is trickier. We maintain an array
245
disc[] to store discovery time of vertices. For every node u, we need to find out
the earliest visited vertex (the vertex with minimum discovery time) that can be
reached from subtree rooted with u. So we maintain an additional array low[]
which is defined as follows.
Graph::Graph(int V)
{
this->V = V;
adj = new list<int>[V];
}
246
// A recursive function that find articulation points using DFS traversal
// u --> The vertex to be visited next
// visited[] --> keeps tract of visited vertices
// disc[] --> Stores discovery times of visited vertices
// parent[] --> Stores parent vertices in DFS tree
// ap[] --> Store articulation points
void Graph::APUtil(int u, bool visited[], int disc[],
int low[], int parent[], bool ap[])
{
// A static variable is used for simplicity, we can avoid use of static
// variable by passing a pointer.
static int time = 0;
247
// (2) If u is not root and low value of one of its child is more
// than discovery value of u.
if (parent[u] != NIL && low[v] >= disc[u])
ap[u] = true;
}
248
// Create graphs given in above diagrams
cout << "\nArticulation points in first graph \n";
Graph g1(5);
g1.addEdge(1, 0);
g1.addEdge(0, 2);
g1.addEdge(2, 1);
g1.addEdge(0, 3);
g1.addEdge(3, 4);
g1.AP();
return 0;
}
Output:
Time Complexity: The above function is simple DFS with additional arrays.
249
So time complexity is same as DFS which is O(V+E) for adjacency list repre-
sentation of graph.
References:
https://www.cs.washington.edu/education/courses/421/04su/slides/artic.pdf
http://www.slideshare.net/TraianRebedea/algorithm-design-and-complexity-course-8
http://faculty.simpson.edu/lydia.sinapova/www/cmsc250/LN250_Weiss/
L25-Connectivity.htm
Please write comments if you find anything incorrect, or you want to share more
information about the topic discussed above.
Source
http://www.geeksforgeeks.org/articulation-points-or-cut-vertices-in-a-graph/
Category: Graph Tags: Graph
Post navigation
← Remove “b” and “ac” from a given string Bridges in a graph →
Writing code in comment? Please use code.geeksforgeeks.org, generate link and
share the link here.
250
Chapter 44
Biconnected graph
251
252
See thisfor more examples.
How to find if a given graph is Biconnected or not?
A connected graph is Biconnected if it is connected and doesn’t have any Artic-
ulation Point. We mainly need to check two things in a graph.
1) The graph is connected.
2) There is not articulation point in graph.
We start from any vertex and do DFS traversal. In DFS traversal, we check
if there is any articulation point. If we don’t find any articulation point, then
253
the graph is Biconnected. Finally, we need to check whether all vertices were
reachable in DFS or not. If all vertices were not reachable, then the graph is
not even connected.
Following is C++ implementation of above approach.
Graph::Graph(int V)
{
this->V = V;
adj = new list<int>[V];
}
254
// variable by passing a pointer.
static int time = 0;
255
else if (v != parent[u])
low[u] = min(low[u], disc[v]);
}
return false;
}
// The main function that returns true if graph is Biconnected, otherwise false.
// It uses recursive function isBCUtil()
bool Graph::isBC()
{
// Mark all the vertices as not visited
bool *visited = new bool[V];
int *disc = new int[V];
int *low = new int[V];
int *parent = new int[V];
return true;
}
256
Graph g2(5);
g2.addEdge(1, 0);
g2.addEdge(0, 2);
g2.addEdge(2, 1);
g2.addEdge(0, 3);
g2.addEdge(3, 4);
g2.addEdge(2, 4);
g2.isBC()? cout << "Yes\n" : cout << "No\n";
Graph g3(3);
g3.addEdge(0, 1);
g3.addEdge(1, 2);
g3.isBC()? cout << "Yes\n" : cout << "No\n";
Graph g4(5);
g4.addEdge(1, 0);
g4.addEdge(0, 2);
g4.addEdge(2, 1);
g4.addEdge(0, 3);
g4.addEdge(3, 4);
g4.isBC()? cout << "Yes\n" : cout << "No\n";
Graph g5(3);
g5.addEdge(0, 1);
g5.addEdge(1, 2);
g5.addEdge(2, 0);
g5.isBC()? cout << "Yes\n" : cout << "No\n";
return 0;
}
Time Complexity: The above function is a simple DFS with additional ar-
rays. So time complexity is same as DFS which is O(V+E) for adjacency list
representation of graph.
References:
http://www.cs.purdue.edu/homes/ayg/CS251/slides/chap9d.pdf
Please write comments if you find anything incorrect, or you want to share more
information about the topic discussed above.
Source
http://www.geeksforgeeks.org/biconnectivity-in-a-graph/
257
Category: Graph Tags: Graph
Post navigation
← Bridges in a graph Dynamic Programming | Set 30 (Dice Throw) →
Writing code in comment? Please use code.geeksforgeeks.org, generate link and
share the link here.
258
Chapter 45
Bridges in a graph
259
How to find all bridges in a given graph?
A simple approach is to one by one remove all edges and see if removal of a edge
causes disconnected graph. Following are steps of simple approach for connected
graph.
1) For every edge (u, v), do following
…..a) Remove (u, v) from graph
..…b) See if the graph remains connected (We can either use BFS or DFS)
…..c) Add (u, v) back to the graph.
Time complexity of above method is O(E*(V+E)) for a graph represented using
adjacency list. Can we do better?
A O(V+E) algorithm to find all Bridges
The idea is similar to O(V+E) algorithm for Articulation Points. We do DFS
traversal of the given graph. In DFS tree an edge (u, v) (u is parent of v in
DFS tree) is bridge if there does not exit any other alternative to reach u or an
ancestor of u from subtree rooted with v. As discussed in the previous post, the
value low[v] indicates earliest visited vertex reachable from subtree rooted with
v. The condition for an edge (u, v) to be a bridge is, “low[v] > disc[u]”.
Following is C++ implementation of above approach.
260
// A C++ program to find bridges in a given undirected graph
#include<iostream>
#include <list>
#define NIL -1
using namespace std;
Graph::Graph(int V)
{
this->V = V;
adj = new list<int>[V];
}
// A recursive function that finds and prints bridges using DFS traversal
// u --> The vertex to be visited next
// visited[] --> keeps tract of visited vertices
// disc[] --> Stores discovery times of visited vertices
// parent[] --> Stores parent vertices in DFS tree
void Graph::bridgeUtil(int u, bool visited[], int disc[],
int low[], int parent[])
{
// A static variable is used for simplicity, we can avoid use of static
// variable by passing a pointer.
static int time = 0;
261
// Initialize discovery time and low value
disc[u] = low[u] = ++time;
// DFS based function to find all bridges. It uses recursive function bridgeUtil()
void Graph::bridge()
{
// Mark all the vertices as not visited
bool *visited = new bool[V];
int *disc = new int[V];
int *low = new int[V];
int *parent = new int[V];
262
// Call the recursive helper function to find Bridges
// in DFS tree rooted with vertex 'i'
for (int i = 0; i < V; i++)
if (visited[i] == false)
bridgeUtil(i, visited, disc, low, parent);
}
return 0;
}
Output:
263
Bridges in first graph
3 4
0 3
Time Complexity: The above function is simple DFS with additional arrays.
So time complexity is same as DFS which is O(V+E) for adjacency list repre-
sentation of graph.
References:
https://www.cs.washington.edu/education/courses/421/04su/slides/artic.pdf
http://www.slideshare.net/TraianRebedea/algorithm-design-and-complexity-course-8
http://faculty.simpson.edu/lydia.sinapova/www/cmsc250/LN250_Weiss/
L25-Connectivity.htm
http://www.youtube.com/watch?v=bmyyxNyZKzI
Please write comments if you find anything incorrect, or you want to share more
information about the topic discussed above.
Source
http://www.geeksforgeeks.org/bridge-in-a-graph/
Category: Graph Tags: Graph
Post navigation
← Articulation Points (or Cut Vertices) in a Graph Biconnected graph →
Writing code in comment? Please use code.geeksforgeeks.org, generate link and
share the link here.
264
Chapter 46
Eulerian Path is a path in graph that visits every edge exactly once. Eulerian
Circuit is an Eulerian Path which starts and ends on the same vertex.
265
How to find whether a given graph is Eulerian or not?
The problem is same as following question. “Is it possible to draw a given graph
without lifting pencil from the paper and without tracing any of the edges more
than once”.
A graph is called Eulerian if it has an Eulerian Cycle and called Semi-Eulerian if
it has an Eulerian Path. The problem seems similar to Hamiltonian Path which
is NP complete problem for a general graph. Fortunately, we can find whether
a given graph has a Eulerian Path or not in polynomial time. In fact, we can
find it in O(V+E) time.
Following are some interesting properties of undirected graphs with an Eulerian
path and cycle. We can use these properties to find whether a graph is Eulerian
266
or not.
Eulerian Cycle
An undirected graph has Eulerian cycle if following two conditions are true.
….a) All vertices with non-zero degree are connected. We don’t care about
vertices with zero degree because they don’t belong to Eulerian Cycle or Path
(we only consider all edges).
….b) All vertices have even degree.
Eulerian Path
An undirected graph has Eulerian Path if following two conditions are true.
….a) Same as condition (a) for Eulerian Cycle
….b) If zero or two vertices have odd degree and all other vertices have even de-
gree. Note that only one vertex with odd degree is not possible in an undirected
graph (sum of all degrees is always even in an undirected graph)
Note that a graph with no edges is considered Eulerian because there are no
edges to traverse.
How does this work?
In Eulerian path, each time we visit a vertex v, we walk through two unvisited
edges with one end point as v. Therefore, all middle vertices in Eulerian Path
must have even degree. For Eulerian Cycle, any vertex can be middle vertex,
therefore all vertices must have even degree.
267
bool isConnected();
268
// Check if all non-zero degree vertices are visited
for (i = 0; i < V; i++)
if (visited[i] == false && adj[i].size() > 0)
return false;
return true;
}
269
// Driver program to test above function
int main()
{
// Let us create and test graphs shown in above figures
Graph g1(5);
g1.addEdge(1, 0);
g1.addEdge(0, 2);
g1.addEdge(2, 1);
g1.addEdge(0, 3);
g1.addEdge(3, 4);
test(g1);
Graph g2(5);
g2.addEdge(1, 0);
g2.addEdge(0, 2);
g2.addEdge(2, 1);
g2.addEdge(0, 3);
g2.addEdge(3, 4);
g2.addEdge(4, 0);
test(g2);
Graph g3(5);
g3.addEdge(1, 0);
g3.addEdge(0, 2);
g3.addEdge(2, 1);
g3.addEdge(0, 3);
g3.addEdge(3, 4);
g3.addEdge(1, 3);
test(g3);
return 0;
}
270
Output:
Source
http://www.geeksforgeeks.org/eulerian-path-and-circuit/
271
Chapter 47
Eulerian Path is a path in graph that visits every edge exactly once. Eulerian
Circuit is an Eulerian Path which starts and ends on the same vertex.
We strongly recommend to first read the following post on Euler Path and
Circuit.
http://www.geeksforgeeks.org/eulerian-path-and-circuit/
In the above mentioned post, we discussed the problem of finding out whether
a given graph is Eulerian or not. In this post, an algorithm to print Eulerian
trail or circuit is discussed.
Following is Fleury’s Algorithm for printing Eulerian trail or cycle (Source Ref1).
1. Make sure the graph has either 0 or 2 odd vertices.
2. If there are 0 odd vertices, start anywhere. If there are 2 odd vertices, start
at one of them.
3. Follow edges one at a time. If you have a choice between a bridge and a
non-bridge, always choose the non-bridge.
4. Stop when you run out of edges.
The idea is, “don’t burn bridges“ so that we can come back to a vertex and
traverse remaining edges. For example let us consider the following graph.
272
There are two vertices with odd degree, ‘2’ and ‘3’, we can start path from any
of them. Let us start tour from vertex ‘2’.
273
There are three edges going out from vertex ‘2’, which one to pick? We don’t
pick the edge ‘2-3� because that is a bridge (we won’t be able to come back to
‘3’). We can pick any of the remaining two edge. Let us say we pick ‘2-0�. We
remove this edge and move to vertex ‘0’.
274
There is only one edge from vertex ‘0’, so we pick it, remove it and move to
vertex ‘1’. Euler tour becomes ‘2-0 0-1�.
275
There is only one edge from vertex ‘1’, so we pick it, remove it and move to
vertex ‘2’. Euler tour becomes ‘2-0 0-1 1-2�
276
Again there is only one edge from vertex 2, so we pick it, remove it and move
to vertex 3. Euler tour becomes ‘2-0 0-1 1-2 2-3�
277
There are no more edges left, so we stop here. Final tour is ‘2-0 0-1 1-2 2-3�.
See thisfor and thisfore more examples.
Following is C++ implementation of above algorithm. In the following code,
it is assumed that the given graph has an Eulerian trail or Circuit. The main
focus is to print an Eulerian trail or circuit. We can use isEulerian() to first
check whether there is an Eulerian Trail or Circuit in the given graph.
We first find the starting point which must be an odd vertex (if there are odd
vertices) and store it in variable ‘u’. If there are zero odd vertices, we start from
vertex ‘0’. We call printEulerUtil() to print Euler tour starting with u. We
traverse all adjacent vertices of u, if there is only one adjacent vertex, we im-
mediately consider it. If there are more than one adjacent vertices, we consider
an adjacent v only if edge u-v is not a bridge. How to find if a given is edge
is bridge? We count number of vertices reachable from u. We remove edge u-v
and again count number of reachable vertices from u. If number of reachable
vertices are reduced, then edge u-v is a bridge. To count reachable vertices, we
can either use BFS or DFS, we have used DFS in the above code. The function
DFSCount(u) returns number of vertices reachable from u.
Once an edge is processed (included in Euler tour), we remove it from the graph.
To remove the edge, we replace the vertex entry with -1 in adjacency list. Note
that simply deleting the node may not work as the code is recursive and a parent
call may be in middle of adjacency list.
278
// A C++ program print Eulerian Trail in a given Eulerian or Semi-Eulerian Graph
#include <iostream>
#include <string.h>
#include <algorithm>
#include <list>
using namespace std;
/* The main function that print Eulerian Trail. It first finds an odd
degree vertex (if there is any) and then calls printEulerUtil()
to print the path */
void Graph::printEulerTour()
{
// Find a vertex with odd degree
int u = 0;
for (int i = 0; i < V; i++)
if (adj[i].size() & 1)
{ u = i; break; }
279
cout << endl;
}
280
// 2.b) Remove edge (u, v) and after removing the edge, count
// vertices reachable from u
rmvEdge(u, v);
memset(visited, false, V);
int count2 = DFSCount(u, visited);
// This function removes edge u-v from graph. It removes the edge by
// replacing adjcent vertex value with -1.
void Graph::rmvEdge(int u, int v)
{
// Find v in adjacency list of u and replace it with -1
list<int>::iterator iv = find(adj[u].begin(), adj[u].end(), v);
*iv = -1;
return count;
}
281
Graph g1(4);
g1.addEdge(0, 1);
g1.addEdge(0, 2);
g1.addEdge(1, 2);
g1.addEdge(2, 3);
g1.printEulerTour();
Graph g2(3);
g2.addEdge(0, 1);
g2.addEdge(1, 2);
g2.addEdge(2, 0);
g2.printEulerTour();
Graph g3(5);
g3.addEdge(1, 0);
g3.addEdge(0, 2);
g3.addEdge(2, 1);
g3.addEdge(0, 3);
g3.addEdge(3, 4);
g3.addEdge(3, 2);
g3.addEdge(3, 1);
g3.addEdge(2, 4);
g3.printEulerTour();
return 0;
}
Output:
Note that the above code modifies given graph, we can create a copy of graph
if we don’t want the given graph to be modified.
Time Complexity: Time complexity of the above implementation is O
((V+E)2 ). The function printEulerUtil() is like DFS and it calls isValid-
NextEdge() which also does DFS two times. Time complexity of DFS for
adjacency list representation is O(V+E). Therefore overall time complexity is
O((V+E)*(V+E)) which can be written as O(E2 ) for a connected graph.
There are better algorithms to print Euler tour, we will soon be covering them
as separate posts.
282
References:
http://www.math.ku.edu/~jmartin/courses/math105-F11/Lectures/chapter5-part2.
pdf
http://en.wikipedia.org/wiki/Eulerian_path#Fleury.27s_algorithm
Please write comments if you find anything incorrect, or you want to share more
information about the topic discussed above
Source
http://www.geeksforgeeks.org/fleurys-algorithm-for-printing-eulerian-path/
283
Chapter 48
Strongly Connected
Components
A directed graph is strongly connected if there is a path between all pairs of ver-
tices. A strongly connected component (SCC) of a directed graph is a maximal
strongly connected subgraph. For example, there are 3 SCCs in the following
graph.
We can find all strongly connected components in O(V+E) time using Kosaraju’s
algorithm. Following is detailed Kosaraju’s algorithm.
1) Create an empty stack ‘S’ and do DFS traversal of a graph. In DFS traversal,
after calling recursive DFS for adjacent vertices of a vertex, push the vertex to
stack.
2) Reverse directions of all arcs to obtain the transpose graph.
284
3) One by one pop a vertex from S while S is not empty. Let the popped vertex
be ‘v’. Take v as source and do DFS (call DFSUtil(v)). The DFS starting from
v prints strongly connected component of v.
How does this work?
The above algorithm is DFS based. It does DFS two times. DFS of a graph
produces a single tree if all vertices are reachable from the DFS starting point.
Otherwise DFS produces a forest. So DFS of a graph with only one SCC always
produces a tree. The important point to note is DFS may produce a tree or a
forest when there are more than one SCCs depending upon the chosen starting
point. For example, in the above diagram, if we start DFS from vertices 0 or 1
or 2, we get a tree as output. And if we start from 3 or 4, we get a forest. To
find and print all SCCs, we would want to start DFS from vertex 4 (which is a
sink vertex), then move to 3 which is sink in the remaining set (set excluding
4) and finally any of the remaining vertices (0, 1, 2). So how do we find this
sequence of picking vertices as starting points of DFS? Unfortunately, there is
no direct way for getting this sequence. However, if we do a DFS of graph and
store vertices according to their finish times, we make sure that the finish time
of a vertex that connects to other SCCs (other that its own SCC), will always
be greater than finish time of vertices in the other SCC (See thisfor proof). For
example, in DFS of above example graph, finish time of 0 is always greater
than 3 and 4 (irrespective of the sequence of vertices considered for DFS). And
finish time of 3 is always greater than 4. DFS doesn’t guarantee about other
vertices, for example finish times of 1 and 2 may be smaller or greater than 3
and 4 depending upon the sequence of vertices considered for DFS. So to use
this property, we do DFS traversal of complete graph and push every finished
vertex to a stack. In stack, 3 always appears after 4, and 0 appear after both 3
and 4.
In the next step, we reverse the graph. Consider the graph of SCCs. In the
reversed graph, the edges that connect two components are reversed. So the
SCC {0, 1, 2} becomes sink and the SCC {4} becomes source. As discussed
above, in stack, we always have 0 before 3 and 4. So if we do a DFS of the
reversed graph using sequence of vertices in stack, we process vertices from sink
to source. That is what we wanted to achieve and that is all needed to print
SCCs one by one.
285
Following is C++ implementation of Kosaraju’s algorithm.
class Graph
{
int V; // No. of vertices
list<int> *adj; // An array of adjacency lists
// The main function that finds and prints strongly connected components
void printSCCs();
286
};
Graph::Graph(int V)
{
this->V = V;
adj = new list<int>[V];
}
Graph Graph::getTranspose()
{
Graph g(V);
for (int v = 0; v < V; v++)
{
// Recur for all the vertices adjacent to this vertex
list<int>::iterator i;
for(i = adj[v].begin(); i != adj[v].end(); ++i)
{
g.adj[*i].push_back(v);
}
}
return g;
}
287
// 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])
fillOrder(*i, visited, Stack);
// The main function that finds and prints all strongly connected components
void Graph::printSCCs()
{
stack<int> Stack;
288
}
}
cout << "Following are strongly connected components in given graph \n";
g.printSCCs();
return 0;
}
Output:
Time Complexity: The above algorithm calls DFS, fins reverse of the graph
and again calls DFS. DFS takes O(V+E) for a graph represented using adjacency
list. Reversing a graph also takes O(V+E) time. For reversing the graph, we
simple traverse all adjacency lists.
The above algorithm is asymptotically best algorithm, but there are other algo-
rithms like Tarjan’s algorithm and path-based which have same time complexity
but find SCCs using single DFS. The Tarjan’s algorithm is discussed in the fol-
lowing post.
Tarjan’s Algorithm to find Strongly Connected Components
Applications:
SCC algorithms can be used as a first step in many graph algorithms that work
only on strongly connected graph.
In social networks, a group of people are generally strongly connected (For
example, students of a class or any other common place). Many people in these
289
groups generally like some common pages or play common games. The SCC
algorithms can be used to find such groups and suggest the commonly liked
pages or games to the people in the group who have not yet liked commonly
liked a page or played a game.
References:
http://en.wikipedia.org/wiki/Kosaraju%27s_algorithm
https://www.youtube.com/watch?v=PZQ0Pdk15RA
You may also like to see Tarjan’s Algorithm to find Strongly Connected Com-
ponents.
Please write comments if you find anything incorrect, or you want to share more
information about the topic discussed above
Source
http://www.geeksforgeeks.org/strongly-connected-components/
290
Chapter 49
A directed graph is strongly connected if there is a path between all pairs of ver-
tices. A strongly connected component (SCC) of a directed graph is a maximal
strongly connected subgraph. For example, there are 3 SCCs in the following
graph.
291
Tarjan Algorithm is based on following facts:
1. DFS search produces a DFS tree/forest
2. Strongly Connected Components form subtrees of the DFS tree.
3. If we can find head of such subtrees, we can print/store all the nodes in that
subtree (including head) and that will be one SCC.
4. There is no back edge from one SCC to another (There can be cross edges,
but cross edges will not be used while processing the graph).
To find head of a SCC, we calculate desc and low array (as done for articulation
point, bridge, biconnected component). As discussed in the previous posts,
low[u] indicates earliest visited vertex (the vertex with minimum discovery time)
that can be reached from subtree rooted with u. A node u is head if disc[u] =
low[u].
Disc and Low Values
(click on image to see it properly)
Strongly Connected Component relates to directed graph only, but Disc and
Low values relate to both directed and undirected graph, so in above pic we
have taken an undirected graph.
In above Figure, we have shown a graph and it’s one of DFS tree (There could
be different DFS trees on same graph depending on order in which edges are
traversed).
In DFS tree, continuous arrows are tree edges and dashed arrows are back edges
(DFS Tree Edges
Disc and Low values are showin in Figure for every node as (Disc/Low).
Disc: This is the time when a node is visited 1st time while DFS traversal. For
nodes A, B, C, .., J in DFS tree, Disc values are 1, 2, 3, .., 10.
Low: In DFS tree, Tree edges take us forward, from ancestor node to one of it’s
descendants. For example, from node C, tree edges can take us to node node G,
node I etc. Back edges take us backward, from a descendant node to one of it’s
ancestors. For example, from node G, Back edges take us to E or C. If we look
at both Tree and Back edge together, then we can see that if we start traversal
from one node, we may go down the tree via Tree edges and then go up via back
edges. For example, from node E, we can go down to G and then go up to C.
Similarly from E, we can go down to I or J and then go up to F. “Low” value of
a node tells the topmost reachable ancestor (with minimum possible Disc value)
via the subtree of that node. So for any node, Low value equal to it’s Disc value
anyway (A node is ancestor of itself). Then we look into it’s subtree and see if
there is any node which can take us to any of it’s ancestor. If there are multiple
back edges in subtree which take us to different ancestors, then we take the one
with minimum Disc value (i.e. the topmost one). If we look at node F, it has
two subtrees. Subtree with node G, takes us to E and C. The other subtree
292
takes us back to F only. Here topmost ancestor is C where F can reach and so
Low value of F is 3 (The Disc value of C).
Based on above discussion, it should be clear that Low values of B, C, and D
are 1 (As A is the topmost node where B, C and D can reach). In same way,
Low values of E, F, G are 3 and Low values of H, I, J are 6.
For any node u, when DFS starts, Low will be set to it’s Disc 1st .
Then later on DFS will be performed on each of it’s children v one by one, Low
value of u can change it two case:
Case1 (Tree Edge): If node v is not visited already, then after DFS of v is
complete, then minimum of low[u] and low[v] will be updated to low[u].
low[u] = min(low[u], low[v]);
Case 2 (Back Edge): When child v is already visited, then minimum of low[u]
and Disc[v] will be updated to low[u].
low[u] = min(low[u], disc[v]);
In case two, can we take low[v] instead of disc[v] ?? . Answer is NO. If you can
think why answer is NO, you probably understood the Low and Disc concept.
Same Low and Disc values help to solve other graph problems like articulation
point, bridge and biconnected component.
To track the subtree rooted at head, we can use a stack (keep pushing node
while visiting). When a head node found, pop all nodes from stack till you get
head out of stack.
To make sure, we don’t consider cross edges, when we reach a node which is
already visited, we should process the visited node only if it is present in stack,
else ignore the node.
Following is C++ implementation of Tarjan’s algorithm to print all SCCs.
293
stack<int> *st, bool stackMember[]);
public:
Graph(int V); // Constructor
void addEdge(int v, int w); // function to add an edge to graph
void SCC(); // prints strongly connected components
};
Graph::Graph(int V)
{
this->V = V;
adj = new list<int>[V];
}
294
// If v is not visited yet, then recur for it
if (disc[v] == -1)
{
SCCUtil(v, disc, low, st, stackMember);
295
for (int i = 0; i < V; i++)
{
disc[i] = NIL;
low[i] = NIL;
stackMember[i] = false;
}
296
Graph g4(11);
g4.addEdge(0,1);g4.addEdge(0,3);
g4.addEdge(1,2);g4.addEdge(1,4);
g4.addEdge(2,0);g4.addEdge(2,6);
g4.addEdge(3,2);
g4.addEdge(4,5);g4.addEdge(4,6);
g4.addEdge(5,6);g4.addEdge(5,7);g4.addEdge(5,8);g4.addEdge(5,9);
g4.addEdge(6,4);
g4.addEdge(7,9);
g4.addEdge(8,9);
g4.addEdge(9,8);
g4.SCC();
return 0;
}
Output:
297
4
6
2 1 0
Time Complexity: The above algorithm mainly calls DFS, DFS takes
O(V+E) for a graph represented using adjacency list.
References:
http://en.wikipedia.org/wiki/Tarjan%27s_strongly_connected_components_
algorithm
http://www.ics.uci.edu/~eppstein/161/960220.html#sca
This article is contributed by Anurag Singh. Please write comments if you
find anything incorrect, or you want to share more information about the topic
discussed above
Source
http://www.geeksforgeeks.org/tarjan-algorithm-find-strongly-connected-components/
Category: Graph
Post navigation
← Shortest path with exactly k edges in a directed and weighted graph Interview
Experience @ Bankbazaar.com →
Writing code in comment? Please use code.geeksforgeeks.org, generate link and
share the link here.
298
Chapter 50
Transitive closure of a
graph
Given a directed graph, find out if a vertex j is reachable from another vertex i
for all vertex pairs (i, j) in the given graph. Here reachable mean that there is
a path from vertex i to j. The reach-ability matrix is called transitive closure
of a graph.
The graph is given in the form of adjacency matrix say ‘graph[V][V]’ where
graph[i][j] is 1 if there is an edge from vertex i to vertex j or i is equal to j,
otherwise graph[i][j] is 0.
Floyd Warshall Algorithm can be used, we can calculate the distance matrix
dist[V][V] using Floyd Warshall, if dist[i][j] is infinite, then j is not reachable
from i, otherwise j is reachable and value of dist[i][j] will be less than V.
Instead of directly using Floyd Warshall, we can optimize it in terms of space
and time, for this particular problem. Following are the optimizations:
1) Instead of integer resultant matrix (dist[V][V] in floyd warshall), we can
create a boolean reach-ability matrix reach[V][V] (we save space). The value
reach[i][j] will be 1 if j is reachable from i, otherwise 0.
2) Instead of using arithmetic operations, we can use logical operations. For
arithmetic operation ‘+’, logical and ‘&&’ is used, and for min, logical or ‘||’ is
used. (We save time by a constant factor. Time complexity is same though)
299
// A function to print the solution matrix
void printSolution(int reach[][V]);
300
{
printf ("Following matrix is transitive closure of the given graph\n");
for (int i = 0; i < V; i++)
{
for (int j = 0; j < V; j++)
printf ("%d ", reach[i][j]);
printf("\n");
}
}
Output:
301
References:
Source
http://www.geeksforgeeks.org/transitive-closure-of-a-graph/
302
Chapter 51
A graph where all vertices are connected with each other, has exactly one con-
nected component, consisting of the whole graph. Such graph with only one
303
connected component is called as Strongly Connected Graph.
The problem can be easily solved by applying DFS() on each component. In
each DFS() call, a component or a sub-graph is visited. We will call DFS on
the next un-visited component. The number of calls to DFS() gives the number
of connected components. BFS can also be used.
What is an island?
A group of connected 1s forms an island. For example, the below matrix contains
5 islands
{1, 1, 0, 0, 0},
{0, 1, 0, 0, 1},
{1, 0, 0, 1, 1},
{0, 0, 0, 0, 0},
{1, 0, 1, 0, 1}
#include <stdio.h>
#include <string.h>
#include <stdbool.h>
#define ROW 5
#define COL 5
304
{
// These arrays are used to get row and column numbers of 8 neighbors
// of a given cell
static int rowNbr[] = {-1, -1, -1, 0, 0, 1, 1, 1};
static int colNbr[] = {-1, 0, 1, -1, 1, -1, 0, 1};
return count;
}
305
};
return 0;
}
Output:
http://en.wikipedia.org/wiki/Connected_component_%28graph_theory%29
Please write comments if you find anything incorrect, or you want to share more
information about the topic discussed above.
Source
http://www.geeksforgeeks.org/find-number-of-islands/
Category: Arrays Graph Tags: Graph
Post navigation
← Floor and Ceil from a BST Reservoir Sampling →
Writing code in comment? Please use code.geeksforgeeks.org, generate link and
share the link here.
306
Chapter 52
Given a directed graph and two vertices ‘u’ and ‘v’ in it, count all possible walks
from ‘u’ to ‘v’ with exactly k edges on the walk.
The graph is given as adjacency matrix representation where value of graph[i][j]
as 1 indicates that there is an edge from vertex i to vertex j and a value 0
indicates no edge from i to j.
For example consider the following graph. Let source ‘u’ be vertex 0, destination
‘v’ be 3 and k be 2. The output should be 2 as there are two walk from 0 to 3
with exactly 2 edges. The walks are {0, 2, 3} and {0, 1, 3}
307
We strongly recommend to minimize the browser and try this yourself
first.
A simple solution is to start from u, go to all adjacent vertices and recur for
adjacent vertices with k as k-1, source as adjacent vertex and destination as v.
Following is C++ implementation of this simple solution.
// Initialize result
int count = 0;
308
// Go to all adjacents of u and recur
for (int i = 0; i < V; i++)
if (graph[u][i]) // Check if is adjacent of u
count += countwalks(graph, i, v, k-1);
return count;
}
Output:
The worst case time complexity of the above function is O(Vk ) where V is
the number of vertices in the given graph. We can simply analyze the time
complexity by drawing recursion tree. The worst occurs for a complete graph.
In worst case, every internal node of recursion tree would have exactly n children.
We can optimize the above solution using Dynamic Programming. The idea
is to build a 3D table where first dimension is source, second dimension is
destination, third dimension is number of edges from source to destination, and
the value is count of walks. Like other Dynamic Programming problems, we fill
the 3D table in bottom up manner.
309
#define V 4
310
{0, 0, 0, 0}
};
int u = 0, v = 3, k = 2;
cout << countwalks(graph, u, v, k);
return 0;
}
Output:
Time complexity of the above DP based solution is O(V3 K) which is much better
than the naive solution.
We can also use Divide and Conquer to solve the above problem in O(V3 Logk)
time. The count of walks of length k from u to v is the [u][v]’th entry in
(graph[V][V])k . We can calculate power of by doing O(Logk) multiplication by
using the divide and conquer technique to calculate power. A multiplication
between two matrices of size V x V takes O(V3 ) time. Therefore overall time
complexity of this method is O(V3 Logk).
Please write comments if you find anything incorrect, or you want to share more
information about the topic discussed above.
Source
http://www.geeksforgeeks.org/count-possible-paths-source-destination-exactly-k-edges/
Category: Graph Tags: Dynamic Programming
Post navigation
← Amazon Interview | Set 100 (On-Campus) A Problem in Many Binary Search
Implementations →
Writing code in comment? Please use code.geeksforgeeks.org, generate link and
share the link here.
311
Chapter 53
Eulerian Path is a path in graph that visits every edge exactly once. Eulerian
Circuit is an Eulerian Path which starts and ends on the same vertex.
A graph is said to be eulerian if it has eulerian cycle. We have discussed eulerian
circuit for an undirected graph. In this post, same is discussed for a directed
graph.
For example, the following graph has eulerian cycle as {1, 0, 3, 4, 0, 2, 1}
312
1) All vertices with nonzero degree belong to a single strongly connected com-
ponent.
2) In degree and out degree of every vertex is same.
We can detect singly connected component using Kosaraju’s DFS based simple
algorithm.
To compare in degree and out degree, we need to store in degree an out degree
of every vertex. Out degree can be obtained by size of adjacency list. In degree
can be stored by creating an array of size equal to number of vertices.
Following is C++ implementation of above approach.
Graph getTranspose();
};
Graph::Graph(int V)
{
313
this->V = V;
adj = new list<int>[V];
in = new int[V];
for (int i = 0; i < V; i++)
in[i] = 0;
}
return true;
}
314
{
g.adj[*i].push_back(v);
(g.in[v])++;
}
}
return g;
}
315
if (adj[i].size() > 0 && visited[i] == false)
return false;
return true;
}
if (g.isEulerianCycle())
cout << "Given directed graph is eulerian \n";
else
cout << "Given directed graph is NOT eulerian \n";
return 0;
}
Output:
Source
http://www.geeksforgeeks.org/euler-circuit-directed-graph/
316
Chapter 54
Biconnected Components
317
// A C++ program to find biconnected components in a given undirected graph
#include<iostream>
#include <list>
#include <stack>
#define NIL -1
using namespace std;
int count = 0;
class Edge
{
public:
int u;
int v;
Edge(int u, int v);
};
Edge::Edge(int u, int v)
{
this->u = u;
this->v = v;
}
Graph::Graph(int V)
{
this->V = V;
this->E = 0;
adj = new list<int>[V];
}
318
E++;
}
319
{
while(st->back().u != u || st->back().v != v)
{
cout << st->back().u << "--" << st->back().v << " ";
st->pop_back();
}
cout << st->back().u << "--" << st->back().v;
st->pop_back();
cout << endl;
count++;
}
}
int j = 0;
320
//If stack is not empty, pop all edges from stack
while(st->size() > 0)
{
j = 1;
cout << st->back().u << "--" << st->back().v << " ";
st->pop_back();
}
if(j == 1)
{
cout << endl;
count++;
}
}
}
Output:
321
8--5 7--8 5--7
6--0 5--6 1--5 0--1
10--11
Above are 5 biconnected components in graph
Source
http://www.geeksforgeeks.org/biconnected-components/
Category: Graph
Post navigation
← How to check if an instance of 8 puzzle is solvable? Amazon Interview
Experience | Set 161 (Off Campus for SDE-1, Banglore) →
Writing code in comment? Please use code.geeksforgeeks.org, generate link and
share the link here.
322
Chapter 55
323
The problem to find chromatic number of a given graph is NP Complete.
Applications of Graph Coloring:
The graph coloring problem has huge number of applications.
1) Making Schedule or Time Table: Suppose we want to make am exam
schedule for a university. We have list different subjects and students enrolled
in every subject. Many subjects would have common students (of same batch,
some backlog students, etc). How do we schedule the exam so that no two exams
with a common student are scheduled at same time? How many minimum time
slots are needed to schedule all exams? This problem can be represented as a
graph where every vertex is a subject and an edge between two vertices mean
there is a common student. So this is a graph coloring problem where minimum
number of time slots is equal to the chromatic number of the graph.
2) Mobile Radio Frequency Assignment: When frequencies are assigned to
towers, frequencies assigned to all towers at the same location must be different.
How to assign frequencies with this constraint? What is the minimum number of
frequencies needed? This problem is also an instance of graph coloring problem
where every tower represents a vertex and an edge between two towers represents
that they are in range of each other.
3) Suduku: Suduku is also a variation of Graph coloring problem where every
cell represents a vertex. There is an edge between two vertices if they are in
same row or same column or same block.
4) Register Allocation: In compiler optimization, register allocation is the
process of assigning a large number of target program variables onto a small
number of CPU registers. This problem is also a graph coloring problem.
5) Bipartite Graphs: We can check if a graph is Bipartite or not by colowing
324
the graph using two colors. If a given graph is 2-colorable, then it is Bipartite,
otherwise not. See thisfor more details.
6) Map Coloring: Geographical maps of countries or states where no two
adjacent cities cannot be assigned same color. Four colors are sufficient to color
any map (See Four Color Theorem)
There can be many more applications: For example the below reference
video lecture has a case study at 1:18.
Akamairuns a network of thousands of servers and the servers are used to dis-
tribute content on Internet. They install a new software or update existing
softwares pretty much every week. The update cannot be deployed on every
server at the same time, because the server may have to be taken down for the
install. Also, the update should not be done one at a time, because it will take
a lot of time. There are sets of servers that cannot be taken down together,
because they have certain critical functions. This is a typical scheduling appli-
cation of graph coloring problem. It turned out that 8 colors were good enough
to color the graph of 75000 nodes. So they could install updates in 8 passes.
We will soon be discussing different ways to solve the graph coloring problem.
References:
Lec 6 | MIT 6.042J Mathematics for Computer Science, Fall 2010 | Video Lecture
Please write comments if you find anything incorrect, or you want to share more
information about the topic discussed above
Source
http://www.geeksforgeeks.org/graph-coloring-applications/
325
Chapter 56
326
// A class that represents an undirected graph
class Graph
{
int V; // No. of vertices
list<int> *adj; // A dynamic array of adjacency lists
public:
// Constructor and destructor
Graph(int V) { this->V = V; adj = new list<int>[V]; }
~Graph() { delete [] adj; }
327
// Process all adjacent vertices and flag their colors
// as unavailable
list<int>::iterator i;
for (i = adj[u].begin(); i != adj[u].end(); ++i)
if (result[*i] != -1)
available[result[*i]] = true;
Graph g2(5);
g2.addEdge(0, 1);
g2.addEdge(0, 2);
g2.addEdge(1, 2);
g2.addEdge(1, 4);
g2.addEdge(2, 4);
328
g2.addEdge(4, 3);
cout << "\nColoring of Graph 2 \n";
g2.greedyColoring();
return 0;
}
Output:
Coloring of Graph 1
Vertex 0 ---> Color 0
Vertex 1 ---> Color 1
Vertex 2 ---> Color 2
Vertex 3 ---> Color 0
Vertex 4 ---> Color 1
Coloring of Graph 2
Vertex 0 ---> Color 0
Vertex 1 ---> Color 1
Vertex 2 ---> Color 2
Vertex 3 ---> Color 0
Vertex 4 ---> Color 3
329
So the order in which the vertices are picked is important. Many people have
suggested different ways to find an ordering that work better than the basic
algorithm on average. The most common is Welsh–Powell Algorithm which
considers vertices in descending order of degrees.
How does the basic algorithm guarantee an upper bound of d+1?
Here d is the maximum degree in the given graph. Since d is maximum degree,
a vertex cannot be attached to more than d vertices. When we color a vertex,
at most d colors could have already been used by its adjacent. To color this
vertex, we need to pick the smallest numbered color that is not used by the
adjacent vertices. If colors are numbered like 1, 2, …., then the value of such
smallest number must be between 1 to d+1 (Note that d numbers are already
picked by adjacent vertices).
This can also be proved using induction. See thisvideo lecture for proof.
We will soon be discussing some interesting facts about chromatic number and
graph coloring.
Please write comments if you find anything incorrect, or you want to share more
information about the topic discussed above
Source
http://www.geeksforgeeks.org/graph-coloring-set-2-greedy-algorithm/
330
Chapter 57
Travelling Salesman
Problem | Set 1 (Naive and
Dynamic Programming)
331
For example, consider the graph shown in figure on right side. A TSP tour in
the graph is 1-2-4-3-1. The cost of the tour is 10+25+30+15 which is 80.
The problem is a famous NP hardproblem. There is no polynomial time know
solution for this problem.
Following are different solutions for the traveling salesman problem.
Naive Solution:
1) Consider city 1 as the starting and ending point.
2) Generate all (n-1)! Permutationsof cities.
3) Calculate cost of every permutation and keep track of minimum cost permu-
tation.
4) Return the permutation with minimum cost.
Time Complexity: Ω(n!)
Dynamic Programming:
Let the given set of vertices be {1, 2, 3, 4,….n}. Let us consider 1 as starting
and ending point of output. For every other vertex i (other than 1), we find the
minimum cost path with 1 as the starting point, i as the ending point and all
vertices appearing exactly once. Let the cost of this path be cost(i), the cost of
corresponding Cycle would be cost(i) + dist(i, 1) where dist(i, 1) is the distance
from i to 1. Finally, we return the minimum of all [cost(i) + dist(i, 1)] values.
This looks simple so far. Now the question is how to get cost(i)?
To calculate cost(i) using Dynamic Programming, we need to have some recur-
332
sive relation in terms of sub-problems. Let us define a term C(S, i) be the cost
of the minimum cost path visiting each vertex in set S exactly once, starting at
1 and ending at i.
We start with all subsets of size 2 and calculate C(S, i) for all subsets where S is
the subset, then we calculate C(S, i) for all subsets S of size 3 and so on. Note
that 1 must be present in every subset.
For a set of size n, we consider n-2 subsets each of size n-1 such that all subsets
don’t have nth in them.
Using the above recurrence relation, we can write dynamic programming based
solution. There are at most O(n*2n ) subproblems, and each one takes linear time
to solve. The total running time is therefore O(n2 *2n ). The time complexity is
much less than O(n!), but still exponential. Space required is also exponential.
So this approach is also infeasible even for slightly higher number of vertices.
We will soon be discussing approximate algorithms for travelling salesman prob-
lem.
References:
http://www.lsi.upc.edu/~mjserna/docencia/algofib/P07/dynprog.pdf
http://www.cs.berkeley.edu/~vazirani/algorithms/chap6.pdf
Please write comments if you find anything incorrect, or you want to share more
information about the topic discussed above
Source
http://www.geeksforgeeks.org/travelling-salesman-problem-set-1/
333
Chapter 58
Travelling Salesman
Problem | Set 2
(Approximate using MST)
334
335
In this case, the approximate algorithm produces the optimal tour, but it may
not produce optimal tour in all cases.
How is this algorithm 2-approximate? The cost of the output produced by
the above algorithm is never more than twice the cost of best possible output.
Let us see how is this guaranteed by the above algorithm.
Let us define a term full walk to understand this. A full walk is lists all
vertices when they are first visited in preorder, it also list vertices when they
are returned after a subtree is visited in preorder. The full walk of above tree
would be 1-2-1-4-1-3-1.
Following are some important facts that prove the 2-approximateness.
1) The cost of best possible Travelling Salesman tour is never less than the cost
of MST. (The definition of MSTsays, it is a minimum cost tree that connects
all vertices).
2) The total cost of full walk is at most twice the cost of MST (Every edge of
336
MST is visited at-most twice)
3) The output of the above algorithm is less than the cost of full walk. In above
algorithm, we print preorder walk as output. In prreorder walk, two or more
edges of full walk are replaced with a single edge. For example, 2-1 and 1-4 are
replaced by 1 edge 2-4. So if the graph follows triangle inequality, then this is
always true.
From the above three statements, we can conclude that the cost of output
produced by the approximate algorithm is never more than twice the cost of
best possible solution.
We have discussed a very simple 2-approximate algorithm for the travelling sales-
man problem. There are other better approximate algorithms for the problem.
For example Christofides algorithm is 1.5 approximate algorithm. We will soon
be discussing these algorithms as separate posts.
References:
http://www.personal.kent.edu/~rmuhamma/Algorithms/MyAlgorithms/AproxAlgor/TSP/tsp.htm
Please write comments if you find anything incorrect, or you want to share more
information about the topic discussed above
Source
http://www.geeksforgeeks.org/travelling-salesman-problem-set-2-approximate-using-mst/
337
Chapter 59
Hamiltonian Cycle
Hamiltonian Path in an undirected graph is a path that visits each vertex exactly
once. A Hamiltonian cycle (or Hamiltonian circuit) is a Hamiltonian Path such
that there is an edge (in graph) from the last vertex to the first vertex of the
Hamiltonian Path. Determine whether a given graph contains Hamiltonian
Cycle or not. If it contains, then print the path. Following are the input and
output of the required function.
Input:
A 2D array graph[V][V] where V is the number of vertices in graph and
graph[V][V] is adjacency matrix representation of the graph. A value graph[i][j]
is 1 if there is a direct edge from i to j, otherwise graph[i][j] is 0.
Output:
An array path[V] that should contain the Hamiltonian Path. path[i] should
represent the ith vertex in the Hamiltonian Path. The code should also return
false if there is no Hamiltonian Cycle in the graph.
For example, a Hamiltonian Cycle in the following graph is {0, 1, 2, 4, 3, 0}.
There are more Hamiltonian Cycles in the graph like {0, 3, 4, 2, 1, 0}
(0)--(1)--(2)
| / \ |
| / \ |
| / \ |
(3)-------(4)
338
(0)--(1)--(2)
| / \ |
| / \ |
| / \ |
(3) (4)
Naive Algorithm
Generate all possible configurations of vertices and print a configuration that
satisfies the given constraints. There will be n! (n factorial) configurations.
Backtracking Algorithm
Create an empty path array and add vertex 0 to it. Add other vertices, starting
from the vertex 1. Before adding a vertex, check for whether it is adjacent to
the previously added vertex and not already added. If we find such a vertex, we
add the vertex as part of the solution. If we do not find a vertex then we return
false.
Implementation of Backtracking solution
Following is C/C++ implementation of the Backtracking solution.
339
void printSolution(int path[]);
return true;
}
340
/* If adding vertex v doesn't lead to a solution,
then remove it */
path[pos] = -1;
}
}
printSolution(path);
return true;
}
// Let us print the first vertex again to show the complete cycle
341
printf(" %d ", path[0]);
printf("\n");
}
return 0;
}
Output:
342
Solution Exists: Following is one Hamiltonian Cycle
0 1 2 4 3 0
Note that the above code always prints cycle starting from 0. Starting point
should not matter as cycle can be started from any point. If you want to
change the starting point, you should make two changes to above code.
Change “path[0] = 0;” to “path[0] = s;” where s is your new starting point.
Also change loop “for (int v = 1; v
Source
http://www.geeksforgeeks.org/backtracking-set-7-hamiltonian-cycle/
Category: Graph Tags: Backtracking, Graph
Post navigation
← Pattern Searching | Set 6 (Efficient Construction of Finite Automata)
Scansets in C →
Writing code in comment? Please use code.geeksforgeeks.org, generate link and
share the link here.
343
Chapter 60
A vertex cover of an undirected graph is a subset of its vertices such that for
every edge (u, v) of the graph, either ‘u’ or ‘v’ is in vertex cover. Although the
name is Vertex Cover, the set covers all edges of the given graph. Given an
undirected graph, the vertex cover problem is to find minimum size
vertex cover.
Following are some examples.
344
Vertex Cover Problem is a known NP Complete problem, i.e., there is no poly-
nomial time solution for this unless P = NP. There are approximate polynomial
time algorithms to solve the problem though. Following is a simple approximate
algorithm adapted from CLRS book.
Approximate Algorithm for Vertex Cover:
Following diagram taken from CLRS book shows execution of above approxi-
mate algorithm.
345
How well the above algorithm perform?
It can be proved that the above approximate algorithm never finds a vertex
cover whose size is more than twice the size of minimum possible vertex cover
(Refer thisfor proof)
Implementation:
Following is C++ implementation of above approximate algorithm.
346
Graph::Graph(int V)
{
this->V = V;
adj = new list<int>[V];
}
list<int>::iterator i;
347
}
g.printVertexCover();
return 0;
}
Output:
0 1 3 4 5 6
348
This article is contributed by Shubham. Please write comments if you find
anything incorrect, or you want to share more information about the topic
discussed above
Source
http://www.geeksforgeeks.org/vertex-cover-problem-set-1-introduction-approximate-algorithm-2/
349
Chapter 61
Given n cities and distances between every pair of cities, select k cities to place
warehouses (or ATMs) such that the maximum distance of a city to a warehouse
(or ATM) is minimized.
For example consider the following four cities, 0, 1, 2 and 3 and distances
between them, how do place 2 ATMs among these 4 cities so that the maximum
distance of a city to an ATM is minimized.
There is no polynomial time solution available for this problem as the problem
is a known NP-Hard problem. There is a polynomial time Greedy approximate
algorithm, the greedy algorithm provides a solution which is never worse that
twice the optimal solution. The greedy solution works only if the distances be-
350
tween cities follow Triangular Inequality (Distance between two points is always
smaller than sum of distances through a third point).
The 2-Approximate Greedy Algorithm:
1) Choose the first center arbitrarily.
2) Choose remaining k-1 centers using the following criteria.
Let c1, c2, c3, … ci be the already chosen centers. Choose
(i+1)’th center by picking the city which is farthest from already
selected centers, i.e, the point p which has following value as maximum
Min[dist(p, c1), dist(p, c2), dist(p, c3), …. dist(p, ci)]
The following diagram taken from hereillustrates above algorithm.
351
b) This means that distances between all centers are also > 2·OPT.
c) We have k + 1 points with distances > 2·OPT between every pair.
d) Each point has a center of the optimal solution with distance ? OPT to it.
e) There exists a pair of points with the same center X in the optimal solution
(pigeonhole principle: k optimal centers, k+1 points)
f) The distance between them is at most 2·OPT (triangle inequality) which is
a contradiction.
Source:
http://algo2.iti.kit.edu/vanstee/courses/kcenter.pdf
This article is contributed by Harshit. Please write comments if you find
anything incorrect, or you want to share more information about the topic
discussed above
Source
http://www.geeksforgeeks.org/k-centers-problem-set-1-greedy-approximate-algorithm/
352
Chapter 62
Ford-Fulkerson Algorithm
for Maximum Flow
Problem
Given a graph which represents a flow network where every edge has a capacity.
Also given two vertices source ‘s’ and sink ‘t’ in the graph, find the maximum
possible flow from s to t with following constraints:
a) Flow on an edge doesn’t exceed the given capacity of the edge.
b) Incoming flow is equal to outgoing flow for every vertex except s and t.
For example, consider the following graph from CLRS book.
353
Ford-Fulkerson Algorithm
The following is simple idea of Ford-Fulkerson algorithm:
1) Start with initial flow as 0.
2) While there is a augmenting path from source to sink.
Add this path-flow to flow.
3) Return flow.
354
Following is C++ implementation of Ford-Fulkerson algorithm. To keep things
simple, graph is represented as a 2D matrix.
355
// If we reached sink in BFS starting from source, then return
// true, else false
return (visited[t] == true);
}
356
// Add path flow to overall flow
max_flow += path_flow;
}
cout << "The maximum possible flow is " << fordFulkerson(graph, 0, 5);
return 0;
}
Output:
357
References:
http://www.stanford.edu/class/cs97si/08-network-flow-problems.pdf
Source
http://www.geeksforgeeks.org/ford-fulkerson-algorithm-for-maximum-flow-problem/
Category: Graph Tags: Graph
Post navigation
← Find the minimum element in a sorted and rotated array Dynamic Program-
ming | Set 34 (Assembly Line Scheduling) →
Writing code in comment? Please use code.geeksforgeeks.org, generate link and
share the link here.
358
Chapter 63
Given a directed graph and two vertices in it, source ‘s’ and destination ‘t’, find
out the maximum number of edge disjoint paths from s to t. Two paths are said
edge disjoint if they don’t share any edge.
There can be maximum two edge disjoint paths from source 0 to destination 7
in the above graph. Two edge disjoint paths are highlighted below in red and
blue colors are 0-2-6-7 and 0-3-6-5-7.
359
Note that the paths may be different, but the maximum number is same. For
example, in the above diagram, another possible set of paths is 0-1-2-6-7 and
0-3-6-5-7 respectively.
This problem can be solved by reducing it to maximum flow problem. Following
are steps.
1) Consider the given source and destination as source and sink in flow network.
Assign unit capacity to each edge.
2) Run Ford-Fulkerson algorithm to find the maximum flow from source to sink.
3) The maximum flow is equal to the maximum number of edge-disjoint paths.
When we run Ford-Fulkerson, we reduce the capacity by a unit. Therefore, the
edge can not be used again. So the maximum flow is equal to the maximum
number of edge-disjoint paths.
Following is C++ implementation of the above algorithm. Most of the code is
taken from here.
360
memset(visited, 0, sizeof(visited));
361
int parent[V]; // This array is filled by BFS and to store path
362
{0, 1, 0, 0, 0, 0, 0, 1},
{0, 0, 0, 0, 0, 1, 0, 1},
{0, 0, 0, 0, 0, 0, 0, 0}
};
int s = 0;
int t = 7;
cout << "There can be maximum " << findDisjointPaths(graph, s, t)
<< " edge-disjoint paths from " << s <<" to "<< t ;
return 0;
}
Output:
http://www.win.tue.nl/~nikhil/courses/2012/2WO08/max-flow-applications-4up.
pdf
Please write comments if you find anything incorrect, or you want to share more
information about the topic discussed above
Source
http://www.geeksforgeeks.org/find-edge-disjoint-paths-two-vertices/
Category: Graph Tags: Graph
Post navigation
← Implement your own itoa() Amazon Interview | Set 48 (On-campus for SDE-
1) →
Writing code in comment? Please use code.geeksforgeeks.org, generate link and
share the link here.
363
Chapter 64
In a flow network, an s-t cut is a cut that requires the source ‘s’ and the sink ‘t’
to be in different subsets, and it consists of edges going from the source’s side
to the sink’s side. The capacity of an s-t cut is defined by the sum of capacity
of each edge in the cut-set. (Source: Wiki)
The problem discussed here is to find minimum capacity s-t cut of the given
network. Expected output is all edges of the minimum cut.
For example, in the following flow network, example s-t cuts are {{0 ,1}, {0,
2}}, {{0, 2}, {1, 2}, {1, 3}}, etc. The minimum s-t cut is {{1, 3}, {4, 3}, {4 5}}
which has capacity as 12+7+4 = 23.
364
maximum flow is equal to capacity of the minimum cut. See CLRS book for
proof of this theorem.
From Ford-Fulkerson, we get capacity of minimum cut. How to print all edges
that form the minimum cut? The idea is to use residual graph.
Following are steps to print all edges of minimum cut.
1) Run Ford-Fulkerson algorithm and consider the final residual graph.
2) Find the set of vertices that are reachable from source in the residual graph.
3) All edges which are from a reachable vertex to non-reachable vertex are
minimum cut edges. Print all such edges.
Following is C++ implementation of the above approach.
365
for (int v=0; v<V; v++)
{
if (visited[v]==false && rGraph[u][v] > 0)
{
q.push(v);
parent[v] = u;
visited[v] = true;
}
}
}
// A DFS based function to find all reachable vertices from s. The function
// marks visited[i] as true if i is reachable from s. The initial values in
// visited[] must be false. We can also use BFS to find reachable vertices
void dfs(int rGraph[V][V], int s, bool visited[])
{
visited[s] = true;
for (int i = 0; i < V; i++)
if (rGraph[s][i] && !visited[i])
dfs(rGraph, i, visited);
}
366
// path filled by BFS. Or we can say find the maximum flow
// through the path found.
int path_flow = INT_MAX;
for (v=t; v!=s; v=parent[v])
{
u = parent[v];
path_flow = min(path_flow, rGraph[u][v]);
}
return;
}
367
minCut(graph, 0, 5);
return 0;
}
Output:
1 - 3
4 - 3
4 - 5
References:
http://www.stanford.edu/class/cs97si/08-network-flow-problems.pdf
http://www.cs.princeton.edu/courses/archive/spring06/cos226/lectures/
maxflow.pdf
Please write comments if you find anything incorrect, or you want to share more
information about the topic discussed above
Source
http://www.geeksforgeeks.org/minimum-cut-in-a-directed-graph/
Category: Graph Tags: Graph
Post navigation
← Maximum Bipartite Matching Stable Marriage Problem →
Writing code in comment? Please use code.geeksforgeeks.org, generate link and
share the link here.
368
Chapter 65
Maximum Bipartite
Matching
369
We strongly recommend to read the following post first.
Ford-Fulkerson Algorithm for Maximum Flow Problem
Maximum Bipartite Matching and Max Flow Problem
Maximum Bipartite Matching (MBP) problem can be solved by converting it
into a flow network (See thisvideo to know how did we arrive this conclusion).
Following are the steps.
370
2) Find the maximum flow.
We use Ford-Fulkerson algorithm to find the maximum flow in the flow network
built in step 1. The maximum flow is actually the MBP we are looking for.
How to implement the above approach?
Let us first define input and output forms. Input is in the form of Edmonds
matrix which is a 2D array ‘bpGraph[M][N]’ with M rows (for M job applicants)
and N columns (for N jobs). The value bpGraph[i][j] is 1 if i’th applicant is
interested in j’th job, otherwise 0.
Output is number maximum number of people that can get jobs.
A simple way to implement this is to create a matrix that represents adjacency
matrix representationof a directed graph with M+N+2 vertices. Call the ford-
Fulkerson() for the matrix. This implementation requires O((M+N)*(M+N))
extra space.
Extra space can be be reduced and code can be simplified using the fact that
the graph is bipartite and capacity of every edge is either 0 or 1. The idea is
to use DFS traversal to find a job for an applicant (similar to augmenting path
in Ford-Fulkerson). We call bpm() for every applicant, bpm() is the DFS based
function that tries all possibilities to assign a job to the applicant.
In bpm(), we one by one try all jobs that an applicant ‘u’ is interested in until
we find a job, or all jobs are tried without luck. For every job we try, we do
following.
If a job is not assigned to anybody, we simply assign it to the applicant and
return true. If a job is assigned to somebody else say x, then we recursively
check whether x can be assigned some other job. To make sure that x doesn’t
get the same job again, we mark the job ‘v’ as seen before we make recursive call
for x. If x can get other job, we change the applicant for job ‘v’ and return true.
We use an array maxR[0..N-1] that stores the applicants assigned to different
371
jobs.
If bmp() returns true, then it means that there is an augmenting path in flow
network and 1 unit of flow is added to the result in maxBPM().
372
// An array to keep track of the applicants assigned to
// jobs. The value of matchR[i] is the applicant number
// assigned to job i, the value -1 indicates nobody is
// assigned.
int matchR[N];
cout << "Maximum number of applicants that can get job is "
<< maxBPM(bpGraph);
return 0;
}
Output:
373
References:
http://www.cs.cornell.edu/~wdtseng/icpc/notes/graph_part5.pdf
http://www.youtube.com/watch?v=NlQqmEXuiC8
http://en.wikipedia.org/wiki/Maximum_matching
http://www.stanford.edu/class/cs97si/08-network-flow-problems.pdf
http://www.cs.princeton.edu/courses/archive/spring13/cos423/lectures/07NetworkFlowII-
2×2.pdf
http://www.ise.ncsu.edu/fangroup/or766.dir/or766_ch7.pdf
Please write comments if you find anything incorrect, or you want to share more
information about the topic discussed above
Source
http://www.geeksforgeeks.org/maximum-bipartite-matching/
374
Chapter 66
Channel Assignment
Problem
There are M transmitter and N receiver stations. Given a matrix that keeps
track of the number of packets to be transmitted from a given transmitter to
a receiver. If the (i; j)-th entry of the matrix is k, it means at that time the
station i has k packets for transmission to station j.
During a time slot, a transmitter can send only one packet and a receiver can
receive only one packet. Find the channel assignments so that maximum number
of packets are transferred from transmitters to receivers during the next time
slot.
Example:
0 2 0
3 0 1
2 4 0
The above is the input format. We call the above matrix M. Each value M[i;
j] represents the number of packets Transmitter ‘i’ has to send to Receiver ‘j’.
The output should be:
375
Note that the maximum number of packets that can be transferred in any slot
is min(M, N).
Algorithm:
The channel assignment problem between sender and receiver can be easily trans-
formed into Maximum Bipartite Matching(MBP) problem that can be solved
by converting it into a flow network.
Step 1: Build a Flow Network
There must be a source and sink in a flow network. So we add a dummy source
and add edges from source to all senders. Similarly, add edges from all receivers
to dummy sink. The capacity of all added edges is marked as 1 unit.
Step 2: Find the maximum flow.
We use Ford-Fulkerson algorithm to find the maximum flow in the flow network
built in step 1. The maximum flow is actually the maximum number of packets
that can be transmitted without bandwidth interference in a time slot.
Implementation:
Let us first define input and output forms. Input is in the form of Edmonds
matrix which is a 2D array ‘table[M][N]‘ with M rows (for M senders) and N
columns (for N receivers). The value table[i][j] is the number of packets that has
to be sent from transmitter ‘i’ to receiver ‘j’. Output is the maximum number of
packets that can be transmitted without bandwidth interference in a time slot.
A simple way to implement this is to create a matrix that represents adjacency
matrix representation of a directed graph with M+N+2 vertices. Call the ford-
Fulkerson() for the matrix. This implementation requires O((M+N)*(M+N))
extra space.
Extra space can be reduced and code can be simplified using the fact that the
graph is bipartite. The idea is to use DFS traversal to find a receiver for a
transmitter (similar to augmenting path in Ford-Fulkerson). We call bpm() for
every applicant, bpm() is the DFS based function that tries all possibilities to
assign a receiver to the sender. In bpm(), we one by one try all receivers that
a sender ‘u’ is interested in until we find a receiver, or all receivers are tried
without luck.
For every receiver we try, we do following:
If a receiver is not assigned to anybody, we simply assign it to the sender and
return true. If a receiver is assigned to somebody else say x, then we recur-
sively check whether x can be assigned some other receiver. To make sure that
x doesn’t get the same receiver again, we mark the receiver ‘v’ as seen before
we make recursive call for x. If x can get other receiver, we change the sender
for receiver ‘v’ and return true. We use an array maxR[0..N-1] that stores the
senders assigned to different receivers.
If bmp() returns true, then it means that there is an augmenting path in flow
network and 1 unit of flow is added to the result in maxBPM().
Time and space complexity analysis:
In case of bipartite matching problem, F ? |V| since there can be only |V|
376
possible edges coming out from source node. So the total running time is O(m’n)
= O((m + n)n). The space complexity is also substantially reduces from O
((M+N)*(M+N)) to just a single dimensional array of size M thus storing the
mapping between M and N.
#include <iostream>
#include <string.h>
#include <vector>
#define M 3
#define N 4
using namespace std;
377
{
// An array to keep track of the receivers assigned to the senders.
// The value of matchR[i] is the sender ID assigned to receiver i.
// the value -1 indicates nobody is assigned.
int matchR[N];
cout << "The number of maximum packets sent in the time slot is "
<< result << "\n";
Output:
378
T2-> R3
Source
http://www.geeksforgeeks.org/channel-assignment-problem/
379
Chapter 67
In the previous post, we introduced union find algorithm and used it to detect
cycle in a graph. We used following union() and find() operations for subsets.
The above union() and find() are naive and the worst case time complexity is
linear. The trees created to represent subsets can be skewed and can become
like a linked list. Following is an example worst case scenario.
380
Let there be 4 elements 0, 1, 2, 3
Do Union(0, 1)
1 2 3
/
0
Do Union(1, 2)
2 3
/
1
/
0
Do Union(2, 3)
3
/
2
/
1
/
0
The above operations can be optimized to O(Log n) in worst case. The idea
is to always attach smaller depth tree under the root of the deeper tree. This
technique is called union by rank. The term rank is preferred instead of height
because if path compression technique (we have discussed it below) is used, then
rank is not always equal to height. Also, size (in place of height) of trees can
also be used as rank. Using size as rank also yields worst case time complexity
as O(Logn) (See thisfor prrof)
Do Union(0, 1)
1 2 3
/
381
0
Do Union(1, 2)
1 3
/ \
0 2
Do Union(2, 3)
1
/ | \
0 2 3
9
/ / \ \
4 5 6 3
/ / \ / \
0 7 8 1 2
382
The two techniques complement each other. The time complexity of each oper-
ations becomes even smaller than O(Logn). In fact, amortized time complexity
effectively becomes small constant.
Following is union by rank and path compression based implementation to find
cycle in a graph.
// A union by rank and path compression based program to detect cycle in a graph
#include <stdio.h>
#include <stdlib.h>
struct subset
{
int parent;
int rank;
};
return graph;
}
383
// A utility function to find set of an element i
// (uses path compression technique)
int find(struct subset subsets[], int i)
{
// find root and make root as parent of i (path compression)
if (subsets[i].parent != i)
subsets[i].parent = find(subsets, subsets[i].parent);
return subsets[i].parent;
}
// The main function to check whether a given graph contains cycle or not
int isCycle( struct Graph* graph )
{
int V = graph->V;
int E = graph->E;
384
subsets[v].parent = v;
subsets[v].rank = 0;
}
if (x == y)
return 1;
Union(subsets, x, y);
}
return 0;
}
int V = 3, E = 3;
struct Graph* graph = createGraph(V, E);
if (isCycle(graph))
printf( "Graph contains cycle" );
385
else
printf( "Graph doesn't contain cycle" );
return 0;
}
Output:
Source
http://www.geeksforgeeks.org/union-find-algorithm-set-2-union-by-rank/
Category: Graph Tags: Graph
Post navigation
← Union-Find Algorithm | Set 1 (Detect Cycle in a an Undirected Graph) [Top-
Talent.in] Rushabh Agrawal from BITS Pilani talks about his Google interview
experience →
Writing code in comment? Please use code.geeksforgeeks.org, generate link and
share the link here.
386
Chapter 68
Given an undirected and unweighted graph, find the smallest cut (smallest num-
ber of edges that disconnects the graph into two components).
The input graph may have parallel edges.
For example consider the following example, the smallest cut has 2 edges.
387
A Simple Solution use Max-Flow based s-t cut algorithm to find minimum cut.
Consider every pair of vertices as source ‘s’ and sink ‘t’, and call minimum s-t
cut algorithm to find the s-t cut. Return minimum of all s-t cuts. Best possible
time complexity of this algorithm is O(V5 ) for a graph. [How? there are total
possible V2 pairs and s-t cut algorithm for one pair takes O(V*E) time and E
= O(V2 )].
Below is simple Karger’s Algorithm for this purpose. Below Karger’s algorithm
can be implemented in O(E) = O(V2 ) time.
388
Let the next randomly picked edge be ‘d’. We remove this edge and combine
vertices (0,1) and 3.
Now graph has two vertices, so we stop. The number of edges in the resultant
graph is the cut produced by Karger’s algorithm.
Karger’s algorithm is a Monte Carlo algorithm and cut produced by
it may not be minimum. For example, the following diagram shows that a
different order of picking random edges produces a min-cut of size 3.
389
Below is C++ implementation of above algorithm. The input graph is repre-
sented as a collection of edges andunion-find data structure is used to keep track
of components.
390
// from src to dest is also edge from dest
// to src. Both are counted as 1 edge here.
Edge* edge;
};
391
// Pick a random edge
int i = rand() % E;
return cutedges;
}
392
subsets[i].parent =
find(subsets, subsets[i].parent);
return subsets[i].parent;
}
393
| \|
2------3 */
int V = 4; // Number of vertices in graph
int E = 5; // Number of edges in graph
struct Graph* graph = createGraph(V, E);
return 0;
}
Output:
394
Note that the above program is based on outcome of a random function
and may produce different output.
In this post, we have discussed simple Karger’s algorithm and have seen that the
algorithm doesn’t always produce min-cut. The above algorithm produces min-
cut with probability greater or equal to that 1/(n2 ). In the next post, we will
discuss proof of this and how repeated calls of Karger’s algorithm can improve
this probability. We will also discuss applications of Karger’s algorithm.
References:
http://en.wikipedia.org/wiki/Karger%27s_algorithm
https://www.youtube.com/watch?v=P0l8jMDQTEQ
https://www.cs.princeton.edu/courses/archive/fall13/cos521/lecnotes/
lec2final.pdf
http://web.stanford.edu/class/archive/cs/cs161/cs161.1138/lectures/11/
Small11.pdf
Please write comments if you find anything incorrect, or you want to share more
information about the topic discussed above.
Source
http://www.geeksforgeeks.org/kargers-algorithm-for-minimum-cut-set-1-introduction-and-implementation/
395
Chapter 69
396
c is number of edges in min-cut
m is total number of edges
n is total number of vertices
..................
..................
The cut produced by Karger's algorithm would be a min-cut if none of the above
events happen.
397
than or equal to c.
Since there are total (n-1) edges left now and number of cut edges is still c,
we can replace n by n-1 in inequality (1). So we get.
P[S2' | S1' ] >= (1 - 2/(n-1))
398
for a graph with 10 nodes, the probability of finding the min-cut is greater than
or equal to 1/100. The probability can be increased by repeated runs of basic
algorithm and return minimum of all cuts found.
Applications:
1) In war situation, a party would be interested in finding minimum number of
links that break communication network of enemy.
2) The min-cut problem can be used to study reliability of a network (smallest
number of edges that can fail).
3) Study of network optimization (find a maximum flow).
4) Clustering problems (edges like associations rules) Matching problems (an
NCalgorithm for min-cut in directed graphs would result in an NCalgorithm for
maximum matching in bipartite graphs)
5) Matching problems (an NC algorithm for min-cut in directed graphs would
result in an NC algorithm for maximum matching in bipartite graphs)
Sources:
https://www.youtube.com/watch?v=-UuivvyHPas
http://disi.unal.edu.co/~gjhernandezp/psc/lectures/02/MinCut.pdf
Please write comments if you find anything incorrect, or you want to share more
information about the topic discussed above.
Source
http://www.geeksforgeeks.org/kargers-algorithm-for-minimum-cut-set-2-analysis-and-applications/
399
Chapter 70
Hopcroft–Karp Algorithm
for Maximum Matching |
Set 1 (Introduction)
400
Augmenting path: Given a matching M, an augmenting path is an alternating
path that starts from and ends on free vertices. All single edge paths that start
and end with free vertices are augmenting paths. In below diagram, augmenting
paths are highlighted with blue color. Note that the augmenting path always
has one extra matching edge.
The Hopcroft Karp algorithm is based on below concept.
A matching M is not maximum if there exists an augmenting path. It is also
true other way, i.e, a matching is maximum if no augmenting path exists
So the idea is to one by one look for augmenting paths. And add the found
paths to current matching.
Hopcroft Karp Algorithm
In the initial graph all single edges are augmenting paths and we can pick in
any order. In the middle stage, there is only one augmenting path. We remove
matching edges of this path from M and add not-matching edges. In final
matching, there are no augmenting paths so the matching is maximum.
401
Implementation of Hopcroft Karp algorithm is discussed in set 2.
Hopcroft–Karp Algorithm for Maximum Matching | Set 2 (Implementation)
References:
https://en.wikipedia.org/wiki/Hopcroft%E2%80%93Karp_algorithm
http://www.dis.uniroma1.it/~leon/tcs/lecture2.pdf
Please write comments if you find anything incorrect, or you want to share more
information about the topic discussed above
Source
http://www.geeksforgeeks.org/hopcroft-karp-algorithm-for-maximum-matching-set-1-introduction/
402
Chapter 71
Hopcroft–Karp Algorithm
for Maximum Matching |
Set 2 (Implementation)
The idea is to use BFS (Breadth First Search) to find augmenting paths. Since
BFS traverses level by level, it is used to divide the graph in layers of matching
and not matching edges. A dummy vertex NIL is added that is connected to
all vertices on left side and all vertices on right side. Following arrays are used
to find augmenting path. Distance to NIL is initialized as INF (infinite). If we
start from dummy vertex and come back to it using alternating path of distinct
vertices, then there is an augmenting path.
403
2. pairV[]: An array of size n+1 where n is number of vertices on right side
of Bipartite Graph. pairU[v] stores pair of v on left side if v is matched
and NIL otherwise.
3. dist[]: An array of size m+1 where m is number of vertices on left side of
Bipartite Graph. dist[u] is initialized as 0 if u is not matching and INF
(infinite) otherwise. dist[] of NIL is also initialized as INF
Once an augmenting path is found, DFS (Depth First Search) is used to add
augmenting paths to current matching. DFS simply follows the distance array
setup by BFS. It fills values in pairU[u] and pairV[v] if v is next to u in BFS.
Below is C++ implementation of above Hopkroft Karp algorithm.
public:
BipGraph(int m, int n); // Constructor
void addEdge(int u, int v); // To add edge
404
// with u
bool dfs(int u);
// Initialize result
int result = 0;
405
}
// If this node is not NIL and can provide a shorter path to NIL
if (dist[u] < dist[NIL])
{
// Get all adjacent vertices of the dequeued vertex u
list<int>::iterator i;
for (i=adj[u].begin(); i!=adj[u].end(); ++i)
{
int v = *i;
406
{
// Consider the pair and add it to queue
dist[pairV[v]] = dist[u] + 1;
Q.push(pairV[v]);
}
}
}
}
407
// Constructor
BipGraph::BipGraph(int m, int n)
{
this->m = m;
this->n = n;
adj = new list<int>[m+1];
}
// Driver Program
int main()
{
BipGraph g(4, 4);
g.addEdge(1, 2);
g.addEdge(1, 3);
g.addEdge(2, 1);
g.addEdge(3, 2);
g.addEdge(4, 2);
g.addEdge(4, 4);
return 0;
}
Output:
408
Source
http://www.geeksforgeeks.org/hopcroft-karp-algorithm-for-maximum-matching-set-2-implementation/
409