gounttt   7년 전

안녕하세요. 크루스칼 알고리즘을 생각한대로 코드로 짰는데 무엇이 문제인지 모르겠습니다. 

일단 순서는 다음과 같습니다. 

엣지를 추가할 때 싸이클이 생기는 것을 방지하기 위해 set배열과 list라는 링크드 리스트를 사용하는데, 

엣지를 추가할 때마다 각각의 from과 to를 집합(그룹)을 만들어 줌으로써 싸이클을 방지하도록 하였습니다. 

4 개의 케이스가 존재합니다. 순서대로 설명하겠습니다.

1. 둘 다 그룹이 없는 경우 (ex. (2 3 2), (4 5 3))

   set[2]와 set[3]을 첫 번째 컴퓨터의 번호인 2로 그룹넘버를 설정하고 list[2]->2->3 이런식으로 됩니다.

   set[4]와 set[5]를 첫 번째 컴퓨터의 번호인 4로 그룹 넘버를 설정하고 list[4]->4->5 이런식으로 됩니다.

   list[x]마다 head와 tail 포인터가 있어 head는 첫번째 vertex를, tail은 마지막 vertex를 가리키도록 합니다.

2. 하나는 그룹이 있는데 하나는 그룹이 없는 경우( ex. 1 3 3)

   set[3]이 2이고 1의 그룹 넘버가 없으므로 set[1]을 set[3]과 동일한 2로 하고 list[2]->2->3->1 이렇게 추가합니다.

3. 둘 다 그룹이 있는데 그룹 넘버가 다를경우 ( ex. 3 4 6)

  set[3]은 2, set[4]가 4이므로 그룹 넘버가 다르므로 한 쪽 그룹에서 다른 한 쪽으로 멤버를 다 옮겨줍니다.

 옮기기 전, list[2]->2->3->1, list[4]->4->5 이고 set배열은 {0,2,2,2,4,4} 이렇게 되어 있습니다.

 옮긴 후에는 list[2]는 null, list[4]->4->5->2->3->1이 되고 set 배열은 {0,4,4,4,4,4}가 됩니다. 

4. 둘 다 그룹이 있는데 그룹 넘버가 같을 경우 (ex. 2 4 8)

 set[2]와 set[4] 둘 다 4로 같으므로 둘을 연결하면 싸이클이 형성됩니다. 따라서 아무 일도 하지 않고 그다음 엣지로 넘어갑니다. 


프로그램을 돌리면 "틀렸습니다"라고 뜹니다. 그래서 답이 잘 못 되게 나오는 것 같은데, 어느 부분에서 문제가 생기는 지 

모르겠습니다. 부탁합니다. 도와주세요!! 

댓글을 작성하려면 로그인해야 합니다.