Computer >> 컴퓨터 >  >> 프로그램 작성 >> Python

Python에서 그래프에 공통으로 연결할 수 있는 노드가 있는지 확인하는 프로그램

<시간/>

방향 그래프의 에지 목록이 있고 n개의 노드가 있고 노드 이름이 0에서 n-1이라고 가정합니다. 또한 두 개의 정수 값 a와 b가 있습니다. c에서 b로 갈 수 있는 노드 c가 있는지 확인해야 합니다.

따라서 입력이 다음과 같으면

Python에서 그래프에 공통으로 연결할 수 있는 노드가 있는지 확인하는 프로그램

그리고 a =2, b =3이면 출력은 True가 됩니다. 여기서 c =0이므로 0에서 2로, 0에서 3으로의 경로도 있습니다.

이 문제를 해결하기 위해 다음 단계를 따릅니다. −

  • DFS() 함수를 정의합니다. 그래프, 노드, 방문 횟수가 필요합니다.
  • 노드를 방문하지 않으면
    • 노드를 방문한 것으로 표시
    • 그래프[노드]의 각 x에 대해 다음을 수행합니다.
      • DFS(그래프, x, 방문)
  • 기본 방법에서 다음을 수행합니다. -
  • graph :=edge_list에서 인접 목록 생성
  • visited_a, Visited_b :=빈 세트 2개
  • DFS(그래프, 방문_a)
  • DFS(그래프, b, 방문_b)
  • ans :=Visited_b와 Visited_a의 교차점에서 가져온 새 목록
  • as가 비어 있지 않으면
    • 참 반환
  • 거짓을 반환

이해를 돕기 위해 다음 구현을 살펴보겠습니다. −

def edge_list_to_graph(edges):
   s = set()
   for x, y in edges:
      s.add(x)
      s.add(y)
   s = len(list(s))
   graph = [[] for x in range(s)]
   for x, y in edges:
      graph[y].append(x)
   return graph

def DFS(graph, node, visited):
   if node not in visited:
      visited.add(node)
      for x in graph[node]:
         DFS(graph, x, visited)

def solve(edges, a, b):
   graph = edge_list_to_graph(edges)

   visited_a, visited_b = set(), set()

   DFS(graph, a, visited_a)
   DFS(graph, b, visited_b)

   ans = list(visited_a.intersection(visited_b))
   if ans:
      return True
   return False

ed_list = [(0, 4),(4, 3),(1, 2),(0, 1),(0, 2),(1, 1)]
a = 2
b = 3
print(solve(ed_list, a, b))

입력

[(0, 4),(4, 3),(1, 2),(0, 1),(0, 2),(1, 1)], 2, 3

출력

True