Is Graph Bipartite? - Leetcode 785 - Python

Key Takeaways

hey everyone welcome back and let's write some more neat code today so today let's solve the problem is graph bipartite I don't know if I'm pronouncing that correctly but we're given an undirected graph with n nodes now n is not given as a parameter but we're also given a second parameter which is graph but thankfully this is actually an adjacency list and usually in graph problems we have to build these ourselves but in this case it's provided for us basically the first or zeroth array represents all of the neighbors of the zero node so in this case we have one two three because the zero node over here has one two three neighbors and the same for the next array and so on so to get the number of nodes we can just take the length of this array we want to know if this graph is bipartite that means that we have to split this graph up into two distinct sets let's call them A and B and you can kind of think of it however you want but the simplest way to understand this is basically to say that every node in this graph cannot be in the same set as any of its neighbors that's the simplest way to think about this and when you think of it like that then the problem becomes a little bit easier not quite easy though and I'll be honest I probably know how to solve this just because I've kind of seen this pattern before but the idea is that any node can't be in the same set as its neighbors and when it comes to graph problems we know kind of the main algorithms available to us are DFS or BFS we know there's more academic algorithms but you always want to start with either of these can we solve this problem in a relatively simple way and in this problem we actually can so let's think about this let's just start from some arbitrary node and we always know the zero node is going to exist because the nodes are numbered from 0 to n minus 1. so let's say this node is going to go in a set let's say a and actually in this problem I'm going to be calling the sets either the odd set or the even set so for the first node let's put it in the even set so 0 is going to go here and the reason I'm putting it in even is because we're going to be alternating because now from zero like I said none of its neighbors this guy this guy or this guy remember these edges are undirected none of these can go in the same set so all three of these nodes must go in the odd set but how exactly are we going to do this the way I'm kind of drawing this is a BFS because we're kind of going about it in this layer instead of just you know going to one neighbor and then running a DFS from that neighbor so that's kind of how I'll also code this up we're taking now this layer and now adding all of these to the odd set so one two and three now from each of these let's continue to run our BFS algorithm so maybe from three let's go to all of its neighbors well what we're going to try to do is go to this first neighbor and since we're coming from an odd node we expect this neighbor to be an even node in this case the node is already visited how would we know that should we have a separate data structure to check if a node's been visited not really because we're already keeping track of it here and what I'm going to be using for this is actually just going to be an array because we know each of the nodes is numbered from 0 to n minus 1 we can literally just use an array where probably we want to initialize the array initially with all zeros to say that none of the nodes have been visited but let's say maybe when we reach an odd node we number it with one and when we reach an even node we number it with negative one to distinguish between those two that should be easy enough and that's just kind of a minor detail you can kind of represent that with many other data structures but the important thing here is when we are continuing our traversal we go from a node and we reach a node that's already been visited well our expected was that this node should be an even node so we have to check is it an even node yes it is so that's fine and we definitely don't want to continue the traversal from here because it's already been visited we don't want to continue to repeatedly visit the same node that was good but now we're going to notice a problem from here now let's go to our other neighbor too the expectation is either this node has not been visited in this case it has been visited though and if that's the case this should be in the even set but it's not it's in the odd set that's a problem because these two nodes have to be in different sets we have a contradiction so this graph cannot possibly be bipartite but you might think well why did we make both of these red in the first place why can't this guy be green remember it was because of this Edge over here because yeah these two aren't neighbors of each other this isn't a neighbor of them either but these guys are neighbors if we got rid of this middle Edge over here then we you could kind of split it up like this where these two go in one set and these two go in the other set Now you kind of realize this problem isn't crazy hard once you kind of conceptually understand that some people solve this problem instead of distinguishing between odd and even like I'm doing which I think is intuitive because we want to alternate each time some people use color like when we start we're starting green and then the neighbors are going to be red and then so on are going to be green you can do it however you would like I'm probably going to stick with this approach though and since we are just doing a pretty normal graph traversal without repeatedly visiting the same nodes the overall time complexity is going to be the size of the graph in this case it's going to be Big O of e which is the number of edges plus v which is the number of nodes memory complexity though I think is just going to be number of vertices because we're already given an adjacency list we don't have to build it ourselves so now let's code this up okay so first thing I'm gonna do is create our odd asset I'm just going to call it odd and then I'm going to initialize it to this multiplied by the length of the graph and I said set but it's obviously an array and what we want to do is map the node index or the node I like the value of the node whatever you want to call it mapping that to whether it's odd and if it's odd let's say we set it to one and if it's even we set it to negative one it doesn't really matter you could swap these the important thing is that they are going to be alternating so now let's call our BFS starting at some node I what we're going to want to do is they clarify that this graph might actually not be connected so after we Define our BFS we want to actually run it on every single starting point so we're going to take the length of the graph and for I in that range we're going to want to call our BFS for every single I and if we try to visit the same node multiple times our function here should immediately return we don't want to end up doing that how will we know if we visited this node already well that's what we have our odd map for at least that's one of the reasons for it if this value is not equal to zero which we can write just like this then we want to return immediately and at this point we don't know that the graph is not bipartite so what I'm going to do here is actually return true because from this BFS we need some indication whether the graph is bipartite or not that's what we're calling the bs4 in the first place so we're always going to check the return value if it's not true that means the graph is not bipartite and at that point we can just immediately return false and if that never executes out here we're going to return true now to actually do the implementation of the BFS it's pretty cookie cutter well there's going to be a little bit of nuance here but the boilerplate is almost always the same we're going to create a q we're going to initialize it in this case with the I value you have to pass in an array to initialize the Q in Python and here I'm going to initialize this value also in the visit set and determining whether it's odd or even since it's a starting point and we know for sure this eye has not been visited because if it was we would have returned by now we're going to initialize it with a negative one I guess because this is going to be an even point and then we're going to say while the queue is not empty we always want to pop from the queue we're going to set that to Q dot pop left because when we append we're gonna append to the right and then for this node we don't have to mark it visited because the way we're doing it is marking it visited here as soon as we add to the cube we're going to be marking a node visited so we just need to go through all of its neighbors and thankfully we have an adjacency list that's provided to us and for each neighbor we will want to say Q dot append that neighbor and we'll also want to say for odd we want the odd of the neighbor to be set to the opposite of the node that we're coming from we want to alternate this now you can kind of see why I made this one and negative one we could have done one and two but that would have required a little bit of extra logic here maybe an if statement or something but when we have 1 and negative 1 we can alternate these pretty easy I can take the value from here and just say negative 1 multiplied by that so that's what the neighbors value will be but we don't necessarily want to visit every neighbor what if this neighbor had already been visited before how would we know that we would check if odd I and if it's been visited we don't want to visit it but there's actually another case if it's been visited and the odd value is equal to the node that we just came from these two nodes are adjacent and they have the same value for odd that means we found a contradiction at this point we should immediately return false so that's exactly what we do here and we only want this to actually execute if this node has not been visited so we do need to add an else here and not just an else probably an else if to say uh not odd of this node it hasn't been visited so then we're going to add it to the queue and give it a value and let me fix that now if we never return false from here we should go ahead and just return true and that is pretty much the BFS and being able to detect nodes with the same color slash odd value which I'm calling it and at this point I kind of regret not using Color you can do whatever is more simple for you I thought being explicit about the fact that these are alternating would be easier to understand but maybe that's not the case and I actually just realized over here we're always initializing this that's not the node that we want to check if it's not null or this is the node that has been visited already it's the neighbor that we want to check and I think we actually don't even need this line because it's a bit redundant this part would only be true if a node had been visited already so actually I'm just going to go ahead and get rid of that part of the code and just leave this as it is and I see the same exact bug down here of course this node is always going to be visited so we would never even append so here let's change that to the neighbor we want to make sure the neighbor is not visited and then we can go ahead and Traverse the neighbor so now let's run this to make sure that it works and as you can see yes it does if you found this helpful please like And subscribe if you're preparing for coding interviews check out neatcode.io it has a ton of free resources to help you prepare thanks for watching and I'll see you soon