CODEWITHSUNDEEP
python-3.xgraphfindgeometry
8324
8324

Reputation: 66

Finding a circle in an undirected graph

I wrote a small function which should find a circle in a given (undiricted) graph and returns true if it finds a circle, false if not.

def dfs(v,last):
    if vis[v] == True:
        return True
    vis[v] = True
    c = False
    for el in adj[v]:
         if el == last:
             adj[v].remove(el)
         else:
             c = c or dfs(el,v)
    return c

The adjacencylist is a dict looks like this:adj ={1: [2], 2: [1,3], 3: [2]}. The other dictionary is to check if the knot has been visited or not. vis = {1: False, 2: False, 3: False} The problem i have is that it seemed to work for the given list in the example but for others it gives me a false result (for example: adj = {1: [2,4], 2: [1,5], 4: [1,5], 5:[2,4]} Can you help me with the issue or tell me how to find a better way for this problem. I don't want to import any other moduls.

Upvotes: 1

Views: 1744

Answers (1)

cleros
cleros

Reputation: 4343

The problem was in the remove-statement. Try the following:

def dfs(v,last):
    if v in vis:
        return True
    vis.append(v)
    c = False
    current_adj_list = list(adj[v])
    for el in current_adj_list:
        if el == last:
            adj[el].remove(v)
        else:
            c = c or dfs(el,v)
    return c

adj = {1: [2,4], 2:[1,5,4], 4: [1,2], 5: [2]}
vis = []

print(dfs(1,None))

Explanation: You were deleting the edge from the currently visiting node to it's successor's. In the loop you were therefore deleting the same element over and over again from the same list. However, you really want to delete the edges from the successors. Therefore, 

adj[v].remove(el)

became

adj[el].remove(v)

Secondly, we need to copy the adjacency list with 

current_adj_list = list(adj[v])

because we edit the list deeper in the recursion, changing the order of elements, and thereby (possibly) ruining the loop in a higher recursion level.

Upvotes: 2

Related Questions