그래프
- 아이템들과 이들 사이의 연결 관계를 표현한다.
- 정점들의 잡합과 이들을 연결하는 간선들의 집합으로 구성된 자료 구조
- 선형, 트리 자료구조로 표현하기 어려운 N:M 관계를 갖는 원소들을 표현
- 정점 (Vertex) : 그래프의 구성요소로 하나의 연결점
- 간선 (Edge) : 두 정점을 연결하는 선
- 차수 (Degree) : 정점에 연결된 간선의 수
📌그래프 유형
트리도 그래프이다.
- 각 노드는 최대 하나의 부모 노드가 존재할 수 있다.
- 각 노드는 자식 노드가 없거나 하나 이상이 존재할 수 있다.
- 두 노드 사이에는 유일한 경로가 존재한다.
💡인접 ( Adjacency)
- 두 개의 정점에 간선이 존재하면 서로 인접해 있다고 한다.
- 완전 그래프에 속한 임의의 두 정점들은 서로 인접해 있다.
💡그래프 경로
- 어떤 정점 A에 시작하여 다른 정점 B로 끝나는 순회로 두 정점 사이를 잇는 간선들을 순서대로 나열한 것.
- 어떤 정점에서 다른 정점으로 가는 경로는 여러가지 일 수 있다.
- 단순 경로
- 시작 정점과 끝 정점을 제외하고 중복된 정점이 없는 경로
- 싸이클
- 경로의 시작 정점과 끝 정점이 같음
- 1 - 3 - 4 - 1
📌그래프 표현
- 인접 행렬 (Adjacent matrix)
- V * V 크기의 2차원 배열을 이용해서 간선 정보를 저장
- 인접 리스트 (Adjacent List)
- 각 정점마다 다른 정점으로 나가는 간선의 정보를 저장
- 간선 리스트 (Edge List)
- 간선(시작 정점, 끝 정점)의 정보를 객체로 표현하여 리스트에 저장
💡인접 행렬
- 두 정점을 연결하는 간선의 유무를 행렬로 표현
- V * V 정방 행렬
- 행 번호와 열 번호는 그래프의 정점에 대응
- 두 정점이 인접되어 있으면 1, 그렇지 않으면 0으로 표현
- 가중치가 없는 그래프면 boolean으로 표현 가능하지만 있다면 int
- 모든 정점에 대한 간선들이 표현되어 있기 때문에 메모리 사용량이 많다.
- 의미있게 정보를 담은 공간을 얼마 되지 않는다.
인접 행렬이 적합한 상황은?
간선이 꽤 많을 경우(밀집 그래프) , 단순하게 풀 때
근데 희소그래프일 경우는 관리하기 어렵고 공간 낭비, 비효율적이다. 시간상 유리하지 않다.
💡인접 리스트
- 각 정점에 대한 인접 정점들을 순차적으로 표현
- 하나의 정점에 대한 인접 정점들을 각각 노드로 하는 연결 리스트로 저장
- 직접 연결리스트를 구현하거나 ArrayList같은 api를 사용해 구현한다.
💡간선 리스트
- 두 정점에 대한 간선 그 자체를 객체로 표현하여 리스트로 저장
- 간선을 표현하는 두 정점의 정보를 나타냄(시작 정점, 끝 정점)
정점중심 해결문제는 인접행렬, 인접리스트
간선중심 해결문제는 간선리스트 를 이용해 풀어야 한다.