Problem 19.6 Making Wired Connections, alternative solution

#1

Hi,

For problem 19.6, as i understand, essentially we need to determine if the graph is bipartite. It seems it can be solved differently than the solution in the book, without doing BFS, in 2 steps:

  1. We build a set of vertices that have no edges between them. We go through each vertex iteratively: start with empty set, then for each vertex we consider check if it has edges to any vertices already in the set and if it doesn’t, put it in the set.

  2. Now consider remaining vertices (the ones not in the set we just built). Check if there are any edges between the remaining vertices. If there are no such edges, the graph is bipartite and the 2 sets represent the sought division. If there are such edges, the graph is not bipartite.

The time complexity is O(|V| + |E|) (provided we can mark the vertices in the 1st step so that each check will take O(1)) since in each step the number of edges we check is O(|E|). Also there is no need for a queue, as in BFS solution.

This algorithm will work whether the graph is connected or not.

I just thought this has a little bit simplier logic than the solution in the book.

Thanks,
Yev

0 Likes
#2

Hi @yevvi,

Thanks for this sharing, and it definitely works after I take sometime to think about it. Compare with the BFS solution, which uses queue, you can use a DFS approach, which will implicitly use a stack, or your approach will require a hash table likely. In my opinion, those are personal flavor on the way you approach this problem, and in interview I will say the ability to understanding what this problem asks and brings the solution you can explain well is the most important thing, and your post clearly demonstrates that well. Good job!

0 Likes
#3

Hi,

Thank you. Here is the code in Java, if anyone interested:

	public static class Pin {
		int n;
		ArrayList<Pin> edges = new ArrayList<Pin>();
		boolean marked;
		Pin(int n) { this.n = n; }
	}
	
	public static boolean isBipartite(ArrayList<Pin> g)
	{
		for(Pin v: g) {
			boolean edgesToSet = false;
			for(Pin e: v.edges)
				if (e.marked) {
					edgesToSet = true;
					break;
				}
			if (!edgesToSet)
				v.marked = true;
		}
		for(Pin v: g) {
			if (v.marked)
				continue;
			for(Pin e: v.edges)
				if (!e.marked) //if e is not in the first set, then it must be one of remaining pins
					return false;
		}
		//Marked/unmarked pins will represent bipartite division.
		return true;
	}

I added “marked” flag to the Pin class, that way we don’t need to do a set or hashtable lookup. If division is possible, marked/unmarked nodes will represent this division at the end of the call, of course we could also collect them into lists or sets if needed.

Thanks,
Yev

0 Likes