크루스컬 사이클을 해결하는 좋은 아이디어 없을까요

ㅁㅁㅁㅁ(211.213) 2010.11.05 23:22:56

조회 52 추천 0 댓글 0

물론 유니온파인드는 알고 있습니다

그런데 제가 만든 형태의 크루스컬로는 유니온파인드를 적용시키기가 참 어렵더군요

소스 안보고 알고리즘만 생각하면서 짜본 소스구성인데요

int e[100] = { }; //모든 공간에 다 0이 들어갑니다

e[c] = i;

여기에서 c는 가중치...결국 간선비용입니다 그리고 i는 정점의 이름이라고 할 수 있겠지요..숫자로 되어있습니다

한마디로 가중치값 위치에 정점의 이름을 넣는거지요...숫자의 형태니까 충분히 가능하죠?

결국 모든 정점을 입력받으면 가중치가 작은값부터 왼쪽에서 오른쪽으로 정점들이 정렬될겁니다

출력은 (0, 1) (3, 4) 이런식으로 나옵니다(좌표라고 칭하겠습니다)

가중치의 값 자체는 출력에 필요없습니다 총 합이라던지 이런건 ...

여튼 이런 구성으로 크루스컬을 만들 수 있었습니다만 역시 사이클을 해결하진 못했습니다

그래서 사이클을 해결하려고 사이클되는 좌표의 특징을 알아보고 그걸 집어내자고 생각했습니다

잘 보니까 사이클되는 좌표, 그 두 숫자들은 모두 같은라인(앞서 나온 좌표들중 오른쪽이냐 왼쪽이냐의 라인입니다)에서 둘다 한번식 나온 경우였습니다

그래서 저는 크루스컬을 한번 돌릴때마다 새로운 두 배열에 각각의 라인의 수들을 순서대로 넣습니다

그리고 돌때마다 마지막으로 나온 출력값 두개(좌표겠지요?)를 앞서 넣었던 수들과 비교해서 하나가 같은게 있으면 나머지 하나도 그 라인에서 같은게 있는지 없는지 검사하고 같은게 나오면 출력을 안하도록 조건을 짜넣었습니다

그런데 나중에 보니까 그런 특징이 사이클이 발생되는 경우에 분명히 나타나지만

사이클이 아닌경우에도 그런 특징이 나타나는 경우도 있었다는걸 알게 됬습니다 ㅜㅜ

결국 제가 만든 사이클 테스트 소스는 삭제되었지요

혹시 이런 방법으로 크루스컬 알고리즘을 구현할때 사이클을 해결하는 요령이랄까요.. 좋은 아이디어 있으신분 댓글좀 부탁드립니다 ㅜ

고정닉 0

전체 댓글 0개

등록순

본문 보기

타인의 권리를 침해하거나 명예를 훼손하는 댓글은 운영원칙 및 관련 법률에 제재를 받을 수 있습니다.
Shift+Enter 키를 동시에 누르면 줄바꿈이 됩니다.

갤러리 리스트
번호	제목	글쓴이	작성일	조회	추천
설문	연예인 안됐으면 어쩔 뻔, 누가 봐도 천상 연예인은?	운영자	24/06/17	-	-
230616	오늘 연봉계약했는데....... [4]	호비뉴	11.01.13	262	0
230615	프겔년들아 나 고퀄짤 만들었는데 평가좀 [3]	jaweb	11.01.13	172	0
230614	이미지 프로세싱....	[성대아싸]	11.01.13	84	0
230613	증권사 api 걍 엑셀로 하세영 [3]	[성대아싸]	11.01.13	994	0
230612	나 상담하러왔음 살려주셈 [7]	BTS(임시)(58.145)	11.01.13	117	0
230611	주갤 11이 얘기가 나와서 말인데 [3]	^^(112.221)	11.01.13	243	0
230610	프갤 눈팅 2개월차 인데요 욕하지 마시고 답변좀.... [15]	늅늅잉(59.10)	11.01.13	159	0
230609	자바 책 추천하나만 부탁드립니다. [3]	ㅇㅇ(119.70)	11.01.13	243	0
230607	특정 프로그렘 사용못하게하는방법..아는횽들없어요? [5]	헛개미\'ㅅ\'	11.01.13	84	0
230605	혹시 FERET DB 가지고 있는 형들 없음?	ShuRA	11.01.13	113	0
230604	오호.. 증권회사들이 api를 제공해? [2]	White_Wolf	11.01.13	177	0
230603	2.E+00 출력 [9]	잡아(118.34)	11.01.13	115	0
230602	무게타 알아요? [3]	무게타(211.211)	11.01.13	133	0
230601	훃들아 밥은 먹고해? [18]	해일리	11.01.13	145	0
230600	님들아 나 좆초본데 존나 아무것도모르겟다.. [12]	ㅁㅁ(116.126)	11.01.13	205	0
230599	vm웨어로 우분투 깔았는데 [1]	할리의본링	11.01.13	115	0
230598	아...공부를 하자 [3]	뇌자알	11.01.13	101	0
230597	안보이내요.. 분명히 어디서봤는데 [2]	헛개미\'ㅅ\'	11.01.13	101	0
230596	vc++ 6이랑 vc++ 2010 차이... [13]	ㅁㅁ(116.126)	11.01.13	317	0
230594	프로그래밍 백날해봐라 얼굴이 잘생겨야 이쁜여자를 만나는거야.. [4]	주방아가씨	11.01.13	253	0
230593	어떻하지? [3]	nRESET	11.01.13	75	0
230591	이쁜 여자..? [3]	아스트랄닭(112.216)	11.01.13	170	0
230590	횽들 물체 중심 좌표 찾는 C++코드좀 알려줘 ㅠㅠ [4]	영영상상(115.145)	11.01.13	635	0
230588	C: A Reference Manual 5판 PDF 파일로 도나요? [2]	C언어(180.227)	11.01.13	95	0
230587	다른 프로그렘과 연관시켜서 움직이는 프로그렘을만들려면 [9]	헛개미\'ㅅ\'	11.01.13	146	0
230586	VS2008 첨써보데 중괄호 어떻게 하면 보기좋게만듬? , [8]	^^(112.221)	11.01.13	133	0
230585	안드로이드 카메라 소스 뭐가 문제인지좀 [1]	123(112.223)	11.01.13	572	0
230582	올바른 코딩? [3]	ㄹㅇㄴ(210.178)	11.01.13	146	0
230581	치킨은 원래 서민들의 것이었다 [1]	분당살람	11.01.13	144	0
230579	그래프 그리는 방법 질문있어요 [6]	연애	11.01.13	148	0
230578	나 태어나서 최초로 여자한테 폰번호 따는꿈꿧음... [4]	꿀레	11.01.13	250	0
230577	담당 아저씨가 개발을 너무 모르니 답답하다. [1]	천회장(211.45)	11.01.13	112	0
230576	형들 리눅스 깔려고 하는데 버전 추천점 [5]	할리의본링	11.01.13	139	0
230575	IT 그만두면 하게되는 일들 [5]	2417(211.232)	11.01.13	291	0
230574	횽들 차조심해.. [2]	LazyGyu	11.01.13	95	0
230573	안녕 얘들아 내가 왔어. 이런 프로그램은 어떻게 구현해? [4]	Java늅늅E(175.199)	11.01.13	131	0
230572	Novelextra 구할수 잇는횽아들제발	횽아들제발(122.35)	11.01.13	166	0
230570	질문있습니다. [5]	우분투짱(168.156)	11.01.13	87	0
230569	JAVA 로 CAS 기반의 lock-free list 구현 왜 해? [9]	앗쌀(175.197)	11.01.13	502	0
230568	[성대아싸]님 [4]	Mayu	11.01.13	162	0
230567	이틀 안들어 왔더니 존나 오래된거같네 [5]	elwlwlwk	11.01.13	114	0
230566	정규식이횽 다익히는데 얼마나 걸려? [6]	Mayu	11.01.13	96	0
230565	MemoryPool 말임 [12]	카디군	11.01.13	185	0
230564	바람의나라핵 보는데 웃겨 죽겠다 ㅋㅋㅋㅋ [2]	파돌이(124.54)	11.01.13	563	0
230560	미안. 소리지르고 싶은데 와 세상 그 어디다가도 말을 못하겠네. [1]	DCode(121.140)	11.01.13	122	0
230557	어휴 컴터 가까스로 조립 ㅎㄷㄷㄷ [5]	[성대아싸]	11.01.13	198	0
230556	윈도우 7 정품 사서 쓰면 병신임? 여러가지 질문좀 [10]	wonC	11.01.13	281	0
230555	토목과님 꼭 전과하세요 [1]	농농이랑마군	11.01.13	97	0
230554	쳇, 나 없는 사이에 재밌는 놈이 왔다갔군.... [1]	땡칠도사	11.01.13	116	0
230553	으흠.. 고생하고있는 파이썬 코드 다 올려버리겠음.. 횽들 ㅋㅋ [8]	파이썬입문(211.110)	11.01.13	169	0