Graph : 그래프

이전 글에서 트리를 다룬적이 있다. 그래프랑 트리는 노드와 간선을 필요한 컴포넌트를 갖고 논하는 자료구조이지만,
그 사용 목적에서 중요한 차이 때문에 많은 사람들은 구분해놓고 사용하곤 한다.

트리는 일종의 계층적인 영역에 가깝고, 그래프는 연결을 표현하는데에 보다 최적화되어있다.

• 이 문장에 바로 감이 안온다면, 트리는 조직도, 그래프는 카카오톡 등록 상태를 사람 단위로 나눠 본다고 생각해보자.

그래프의 특징에 대해 정리해보겠다.

• 트리보다 일반적이다. 노드와 간선으로 데이터를 연결한다는 점은 공통점이다.
• 간선은 방향이 있는경우, 없는경우로 나뉜다. 이것을 Directed, Undirected로 나눌 수 있다.
• 사이클이 허용된다. 그렇기 때문에 트리보다 더 복잡한 상태를 나타낼 수 있다.
  • 사이클은 시작 노드에서 출발해, 간선을 따라 이동하다가 자기 자신으로 돌아오는 경우를 말한다.
    즉, 사이클은 그래프 내에서 순환이 발생하는 구조를 말한다.
    • Directed, Undirected 상태가 사이클 생성에 대해서도 영향을 끼칠 수 있다.
      • Directed, 방향이 정해져 있는 경우
        간선의 방향을 고려한다. 간선의 방향에 맞게 움직이면서 순환을 형성 할 수 있다.
        
      • Undirected, 방향이 정해져 있지 않은 경우
        간선의 방향이 정해져 있지 않으니, 순환을 형성하기가 더 쉬워진다.
    • 사이클의 유형은 보통 세 가지가 있다 :
      • 단순 사이클 : 노드와 간선이 중복되지 않는다. 단, 사이클 조건 상 시작 노드는 중복된다.
      • 하밀턴 사이클 : 그래프의 모든 노드를 한 번씩 방문하며, 시작 점으로 돌아오는 경로를 말한다.
      • 오일러 사이클 : 그래프의 모든 간선을 한 번 씩 지나며, 시작 점으로 돌아오는 경로를 말한다.
        
        
      • 사실 단순 사이클 하의 하밀턴, 오일러, 둘 다 아닌 유형 정도로 나뉘는 느낌이다.
        다시 말해 하밀턴 사이클이면서 단순 사이클일 수 있다.
• 그래프는 반드시 모든 노드가 연결 될 필요는 없다. 다시 말해, 분리된 노드가 충분히 있을 수 있다.
• 그래프는 복잡한 연결 관계, 최단 경로 탐색 등에 사용하게 된다.

특징	Tree	Graph
구조	계층적 구조	일반적인 노드-간선 연결
사이클	X	O
루트 노드	X	O
연결성	모든 노드가 연결 되어 있다.	분리된 요소가 존재 할 수 있다.
사용 목적	계층적 관리	복잡한 관계, 네트워크 표현

일반적 논하기

G(V, E) : Graph G는 V(vertex set)와 E(edge set)으로 이루어져 있다.

그리고 edge set을 어떻게 입력하냐에 따라 directed 여부를 결정하게 된다.

• Undirected graph, 대칭 그래프
  • 왜 대칭이라고도 부를 수 있을까? 그건 edge (a, b) = (b, a)
    edge에 방향이 없어 (a, b)를 (b, a)로 나타내도 상관 없는 그래프를 의미한다.
• Directed graph, 비대칭 그래프
  • 앞 설명을 들었다면 바로 잡을 수 있는 감, edge (a, b) != (b, a)
• 문제로 자주 출제되는 가중 그래프
  • 간선에 가중치가 존재하는 경우를 가중 그래프라고 한다. 위의 두 그래프 개념과 양립 할 수 있는 개념이다.

 

코드로 어떳개 하나요?

노드는 하나의 정점으로, 노드의 갯수만큼의 공간이 있다면 가능하다.
간선은 두 노드 사이를 잇기 때문에, 간선 1개의 표기는 노드 2개로 표현 할 수 있다.

이렇게 살펴본 노드와 간선의 특징에 따라 그래프를 표현하면 다음과 같이 3가지 방법이 제시된다 :

1. 인접 리스트 (Adjacency List)
   • 이 방법은 노드의 개수만큼 공간을 확보 한 뒤에, 각 노드를 기준으로 연결된 노드를 저장하는 방법이다.
2. 인접 행렬 (Adjacency Matrix)
   • 이 방법은 노드의 갯수를 제곱한 값 만큼의 행렬을 만든 후에 간선을 표현 하는 방식이다.
3. 간선 리스트 (Edge List)
   • 이 방법은 간선의 정보만을 표현하는 방식으로 간선에 대한 정보만을 저장하는 방식이다.

이 간단한 그래프를 각 방법으로 표시하기

인접 리스트 형식의 경우

인접 행렬의 경우. 우측은 양방향일 때이다.

간선 리스트. 아래 줄은 양방향을 의도 할 때 사용한다.

가중치 그래프에서 이러한 배치를 사용하겠다면, 데이터에 가중치의 추가가 필요하다.

언재 어떳개 쓰면 됩니까?

각 상황마다 좋은 방법이 있다고 한다.

인접 리스트
그래프를 코드로 표현한다고 하면 이 방법을 기본으로 생각한다. 탐색에 있어 보다 편리하기 때문이다.
인접 리스트는 다익스트라 알고리즘에서 사용되는 주된 표현 방식이기도 하다.

인접 행렬
인접 행렬같은 경우는 어떤 간선이 존재하는지에 대한 빠른 확인이 필요 할 때 사용한다.
graphMat[A][B]라면 A-B 경로를 순식간에 확인 할 수 있다.
인접 행렬은 플로이드-워셜 알고리즘에서 쓰인다.

간선 리스트
간선 리스트는 간선들을 기준으로 무언가를 처리해야 할 때 쓰면 된다.
코딩 테스트에서는 덜 다룬다는데, 벨만 포드 알고리즘에서 사용 하기 때문에 알아두면 도움이 될 수 있다.

https://gliver.tistory.com/35 참고