Graph

Graph의 정의

• 여러개의 점들이 서로 복잡하게 연결되어 있는 관계를 표현한 자료구조
• 복잡한 네트워크 망의 형

Graph의 구조

• 직접적인 관계가 있는 경우 두 점을 이어주는 선이 있다.
• 간접적인 관계는 몇 개의 점과 선에 걸쳐 이어진다.
• 정점(vertex) : 그래프에서 하나의 점
• 간선(Edge) : 그래프에서 하나의 선

Graph의 표현 방식

• 두 정점을 이어주는 간선이 존재하면 두 정점은 인접한 관계이다.

인접 행렬

• 서로 다른 정접들이 인접한 상태인지를 표시한 2차원 배열 형태의 행렬
• 이어져있다면 1(true), 그렇지 않다면 0(false)로 표시한다.

예시

• A의 진출차수는 1개 입니다: A —> C

  • [0][2] == 1

• B의 진출차수는 2개 입니다: B —> A, B —> C

  • [1][0] == 1
  • [1][2] == 1

• C의 진출차수는 1개입니다: C —> A

  • [2][0] == 1

인접 행렬을 사용하는 경우

• 두 정점 사이에 관계가 있는지, 없는지 확인할 때 용이하다.
• 가장 빠른 경로를 찾고자 할 때 주로 사용
  

인접 리스트

• 각 정점이 어떤 정점과 인접하는지를 리스트 형태로 표현
• 각 정점마다 하나의 리스트를 가지고 있으며, 이 리스트는 자신과 인접한 다른 정점을 담고 있다.

예시

B와 이어진 A, C의 순서는 중요하지 않다.
리스트로 구현할 때, 우선순위를 고려하여 나열할 수 있다.

인접 행렬을 사용하는 경우

• 메모리를 효율적으로 사용하고 싶을 때
  • 인접 행렬은 연결 가능한 모든 경우의 수를 저장하기 때문에 상대적으로 많은 메모리를 차지

Graph의 사용되는 용어

• 정점(vertex) : 노드(Node)라고도 하며 데이터가 저장되는 그래프의 기본 원소
• 간선(edge) : 정점 간의 관계(정점을 이어주는 선)
• 인접 정점(adjacent vertex) : 하나의 정점에서 간선에 의해 직접 연결되어 있는 정점
• 진입차수 (in-degree) / 진출차수 (out-degree) : 한 정점에 진입하고 진출하는 간선이 몇 개인지를 표현하는 것
• 자기 루프(self loop) : 정점에서 진출하는 간선이 곧바로 자기 자신에게 진입하는 경우(다른 정점을 거치지 않는다.)
• 사이클(Cycle) : 한 정점에서 출발하여 다시 해당 정점으로 돌아가는 것

Graph의 종류

• 가중치 그래프(weighted Graph) : 연결의 강도(추가적인 정보)가 적혀 있는 그래프
• 비가중치 그래프(unweighted Graph) : 연결의 강도가 적히지 않은 그래프
• 무(방)향 그래프(undirected graph) : 방향이 나타나지 않은 그래프
  • 무방향일 경우 양방향으로 통행이 가능하다
• 방향 그래프(directed graph) : 방향을 가지는 그래프(정해진 방향으로만 이동이 가능)
• 완전 그래프 : 모든 정점이 간선으로 연결되어 있는 그래프

Graph의 탐색

• 그래프는 배열처럼 정렬되어 있지 않기 때문에 원하는 자료를 찾기 위해서는 특정한 방법을 사용해야 한다.
• 하나의 정점을 시작으로 차례대로 모든 정점을 한 번씩 방문하는 것
  

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

• 루트 노드(혹은 다른 임의의 노드)에서 시작해서 다음 분기(branch)로 넘어가기 전에 해당 분기를 완벽하게 탐색하는 방법
• 하나의 정점에서 시작해 해당 경로를 끝까지 탐색한 후, 다음 경로로 넘어가 탐색하는 방법

BFS (Breadth-First Search) : 너비 우선 탐색

• 루트 노드(혹은 다른 임의의 노드)에서 시작해서 인접한 노드를 먼저 탐색하는 방법

Graph의 메서드

메서드	설명
setGraph(size)	그래프에 size만큼의 버텍스를 추가
getGraph()	인접 행렬 정보가 담긴 배열을 반환
addEdge(from, to)	fromVertex와 toVertex 사이의 간선을 추가
hasEdge(from, to)	fromVertex와 toVertex 사이의 간선이 존재하는지 여부를 Boolean으로 반환
removeEdge(from, to)	fromVertex와 toVertex 사이의 간선을 삭제