CODEWITHSUNDEEP
pythonbreadth-first-search
A. Radek Martinez
A. Radek Martinez

Reputation: 235

Cycle Detection in Graph Implementation in Python

I am trying to implement a cycle dector in python. Essentially, the algorithm applies a BFS and labels each node as either -1 (not visited) 0 (in working) or 1 (visited). My algorithm scans neighbours, and if a neighbour has a 0 status then a cycle has been detected.

# this is a non-directed graph in nature
graph = {
    'A': ['B', 'C'],
    'B': ['D', 'E'],
    'C': [],
    'D': ['B', 'E'],
    'E': ['B', 'D']
}

# 1 means visited 0 means in queue and -1 means not touched yet

status = {node: -1 for node in graph}

start = 'A'
queue = [start]
cycle = False
    
def traversal(graph): 
    start = queue.pop(-1)
    for node in graph[start]:
        if status[node] == -1:
            queue.append(node)
            status[node] = 0
        if status[node] == 0:
            cycle = True
    if queue:
        status[start] = 1
        traversal(graph)

traversal(graph)
print(cycle)

I can not seem to find the issue with the code. Could someone point it out?

Upvotes: 1

Views: 352

Answers (1)

Jan Stránský
Jan Stránský

Reputation: 1691

Inside your traversal function, the cycle variable is local. So

cycle = True

sets a local variable cycle to True, having no effect on global cycle variable.

Either return the value from your function

def traversal(graph): 
    cycle = False
    ... # the original function
    return cycle

cycle = traversal(graph)
print(cycle)

or mark the cycle variable as global

cycle = False # global variable here
def traversal(graph): 
    global cycle
    ... # the original function

traversal(graph)
print(cycle)

Upvotes: 2

Related Questions