> For the complete documentation index, see [llms.txt](https://kde6260.gitbook.io/dev/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://kde6260.gitbook.io/dev/undefined.md).

# 방향없는 그래프(undirected graph)

### 그래프의 구성 요소

* 정점 (vertex)
* 간선 (edge)

![그래프의 예시](https://1792721125-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-Lo8iAG2zHsS2e9mIAqX%2F-LxUBsEUOi3Fnvm1sdC7%2F-LxUORvgEvzWtK6tGDrO%2Fgraph.png?alt=media\&token=1bd9949e-9f44-45d1-967e-f65756449efd)

* 경로(path)의 길이 = 경로 내 간선의 갯수
* 거리(distance) = 두 정점 사이의 최단 경로 (shortest path)

### 인접행렬 (adjacent matrix)

임의의 두 정점 사이의 간선 유무를 행렬로 나타낸다.

```
  A B C D
A 0 1 1 0
B 1 0 0 0
C 1 0 0 1
D 0 0 1 0
```

### 간선 리스트 (edge list)

두 정점 사이의 간선을 중첩 리스트로 나타낸다.

```
[
  (A, B),
  (A, C),
  (C, D)
]
```

### 인접 리스트 (adjacent list)

어느 한 정점과 인접한 정점을 리스트로 나타낸다.

```
A: [B, C]
B: [A]
C: [A, D]
D: [C]
```

###

### 시간복잡도

* V = 그래프 내 정점의 총 갯수 
* E = 그래프 내 간선의 총 갯수 
* Deg = 어느 한 정점의 차수 (어느 한 정점과 연결된 간선의 갯수 또는 가중치의 합)

|       | 두 정점 사이에 간선 유무 | 그래프 내 모든 간선 탐색 | 한 정점과 인접한 모든 정점 탐색 |
| ----- | -------------- | -------------- | ------------------ |
| 인접행렬  | O(1)           | O(V^2)         | O(V)               |
| 간선리스트 | O(E)           | O(E)           | O(E)               |
| 인접리스트 | O(Deg)         | O(E)           | O(Deg)             |

### 그래프의 밀도(density)

그래프를 탐색할 때 어떤 두 알고리즘의 시간복잡도가 각각 `O(V^1.5)`와  `O(E)`라면 둘 중 어떤 알고리즘이 더 효율적일까? 답은 그래프의 밀도에 따라 다르다.

![densed graph](https://1792721125-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-Lo8iAG2zHsS2e9mIAqX%2F-LxUPcIN5jzC5tiC9QO8%2F-LxUURkGmm1eNtV1Uvvm%2Fdensed.png?alt=media\&token=30e8d0e5-1718-48d1-afdb-071dfe47e48a)

위와 같이 **정점에 비해 간선이 많은 그래프를 밀도가 높은 그래프**라고 한다. 위 그래프의 정점의 갯수는 7개, 간선의 갯수는 6 + 5 + 4 + 3 + 2 + 1 = 21개이므로 시간복잡도가 `O(V^1.5)`인 알고리즘을 쓰는 게 더 유리하다.

* V ^ 1.5 = 18.52
* E = 21

![sparsed graph](https://1792721125-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-Lo8iAG2zHsS2e9mIAqX%2F-LxUPcIN5jzC5tiC9QO8%2F-LxUZLAXkkI2mS9yUM7n%2Fsparsed.png?alt=media\&token=c1556966-3fd0-4336-9f8a-a20748d10431)

반면에 **정점에 비해 간선이 적은 그래프를 밀도가 낮은 그래프**라고 한다. 위 그래프의 정점의 갯수는 8개, 간선의 갯수는 9개이므로 시간복잡도가 O(E)인 알고리즘을 쓰는 게 더 유리하다.

* V^1.5 = 22.62
* E = 9

### 그래프의 경로탐색

**어느 한 정점에서 1개 이상의 간선을 통해 다른 정점으로 이동하는 것을 경로탐색**이라 한다. 어느 한 정점의 인접리스트를 구하는 함수가 `adjacent_list()`일 때 정점 `v`에서 출발하여 이동가능한 경로를 모두 탐색하는 방법은 아래와 같다. 

```python
def explore(v):
    visitied[v] = True  # O(1)
    for w in adjacent_list(v):  # O(Deg)
        if not visited[w]:
            explore(w)
```

위 방법은 **DFS(Depth First Searching)**이며 어느 한 정점에서 더이상 이동할 경로가 없으면 그 전에 방문했던 정점으로 되돌아가는 백트래킹(back-tracking)을 사용한다. 인접리스트와 DFS를 이용하여 정점 `v`에서 이동가능한 경로를 모두 탐색할 때 시간복잡도는 `O(E)`다.

그래프 내의 모든 경로를 탐색하려면 아래와 같이 모든 정점의 `visited`를 검사하면서 방문하지 않은 정점에서 출발하는 탐색이 필요하다. 그래프 내의 모든 경로를 탐색할 경우 시간복잡도는 `O(V+E)`다. 

```python
for v in vertexes:  # O(V)
    if not visited[v]:
        explore(v)  #(Degree per v)
```

### Connected component

connected component는 그래프 내에 정점들이 서로 이동가능한 경로를 가지고 있는 고립된 서브그래프라고 할 수 있다. 아래 그림에서 connected component는 총 3개다.

![connected components](https://1792721125-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-Lo8iAG2zHsS2e9mIAqX%2F-LxUiMLyl8uIHJ3Db0Jq%2F-LxUk-5nyEp8v2dic8dG%2Fconnected_components.png?alt=media\&token=73b354b7-db06-4352-b7c5-d225e69c4013)

DFS를 활용하여 그래프 내의 connected component들을 구별할 수 있다. 아래 코드는 각 connected component에 소속된 정점들의 `cc` 속성에 connected component를 구별하기 위한 숫자를 저장한다.

```python
cc = 1
for v in vertexs:
    if not visited[v]:
        explore(v, cc)
    cc += 1

def explore(v, cc):
    visited[v] = True
    cc[v] = cc
    for w in adjacent_list(v):
        explore(w, cc)
```

* 두 정점이 같은 connected component에 있는지 여부를 출력하는 문제풀이 [coursera - reachability](https://github.com/dev-daeun/algo-course/blob/master/algorithm_on_graphs/week1_decomposition1/1_reachability/reachability.py) 
* 어떤 그래프의 connected component의 갯수를 구하는 문제풀이 [cousera - connected component](https://github.com/dev-daeun/algo-course/blob/master/algorithm_on_graphs/week1_decomposition1/2_connected_components/connected_components.py)

출처

* [코세라 알고리즘 강의](https://www.coursera.org/learn/algorithms-on-graphs?specialization=data-structures-algorithms)