그래프가 있다고 가정하고 소스 정점과 숫자 k도 있습니다. k는 소스에서 목적지까지의 그래프의 경로 길이이며, 소스에서 시작하여 다른 정점(목적지)에서 끝나는 단순 경로(주기 없음)를 찾을 수 있는지 확인해야 합니다. 그래프는 다음과 같습니다 -
따라서 입력이 Source =0, k =64와 같으면 0에서 7에서 1에서 2에서 8에서 6에서 5에서 3에서 4까지의 단순 경로가 존재하므로 출력은 True가 됩니다. 이 경로 길이는 총 64보다 큰 68의 거리입니다.
이 문제를 해결하기 위해 다음 단계를 따릅니다. −
-
order node x node의 adjacency matrix adj를 사용하여 그래프를 정의하고 edge cost로 채움
-
solve() 함수를 정의합니다. 소스, k, 경로가 필요합니다.
-
k <=0이면
-
참을 반환
-
-
나는 :=0
-
i는 adj[source]의 크기와 같지 않지만
-
v :=adj[소스, i, 0]
-
w :=adj[소스, i, 1]
-
나는 :=나는 + 1
-
경로[v]가 True이면
-
다음 반복으로 이동
-
-
w>=k이면
-
참을 반환
-
-
경로[v] :=참
-
solve(v, k-w, path)가 참이면
-
참을 반환
-
-
경로[v] :=거짓
-
-
거짓을 반환
-
기본 방법에서 다음을 수행하십시오 -
-
경로 :=노드와 동일한 크기 목록, 거짓 값으로 채우기
-
경로[출처] :=1
-
해결 반환(소스, k, 경로)
예
이해를 돕기 위해 다음 구현을 살펴보겠습니다. −
class Graph: def __init__(self, nodes): self.nodes = nodes self.adj = [[] for i in range(nodes)] def insert_edge(self,u, v, w): self.adj[u].append([v, w]) self.adj[v].append([u, w]) def solve(self,source, k, path): if (k <= 0): return True i = 0 while i != len(self.adj[source]): v = self.adj[source][i][0] w = self.adj[source][i][1] i += 1 if (path[v] == True): continue if (w >= k): return True path[v] = True if (self.solve(v, k-w, path)): return True path[v] = False return False def is_there_any_path(self,source, k): path = [False]*self.nodes path[source] = 1 return self.solve(source, k, path) nodes = 9 g = Graph(nodes) g.insert_edge(0, 1, 5) g.insert_edge(0, 7, 9) g.insert_edge(1, 2, 9) g.insert_edge(1, 7, 12) g.insert_edge(2, 3, 8) g.insert_edge(2, 8, 3) g.insert_edge(2, 5, 5) g.insert_edge(3, 4, 10) g.insert_edge(3, 5, 15) g.insert_edge(4, 5, 11) g.insert_edge(5, 6, 3) g.insert_edge(6, 7, 2) g.insert_edge(6, 8, 7) g.insert_edge(7, 8, 8) source = 0 k = 64 print(g.is_there_any_path(source, k))
입력
nodes = 9 g = Graph(nodes) g.insert_edge(0, 1, 5) g.insert_edge(0, 7, 9) g.insert_edge(1, 2, 9) g.insert_edge(1, 7, 12) g.insert_edge(2, 3, 8) g.insert_edge(2, 8, 3) g.insert_edge(2, 5, 5) g.insert_edge(3, 4, 10) g.insert_edge(3, 5, 15) g.insert_edge(4, 5, 11) g.insert_edge(5, 6, 3) g.insert_edge(6, 7, 2) g.insert_edge(6, 8, 7) g.insert_edge(7, 8, 8) source = 0 k = 64
출력
True