An undirected graph G = ( V , E ) is called 2-colorable if all vertices in V can

Question

An undirected graph G = (V, E) is called 2-colorable if all vertices in V can be assigned one of two colors (Red or Blue) and all edges in E have one Red endpoint and one Blue endpoint. Such graphs are also called bipartite, since the vertices can be partitioned into two disjoint sets V = V1 V2 such that every edge in E joins a vertex in V1and a vertex in V2. Given an undirected graph G = (V, E) in adjacency list format, give an O(V + E) time algorithm which determines if G is 2-colorable. If G is 2-colorable, your algorithm should construct a valid 2-coloring of G in O(V + E) time. You may assume that G is connected. Hint: Modify BFS.

1. Describe your algorithm in pseudocode. Comment your code.

2. Explain clearly and concisely why your algorithm is correct.

3. Analyze the running time of your algorithm.

Explanation / Answer

public boolean edgeBackTrace (List edgesList, Map neighborEdges) { for (Edge e : edgesList) { e.setColor(0); } int i = 0; while (true){ Edge edge = edgesList.get(i); edge.setColor(edge.getColor() + 1); if (edge.getColor().equals(4)) { edge.setColor(0); if (i == 0) { return true; } else { i--; } } else { boolean diferentColor = false; for (Edge e : neighborEdges.get(edge)) { if (e.getColor().equals(edge.getColor())) { diferentColor = true; } } if (diferentColor == false) { i++; if (i == edgesList.size()) { return false; } } } } }

Related Questions

Navigate

• Browse (All)
• Browse A
• Subjects

---