정점과 간선의 집함, Graph
그래프 관련 용어 정리

정점과 간선의 집함, Graph

그래프란 정점과 간선의 집합을 말한다.
ex) 트리는 그래프. [싸이클이 허용되지 않는 그래프이다.]

그래프 관련 용어 정리

  • V(vertex) : 정점을 의미한다.
  • E(edge) : 간선을 의미한다.
  1. Directed Graph(Digraph)
    말 그대로 정점과 간선의 연결관계에 있어서 방향성이 포함되어 있는 그래프를 말한다.
V = {1,2,3,4,5,6}
E = {(1,4),(2,1),(3,4),(5,6)}
(u,v) = vertex u에서 vertex v로 가는 edge
  1. Undirected Graph
    정점과 간선의 연결관계에 있어서 방향성이 없는 그래프를 말한다.
  1. Degree
    Undirected Graph에서 각 정점(Vertex)에 연결된 Edge의 개수를 Degree라고 한다.
    Directed Graph에서는 간선에 방향성이 존재하기 때문에 Degree가 두 개로 나뉘게 된다.
    각 정점으로부터 나가는 간선의 개수를 Outdegree라고 하고, 들어오는 간선의 개수를 Indegree라고 한다.
  1. 가중치 그래프(Weight Graph)
    가중치 그래프란 간선에 가중치 정보를 두어서 구성한 그래프를 말한다. 반대의 개념인 비가중치 그래프는 모든 간선의 가중치가 동일한 그래프이다.
  1. 부분 그래프(Sub Graph)
    부분 집합과 유사한 개념으로 부분 그래프라는 것이 존재한다.
    부분 그래프는 본래의 그래프의 일부 정점 및 간선으로 이루어진 그래프를 말한다.

그래프를 구현하는 두 방법

[무슨 말일까…?ㅠ^ㅠ]

  1. 인접 행렬(adjacent matrix)
    정방 행렬을 사용하는 방법이다.
    해당하는 위치의 value 값을 통해서 vertex(정점)간의 연결 관계를 O(1)으로 파악할 수 있다.
    Edge 개수와는 무관하게 V^2의 Space Complexity(공간 복잡도)를 갖는다.
    => Dense graph를 표현할 때 적절한 방법이다.

  2. 인접 리스트(adjacent list)
    연결 리스트를 사용하는 방법이다.
    vertex의 adjacent list를 확인해봐야 하므로 vertex간 연결되어 있는지 확인하는데 오래 걸린다.
    Space Complexity는 O(E + V)이다.
    => Sparse graph를 표현하는데 적당한 방법이다.

[어려운 용어가 많이 나온다… 더 공부하자!!]

그래프 탐색

그래프는 정점의 구성 뿐만 아니라 간선의 연결에도 규칙이 존재하지 않기 때문에 탐색이 복잡하다. 따라서 그래프의 모든 정점을 탐색하기 위한 방법은 다음의 두 가지 알고리즘을 기반으로 한다.

1. 깊이 우선 탐색(Depth First Search: DFS)
그래프 상에 존재하는 임의의 한 정점으로부터 연결되어 있는 한 정점으로만 나아간다라는 방법을 우선으로 탐색한다. 일단 연결된 정점으로 탐색하는 것이다. 연결할 수 있는 정점이 있을 때까지 계속 연결하다가 더 이상 연결된 정점이 없으면 그 전 단계의 정점으로 돌아가서 연결할 수 있는 정점이 있는지 살펴봐야 할 것이다. 갔던 길을 되돌아 오는 상황이 존재하는 미로찾기처럼 구성하면 되는 것이다.
어떤 자료구조를 사용해야 할까? 바로 Stack이다.
Time Complexity : O(V + E) => vertex개수+edge개수

2. 너비 우선 탐색(Breadth First Search: BFS)
그래프 상에 존재하는 임의의 한 정점으로부터 연결되어 있는 모든 정점으로 나아간다. Tree에서의 Level Order Traversal 형식으로 진행되는 것이다. BFS에서 자료구조로 Queue를 사용한다. 연락을 취한 정점의 순서를 기록하기 위한 것이다.
우선, 탐색을 시작하는 정점을 Queue에 넣는다.(enqueue)
그리고 dequeue를 하면서 dequeue를 하는 정점과 간선으로 연결된 정점들을 enqueue한다.
즉, vertex들을 방문한 순서대로 queue에 저장하는 방법을 사용하는 것이다.
Time Complexity : O(V + E) => vertex개수+edge개수

BFS로 구한 경로는 최단 경로이다.

참고