[Algorithm] 그래프 Graph - 개념과 표현

무방향 그래프 G = (V, E)

• V : 노드(node) 혹은 정점(vertex)
• E : 노드쌍을 연결하는 에지(edge) 혹은 링크(link)
• 개체(object)들 간의 이진관계 표현
• n = |V|, m = |E|

인접 행렬 (adjacency matrix)

• 노드가 n개인 그래프를 nxn행렬로 표현 가능

인접 리스트 (adjacency list)

• 노드가 n개인 그래프를 크기가 n인 배열로 표현 가능
• 노드 개수는 에지의 갯수의 2배

---

방향 그래프 (directed Graph) G = (V, E)

• 에지 (u, v)는 u에서 v로의 방향을 가짐

인접 행렬과 인접 리스트

• 각 에지마다 방향이 있으므로 인접 행렬은 비대칭
• 인접 리스트는 m개의 노드를 가짐

---

가중치 그래프 (weighted Graph)

• 에지마다 가중치가 지정되어 있음

인접 행렬

• 에지의 존재 여부를 나타내는 값으로 1대신 에지의 가중치를 저장
• 에지가 없을 때 혹은 대각선
  • 특별히 정해진 규칙은 없지만, 그래프와 가중치가 의미하는 바에 따라서
  • 예시 : 가중치가 거리 혹은 비용을 의미하는 경우라면 에지가 없으면 무한대, 대각선은 0 으로 표기
  • 예시 : 가중치가 용량을 의미한다면 에지가 없을 때 0, 대각선은 무한대로 표기

---

경로와 연결성

• 무방향 그래프 G=(V, E)에서 노드 u와 노드 v를 연결하는 경로가 존재할 때 u와 v는 연결되어 있다고 말함
• 모든 노드 쌍들이 서로 연결되어 있으면 연결된(connected) 그래프라고 함
• 연결 요소 (connected component)