[Algorithm] 그래프(Graph)

그래프 (Graph)

 

* 그래프 자료구조란

• 노드와 노드를 연결하는 간선으로 구성된 자료구조이다.
• 그래프의 순회는 DFS 혹은 BFS로 이루어진다.
• 노드 사이에 양방향 경로를 가질 수 있으므로, 2개 이상의 경로가 가능하다.
• 루트 노드, 부모-자식 관계가 존재하지 않는다.
• 아래와 같이 방향이 존재할 수도 있고, 존재하지 않을 수도 있다.

 

 

* 관련 용어

• 정점(vertex, node): 위치의 개념
• 간선(edge): 위치 간의 관계, 노드를 연결하는 선 (link, branch)
• 인접 정점(adjacent vertex): 간선에 의해 직접 연결된 정점
• 경로(path): 어느 한 정점에서 다른 정점 까지의 경로
• 싸이클(cycle): 단순 경로의 시작 정점과 종료 정점이 동일한 경우
• 단순 경로(Simple Path): 경로 중에서 반복되는 정점이 없는 경우
• 정점의 차수(degree): 무방향 그래프에서 하나의 정점에 인접한 정점의 수
• 진입 차수(in-degree): 유방향 그래프에서 외부에서 오는 간선의 수
• 진출 차수(out-degree): 유방향 그래프에서 외부로 향하는 간선의 수

 

* 그래프의 종류

• 무방향 그래프(Undirected Graph)
  • 간선에 방향성이 없는 그래프
  • 간선을 통해 양방향으로 갈 수 있다.
  • A <-> B 이므로 (A, B), (B, A)는 동일하다.
• 유방향 그래프(Directed Graph)
  • 간선에 방향성을 가진 그래프
  • 간선에 방향성이 존재하는 그래프이다.
  • A -> B, B -> A가 각각 존재하므로 (A, B), (B, A)는 다르다.
• 비순환 그래프(Acyclic Graph)
  • 사이클이 없는 그래프
• 연결 그래프
  • 무방향 그래프에 있는 모든 정점 쌍에 대해 항상 경로가 존재하는 경우
  • 트리는 사이클을 가지지 않는 연결 그래프이다.
• 비연결 그래프
  • 무방향 그래프에서 특정 정점 쌍 사이에 경로가 존재하지 않는 경우
• 완전 그래프
  • 그래프에 속해있는 모든 정점이 서로 연결되어 있는 그래프

 

* 그래프를 구현하는 방법

1. 인접 행렬 (adjacency matrix)

무방향

방향

• 인접 행렬은 그래프의 연결관계를 NxN의 boolean 행렬로 나타내는 방식으로 이차원 배열을 사용한다.
• adj[i][j]와 같이 정점 i에서 정점 j로 가는 간선이 있다면 1, 없다면 0으로 표시한다.

 

2. 인접 리스트(adjacency list)

• 그래프를 표현하는 가장 일반적인 방법이다.
• 모든 정점을 인접 리스트에 저장하는데, 이에는 ArrayList나 LinkedList를 사용한다.
• 정점의 번호를 알고있다면 이 번호를 배열의 인덱스로 하여 각 정점의 리스트에 쉽게 접근할 수 있다.

---

[참고한 곳]

kingpodo.tistory.com/46

gmlwjd9405.github.io/2018/08/13/data-structure-graph.html