Graph

문지원(JiwonMoon)·2022년 6월 15일
0
post-thumbnail

🤔 목적

컴퓨터공학의 기초가 되는 cs지식을 되새기면서 이 후 있을 기술면접을 대비 하고자한다.

그래프(Graph)란?

단순히 노드(node,N)와 그래프를 연결하는 간선(edge, E)을 하나로 모아놓은 자료구조
즉, 연결되어 있는 객체 간의 관계를 표현할 수 있는 자료구조이다.

그래프(Graph)의 용어 정리

  • 정점(vertex): 위치라는 개념. (node 라고도 부름)
  • 간선(edge): 위치 간의 관계. 즉, 노드를 연결하는 선 (link, branch 라고도 부름)
  • 인접 정점(adjacent vertex): 간선에 의 해 직접 연결된 정점
  • 정점의 차수(degree): 무방향 그래프에서 하나의 정점에 인접한 정점의 수
  • 무방향 그래프에 존재하는 정점의 모든 차수의 합 = 그래프의 간선 수의 2배
  • 진입 차수(in-degree): 방향 그래프에서 외부에서 오는 간선의 수 (내차수 라고도 부름)
  • 진출 차수(out-degree): 방향 그래픙에서 외부로 향하는 간선의 수 (외차수 라고도 부름)
  • 방향 그래프에 있는 정점의 진입 차수 또는 진출 차수의 합 = 방향 그래프의 간선의 수(내차수 + 외차수)
  • 경로 길이(path length): 경로를 구성하는 데 사용된 간선의 수
  • 단순 경로(simple path): 경로 중에서 반복되는 정점이 없는 경우
  • 사이클(cycle): 단순 경로의 시작 정점과 종료 정점이 동일한 경우

그래프(Graph)의 특징

  • 그래프는 네트워크 모델 이다.
  • 2개 이상의 경로가 가능하다.
    • 즉, 노드들 사이에 무방향/방향에서 양방향 경로를 가질 수 있다.
  • self-loop 뿐 아니라 loop/circuit 모두 가능하다.
  • 루트 노드라는 개념이 없다.
  • 부모-자식 관계라는 개념이 없다.
  • 순회는 DFS나 BFS로 이루어진다.
  • 그래프는 순환(Cyclic) 혹은 비순환(Acyclic)이다.
  • 그래프는 크게 방향 그래프와 무방향 그래프가 있다.
  • 간선의 유무는 그래프에 따라 다르다.

그래프(Graph)의 종류

무방향 그래프 VS 방향 그래프

무방향 그래프(Undirected Graph)

  • 무방향 그래프의 간선은 간선을 통해서 양 방향으로 갈 수 있다.
  • 정점 A와 정점 B를 연결하는 간선은 (A, B)와 같이 정점의 쌍으로 표현한다.
    • (A, B)는 (B, A) 동일
    • Ex) 양방향 통행 도로

방향 그래프(Directed Graph)

  • 간선에 방향성이 존재하는 그래프
  • A -> B로만 갈 수 있는 간선은 <A, B>로 표시한다.
    • <A, B>는 <B, A>는 다름
    • Ex) 일방 통행

가중치 그래프(Weighted Graph)

간선에 비용이나 가중치가 할당된 그래프
‘네트워크(Network)’ 라고도 한다.
Ex) 도시-도시의 연결, 도로의 길이, 회로 소자의 용량, 통신망의 사용료 등

연결 그래프 VS 비연결 그래프

연결 그래프(Connected Graph)

  • 무방향 그래프에 있는 모든 정점쌍에 대해서 항상 경로가 존재하는 경우
    • Ex) 트리(Tree): 사이클을 가지지 않는 연결 그래프

비연결 그래프(Disconnected Graph)

  • 무방향 그래프에서 특정 정점쌍 사이에 경로가 존재하지 않는 경우

사이클 VS 비순환 그래프

사이클(Cycle)

  • 단순 경로의 시작 정점과 종료 정점이 동일한 경우
    • 단순 경로(Simple Path): 경로 중에서 반복되는 정점이 없는 경우

비순환 그래프(Acyclic Graph)

  • 사이클이 없는 그래프

완전 그래프(Complete Graph)

  • 그래프에 속해 있는 모든 정점이 서로 연결되어 있는 그래프
  • 무방향 완전 그래프
    • 정점 수: n이면 간선의 수: n * (n-1) / 2

그래프(Graph)를 구현하는 두 방법

인접 행렬 (adjacent matrix) : 정방 행렬을 사용하는 방법

해당하는 위치의 value 값을 통해서 vertex 간의 연결 관계를 O(1) 으로 파악할 수 있다. Edge 개수와는 무관하게 V^2 의 Space Complexity 를 갖는다. Dense graph 를 표현할 때 적절할 방법이다.

인접 리스트 (adjacent list) : 연결 리스트를 사용하는 방법

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

그래프(Graph) 탐색

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

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

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

너비 우선 탐색 (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 로 구한 경로는 최단 경로이다.

References (참고 자료)

0개의 댓글