그래프에서 버텍스의 도달 가능한 버텍스 찾기

Question

내 코드에서 그래프의 도달 가능한 버텍스를 계산하는 데 문제가 있습니다.

는 I는 I가 자신과 B로 에지를 갖는다 따라서 1 정점 다음 방법

a = Vertices() 
a.Reachable = [1,2] 
b = Vertices() 
b.Reachable = [3] 
c = Vertices() 
c.Reachable= [3] 
List = [] 
List.append(a) 
List.append(b) 
List.append(c) 

의 그래프를 작성 그래프

class Vertices(): 
    number = 0 
    def __init__(self): 
     Vertices.number += 1 
     self.number = Vertices.number 
     self.Reachable= [] 

다음 코드를 갖는다. b와 c의 경우도 마찬가지입니다.

이 목록에 도달하는 우리는 정점 목록의 예를 사용하여 그래프 주위를 이동할 수 있습니다 [트랜스-1] 트랜스은이 그래프에서 지금 Reachable list of a (List[0] and List[1])

을 의미 어디 각각의 정점, 즉에 대한 접근 가능성을 계산해야 예를 들어, a, b, c에 도달 할 수 있습니다.

나는 모든 목록에서 깊이 우선 검색을 수행 할 수 있다고 읽었습니다. 계속 진행하는 방법에 대한 해결책을 제게 제공해 줄 수 있습니까?

누구나 세트를 사용하는 방법을 말해 줄 수 있습니까?이 문제와 관련된 조합 및 차이 기능이 있다는 것을 알기에 이상적이라고 생각합니다. 추신 : 이것은 학교 기반 과제가 아닙니다. ....

Answer 1

어떻게 문제 well-known solution 사용에 대한?

먼저 그래프의 데이터 구조가 필요합니다. 각 정점이 키로 표시되고 도달 가능한 정점이 목록 값인 목록 사전으로이 작업을 수행 할 수 있습니다.

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

될 것이다주기없이 모든 경로를 찾는 (같은 사이트에서) 단지

neighbours_of_B = graph['B'] 

을 것 B의 이웃 정점을 발견, 위의 그림과 같이 당신은 당신의 그래프를 나타낼 경우

def find_all_paths(graph, start, end, path=[]): 
    path = path + [start] 
    if start == end: 
     return [path] 
    if not graph.has_key(start): 
     return [] 
    paths = [] 
    for node in graph[start]: 
     if node not in path: 
      newpaths = find_all_paths(graph, node, end, path) 
      for newpath in newpaths: 
       paths.append(newpath) 
    return paths 

과로 실행 :

find_all_paths(graph, 'A', 'D') 

희망은 도움이됩니다. 위 링크에서 자세한 내용을 읽어보십시오.

Answer 2

NetworkX 또는 다른 그래프 라이브러리를 사용하지 않는 이유는 무엇입니까?

현재 표시가 작동하지 않습니다. 어떤 함수가 숫자 2에서 버텍스 b으로 어떻게 이동해야합니까? 번호가 아니라 실제 객체를 추가해야합니다.

당신이 이런 일을 할 수있는 한 후 :

def reachable(start): 
    # the set of reachable nodes 
    reachable = set() 

    # recursive function to add all reachable nodes to `reachable` 
    def finder(node): 
     reachable.add(node.) 
     for other in node.Reachable: 
      finder(other) 

    # add everything we can reach from here 
    finder(start) 
    return reachable 

Answer 3

글쎄 우선은 Vertex이 아니고 Vertice이 아닙니다. 두 번째로 그래프의 데이터 구조로 adjacency list을 (거의) 구현했습니다. adjacency matrix을 사용하는 것이 더 표준적일 것입니다.

무엇이 depth-first search인지 아십니까? 대략적으로, 정점에서 시작하여 이웃을 선택하고 이웃을 선택하는 등의 작업을 수행 할 때까지 이웃을 선택해야합니다. 그런 다음 뒤로 건너 뛰고 다음 이웃을 선택합니다. 문제가 쉽게 작은 조각으로 분리 될 수 있기 때문에 재귀 적으로 우아하게 구현됩니다. 그래프 깊이를 검색하려면 먼저 모든 버텍스에서 시작한 다음 모든 이웃에서 깊이 우선 검색을 시작합니다. 회전.

구체적으로 문제를 작은 문제로 해결해야합니다. b과 c에서 연결할 수있는 노드를 찾을 수 있다고 가정합니다. a에서 무엇을 얻을 수 있습니까? 음, b, 모든 것이 b, c에서 가능하며 모든 것이 c에 도달 할 수 있습니다.