그래프는 삼성전자나 기존의 대기 IT문제에서 단골로 출몰되는 언어라고 들었다.
언제나 그렇듯 알고리즘 문제 해결전략 책을 읽고 정리한닷..!
이번엔 이미 알고 있는 내용이라 조금 빨리 읽혔다.
그래프의 정의
Graph G (V,E) 는 어떤 자료나 개념을 표현하는 정점(Vertex)들의 집합 V와 이들을 연결하는 간선(Edge)들의 집합 E로 구성된 자료구조
그래프의 종류
그래프의 다음과 같은 종류가 있다.
- 방향그래프
- 무방향그래프
- 가중치그래프
- 다중그래프
- 단순 그래프
- 이분 그래프
뭐 이런것들이 있다.
그래프의 경로
한 Vertex에서 다른 Vertex로까지 연결된 간선들을 순서대로 나열 한것
다양한 경로들이 나올 수 있는데, 우리는 단순경로(Simple Path)에 대해 알 필요가 있다.
경로 중 한 정점을 최대 한 번만 지나는 경로를 단순경로 라고 한다.
그래프의 사용 예
- 철도망의 안정성 분석 (절단점 찾기 알고리즘)
- 소셜 네트워크 분석 (너비 우선탐색)
- 인터넷 전송 속도 계산(최소 스패닝 트리 알고리즘 , Kruskal 알고리즘)
- 한 붓 그리기 (오일러 경로)
- 외환 거래 (가중치의 곱)
암시적 그래프 구조들
암시적 그래프란?
현실세계에서 그래프 같은 형태를 갖는 구조가 아니라도 그래프를 통해서 표현하면 쉽게 해결할 수 있는 문제
- 할 일 목록 정리 (위상 정렬, 28장 참고해보입시다)
- 15-퍼즐
- 게임판 덮기
- 회의실 배정
그래프의 표현 방법들
이번 장에서 아마 가장 중요한 부분이 아닌가 싶다.
그래프는 트리에 비해 정적인 용도에 많이 사용된다. 이말은 다음과 같다.
그래프는 새로운 정점이나 간선을 추가하고 삭제하는 일이 자주 일어나지 않는다.
인접 리스트 표현
인접 리스트의 표현은 각 정점마다 연결된 간선들을 연결리스트로 표현하는 방식.
List<int>[] adjacent;v에 연결된 간선들은 adjacent[v]에 그 값이 들어가게 된다.
그런데 만약 간선에 가중치가 있다면 어떻게 표현해야 할까?
class Edge {
int vertex;
int weight;
}라는 클래스를 만들고 List에 int 대신 Edge를 넣어준다.
인접 행렬 표현
인접 행렬은 2차원 배열을 이용해 그래프의 간선 정보를 저장하는 방식
boolean[][] adjacent;간선이 연결되어있으면 1, 간선이 연결되어 있지 않으면 0으로 표현한다.
만약 간선들의 가중치가 존재한다면 어떻게 해결할까
int[][] adjacent;간선이 연결되어있다면 0, 나머지는 간선들의 가중치가 그 값으로 들어간다..
인접 행렬 표현과 인접 리스트 표현의 비교
- 인접 리스트 장점
인접 리스트 표현은 전체 의 공간 만큼 사용한다.
- 인접 행렬 장점
인접 행렬은 인접 리스트와 달리 간선의 정보를 바로 획득 할 수 있다.
배운 것
어느정도 알고 있었던 점이라 편하게 읽었다.
그러나 가중치를 표현하는데 있어 대부분 인접행렬을 사용했던 것 같은데,
클래스를 만들어서 하는 방법은 가독성 좋게 프로그래밍을 짤 때 있어서 꽤 도움이 될 것 같다.
