방향 그래프의 에지 목록이 있고 n개의 노드가 있고 노드 이름이 0에서 n-1이라고 가정합니다. 또한 두 개의 정수 값 a와 b가 있습니다. c에서 b로 갈 수 있는 노드 c가 있는지 확인해야 합니다.
따라서 입력이 다음과 같으면
그리고 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