[자료구조] 14강 - 그래프(1)

✅ 1. 개념 및 용어

• 전기회로의 분석, 최단 거리 탐색, 프로젝트 계획, 스케줄링, 운송, 컴퓨터 네트워크 시뮬레이션 등에 사용된다

(1) 그래프 - 정의

• 그래프 G 는 하나 이상의 정점(노드)을 포함하는 집합 V 와 두 정점의 쌍으로 구성되는 간선을 포함하는 집합 E 의 순서쌍으로 정의함.
• 그래프: G = (V, E) / [ V = 정점, E = 간선 ]

(2) 그래프 - 용어 정의

[ 간선 ]

• 두 정점을 연결하는 선을 의미하며, 두 정점 쌍으로 나타냄.
• 무방향 그래프: 간선의 방향성이 없는 그래프 ( 실선 표현 ) / 두 정점 {v1, v2} 중괄호로 표현함.
• 방향 그래프: 방향성이 있는 그래프 ( 화살표 표현 ) / 순서쌍 (v1, v2) 소괄호로 표현함.
• 무방향의 경우 순서쌍이 없기 때문에 구분을 하지 않아 v1, v2 / v2, v1 동일하게 봄.
• 하지만, 방향이 있는 경우 순서쌍이 존재하기 때문에 v1, v2 / v2, v1 이 동일하지 않음.

(3) 그래프 - 연결

• 혼합 그래프: 무방향과 방향이 있는 간선이 같이 존재하는 경우 혼합 그래프라고 함.

[ 방향 그래프 ]

• 방향 그래프의 간선은 소괄호로 표현을 함.

[ 무방향 그래프 ]

• 무방향 그래프의 간선은 중괄호로 표현을 함.

[ 혼합 그래프 ]

• 혼합 그래프의 간선은 중괄호 또는 소괄호로 표현이 됨.
• 위에서는 v3 에서는 v2로 가는 경로가 존재하지 않음.

(4) 다중 그래프

• 다중 그래프(Multi-Graph): 서로 다른 두 정점을 잇는 간선이 두 개 이상인 그래프를 의미한다.
• ** 단 한쌍만이라도 다중으로 연결이 되어있는 경우이면 모두 다중 그래프로 볼 수 있음. **

(5) 다중 그래프 - 방향 다중 그래프

• 방향 다중 그래프: 방향성을 갖는 간선으로 이루어진 다중 그래프를 의미한다.

(6) 다중 그래프 - 무방향 다중 그래프

• 무방향 다중 그래프: 방향성이 없는 간선으로 이루어진 다중 그래프를 의미한다.

(7) 가중 그래프

• 가중 그래프: 간선이 가중치를 갖는 그래프를 의미한다.
• 쉽게말해, 간선(Edge)에 숫자로 된 값이 할당된 그래프를 말하며, 이 할당된 숫자를 가중치(Weight) 또는 **비용(Cost)**이라고 부른다.
• 예를들면, 위의 이미지와 같이 서울에서 부산까지의 간선에 가중치 시간을 넣어 몇 시간이 걸리는지 기재하는 느낌임.
• ** 가중치가 없는 일반적인 그래프는 단순히 두 정점(Node)이 '연결되어 있다', '연결되어 있지 않다'만을 표현하지만, 가중치 그래프는 그 연결에 대한 정보의 강도, 비용, 거리 등 정량적인 의미를 부여한다. **

(8) 그래프 - 최대 간선 개수

[ 무방향 그래프 최대 간선 개수 ]

• n 개의 정점을 갖는 무방향 그래프의 무순서쌍 최대 개수를 구하는 공식이며, 위의 경우 최대 3개가 나오게 됨.

[ 방향 그래프 최대 간선 개수 ]

• 방향 그래프의 경우 방향에 따라서 개수가 많아질 수 있으며, 위의 공식을 통해서 최대 간선 개수를 구할 수 있음.
• 방향을 가지기 때문에 무순서쌍이 아닌 순서쌍으로 표현이 된다. 
• 순서쌍: 쉽게말해, 방향이 있기 때문에 순서가 존재할 수 있는 쌍을 의미함.

(9) 완전 그래프

• 완전 그래프(Complete Graph): 모든 정점들이 간선으로 서로 연결된 그래프를 의미한다.

(10) 그래프 - 성질

[ 인접 ]

• 인접: 두 정점 vi 와 vj 가 서로 연결하는 간선이 존재하는 경우에 "인접한다" 라고 표현함.
• ** 인접은 그래프의 방향성 여부와 상관없이 적용되며, 핵심은 두 정점 사이에 간선이 존재하는가 이다. **

[ 독립 정점 ]

• 독립 정점: 다른 어떤 정점과도 인접하지 않고 동떨어진 정점을 의미한다. ( 즉, 해당 정점은 간선이 없음. )

[ 널(Null) 그래프 ]

• 널(null) 그래프: 독립 정점만으로 구성된 그래프이며, 간선의 집합 E는 공집합임.
• ** Null-Graph는 간선이 존재하지 않고 정점만 존재하는 그래프로 볼 수 있음 **

[ 경로(Path) ]

• 임의의 두 정점을 연결하는 간선의 개수를 의미한다.
• ** 쉽게말해, 임의의 두 정점을 골라서 시작 지점과 끝 지점으로 나눌 때 중간에 거쳐서 가는 모든 간선의 개수를 의미함. **
• 경로 길이: 경로에 있는 간선의 수
• 단순 경로: 경로 상에 있는 모든 정점이 서로 다른 경로
• 기본 경로: 경로 상에 있는 모든 간선이 서로 다른 경로
• ** 근데 문서에서는 단순 경로, 기본 경로 둘 다 "정점들 중에 중복된 정점이 없는 경로" 로 같은 말로 쓰이는데? **

[ 경로 예시 - 방향 그래프 ]

• 위와 같이 방향 그래프가 존재 할 때, P1~6 모두가 v2 -> v4 로 가는 경로임.

• 단순 경로: 경로 상에 있는 모든 정점이 서로 다른 경로
• ** 예시 이미지의 경우 경로상의 정점이 중복 방문을 하지 않는 경로를 단순 경로로 볼 수 있음. **
• 즉, 빨간색 부분은 기본 경로는 될 수 있지만, 중복 방문이 일어나기 때문에 단순 경로는 될 수 없음.

[ 경로 예시 - 사이클을 포함한 경로 ]

• 사이클: 출발점과 도착점이 동일한 단순 경로를 의미한다.
• 사이클 그래프: 오직 하나의 닫힌 루프(고리)만을 형성하는 특정한 구조의 그래프를 의미하며, 위의 내용과는 무관함.
• ( 대각선은 없고 변으로만 간선이 이루어져서 하나의 고리를 형성한다고 보면됨. )
• ** 즉, 위의 그래프는 사이클을 포함한 방향 그래프로 볼 수 있음. **

(11) 그래프 - 이론에서 사용하는 용어 정리

• 진입 차수: 주어진 정점으로 향한 간선의 개수를 의미한다.
• 진출 차수: 주어진 정점에서 시작하는 간선의 개수를 의미한다. ( 즉, 주어진 정점에서 나가는 간선의 개수를 말함. )
• 정점의 차수: 진출 차수와 진입 차수의 합을 의미함.
• ** 무방향 그래프에서 "차수"는 단순히 정점에 연결된 간선들의 개수를 의미함. **
• 루프: 간선의 시작점과 끝점이 같은 정점인 길이가 1인 경로를 의미함. ( 한 바퀴 돌아서 다시 돌아온 느낌임 )
• 무사이클 그래프: 사이클이 없는 그래프를 무사이클 그래프라고 말하며, 방향성이 없다면 일반적으로는 "트리" 라고함.
• ( 방향이 있는 무사이클 그래프를 DAG(directed acycclic graph) 라고 부름 )

(12) 그래프와 트리의 차이

• 방향성이 없는 무사이클 그래프는 트리가 되고, 그래프는 트리를 포괄하고 있음.

---

✅ 2. 추상 자료형

(1) 그래프 - 추상 자료형

• 추상자료형은 "객체의 정의" 와 "연산" 으로 구성이 됨.

---

✅ 3. 그래프 표현법

• 그래프가 컴퓨터에서 표현할 때 가장 대표적이고 일반적인 방식은 인접 행렬, 인접 리스트 두 가지 방식임.

(1) 그래프 표현 - 인접 행렬

• 정점 vi, vj 의 행렬값이 1이면 true 간선이 존재한다는 의미이고, 0 이면 false 로 간선이 존재하지 않음을 표현한다.
• 즉, 1, 0 은 간선의 존재 유무만을 나타내는 값으로 쓰임.

[ 가중치 그래프 표현 ]

• 가중치 값 w 를 행렬의 요소로써 넣게 되며, 간선의 유무 + 가중치 값을 표현

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

• 무방향 그래프는 위의 예시로 보면, 1에서 4로 가는 방향도 있는 반면 4에서 1로 가는 방향도 가능하기 때문에 인접행렬 표현이 두 개씩 존재 할 수 있음.
• 즉, 위와 같이 인접 행렬이 대칭이 될 수가 있음.

• 위와 같이 또 다른 무방향 인접행렬 예시를 봐도, 동일하게 대칭이 되는 구조가 될 수 있음.

(3) 그래프 표현 - 인접 리스트