Graph

Input

방법1

  • int map[5][5]를 선언하여 연결 정보 있을 시 map[from][to] 를 1로 체크하고 찾을땐 다 돌면서 찾는 방식
  • 메모리를 많이 사용하고 초기화에 시간이 걸림

방법2

  • single linked list 사용하는 방법
  • 1번 노드에 연결 된 2,3,4와 2번에 연결된 3,4를 각각 single linked list로 표시, 아래와 같은 연결 형태

Code

  • 연결리스트로 table[from]에 연결되는 정보(가령 table[1]에 연결된 3->4->2)는 노드1번에 연결된 애들이란 것이지, 3번다음 4번이 오고 4번에 2번이 연결되고 하는 것이 아니니 헷갈리지 말것.
  • 방향성이 없는 경우 table[from]=to, table[to]= from 도 저장하면 됨
  • 가중치가 있는 그래프의 경우 node 구조체에 weight를 추가하여 node->weight에 가중치 저장
  • 노드가 자연수가 아닌 경우 이전 Tree 게시물처럼 id값을 자연수로 변경
  • single linked list 특성 상 다양한 활용이 가능
It's only fair to share...Share on Facebook
Facebook
Share on Tumblr
Tumblr
Share on Google+
Google+
Tweet about this on Twitter
Twitter
Email this to someone
email
Musicals, Travel, Photo, Coding, English, Cat