A graph is said to be bipartite if all its vertices can be partitioned into two

ID: 3542976 • Letter: A

Question

disjoint subsetsX and Y so that every edge connects a vertex inX with a vertex

in Y . (One can also say that a graph is bipartite if its vertices can be colored in

two colors so 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.

(i)

x1-y1-x3

| | |

y2-x2-y3

(ii)

a-b

| / |

c-d

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.

a.DFS-based

b.BFS-based

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

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.