이 Q & A 흐름의 최단 경로와 최장 경로를 어떻게 계산할 수 있습니까?</p> <p><img src="https://i.stack.imgur.com/vBygD.png" alt="enter image description here"></p> <p>기본적인 아이디어는 질문에 대해 선택한 답변에 따라 다른 질문은 다음 질문 할 것입니다 :

Question

이 나는 ​​Q & 다음과 같은 흐름이있다.

나는 현재이 Q & 다음과 같은 자바 스크립트 객체와 흐름 표현하고있다 :

var QAndAObj = { 
    1: { 
    question: 'Question 1', 
    answers: [ 
     { 
     answerText: 'Answer 1-1', 
     nextQuestion: 2 
     }, 
     { 
     answerText: 'Answer 1-2', 
     nextQuestion: 3 
     } 
    ] 
    }, 
    2: { 
    question: 'Question 2', 
    answers: [ 
     { 
     answerText: 'Answer 2-1', 
     nextQuestion: 3 
     }, 
     { 
     answerText: 'Answer 2-2', 
     nextQuestion: null 
     } 
    ] 
    }, 
    3: { 
    question: 'Question 3', 
    answers: [ 
     { 
     answerText: 'Answer 3-1', 
     nextQuestion: 4 
     }, 
     { 
     answerText: 'Answer 3-2', 
     nextQuestion: null 
     }, 
     { 
     answerText: 'Answer 3-3', 
     nextQuestion: null 
     } 
    ] 
    }, 
    4: { 
    question: 'Question 4', 
    answers: [ 
     { 
     answerText: 'Answer 4-1', 
     nextQuestion: null 
     }, 
     { 
     answerText: 'Answer 4-2', 
     nextQuestion: null 
     } 
    ] 
    } 
}; 

는 사용자에게 진행률 표시 줄을 표시하려면를, 나는 통해 길고 짧은 경로를 계산할 수 있도록하고 싶습니다 질문의 흐름.

내 초기 생각은이 흐름에 각각의 가능한 경로를 아래로 이동하려면 다음과 같은 재귀 함수를 작성했다 :

function recurse(node) { 
    for (var i = 0; i < node.answers.length; i++) { 
    if (node.answers[i].nextQuestion) { 
     recurse(QAndAObj[node.answers[i].nextQuestion]); 
    } 
    } 
} 

은 위의 기능이 나 흐름의 각 노드에 충돌 할 수 않습니다,하지만 난 흐름을 통해 가장 길고 가장 짧은 경로를 계산하는 방법을 모르겠습니다.

도움/조언/코드를 크게 높이세요.
대단히 감사합니다.

Answer 1

작동 예제를 보려면을보십시오.

function shortAndLong(QATree, startNode) { 
    var paths = []; 
    function findAllPaths(startNode, currentCost) { 
     for (var i = 0; i < startNode.answers.length; i++) { 
      var child = startNode.answers[i]; 
      if (child.nextQuestion == null) { 
       paths.push(currentCost); 
      }else { 
       findAllPaths(QATree[child.nextQuestion], currentCost+1); 
      } 
     } 
    } 
    findAllPaths(startNode, 1); 
    return [Math.min.apply(Math, paths), Math.max.apply(Math, paths)] 
} 
console.debug('ans',shortAndLong(QAndAObj, QAndAObj[1]));//returns [2, 4] 
console.debug('ans',shortAndLong(QAndAObj, QAndAObj[2]));//returns [1, 3] 
console.debug('ans',shortAndLong(QAndAObj, QAndAObj[3]));//returns [1, 2] 
console.debug('ans',shortAndLong(QAndAObj, QAndAObj[4]));//returns [1, 1] 

기본은

1. 필요한 답변의 수
2. 찾기 최대 유지, 그래프를 통해 모든 경로의 목록을 작성하고 당신이 원하는 게 어떤 형식으로