본문 바로가기
알고리즘, 자료구조/자료구조

27. 그래프

by Wordbe 2019. 9. 8.
728x90

그래프 사용의 예

  • 철도망의 안정성 분석 - 28 절단점 찾기 알고리즘
  • 소셜 네트워크 분석 - 29 BFS(너비 우선 탐색)
  • 인터넷 전송 속도 계산 - 31 최소 스패닝 트리
  • 한 붓 그리기 (오일러 경로) - 28.4 DFS(깊이 우선 탐색)
  • 외환 거래 - 30 최단 거리 알고리즘

암시적 그래프 구조들

그래프 형태를 갖는 구조가 아니라도, 그래프를 통해서 표현하면 쉽게 해결할 수 있는 문제들이 있음.

이를 암시적 그래프(implicit graph)라 한다.

  • 할일 목록 정리 - 위상 정렬(topological sort) - 28 DFS(깊이 우선 탐색)
  • 15-퍼즐 - 29, 30 최단 경로 문제
  • 게임판 덮기 - 32 이분 그래프, 이분 매칭 알고리즘
  • 회의실 배정 - 28 강 결합성 문제

그래프의 표현: 인접행렬과 인접리스트

인접행렬 :

​ 장 - 두 정점을 잇는 간선(u, v)이 있는지 한 번의 배열 접근만으로 확인할 수 있다.

​ 단 - 실제 간선 개수와 상관없이 O(|V|2) 공간을 사용한다. (밀집 그래프, dense graph)

vector<vector<bool> > adjmatrix 혹은
vector<vector > adjmatrix (가중치 그래프)

인접리스트:

​ 장 - O(|V| + |E|)의 간선 수를 가진다. (희소 그래프, sparse graph)

​ 단 - 간선(u, v)의 존재를 확인하기 위하여 연결 리스트 adjacent[u]를 처음 부터 읽어가면서, 원소를 일일이 비교해야 한다.

vector<list > adjlist 혹은  
vector<vector > adjlist
728x90

'알고리즘, 자료구조 > 자료구조' 카테고리의 다른 글

19. [스택, 큐, 데크] 간단 정리  (0) 2019.08.27
선형자료구조  (0) 2019.08.26

댓글