如何允许用户在节点之间添加边？

Question

我从该网站使用了以下代码： https://www.geeksforgeeks.org/depth-first-search-or-dfs-for-a-graph/

我应该做的是允许用户在节点之间添加边。

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)

在代码中，我为我的做法和原始方式添加了注释。

这是我运行遇到的问题：

我的做法是：让用户输入边缘。但是，当我运行它使用不同的数字时，它要么搜索一个数字，要么说索引超出范围。

我已经尝试解决这个问题两天了，但我没有运气。任何帮助表示赞赏！

Answer 1

DFS 方法正在创建一个列表，其长度与图中的非叶节点数相同，我将其称为 N，然后 DFSUtil 方法通过节点号对其进行索引。只有当每个节点的编号都在 0 到 N-1 之间时，这才有效。如果您的用户要输入任意数字（用户通常会输入），那么在 DFS 中将 visited 设为字典会更安全：

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

如何允许用户在节点之间添加边？

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

python-3.x

nodes

graph-theory

vertices

edges