Review 4: Paths in graphs

printable version

R4: [1] [2] [3] [4] [5]

Problem R4.1

Recall the breadth-first search algorithm.

def bfs(verticessource):
    for v in verticesv.dist = INFINITY
    source.dist = 0

    q = new queue()
    while not q.isEmpty():
        u = q.remove()
        for v in u.neighbors:
            if v.dist == INFINITY:
                v.dist = u.dist + 1

A graph is said to be bipartite if the vertices can be divided into two groups, and every edge connects one group to another. Assuming we're given a graph where all vertices are reachable from each other, how can we modify our breath-first search code in order to determine whether our graph is bipartite?