How can I allow the user to add edges between nodes?

Question

I have the following code which I used from this websites: https://www.geeksforgeeks.org/depth-first-search-or-dfs-for-a-graph/

What I'm supposed to do is allow the user to add edges between nodes.

from collections import defaultdict
import time

class Graph:

    def __init__(self):

        self.graph = defaultdict(list)

    def addEdge(self,u,v):
        self.graph[u].append(v)

    def DFSUtil(self,v,visited):

        visited[v]= True
        print (v)

        for i in self.graph[v]:
            if visited[i] == False:
                self.DFSUtil(i, visited)


    def DFS(self, v):

        visited = [False]*(len(self.graph))

        self.DFSUtil(v,visited)

g = Graph()

# My way of adding edges - 
v = int(input("Enter a number for v: "))
w = int(input("Enter a number for W: "))
g.addEdge(v, w)
v = int(input("Enter a number for v: "))
w = int(input("Enter a number for w: "))
g.addEdge(v, w)
v = int(input("Enter a number for v: "))
w = int(input("Enter a number for w: "))
g.addEdge(v, w)
v = int(input("Enter a number for v: "))
w = int(input("Enter a number for w: "))
g.addEdge(v, w)
v = int(input("Enter a number for v: "))
w = int(input("Enter a number for w: "))
g.addEdge(v, w)
v = int(input("Enter a number for v: "))
w = int(input("Enter a number for w: "))
g.addEdge(v, w)

# Original way of adding edges - 
# g.addEdge(0, 1)
# g.addEdge(0, 2)
# g.addEdge(1, 2)
# g.addEdge(2, 0)
# g.addEdge(2, 3)
# g.addEdge(3, 3)


print ("Following is Depth First Traversal" " (starting from vertex 2)")

g.DFS(2)

In the code I added comments for the way I did it and the original way.

Here is where I run into the problem:

In the way I did it: I let the user input the edges. However, when I run it using different numbers, it either searches one number or says that index is out of range.

I've been trying to solve this for two days now and I have no luck. Any help is appreciated!

Answer 1

The DFS method is creating a list whose length is the same as the number of non-leaf nodes in your graph, which I'll call N, then the DFSUtil method is indexing it by node number. This will only work if every node is numbered between 0 and N-1. If your users are going to be entering arbitrary numbers (which users generally will), then it would be safer to make visited a dictionary in DFS:

visited = {}
for parent in self.graph:
    visited[parent] = False
    for child in self.graph[parent]:
        visited[child] = False