두 그래프 노드 사이의 고정 길이 경로

Question

그래프에 두 개의 노드가있는 경우 지정된 홉 수 사이의 경로를 찾으려는 알고리즘이 있습니까? 모든 노드는 다른 노드에 연결할 수 있습니다.

현재 시점은 2D 공간에 위치하므로 그래프가 최상의 접근 방식인지는 확실하지 않습니다.

Answer 1

노드가 홉을 기준으로 경로를 찾고자한다면 그래프가 적합한 방법 일 것입니다. 나는 당신이 무엇을하려고하는지, 제약 조건이 무엇인지를 잘 모르겠다. 특히, "Any Node는 다른 어떤 노드에도 연결될 수있다."와 관련해서는 약간 열려있다.

그러나 무시하면;

첫 번째 노드에서 시작하여 깊이 우선 검색을하고 (a) 찍은 홉이 지정한 숫자보다 크거나 (b) 우리가 가지고있는 홉이있는 경우 검색을 종료하는 것처럼 보입니다. 두 번째 노드에 도착했다. 이것은 두 개의 노드를 (최대로) 많은 홉으로 연결하는 첫 번째 (뿐만 아니라) 경로를 결정합니다.

정확하게 지정된 홉이어야한다면 홉이 끝나면 검색의 분기를 종료하고 두 번째 노드에도 도착한 경우 성공으로 종료하십시오.

Answer 2

iterated-deepening DFS을 사용해 보셨습니까?

Answer 3

멍청한 접근 : (데이터 구조는 스택의 배열 임). 기본적으로 Breadth First Search (BFS)를 깊이 N으로하고 있습니다. 단, 루프가 허용되는 경우 (명확히하지는 않았지만 가정했다고 가정), 방문한 노드를 추가 검색에서 제외하지 않습니다. 인덱스 0 (인덱스 = 깊이) 각 레벨/인덱스

에서 어레이에 저장된 스택

1. 푸시 개시 노드 "L"0-N : 각 노드 용

   레벨 "l"에 저장된 스택, 모든 이웃을 찾아 레벨 "l + 1"에 저장된 스택으로 밀어 넣습니다.

   중요 : 작업에서 루프가있는 경로를 찾을 수 있으면 이미 추가 한 노드를 방문했는지 확인하지 마십시오. 루프를 허용하지 않는 경우 방문한 노드의 해시를 사용하여 노드를 두 번 추가하지 마십시오 **

2. "N-1"수준을 종료하면 중지하십시오.

3. 방금 ​​추가 한 모든 노드를 루프하여 인덱스 "N"에 스택하고 대상 노드를 찾으십시오. 발견 된 경우 : 성공, 그렇지 않은 경우 해당 경로가 없습니다.

에 의해 "모든 노드를 연결 할 수있다"경우에 당신이 완전히 연결 그래프를 함축되어 있습니다 후 실제로 방문 노드

과 관련이없는 수학 대답 (그러나 공식은 존재 StackOverflow의 텍스트 입력 필드에 글자를 쓸 수 없을 때)