Как я могу позволить пользователю добавлять ребра между узлами? - PullRequest
Новая
       91

Как я могу позволить пользователю добавлять ребра между узлами?

0 голосов
/ 07 декабря 2018

У меня есть следующий код, который я использовал с этих сайтов: 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)

В коде я добавил комментарии о том, как я это сделал, и оригинальном способе.

Вот где я столкнулся с проблемой:

Как я это сделал: я позволил пользователю вводить края.Однако, когда я запускаю его, используя разные числа, он либо ищет один номер, либо говорит, что индекс находится вне диапазона.

Я пытался решить эту проблему уже два дня, и мне не повезло.Любая помощь приветствуется!

1 Ответ

0 голосов
/ 07 декабря 2018

Метод DFS создает список, длина которого равна количеству неконечных узлов в вашем графике, который я назову N, затем метод DFSUtil индексирует его по номеру узла.Это будет работать, только если каждый узел пронумерован от 0 до N-1.Если ваши пользователи будут вводить произвольные числа (что обычно делают пользователи), то было бы безопаснее сделать посещаемый словарь в DFS: 

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