[알고리즘] Graph (1) - Prologue

[1. Prologue 개요]

1. 그래프란?

  → Graph : 개체와 개체들 사이의 링크로 연결된 1:1 관계를 시각적으로 나타내는 수학적 표시, 개체와 그 개체를 연결하는 링크의 집합

  → vertex : 개체

  → edge : 개체를 연결하는 링크, 개체간 관계를 나타냄

  → G = (V, E), 그래프는 두 개의 요소(개체, 관계)를 가짐

 

2. 그래프의 종류

  → 방항성 : 링크의 방향이 정해진 그래프 / 방향이 정해지지 않은 그래프

  → 가중치 : 링크의 가중치가 정해진 그래프 / 가중치가 정해지지 않은 그래프

  → 방향x, 가중치x : 무방향 그래프

  → 방향x, 가중치o : 가중치 그래프

  → 방향o, 가중치x : 방향그래프

  → 방향o, 가중치o : 방향가중치 그래프

3. 그래프의 표현

(1) Edge list

    → edge들의 리스트

(2) Adjacency matrix of G=(V, E) 그래프의 인접행렬

    → vertex u와 v가 연결되어 있다면, 둘은 인접한 것.

    → 2차원 배열로 표현한 그래프

    → 행 = i, 열 = j

    → n개의 vertex를 나타내는 행렬 A[n][n]

    → Undirected graph의 인접행렬 = 대칭행렬

    → 방향이 정해진 그래프 : 방향에 따라 연결 여부 결정

(3) Adjacency list of G=(V, E) 그래프의 인접리스트

    → Alist[n]

    → Aist[i]는 vertex i의 인접리스트에 있는 다음 노드를 가리킴

(4) 성능 분석

    → sparse graph & dense(complete) graph

    → 성능 비교

4. 그래프의 탐색 (search)

  → 주어진 그래프의 개체(v) 중 하나에서 시작하여 그래프의 모든 개체를 방문하는 문제

  →  탐색과정에서 가장 중요한 요소

        ① 탐색 과정에서 이미 방문한 노드를 기록할 것 (visit을 저장하는 배열 필요)

        ② 탐색 과정에서 노드를 방문하는 순서를 기억할 것 (stack 또는 queue 활용)