Differences
This shows you the differences between two versions of the page.
| Both sides previous revisionPrevious revision | |||
| courses:cs211:winter2018:journals:holmesr:section_3.4 [2018/02/06 03:55] – holmesr | courses:cs211:winter2018:journals:holmesr:section_3.4 [2018/02/06 03:57] (current) – holmesr | ||
|---|---|---|---|
| Line 4: | Line 4: | ||
| This lays down the basis for a very easy addition to be made to the BSF algorithm that will help determine whether a graph is bipartite or not. Simply add an array of size n called Partition and assign all the nodes //n// in an odd layer to be Partition[n] = X and all the nodes in even layers to be Partition[n] = Y. If any edge has both ends being Partition[n] = X or Partition[n] = Y, then the graph is bipartite. Since this all occurs in constant time, it does not bump up the O(n+m) running time of BFS. | This lays down the basis for a very easy addition to be made to the BSF algorithm that will help determine whether a graph is bipartite or not. Simply add an array of size n called Partition and assign all the nodes //n// in an odd layer to be Partition[n] = X and all the nodes in even layers to be Partition[n] = Y. If any edge has both ends being Partition[n] = X or Partition[n] = Y, then the graph is bipartite. Since this all occurs in constant time, it does not bump up the O(n+m) running time of BFS. | ||
| + | |||
| + | This section was fascinating in that it demonstrated that determining bipartiteness of a graph is reliant on the same algorithmic skeleton as the BFS algorithm. | ||
