현재 위치

홈 ›› Forums ›› 공부 ›› 프로그래밍 QnA

Minimum Spanning Tree 와 알고리즘에 관련하여 몇몇 질문 드립니다

goldedit의 이미지
글쓴이: goldedit / 작성시간: 토, 2005/12/10 - 3:30오후

안녕하세요.
몇가지 궁금한 사항이 있어 질문 드립니다
그래프에서 Minimum Spanning Tree를 구현할수 있는 알고리즘이
어떤것이 있을까요??? 제가 알기론 프라임, 크루스칼 등등 많은것이 있는거 같은데요
어떤알고리즘을 주로 사용하는지 궁금합니다...

아 그리고 지하철 노선도 처럼 그래프의 특정 정점에서 먼 특정한 정점까지
가장 짧게 구해주는 알고리즘은 어떤것이 있는지요?

그리고 최소값과 최대값을 동시에 O(1)안에 가져오고 최소, 최대, 입력과 삭제가
모두 O(log n) 시간안에 가능한 자료구조가 있다고 들었는데
이런 자료나 정보 아시는분은 어디서 있는지...
좀 알려 주세요;;; !!!

Forums: 
프로그래밍 QnA
ssehoony의 이미지

글쓴이: ssehoony / 작성시간: 일, 2005/12/11 - 2:38오전

n : vertices
m : edges

Kruskal's algorithm : O(m log n)
Prim's algorithm : O(m + n log n)
Boruvka's algorithm : O(m log n)
A hybrid algorithm : O(m log log n)

이렇게 되네요.
당연히 이것 말고도 있겠죠? 더 효율적인지 아닌지는 모르겠지만...
뭐 그게 거기서 거기인 녀석들이라 구현하기 쉬운걸로 하면 되지 않을까요?
Boruvka's algorithm 요넘이 좀 쉬운듯 한데.
제 생각엔 저것 이상의 효율적인 알고리즘은 나오기 힘들 듯한데요.

Quote:
최소값과 최대값을 동시에 O(1)안에 가져오고 최소, 최대, 입력과 삭제가
모두 O(log n) 시간안에 가능한 자료구조가 있다고 들었는데
이런 자료나 정보 아시는분은 어디서 있는지...

이런 알고리즘을 아는 것은 아니지만
O(1) 에 검색이 된다는건 1:1 로 맵핑해서 해당 인덱스를 바로 찾아가는 방법 말고는 없지 않나요?
이건 그래프에서 MST 를 찾는 알고리즘이라기 보다는, 찾아진 MST 를 이용해서 검색을 빠르게 하기 위해 그냥 배열에 저장한 것일 듯 하군요.
그래프에서 최소 패스만을 골라낸게 MST 이고, MST만 보면 한곳에서 다른 한곳으로 가는 패스는 유일하기 때문에 최소나 최대라는 개념이 없을 듯 한데요....

혹시 저것 보다 더 좋은거 발견하시면 여기에도 남겨주세요.
저도 공부 할 수 있도록요 ^^

정태영의 이미지

글쓴이: 정태영 / 작성시간: 일, 2005/12/11 - 4:18오전

goldedit wrote:
그리고 최소값과 최대값을 동시에 O(1)안에 가져오고 최소, 최대, 입력과 삭제가
모두 O(log n) 시간안에 가능한 자료구조가 있다고 들었는데
이런 자료나 정보 아시는분은 어디서 있는지...
좀 알려 주세요;;; !!!

바이너리 트리 의 insert, delete 가 일어날 때 대상값이 최소,최대값과 연관이 있을 경우에 최소, 최대값을 다시 구해서 저장하도록 구현하면 어렵지 않게 구현할 수 있을 듯 한데요 ;)

binary search tree 의 insert, delete 는 O(log n) 의 복잡도를 가지며... 최대, 최소 값을 구하는 것도 같은 비용이니까 결국 O(log n) 으로 원하는 동작을 할 수 있겠습니다...

다만... full binary tree 가 아닐 경우엔 비용이 비싸질 수도 있으니까... 균형을 자동으로 맞춰주는 AVL 에 최대, 최소값을 저장한다!? 정도로 =3=33

오랫동안 꿈을 그리는 사람은 그 꿈을 닮아간다...

http://mytears.org ~(~_~)~
나 한줄기 바람처럼..

댓글 달기

텍스트 포맷에 대한 자세한 정보

Filtered HTML

  • 텍스트에 BBCode 태그를 사용할 수 있습니다. URL은 자동으로 링크 됩니다.
  • 사용할 수 있는 HTML 태그: <p><div><span><br><a><em><strong><del><ins><b><i><u><s><pre><code><cite><blockquote><ul><ol><li><dl><dt><dd><table><tr><td><th><thead><tbody><h1><h2><h3><h4><h5><h6><img><embed><object><param><hr>
  • 다음 태그를 이용하여 소스 코드 구문 강조를 할 수 있습니다: <code>, <blockcode>, <apache>, <applescript>, <autoconf>, <awk>, <bash>, <c>, <cpp>, <css>, <diff>, <drupal5>, <drupal6>, <gdb>, <html>, <html5>, <java>, <javascript>, <ldif>, <lua>, <make>, <mysql>, <perl>, <perl6>, <php>, <pgsql>, <proftpd>, <python>, <reg>, <spec>, <ruby>. 지원하는 태그 형식: <foo>, [foo].
  • web 주소와/이메일 주소를 클릭할 수 있는 링크로 자동으로 바꿉니다.

BBCode

  • 텍스트에 BBCode 태그를 사용할 수 있습니다. URL은 자동으로 링크 됩니다.
  • 다음 태그를 이용하여 소스 코드 구문 강조를 할 수 있습니다: <code>, <blockcode>, <apache>, <applescript>, <autoconf>, <awk>, <bash>, <c>, <cpp>, <css>, <diff>, <drupal5>, <drupal6>, <gdb>, <html>, <html5>, <java>, <javascript>, <ldif>, <lua>, <make>, <mysql>, <perl>, <perl6>, <php>, <pgsql>, <proftpd>, <python>, <reg>, <spec>, <ruby>. 지원하는 태그 형식: <foo>, [foo].
  • 사용할 수 있는 HTML 태그: <p><div><span><br><a><em><strong><del><ins><b><i><u><s><pre><code><cite><blockquote><ul><ol><li><dl><dt><dd><table><tr><td><th><thead><tbody><h1><h2><h3><h4><h5><h6><img><embed><object><param>
  • web 주소와/이메일 주소를 클릭할 수 있는 링크로 자동으로 바꿉니다.

Textile

  • 다음 태그를 이용하여 소스 코드 구문 강조를 할 수 있습니다: <code>, <blockcode>, <apache>, <applescript>, <autoconf>, <awk>, <bash>, <c>, <cpp>, <css>, <diff>, <drupal5>, <drupal6>, <gdb>, <html>, <html5>, <java>, <javascript>, <ldif>, <lua>, <make>, <mysql>, <perl>, <perl6>, <php>, <pgsql>, <proftpd>, <python>, <reg>, <spec>, <ruby>. 지원하는 태그 형식: <foo>, [foo].
  • You can use Textile markup to format text.
  • 사용할 수 있는 HTML 태그: <p><div><span><br><a><em><strong><del><ins><b><i><u><s><pre><code><cite><blockquote><ul><ol><li><dl><dt><dd><table><tr><td><th><thead><tbody><h1><h2><h3><h4><h5><h6><img><embed><object><param><hr>

Markdown

  • 다음 태그를 이용하여 소스 코드 구문 강조를 할 수 있습니다: <code>, <blockcode>, <apache>, <applescript>, <autoconf>, <awk>, <bash>, <c>, <cpp>, <css>, <diff>, <drupal5>, <drupal6>, <gdb>, <html>, <html5>, <java>, <javascript>, <ldif>, <lua>, <make>, <mysql>, <perl>, <perl6>, <php>, <pgsql>, <proftpd>, <python>, <reg>, <spec>, <ruby>. 지원하는 태그 형식: <foo>, [foo].
  • Quick Tips:
    • Two or more spaces at a line's end = Line break
    • Double returns = Paragraph
    • *Single asterisks* or _single underscores_ = Emphasis
    • **Double** or __double__ = Strong
    • This is [a link](http://the.link.example.com "The optional title text")
    For complete details on the Markdown syntax, see the Markdown documentation and Markdown Extra documentation for tables, footnotes, and more.
  • web 주소와/이메일 주소를 클릭할 수 있는 링크로 자동으로 바꿉니다.
  • 사용할 수 있는 HTML 태그: <p><div><span><br><a><em><strong><del><ins><b><i><u><s><pre><code><cite><blockquote><ul><ol><li><dl><dt><dd><table><tr><td><th><thead><tbody><h1><h2><h3><h4><h5><h6><img><embed><object><param><hr>

Plain text

  • HTML 태그를 사용할 수 없습니다.
  • web 주소와/이메일 주소를 클릭할 수 있는 링크로 자동으로 바꿉니다.
  • 줄과 단락은 자동으로 분리됩니다.
댓글 첨부 파일
이 댓글에 이미지나 파일을 업로드 합니다.
파일 크기는 8 MB보다 작아야 합니다.
허용할 파일 형식: txt pdf doc xls gif jpg jpeg mp3 png rar zip.
CAPTCHA
이것은 자동으로 스팸을 올리는 것을 막기 위해서 제공됩니다.