본문 바로가기
자료구조

[자료구조] 10. 그래프(1)

by jw.cs 2023. 12. 14.
  1. 그래프
  2. 그래프 용어
    1. 그래프 정의
      • 무방향 그래프, 방향 그래프
      • 가중치 그래프
      • 부분 그래프
    2. 그래프 용어
      1. 인접 정점
      2. 정점의 차수
        • 진입 차수(in-degree)
        • 진출 차수(out-degree)
    3. 경로(path)
      1. 단순 경로(simple cycle): 반복되는 정점 없음
      2. 사이클(cycle): 시작 정점 = 종료 정점
      3. 단순 사이클(simple cycle)
        • 오일러 사이클: 모든 edge 한번씩만 거쳐서 제자리로으로 돌아온다. (단순 사이클 x)
        • 헤밀턴 사이클: 모든 node 한번씩만 거쳐서 제자리로 돌아온다. (단순 사이클)
    4. 그래프 연결 정도
      1. 연결 그래프
      2. 비연결 그래프
      3. 완전 그래프: 모든 정점이 연결되어 있는 그래프
  3. 그래프의 표현 방법
    • 인접 행렬(adjacent matrix)
    • 인접 리스트(adjacent list)
  4. 그래프의 탐색
    • 깊이 우선 탐색(DFS: Depth-First Search)
    • 너비 우선 탐색(BFS: Breadth-First Search)
  5. 깊이 우선 탐색(DFS)
    • 스택: Last in First out
      --> Source node, 아직 방문되지 않은 노드부터 스택에 push하다가, 더이상 push할 것이 없으면 pop한다.
      • 인접 행렬
      • 인접 리스트
      • 명시적 스택
  6. 너비 우선 탐색(BFS)
    • 큐: First in First out
      --> Source node부터 큐에 push하고, pop하면서 방문한 후, 인접 노드를 push하고, pop하면서 방문한다. 더이상 push할 것이 없으면 멈춘다.
      • 인접 행렬
      • 인접 리스트

 

10.1 그래프 (Graph)

▶ 그래프란?! 

: 객체 사이의 연결 관계를 표현할 수 있는 자료구조

  • 정점(vertex, node)
  • 간선(edge)

▶ G = (V, E)

: 정점(vertex)와 간선(edge)들의 유한집합

  • V(G): 그래프 G의 정점(vertex)들의 집합 --> |V| = 총 정점의 개수
  • E(G): 그래프 G의 간선(edge)들의 집합 --> |E| = 총 간선의 개수
  • 오일러 경로: 그래프에 존재하는 모든 간선(edge)를 한번만 통과하면서 처음 정점(node)로 되돌아오는 경로

 

 

10.2 그래프 용어
무방향 그래프 (undirected graph) vs. 방향 그래프 (directed graph)

무방향 그래프 (undirected graph) vs. 방향 그래프 (directed graph)

  • 무방향 그래프(undirected graph)
  • 방향 그래프(directed graph)

 

가중치 그래프 (weighted graph)

: 간선에 가중치(weight)가 할당된 그래프

 

부분 그래프 (subgraph)

: 어떤 그래프의 정점(vertex)와 간선(edge)의 일부로 이루어진 그래프

 

 

그래프 기본 용어
  • 인접 정점 (adjacent vertex): 하나의 정점에서 간선에 의해 직접 연결된 정점

▶ 정점의 차수(degree)

  • 무방향 그래프: 그 정점에 인접한 정점의 수
  • 방향 그래프
    - 진입 차수(in-degree): 외부에서 오는 간선의 개수
    - 진출 차수(out-degree): 외부로 향하는 간선의 개수

 

경로 (path)

: 하나의 정점으로부터 다른 정점까지의 경로 --> 정점의 나열

  • 단순 경로 (simple path): 반복되는 정점이 없는 경로
  • 사이클 (cycle): 시작 정점과 종료 정점이 동일한 경로
  • 단순 사이클 (simple cycle): 반복되는 정점이 없고, 시작 정점과 종료 정점이 동일한 경로 (단순 경로 + 사이클)

▶ 대표적인 사이클 문제:

  • 오일러 사이클: 모든 edge를 한번씩만 거쳐서 제자리로 돌아오는 사이클 (단순 사이클 x)
  • 헤밀턴 사이클: 모든 vertex를 한번씩만 거쳐서 제자리로 돌아오는 사이클 (단순 사이클 o)

 

그래프의 연결 정도
  • 연결 그래프 (connected graph)
  • 비연결 그래프 (unconnected graph)
  • 완전 그래프 (complete graph): 모든 서로 다른 정점들이 서로 연결되어 있는 그래프

Cf) bridge: 없어지면 비연결 그래프가 되도록 하는 edge.

▶ bridge의 존재 여부를 판단하는 알고리즘:

  • 현재 정점의 자식 정점 중에서, 현재 정점을 거치지 않고는 현재 정점 이전에 방문했던 정점에 갈 수 없는 정점이 있다면, bridge이다.

 

 

10.3 그래프의 표현 방법
  • 인접 행렬 (adjacent matrix)
  • 인접 리스트 (adjacent list)
1) 인접 행렬 (adjacent matrix)

1) 인접 행렬 (adjacent matrix)

  • 무방향 그래프의 경우 대칭 행렬이기 때문에, 배열의 상위 삼각이나 하위 삼각만 저장하면 메모리를 절약할 수 있다.
  • n개의 정점을 가지는 그래프를 인접 행렬로 표현하기 위해서는 간선의 수에 무관하게 항상 (n x n)개의 메모리 공간이 필요하다.
    --> 인접 행렬 방법은 그래프에 간선이 많이 존재하는 밀집 그래프(dense graph)를 표현하는 경우에는 적합하나, 그래프 내에 적은 숫자의 간선만을 가지는 희소 그래프(sparse graph)의 경우에는 메모리 낭비가 심하므로, 적합하지 않다.
  • 인접 행렬을 이용하면 두 정점을 연결하는 간선의 존재 여부를 O(1) 시간 안에 즉시 알 수 있다는 장점이 있다. 정점 u와 정점 v를 연결하는 정점이 있는지를 알기 위해서는 M[u][v]의 값을 조사하면 된다.
  • 정점의 차수는 인접 행렬의 행이나 열을 조사하면 알 수 있으므로, O(n)의 연산에 의해 알 수 있다.
  • 반면에 그래프에 존재하는 모든 간선의 수를 알아내려면 인접 행렬 전체를 조사해야 하므로, n^2 번의 조사가 필요하게 되어, O(n^2)의 시간이 요구된다.

 

2) 인접 리스트 (adjacent list)

2) 인접 리스트 (adjacent list)

  • 리스트의 헤더 노드: 정점
    --> 해당 정점과 연결된 다른 정점을 리스트로 표현한다.

 

그래프 표현 방법: 인접 행렬 vs. 인접 리스트

 

 

10.4 그래프의 탐색
  • 깊이 우선 탐색 - 스택
  • 너비 우선 탐색 - 큐

깊이 우선 탐색 vs. 너비 우선 탐색

 

 

10.5 깊이 우선 탐색 (DFS; Depth First Search)

10.5 깊이 우선 탐색

  • 스택: Last In First Out
  1. 0 --> 1
  2. 1 --> 3 --> 4
  3. 4 --> 2
  4. 2 --> 5 --> 6

--> 스택에 가장 최근에 들어간 정점이 다시 빠져나와, 새로운 source node 역할을 하며 정점을 찾는다.

 

DFS 알고리즘

DFS 알고리즘

 

DFS 과정

 

DFS 과정

 

▶ 그래프에 사이클이 있는지 검사하는 알고리즘

그래프에 사이클이 있는지 검사하는 알고리즘

: 임의의 노드에서 ancestor로의 간선이 있으면, 사이클이 존재한다.

  • Cf) Bridge: 임의의 노드에서의 자식 노드가 그 자식 노드에서 ancestor로의 간선이 없으면, bridge이다.

 

깊이 우선 탐색 (DFS) 프로그램 - 인접 행렬

깊이 우선 탐색 (DFS) 프로그램 - 인접 행렬

  • 인접 행렬: O(n^2)

 

깊이 우선 탐색 (DFS) 프로그램 - 인접 리스트

깊이 우선 탐색 (DFS) 프로그램 - 인접 리스트

  • 인접 리스트: O(n+e)
    : 리스트는 간선이 있는 것만 처리하므로, vertex (|V|) 들이 자신의 간선 (2 x |E| in undirected graph)들만 처리하므로, 리스트에서 노드(data + link)들의 개수와 동일하게, |V| + |E| 가 된다.

 

깊이 우선 탐색 (DFS) - 명시적 스택 버전 알고리즘

깊이 우선 탐색 (DFS) - 명시적 스택 버전 알고리즘

 

 

10.6 너비 우선 탐색

10.6 너비 우선 탐색

  • 큐: First In First Out

: 시작 정점에서 가까운 정점부터 탐색한다. 

 

너비 우선 탐색 (BFS) 알고리즘

너비 우선 탐색 (BFS) 알고리즘

 

너비 우선 탐색 (BFS) 과정
 
너비 우선 탐색 (BFS) 과정
 

: Source node, source node와 연결되어 있는 인접 정점부터 방문하여 큐에 push하고, 더 이상 방문하지 않은 정점이 없으면 멈춘다.

 

너비 우선 탐색 (BFS) 프로그램 - 인접 행렬

너비 우선 탐색 (BFS) 프로그램 - 인접 행렬

  • 인접 행렬: O(n^2)

 

너비 우선 탐색 (BFS) 프로그램 - 인접 리스트

너비 우선 탐색 (BFS) 프로그램 - 인접 리스트

 

  • 인접 리스트: O(n+e)

 

깊이 우선 탐색 (DFS) - example

깊이우선탐색 (DFS) - example

▶ 깊이 우선 탐색 (DFS)

: 숫자가 작은 것부터 시작해서, 간선이 있는 숫자들로 내려간다.

  • 스택: Last In First Out
  1. 0 
  2. 0 --> 1 --> 3 --> 7 --> 6 --> 5
  3. 5 --> 2
  4. 2 --> 4
  5. 4 --> 8
  6. 8 --> 9

 

 

 

 

 

출처: 이화여자대학교 이숙영교수님 자료구조

저작자표시

'자료구조' 카테고리의 다른 글

[자료구조] 12. 정렬  (0) 2023.12.14
[자료구조] 11. 그래프(2)  (0) 2023.12.14
[자료구조] 1205 (2) 14. 해싱  (1) 2023.12.07
[자료구조] 1205 (1)  (1) 2023.12.07
[자료구조] 1201 (2) 13. 탐색  (1) 2023.12.06

관련글

티스토리툴바