📚 Graph

노드와 간선으로 이루어져 있는 자료구조.

😵‍💫 성질

그래프 G=(V,E) 는

• 유한한 공집합이 아닌 Vertex의 집합 V와

• 서로 다른 Vertices의 쌍인 Edge의 집합 E로 이루어진다.

• adjacent : 두 Vertex가 Edge로 연결되어 있으면 adjacent하다.

• incident : Edge (0,1)은 두 노드 0, 1과 incident라고 하고, 0,1을 Edge (0, 1)의 endpoints 라고 한다.

• path : 노드 u에서 v까지 연결되어 있는 Edge의 집합. 길이는 원소의 수이다.

• cycle : 한 노드에서 출발해 같은 노드로 도착하는 path.

• non-cycle=simple : 길이가 3 이상이고 cycle이 없는 그래프를 simple이라고 한다.

• acyclic : simple cycle을 포함하지 않는 그래프

• degree : vertex에 연결된 Edge의 개수
• induced Graph : Vertex-induced와 edge-induced로 나눌 수 있다.
  Vertex-induced graph면 특정 노드들과 그를 양 끝점으로 삼는 Edges,
  Edge-induced면 특정 edge들과 그의 양 끝점인 vertex를 포함하는 Subgraph이다.

Weighted graph

간선에 가중치가 주어진 그래프.

Connected Graph

모든 쌍의 vertices 사이에 path가 존재한다면 connected라고 한다.
connect 그래프가 아니라면 두개 이상의 부분 그래프의 합집합이 되는데, 이 경우 각 연결된 부분 그래프를 Connected Component라고 한다.

Trees

Tree도 일종의 그래프라고 볼 수 있다.
차이점을 꼽자면

• degree : 트리에서는 child의 개수이지만 그래프에서는 edge의 개수이다.
• Tree는 cycle이 없으므로 반드시 acyclic하다.

Spanning tree

무방향 그래프 G에 대해, G의 모든 vertex를 포함하는 부분 그래프.

Directed Graph

• 간선에 방향이 주어지는 그래프.
• 간선을 나타내는 튜플이 순서를 가지게 되고, <u, v> 라면 u에서 v로 간선이 형성된다는 뜻.
• 이 때 u is adjacent to v, v is adjacent from u 라고 한다. 단순히 화살표의 방향을 생각하면 된다.
• u는 tail of <u, v>, v is head of <u, v>.
• in-degree는 vertex로 들어오는 간선의 개수, out-degree는 나가는 간선의 개수이다.

Underlying Graph

방향 그래프에서 방향을 제거한 무방향 그래프.
원래 digraph가 방향에도 불구하고 모든 노드 간 path가 존재한다면 strongly connected라고 하고, underlying graph만 connected라면 weakly connected라고 한다.

MultiGraph

한 vertex의 쌍에 대해 여러 간선이 존재할 수 있다.

• loop : 자기 자신을 가리키는 간선

PseudoGraph

loop이 허용되는 Multigraph이다.

💻 Implementation

대부분 그래프는 인접행렬이라는 것으로 구현한다.

인접행렬

인접행렬이란 위 그림처럼 <i, j> 간 간선이 존재한다면 [i][j]와 [j][i]에 모두 true 혹은 정수를 넣어주는 방법이다. 이를 통해 vertex 간 연결을 확인할 수 있다.

Directed Graph의 경우에는 <i, j>인 경우에만 [i][j]에 표시한다.
Weighted Graph의 경우 가중치만큼 표시하거나, 따로 행렬을 만들어서 가중치를 함께 보관하는 방법이 있다.

인접 리스트

인접 리스트도 같은 개념이지만, Linked List의 배열을 통해서 구현한다. i번째 요소는 i번째 vertex와 연결되어 있는 vertex를 연결 리스트의 형태로 담고 있다.

방향 그래프라면 adjacent to, from 식으로 다른 응용을 통해 저장할 수 있다.

인접 Multilist

[ v1, v2, link for v1, link for v2 ] 식으로 노드가 구성되어 있어 훨씬 적은 수의 포인터로 구현이 가능하다.