Graph Search Algorithms (Python Code)

 Graph Algorithm Code for YT Videos

Detect Cycle in Graph

Code Explanation :

https://www.youtube.com/watch?v=yaJ6FgyoXCw&t=225s

• For UnDirected Graph

adj_list = {
    "A" : ["C", "B", "D"],
    "B" : ["A", "D"],
    "C" : ["A"],
    "D" : ["A","B" "E"],
    "E" : ["D"]
}

color = {}
parent = {}

for u in adj_list.keys():
    color[u] = 'W'
    parent[u] = None

def dfs(u, color, parent):
    color[u] = 'G'
    for v in adj_list[u]:
        if color[v] == 'W':
            parent[v] = u
            cycle = dfs(v, color, parent)
            if cycle == True:
                return True
        elif color[v] == "G" and parent[u]!=v:
            print ("Cycle found", u, v)
            return True
    color[u] = "B"
    return False

is_cyclic = False
for u in adj_list.keys():
    if color[u] == 'W':
        is_cyclic = dfs(u, color, parent)
        if is_cyclic == True:
            break
print ("Is_cyclic ", is_cyclic)

For Directed Graph

adj_list = {
    "A" : ["C", "B"],
    "B" : ["D"],
    "C" : [],
    "D" : ["A", "E"],
    "E" : []
}

color = {}
parent = {}

for u in adj_list.keys():
    color[u] = 'W'
    parent[u] = None
              
def dfs(u, color):
    color[u] = 'G'
    print (u)
    for v in adj_list[u]:
        if color[v]=='W':
            cycle = dfs(v, color)
            if cycle:
                return True
        elif color[v]=='G': # cycle is present
            print (u, v)
            return True
    color[u] = 'B'
    return False

is_cyclic = False
for u in adj_list.keys():
    if color[u] == 'W':
        is_cyclic = dfs(u, color)
        if is_cyclic:
            break
print ("Is cyclic " ,is_cyclic)
>> True