인접 목록 표현으로 그래프가 있다고 가정하고 2D 행렬 M을 찾아야 합니다. 여기서
-
정점 i와 j 사이에 경로가 있을 때 M[i, j] =1입니다.
-
그렇지 않으면 M[i, j] =0입니다.
따라서 입력이 다음과 같으면
그러면 출력은
| 1 | 1 | 1 | 1 | 1 |
| 0 | 1 | 1 | 1 | 1 |
| 0 | 1 | 1 | 1 | 1 |
| 0 | 1 | 1 | 1 | 1 |
| 0 | 1 | 1 | 1 | 1 |
이 문제를 해결하기 위해 다음 단계를 따릅니다. −
-
ans:=크기가 n x n인 2차원 행렬, 여기서 n은 꼭짓점의 수이며 0으로 채움
-
0에서 n 사이의 i에 대해 수행
-
q:=대기열, 처음에 i 삽입
-
q가 비어 있지 않은 동안 수행
-
node:=q의 첫 번째 요소, q에서 첫 번째 요소 삭제
-
ans[i, node]가 0이 아니면
-
다음 반복으로 이동
-
-
ans[i, 노드]:=1
-
이웃:=그래프[노드]
-
이웃의 각 n에 대해 수행
-
q 끝에 n 삽입
-
-
-
-
반환
이해를 돕기 위해 다음 구현을 살펴보겠습니다. −
예시
class Solution: def solve(self, graph): ans=[[0 for _ in graph] for _ in graph] for i in range(len(graph)): q=[i] while q: node=q.pop(0) if ans[i][node]: continue ans[i][node]=1 neighbors=graph[node] for n in neighbors: q.append(n) return ans ob = Solution() adj_list = [[1,2],[4],[4],[1,2],[3]] priunt(ob.solve(adj_list))
입력
[[1,2],[4],[4],[1,2],[3]]
출력
[[1, 1, 1, 1, 1], [0, 1, 1, 1, 1], [0, 1, 1, 1, 1], [0, 1, 1, 1, 1], [0, 1, 1, 1, 1] ]