익스트라 첫 번째 노드는

Question

내가 C에서 익스트라 프로그램을 구현하고있어 ++ 나는 몇 가지 문제가 있어요, 내가 설명하자 방문 코드는 소스에서 다른 모든 정점으로 전체 경로를 인쇄합니다. 배열을 사용하고 있습니다. int parent [num_vertexs]; 경로를 저장합니다. 그러나 문제는 전체 경로를 원하지 않는다는 것입니다. 첫 번째 꼭지점 만 방문했습니다.

첫 번째 노드 만 어떻게 방문 할 수 있습니까? 각 노드에 대해 상위 배열의 첫 번째 노드 만 인쇄하는 방법이 있습니까?

감사합니다.

편집 : 원본 정점에서 다른 모든 정점까지의 전체 경로를 포함하는 상위 배열을 인쇄하는 기능을 보여 드리겠습니다.

void printPath(int parent[], int j){ 
// Base Case : If j is source 
if (parent[j]==-1) 
    return; 

printPath(parent, parent[j]); 

printf("%d ", j); 

}

이 기능은 전체 경로를 인쇄,하지만 난 단지 경로의 첫 번째 정점을 원한다. 문제는 printf 명령이 전체 경로를 인쇄하기 때문에 각 꼭지점의 첫 번째 행만 인쇄하는 방법을 모른다는 것입니다. 어떻게 할 수 있니? 고맙습니다!

Answer 1

이 함수는 재귀 적입니다. 그것은 마지막 정점을 제외한 모든 경로를 출력하기 위해 자신을 호출 한 다음 마지막 정점을 인쇄합니다. 첫 번째 정점을 인쇄로 제한하는 간단한 원유 방법은 나머지 제외하는 것입니다 : 더 좋은 방법은 반복적으로 재귀의 코드를 변경하는 것입니다

void printFirstStep(int parent[], int j){ 
    // Base Case : If j is source 
    if (parent[j]==-1) 
    return; 

    printFirstStep(parent, parent[j]); 

    if (parent[parent[j]]==-1) 
    printf("%d ", j); 
} 

을 (즉, 비 재귀) :

void printFirstStep(int parent[], int j){ 
    // Base Case : If j is source 
    if (parent[j]==-1) 
    return; 

    while(parent[parent[j]] != -1) 
    j = parent[j]; 

    printf("%d ", j); 
} 

은 (그것은 당신이 재귀을 이해 귀하의 질문에서 명확하지 않다. 당신에게 더 좋은하지 않을 것이다 코드로 붙여 넣기, 그렇게하지 않으면 이 이러한 기능을 이해할 수 있습니다.)