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

StackOverflow https://stackoverflow.com/questions/1603334

  •  05-07-2019
  •  | 
  •  

문제

그래프에 두 개의 노드가 주어지면 지정된 수의 홉을 가져 오는 경로를 찾는 알고리즘이 있습니까? 모든 노드는 다른 노드에 연결할 수 있습니다.

현재 포인트는 2D 공간에 위치하고 있으므로 그래프가 최선의 방법인지 확실하지 않습니다.

도움이 되었습니까?

해결책

노드가 홉 측면에서 경로를 찾으려고한다면 그래프가 올바른 접근법 일 것입니다. 나는 당신이 무엇을하려고하는지, 특히 "어떤 노드는 다른 노드에 연결될 수있다"와 관련하여 제약이 무엇인지 이해하지 못한다. 이는 약간 열린 것으로 보인다.

그러나 그것을 무시한다. 일부 그래프 표현 :

첫 번째 노드에서 시작하여 먼저 깊이 검색을 수행하고 (a) 홉이 지정된 숫자보다 크거나 (b) 두 번째 노드에 도착한 경우 검색을 종료하는 것 같습니다. 이것은 많은 홉이있는 두 노드를 (최대) 연결하는 첫 번째 (뿐만 아니라) 경로를 결정합니다.

정확히 지정된 홉이어야하는 경우 홉이 끝나면 검색의 지점을 종료하고 두 번째 노드에 도착한 경우 성공으로 끝납니다.

다른 팁

당신은 시도 했습니까? 반복적 인 DFS?

멍청한 접근 : (데이터 구조는 스택 배열입니다). 이것은 기본적으로 루프가 허용되는 경우 (명확히하지 않았지만 그것들이라고 가정 함)를 제외하고는 깊이 n에 대한 폭을 가장 먼저 검색합니다.

  1. 인덱스 0 (index = 깊이)에 배열에 저장된 스택에서 시작 노드를 푸시

  2. 각 레벨/색인 "L"0-N에 대해 :

    레벨 "L"에 저장된 스택의 각 노드에 대해 모든 이웃을 찾아 "L+1"레벨에 저장된 스택으로 밀어 넣습니다.

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

  3. "N-1"레벨을 종료하면 중지하십시오.

  4. 방금 추가 한 모든 노드를 인덱스 "N"로 스택하고 대상 노드를 찾으십시오. 발견 된 경우 : 성공하지 못한 경우 그러한 경로가 없습니다.

"모든 노드를 연결할 수있는"이라면 완전히 연결된 그래프를 암시하는 경우 실제로 방문 노드가 포함되지 않은 수학적 답이 있습니다.

(그러나 공식은 StackoverFlow의 텍스트 입력 필드에 쓸 수 없을 정도로 너무 길다)

라이센스 : CC-BY-SA ~와 함께 속성
제휴하지 않습니다 StackOverflow
scroll top