주어진 무향 그래프에서 선형 스패닝 트리의 수를 계산하십시오.

Question

온라인 코딩 사이트 중 하나의 문제를 해결하는 동안이 문제가 발생했습니다. 주어진 무향 그래프에서 선형 스패닝 트리의 수를 찾는 알고리즘이 있습니까? 예를 들어 스패닝 트리의 각 노드에 자식이 하나 이상 있어야합니다.

Answer 1

나는 하나의 라인 노드의 수를 찾아야한다고 생각한다.

 o 
    /
o-o-o 

그리고 당신은 DFS를 사용할 수있는 등 나무를 찾을 수 : 그래프가 될 것입니다 선형 스패닝 트리의

 o 
    /
o-o-o-o 
    \ \ 
    o-o-o 

그래서 한 경우 하나의 선으로 내 말은.