📒 갈무리 - 그래프(Graph)

📌 그래프란?

- 비선형 자료구조로서 정점과 간선으로 구성되어 있다.

- 트리와 다르게 사이클을 허용하고 간선의 방향이 있을 수도 있고 없을 수도 있다.

- 간선에 가중치를 주어 노드와 노드 사이의 숫자로 거리 비용 등의 관계를 표현할 수 있다.

- 도시와 도시 간의 최단 경로, 최소 경비 등을 표현하는 데 사용

- 트리 또한 아래로 가는 방향 그래프의 형태이지만 그래프는 루트의 개념이 없다.

G = (V, E)

정점 : 노드

간선 : 정점끼리 연결한 선

 

📌 그래프의 종류

방향 그래프 : 간선에 방향이 존재하는 그래프

무방향 그래프 : 간선에 방향이 없는 그래프

순환 그래프 : 사이클이 하나 이상 존재하는 그래프

- 간선이 자기 자신을 가리키는 순환도 존재함

비순환 그래프 : 사이클이 존재하지 않는 그래프

가중치 그래프 : 간선 간의 비용을 표시한 그래프

 

📌 그래프의 표현 - 인접 리스트

- 모든 정점에 대해 그 정점에 인접한 노드들을 리스트로 표현한 것

 

📌 그래프의 표현 - 인접 행렬

- 그래프의 간선 연결 관계를 2차원 배열로 나타낸 방식

- 갈 수 없는 곳은 0, 갈 수 있는 곳은 1로 표현한다.

- 만약, 가중치가 생긴다면 0과 1이 아닌 가중치 값을 넣는다.

- 자기 자신에게는 갈 수 없기 때문에 0(false)으로 표현 (0,0), (1, 1), (2, 2) 등

 

📌 그래프의 표현 - 인접 행렬(무방향 그래프)

- 인접 행렬에서는 인접해 있지 않는 행렬은 갈 수 없다고 처리한다.

 

📌 그래프의 표현 - 행렬(방향 그래프)

- 방향이 가리키는 곳이 연결된 곳은 모두 갈 수 있다.

- 인접해 있더라도 방향이 가리키지 않고 있다면 갈 수 없다.