그래프

그래프 정의

그래프는 다대다의 연결관계를 표현합니다. 정점들의 집합과 이들을 연결하는 간선들의 집합으로 구성된 자료구조입니다.

• 정점(Vertex) : 그래프의 구성요소로 하나의 연결점
  • 인접 정점 : 두 개의 정점 간 간선이 존재하면 인접하다고 함
• 간선(Edge) : 두 정점을 연결하는 선
• 차수(Degree) : 정점 하나에 연결된 간선의 수
• V 개의 정점을 갖는 그래프의 최대 간선의 수는 V * (V-1) / 2 (무향 그래프 - 양방향)

그래프 유형

• 무향 그래프(Undirected Graph) : 일방통행이 없는 양방향 그래프
• 유향 그래프, 방향 그래프(Directed Graph) : 하나의 간선이 하나의 방향만을 표현(화살표로 표현)
• 가중치 그래프(Weighted Graph) : 관계의 정도를 수치로 표현한 그래프 → 간선이 값을 갖고 있음
• 사이클 없는 유향, 방향 그래프(DAG, Directed Acyclic Graph) : 순환되지 않는 방향 그래프, 각 간선의 끝을 따라가면 원래의 정점으로 돌아오지 않음

• 완전 그래프 : 정점에 대해 가능한 모든 간선을 가진 그래프
• 부분 그래프 : 원래 그래프에서 일부의 정점이나 간선을 제외한 그래프
• 트리 : 싸이클 없는 무향 연결 그래프
  • 두 정점 사이에 유일한 경로가 존재
  • 하나의 루트 노드를 가짐
  • 각 정점은 최대 하나의 부모노드만을 가짐
  • 각 정점는 자식 정점(단말 노드)가 없거나 하나 이상 존재

경로

경로(Path)란 어떤 정점에서 시작하여 다른 정점으로 끝나는 순회로 두 정점 사이를 잇는 간선들을 순서대로 나열한 것을 말합니다.

• 단순 경로 : 경로 중 정점을 최대 한 번만 지나는 경로
• 순환 경로
  • 경로의 시작점과 끝점이 같음 또는
  • 경로에서 어떤 정점을 2번이상 거치는 경우

그래프의 표현

• 인접 행렬(Adjacent matrix)
  • 정점 중심
  • V * V 크기의 2차원 배열을 이용해서 간선 정보를 저장
    • 그래프가 가중치가 없다면 boolean 형으로 연결 정보를 표현
    • 가중치가 있다면 각 간선의 가중치를 배열로 저장
• 인접 리스트(Adjacent List)
  • 정점 중심
  • 각 정점마다 다른 정점으로 나가는 간선의 정보를 저장(일반적 그래프)
• 간선 리스트(Edge List)
  • 간선(시작 정점, 끝 정점)의 정보를 객체로 표현하여 리스트에 저장

인접 행렬

• V * V 정방 행렬
• 행 번호와 열 번호는 각 그래프의 정점에 대응
• 가중치가 없을 경우 연결정보만 저장, 가중치가 표현된다면 각 간선의 가중치를 표현

무향 그래프

• i 번째 행의 합 = i 번째 열의 합 = Vi의 차수

유향 그래프

• 행 i 의 합 = Vi의 진출 차수( 나가는 경우 )
• 열 i 의 합 = Vi의 진입 차수( 들어오는 경우 )

인접 행렬의 단점

• 희소그래프
  • 정점은 많지만 간선이 적은 그래프
  • 각 정점의 몇 개 없는 간선을 표현하기 위해 큰 크기의 배열이 필요함
  • 또한 각 정점의 탐색에서 모든 정점의 연결 경우를 탐색하기 위해 모든 행을 탐색하므로 시간복잡도 비효율
• 밀집 그래프
  • 정점은 적지만 간선이 많은 그래프(ex 완전 그래프)
  • 밀집 그래프를 표현하기 좋음

인접 리스트

• 각 정점에 대한 인접 정점들을 순차적으로 표현
• 하나의 정점에 대한 인접 정점들을 각각 노드로 하는 연결리스트로 저장

무향 그래프

유향 그래프

그래프 탐색

너비우선탐색(BFS)

너비우선 탐색은 탐색 시작점의 인접한 정점들을 먼저 모두 차례로 방문한 후에 방문했던 정점을 시작점으로 하여 다시 인접한 정점들을 차례로 방문하는 방식입니다. 따라서 선입선출 형태의 큐 자료구조를 활용하여 만듭니다.

탐색의 과정 중 정점에 도착한 경로가 있을 때, 해당 경로는 시작 정점과 해당 정점에 대한 최단 경로입니다.

깊이우선탐색(DFS)

시작 정점의 한 방향으로 갈 수 있는 경로가 있는 곳까지 깊이 탐색해가다가 더 이상 갈 곳이 없게 되면 가장 마지막에 만났던 갈림길 간선이 있는 정점으로 되돌아와서 다른 방향의 정점으로 탐색을 계속 반복하여 결국 모든 정점을 방문하는 순회 방법입니다.

가장 마지막에 만났던 갈림길의 정점으로 되돌아가서 탐색하므로 후입선출 구조로 구현합니다. 메모리 스택을 활용한 재귀 함수, 혹은 직접 스택에 탐색 내용을 사용합니다.