Detect Simple Graph Circle

Detect Simple Graph Circle

from collections import deque

# graph - adjacency - list
def bfs(s, graph):
    queue = deque()
    visited = []

    queue.append((s, s))

    while queue:
        u, v = queue.popleft()  # v is discovered by u
        visited.append(v)

        adj_list = graph[v]
        print v, ':', 'adj_list:', adj_list

        for node in adj_list:
            # check if there is a circle 
            # v's adjacent nodes already in visited set & the adjacent node is not the one that discovers current node)
            if node in visited and u != node:
                print 'circle detected! ', str(v) + ' -> ' + str(node)
                return

            if node not in visited:
                queue.append((v, node))  # node is discorvered by v


# has circle
graph1 = {}
graph1[1] = [2]
graph1[2] = [1, 3]
graph1[3] = [2, 4]
graph1[4] = [3, 5, 8]
graph1[5] = [4, 6, 7, 8]
graph1[6] = [5, 7]
graph1[7] = [5, 6, 8]
graph1[8] = [4, 5, 7]

# has circle
graph2 = {}
graph2[1] = [2]
graph2[2] = [1, 3]
graph2[3] = [2, 4, 6]
graph2[4] = [3, 5]
graph2[5] = [4, 6]
graph2[6] = [3, 5]

# no circle
graph3 = {}
graph3[1] = [2]
graph3[2] = [1, 3]
graph3[3] = [2, 4, 5]
graph3[4] = [3]
graph3[5] = [3]

bfs(1, graph2)