효율적으로

첫째 대한 MST 대신에, 단지 all possible spanning trees을 묻는이 질문은 하지 있음을 유의하시기 바랍니다 그래프에서 가능한 모든 스패닝 트리를 생성하는 방법.효율적으로

그래서이 하지 finding all minimal spanning trees 같은 또는 그냥 그래프에서 모든 가능한 spanning trees를 생성해야

All minimum spanning trees implementation입니다.

은 내가 무차별 방법은 바로 생각 :

한다고 가정 우리가 V 노드와 E 가장자리를 가지고있다.

그래프
의 모든 에지를 받기 E 가장자리 중 V-1의 가능한 모든 조합을 얻기.
이 조합에서 non-spanning-tree을 필터링 (스패닝 트리를 들어, V-1 가장자리 한 세트 내부의 모든 노드는 정확히 한 번만 나타납니다)

하지만 큰 그래프에 직면 할 때 너무 느린 생각합니다.

더 좋은 방법이 있습니까?

출처

2014-03-02 Jackson Tale

실제로 링크하는 알고리즘은 모든 가장자리를 설정 한 후에 작동 할 것이다. 동일한 값으로 가중치를 부여합니다. 가중치에 대한 가장 확실한 선택은 1 또는 0이지만, (존재하는 경우 오버 플로우 문제를 제외하고는) 전적으로 관련이 없습니다. –

@ G.Bach 귀하의 의견을 답변으로 변환 해 주시겠습니까? –

모든 에지의 가중치를 같은 값으로 설정 한 다음 알고리즘을 사용하여 모든 최소 스패닝 트리를 찾습니다. 모든 스패닝 트리에는 모서리가 있고 모든 모서리 가중치가 같으므로 모든 스패닝 트리는 최소 스패닝 트리가됩니다.

출처

2014-03-02 15:21:35

나는 이것이 정답이라고 생각하지만 그것은 나에게 회상한다. [수학자의 끓는 물에 관한 농담] (http://www-users.cs.york.ac.uk/susan/joke/3.htm#boil 왜냐하면 내가 아는 모든 MST 열거 알고리즘은 안전한 가장자리의 하위 그래프에있는 모든 스패닝 트리를 열거하기 때문입니다. –

@DavidEisenstat MST를 열거하는 알고리즘을 한 번도 본 적이 없으므로 블랙 박스로만 생각하면 확실한 접근 방식이 내 대답입니다. 나는 그 농담을 좋아한다. 엔지니어 나 수학자, 또는 둘 모두를 괴롭히는 지 확실하지 않습니다. 편집 : 그 웹 사이트 주셔서 감사합니다, 그 동안 잠시 웃지 않았다. –

@DavidEisenstat 더 좋은 아이디어가 있습니까? –

나는이 질문에 관심이있어 아직까지는 정말로 만족스러운 대답을 찾지 못했다. 그러나 나는 Knuth의 Algorithms S와 TAOCP Volume 4 Fascicle 4의 S '를 paper by Sorensen and Janssens, GRAYSPAN, SPSPAN 및 GRAYSPSPAN Knuth가 발견했습니다. 그것들 중 어느 것도 내가 사용할 수있는 언어로 구현되지 않았다 ... 나는이 코드를 코딩하는데 약간의 시간을 소비해야만한다고 생각한다. ...

출처

2015-08-25 04:14:34

답변

관련 문제