A Graph is said to be bipartite if all its vertices can be partitioned into two
ID: 674137 • Letter: A
Question
A Graph is said to be bipartite if all its vertices can be partitioned into two disjoint subsets X and Y so that every edge connects a vertex in X with a vertex in Y. (One can also say that a graph is bipartite if its vertices can be colored in two colors os that every edge has its vertices colored in different colors; such graphs are also called 2-colorable.) For example, graph (i) is bipartite while graph (ii) is not.
a. Design a DFS-based algorithm for checking whether a graph is bipartite.
b. Design a BFS-based algorithm for checking whether a graph is bipartite.
This is an unanswered book problem ( http://www.chegg.com/homework-help/introduction-to-the-design-and-analysis-of-algorithms-3rd-edition-chapter-3.5-problem-8e-solution-9780132316811 )
Explanation / Answer
ALGORITHM USING DFS APPROACH
ALGORITHM bipartite(G)
//checks whether the given graph is bipartite or not using DFS
//input: Graph G={V,E}
//output: returns true if graph is bipartite otherwise false
visit[0…n-1] 0 //global variable
colour[0…n-1] 0 //global array
flag 0 //global variable
For every vertex v in V do
if visit[v]=0
dfs(v)
dfs(v)
//visits all the adjacent vertices of v recursively & colours the vertices
visit[v] 1
if colour[v]=0
colour[v] 1 //coloured as blue
for each vertex w in V adjacent to v do
if visit[w]=0
if colour[v]=1
colour[w]=2 //coloured as red
else
colour[w]=1 //coloured as blue
dfs(w)
if visit[w]=1 and colour[w]=colour[v]
flag -1 //adjacent vertex and current vertex //are of same colour, for other cases it will //continue…
//the entire graph is checked and coloured
ALGORITHM USING BFS
ALGORITHM Bipartite(G)
//checks whether a given graph is bipartite or not using BFS
//input: A graph G={V,E}
//output: if flag is -1 it is not bipartite else it is bipartite
flag 0 //global variable
colour[0…n-1] 0 //global array
visit[0…n-1] 0 //global array
for each vertex v in V do
If visit[v]=0
bfs(v)
bfs(v)
//visits all the unvisited vertices connected to v
visit[v] 1
colour[v] 1//coloured blue
enqueue v
while the queue is not empty do
for each vertex w in V adjacent to the front’s vertex v do
if visit[w]=0
visit[w] 1
colour[w] 2 // coloured red
enqueue w
if visit[w]=1 and colour[w]=colour[v]
flag -1
dequeue w
BFS-based C++ implementation for checking whether a graph is bipartite.
#include <iostream>
#include <queue>
#define V 4
using namespace std;
// This function returns true if graph G[V][V] is Bipartite, else false
bool isBipartite(int G[][V], int src)
{
// Create a color array to store colors assigned to all veritces. Vertex
// number is used as index in this array. The value '-1' of colorArr[i]
// is used to indicate that no color is assigned to vertex 'i'. The value
// 1 is used to indicate first color is assigned and value 0 indicates
// second color is assigned.
int colorArr[V];
for (int i = 0; i < V; ++i)
colorArr[i] = -1;
// Assign first color to source
colorArr[src] = 1;
// Create a queue (FIFO) of vertex numbers and enqueue source vertex
// for BFS traversal
queue <int> q;
q.push(src);
// Run while there are vertices in queue (Similar to BFS)
while (!q.empty())
{
// Dequeue a vertex from queue ( Refer http://goo.gl/35oz8 )
int u = q.front();
q.pop();
// Find all non-colored adjacent vertices
for (int v = 0; v < V; ++v)
{
// An edge from u to v exists and destination v is not colored
if (G[u][v] && colorArr[v] == -1)
{
// Assign alternate color to this adjacent v of u
colorArr[v] = 1 - colorArr[u];
q.push(v);
}
// An edge from u to v exists and destination v is colored with
// same color as u
else if (G[u][v] && colorArr[v] == colorArr[u])
return false;
}
}
// If we reach here, then all adjacent vertices can be colored with
// alternate color
return true;
}
// Driver program to test above function
int main()
{
int G[][V] = {{0, 1, 0, 1},
{1, 0, 1, 0},
{0, 1, 0, 1},
{1, 0, 1, 0}
};
isBipartite(G, 0) ? cout << "Yes" : cout << "No";
return 0;
}
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.