자료구조 그래프(Graph)와 그래프의 종류 알아보기

자료구조 그래프와 그래프의 종류 알아보기

 

그래프(Graph)는 무엇인가?

• 그래프는 노드와 간선(Edge) 의 집합이다.
  • G = (V, E)
•  그래프는 비선형(non-linear) 자료구조이다.

 

트리와 그래프의 차이

트리와 그래프

• 트리의 특징
  • 루트 노드가 존재한다
  • 루트 노드를 제외한 데이터들은 서브 트리로 구분된다.
  • 트리는 아래쪽으로 확장된다.
  • 트리는 반드시 연결되어 있어야 한다.
  • 루프를 포함하지 않는다.
• 그래프의 특징
  • 그래프의 정점은 다른 다양한 다른 정점과 연결될 수 있다.
  • 간선에 가중치를 설정할 수 있다.
  • 간선은 방향을 가지거나 가지지 않을 수 있다.

 

그래프의 용어

그래프의 예시

• 정점 (Vertex) - 그래프에서 각각의 노드는 정점을 의미한다.
• 간선 (Edge) - 간선은 두 정점을 잇는 선을 의미한다.

• 인접 (Adjacency) - 두 정점이 간선을 통해 연결되어 있으면 두 정점은 인접한다고 할 수 있다.
• 경로 (Path) - 경로는 두 정점을 잇는 간선의 순서(Sequence)이다.
  • 경로 길이 (Path length) - 경로를 구성하는 간선의 개수를 경로 길이라고 한다.
    • ABDE 의 경로 길이는 3
  • 단순 경로 (Simple path) - 경로를 구성하는 노드중에 같은 노드가 없다면 단순 경로이다.
  • 순환 (Cycle) - 경로의 시작노드와 마지막 노드가 같다면 순환이다.
  • 비순환 (Acyclic) - 경로의 시작 노드와 마지막 노드가 같지 않다면 비순환

그래프의 경로

• 차수 (Degree) - 정점에 연결되어 있는 간선의 개수를 차수라 한다.
  • 방향 그래프 (Directed graph) 에서
    • 진입차수(in-degree) - 노드에 들어오는 간선의 개수
    • 진출차수(out-degree) - 노드에서 나가는 간선의 개수
• 루프 (loop) - 그래프의 한 노드에서 자기 자신으로 이어지는 간선이 있을때 그 간선을 루프라고 한다.

루프

그래프의 종류

• 무방향 그래프 (Undirected graph)
  • 두 노드를 연결하는 간선에 방향이 없는 그래프
  • 두 노드의 양방향으로 이동 가능하다.
  • 간선은 (Vi, Vj) 또는 (Vj, Vi)로 표현 가능

무방향 그래프

• 방향 그래프 (directed graph)
  • 두 노드를 연결하는 간선에 방향이 있는 그래프
  • 두 노드에서 특정한 방향으로만 이동 가능하다.
  • 간선은 (Vi, Vj) 로 표현

방향 그래프

• 가중 그래프 (weighted graph)
  • 노드를 연결하는 간선에 가중치(Weight)가 있는 그래프이다.
  • 네트워크(Network) 라고도 한다.

• 완전 그래프 (Complete graph)
  • 그래프의 모든 정점이 1:1 간선으로 연결된 그래프이다.
  • 모든 노드가 서로 연결되어 있어 추가할 간선이 없다.
  • 연결 가능한 최대 간선 수를 가진다.
  • 최대 간선 수
    • 무방향 그래프: n(n-1) / 2, n은 노드의 개수
    • 방향 그래프: n(n-1)

• 다중 그래프 (Multi graph)
  • 두 정점 사이에 여러개의 간선이 연결되어 있다.

• 부분 그래프 (Sub-graph)
  • 원래의 그래프에서 간선을 제외하여 만든 그래프.
  • G2 는 G1의 부분 그래프이다.

• 연결 그래프 (Connected graph)
  • 모든 정점 사이에 경로가 존재하는 그래프이다.
  • 한 노드에서 어떤 노드로든 이동이 가능하다.

• 비연결 그래프 (Disconnected graph)
  • 모든 정점 사이에 경로가 하나라도 존재하지 않는 그래프