[개념] 그래프 이론

 

(무방향) 그래프 G=(V,E)

- V: 노드(node) 혹은 정점(vertex)

- E: 노드쌍을 연결하는 에지(edge) 혹은 링크(link)

- 개체(object)들 간의 이진관계를 표현

- n=|V|, m=|E|

 

 

 

---

 

- 어떤 노드 v에 인접한 노드를 찾으려면 결국 해당 v의 한 행을 봐야하므로 O(n) 시간이 걸린다.
- 어떤 에지 (u,v) 검사 -> 배열의 (u,v) 만 찾으면 되므로 O(1) 시간

 

 

---

 

 

 

- 어떤 노드 v에 인접한 모든 노드 찾으려면 결국 v의 연결리스트들의 길이를 구하면 되고 그것은 인접한 노드의 수와 동일하다.

degree(v) = v에 인접한 노드의 갯수 (인접행렬보다 유리)

 

- 어떤 에지 (u,v) 가 존재하는지 검사 - 연결리스트의 길이에 비례하는 시간이 걸린다. (인접행렬보다 불리)

 

 

---

위의 개념을 가지고 DFS, BFS를 알아보자

 

 

 

 

 

 

잘 정리된 글 - https://seongkyun.github.io/algorithm/2019/09/21/algorithm5/ 

 

인접 행렬의 깊이 우선 탐색(DFS) 구현

재귀 호출을 이용해 구현한다.

• dfs(x)는 현재 x 노드에 방문했음을 의미한다.
• 전체 정점의 개수를 V 라고 정의한다.

void dfs (int x)
{
  check[x] = true; // 현재 x 노드에 방문했으므로 check를 1로
  printf("%d ", x); // 현재 노드 값을 출력 (필요없음)
  for (int i=1; i<=n; i++) // 노드(i) 1번부터 마지막 노드 n번까지 돌면서
  {
    if (a[x][i] == 1 && check[1] == false) // x에서 i노드로 간선이 존재하고, check가 false로 방문한 적이 없으면
    {
      dfs(i); // i 노드를 방문한다.
    }
  }
}

 

 

인접 리스트의 깊이 우선 탐색(DFS) 구현

재귀 호출을 이용해 구현한다.

• 동일하게 dfs(x)는 현재 x 노드에 방문함을 의미한다.
• 전체 정점의 개수는 동일하게 V, 간선의 개수는 E 개다.

void dfs (int x)
{
  check[x] = true; // 현재 노드 x에 방문했으므로
  printf("%d ", x); // 현재 노드 값 출력
  // 인접 리스트가 저장된 a의 x번째 항에는 연결된 노드 값들이 저장되어있으므로, for문은 x에서 연결된 노드 개수인 a[x].size() 만큼 돈다.
  for (int i=0; i<a[x].size(); i++)
  {
    int y = a[x][i]; // y에는 x에서 연결된 i 번째 노드 값들이 저장된다.(다음에 방문할 노드 값 y)
    // 위 그림의 경우, a[0] = 1이라면 a[0][0] = 2, a[0][1] = 5가 저장되어 있다.
    if (check[y] == false) // 방문한 적이 없는 경우
    {
      dfs(y) // 방문
    }
  }
}