자료구조
Graph : 여러개의 점들이 서로 복잡하게 연결되어 있는 관계를 표현한 자료구조
그래프의 실사용 예 : 네비게이션 길찾기
네비게이션에서의 정점 : 특정 도시(출발지, 도착지로 설정할 수 있는 곳)
네비게이션에서의 간선 : 이동가능 여부를 표시
그래프 용어
• 무(방)향그래프(undirected graph) : 두 정점을 방향에 관계없이 자유롭게 이동 가능
• 단방향그래프(directed graph) : 두 정점을 지정된 방향으로만 이동 가능
• 진입차수(in-degree)/진출차수(out-degree) : 한 정점에 진입하고 진출하는 간선이 몇개인지를 나타냄
• 인접(adjacency) : 두 정점간에 간선이 직접 이어져 있다면 이 두 정점은 인접한 정점
• 자기루프(self loop) : 정점에서 진출한 간선이 곧바로 자기 자신에게 진입하는 경우
• 사이클(cycle) : 한 정점에서 출발하여 다시 해당 정점으로 돌아갈 수 있을 경우 사이클이 있다고 표현
인접 행렬
인접 행렬 : 그래프에서 어떤 정점들이 간선으로 연결되었는지를 나타내는 행렬
| A | B | C | |
|---|---|---|---|
| A | 0 | 0 | 1 |
| B | 1 | 0 | 1 |
| C | 1 | 0 | 0 |
인접 리스트
인접 리스트 : 각 정점이 어떤 정점과 인접한지를 리스트의 형태로 표현
그래프를 인접 리스트로 구현할 때, 정점별로 살펴봐야 할 우선 순위를 고려해 구현할 수 있음 이때 리스트에 담겨진 정점들을 우선 순위별로 정렬할 수 있음, 우선 순위가 없다면 연결된 정점들은 단순하게 나열한 리스트가 됨
인접 리스트 사용?
• 메모리를 효율적으로 사용하고 싶을 때 사용(인접 행렬은 연결 가능한 모든 경우의 수를 저장하기 때문에 상대적으로 메모리를 많이 차지함)
여담 : ......
.jpeg)