모든 경로의 신장트리 구하기
리라
질문 제목 : 모든 경로의 신장 트리 구하기질문 요약 :단 한개의 신장트리가 아닌, 존재하는 모든 신장트리의 경로 혹은 개수를 구한다질문 내용 :신장트리는 보통 dfs나 bfs를 통하여 한개를 구해지는데요, 이걸 변형하여, 여러개 존재하는 모든 신장트리에 대하여 경로나 개수를 구할수 있을가요?, 보통 mst의 경우 프림이나 크루스칼을 이용하여 구하는데요,,,,, st는 dfs, bfs에 의존할수 밖에 없는 건가요?... 고수님들 부탁 드립니다!ex) 인접행렬이 아래와 같을때 (딱지모양)
0 1 1 1
1 0 1 1
1 1 0 1
1 1 1 0대략 16개 정도의 신장트리가 나오게 되고 그 모든 신장트리의 경로나 16개라는 개수를 출력 시키고 싶습니다//////////// 아래는 dsf를 실험하다 막힌 - 한개의 신장트리 출력 코드 입니다 ///////////#include stdio.h
#include stdlib.h#define m 999
#define max 4typedef struct edge {
int pair1;
int pair2;
};edge edge[max-1];int b[max] = {0};
int n = max;
int g[max][max] = {
{ 0, 1, 1, 1}, //1
{ 1, 0, 1, 1}, //2
{ 1, 1, 0, 1}, //3
{ 1, 1, 1, 0}, //4
};int s[100], ns = 0;
int i, j;
int v[max + 1]={0,};void a(int ac){ for (i=0; imax; i++){
for (j=0; jmax; j++) {
if (g[i][j] == 1) {
s[++ns] = i;
break;
}
}
if (ns == 1) break;
} while(1) {
if (s[ns] == max-1) {
for (i=1; ins; i++) printf(%d - , s[i]+1);
printf(%d\n, s[ns]);
break;
}
for (i=0; imax; i++) {
if (s[ns] == i) continue;
if (g[s[ns]][i] == 1) {
g[s[ns]][i] = 2;
g[i][s[ns]] = 2;
s[++ns] = i;
break;
}
} if (i == 7){
ns--;
if(ns == 0) break;
}
}
} int main()
{
printf(minimum spanning tree (using all algorithm)\n);
a(1);
system(pause);
}
