CODEWITHSUNDEEP
pythongraph
Clem
Clem

Reputation: 23

Missing node in the output of my Depth-First Search

graph = {}

def dfs(graph, node, visited):
    if node not in visited:
        visited.append(node)
        for n in graph[node]:
            dfs(graph,n, visited)
    return visited

n = int(input())
drinks = [d for d in input().split()]
m = int(input())
obs = []
for _ in range(m):
    di, dj = input().split()
    obs += [(di, dj)]

for drink in drinks:
    graph[drink] = []

for drink1, drink2 in obs:
    graph[drink1].append(drink2)
    
order = dfs(graph,drinks[0], [])
print(order)

Hi guys!

I'm supposed to input a certain amount of drinks and their names. After that I would have to input the number of combinations and the combinations which pratically serve as the vertices for the graph

Sample input would be:

7
A B C D E F G
12
A B
A C
A D
B D
B E
C F
D C
D F
E D
G D
G E
G F

The problem is my output is ['A', 'B', 'D', 'C', 'F', 'E']. It's missing 'G' and is not one of the three possible outputs ['A','B','G','E','D','C','F'], ['A','G','B','E','D','C','F'], or ['G','A','B','E' ,'D','C','F']. I have no clue why

Upvotes: 2

Views: 149

Answers (2)

Jay Mody
Jay Mody

Reputation: 4033

The graph you've constructed is a directed graph, in which case, no other nodes ever point to node G. This means G is unreachable by DFS unless DFS is started at G itself. Here's an illustration of the graph:

enter image description here

If you're intent was to use an undirected graph, you can fix this behaviour by changing the loop where the edges are added to the graph:

for drink1, drink2 in obs:
    graph[drink1].append(drink2)
    graph[drink2].append(drink1)

In this case, you'll build the following undirected graph (notice the absence of arrows):enter image description here

Finally, you should probably change your dfs function to use a set instead of a list to keep track of the visited nodes, since checking if an element is contained in a list takes O(n) time while for a set it takes O(1) time:

def dfs(graph, node):
    visited = set()
    if node not in visited:
        visited.add(node)
        for n in graph[node]:
            dfs(graph, n)
    return list(visited)

Upvotes: 2

Frankie
Frankie

Reputation: 48

The issue is with the way you are creating your graph.

The resulting data structure looks like this:

{'A': ['B', 'C', 'D'], 'B': ['D', 'E'], 'C': ['F'], 'D': ['C', 'F'], 'E': ['D'], 'F': [], 'G': ['D', 'E', 'F']}

As you can see, G does not appear in any of the lists (i.e. there are no paths to it). If this is a directed Graph, then it is correct, and there is simply no path to G. However, if each branch can be traveled along in both directions then you have an issue.

Upvotes: 1

Related Questions