[자료구조] Graph

1.그래프 개념

그래프란?

• 그래프는 객체간의 관계를 Vertext와 Edge로 나타내는 자료구조
• Grap를 활용해서 표현 할 수 있는 것들
  • 소셜 네트워크
  • 도시-도시 네트워크
  • 인터넷

그래프 용어

• 인접 (Adjacent)
  • 인접: 두 노드(Vertax) 사이에 간선이 존재 할 경우
• 부속 (Incidnet)
  • 부속: 두 노드를 연결하는 간선은
• 차수 (Degree)
  • 차수: 한 노드에 부속된 간선의 개수
  • 무방향 그래프에서, 노드의 차수는 그 노드에 연결된 간선의 개수와 같습니다.
  • 진입차수(In-Degree): 방향 그래프에서 노드로 들어오는 간선의 개수
  • 진출차수(Out-Degree): 방향 그래프에서 노드에서 나가는 간선의 개수
• 경로 (Path)
  • 정점 A (출발지)에서 정점 B (목적지)로 이어지는 일련의 간선들을 의미
  • 경로 길이 : 경로를 구성하는 간선의 개수
  • 단순 경로 : 동일한 노드를 중복해서 포함하지 않는 경로
  • 사이클 : 그래프 내에서 시작노드와 종료 노드가 동일한 단순경로 의미
• 루프 (Loop)
  • 루프: 그래프 내의 특정 노드에서 시작해서 동일한 노드로 끝나는 간선 의미, 단일 노드 연결 간선

2.Graph 종류

일반적으로 간선의 특성에 따라서 그래프의 종류가 구분 됩니다.

무방향 그래프& 방향 그래프

• 무방향 그래프
  • 간선에 방향이 없는 그래프
  • 두노드 A와 B사이ㅔ 간선이 잇다면 A에서 B로의 연결과 B에서 A로의 연결이 가능하다.
• 방향 그래프
  • 간선에 방향이 있는 그래프
  • 두 노드 A와 B사이에 방향성을 갖는 간선이 있으며, 해당 방향으로만 연결 가능하다.비가중 그래프 & 가중 그래프
• 비가중 그래프
  • 모든 간선이 동일한 값을 가진 그래프.
• 가중 그래프
  • 간선이 가중치를 갖는 그래프
  • 이 값은 간선 사이의 '비용','길이','거리'등 다양한것을 나타낼 수 있습니다.
  • 무방향 가중 그래프 = 무방향 + 가중치
  • 방향 가중 그래프 = 방향 그래프 + 가중치비순환 그래프 & 순환 그래프
• 가중그래프는 노드 사이의 연결 관계에 추가로 비용 혹은 거리등의 추가 속성을 정의 할 수 있어 응용분야가 포괄적인 그래프 모델\

비순환 그래프 & 순환 그래프

• 비순환 그래프
  • 그래프 내에 어떠한 사이클이 포함 되어있지 않은 그래프
  • 트리는 가장 대표적인 비순환 그래프
  • 의존성 구조, 계층 구조 등에서 비순환 그래프는 자주 사용된다.
• 순환 그래프
  • 순환 그래프는 그래프 내에 하나 이상의 사이클이 존재
  • 소셜 네트워크 에서 친구 관계를 그래프로 나타낼 때, A와 B가 친구 B와 C가 친구, C와 A가 친구라면 A-B-C-A\

기타 그래프

• 연결 그래프 : 무방향 그래프에서 임의의 두 노드 사이에 경로가 항상 존재
• 비 연결 그래프 : 무방향 그래프에서 임의의 두 노드 사이에 경로가 존재 하지 않을 수 있는 그래프
• 완전 그래프 : 그래프 내의 모든 노드가 1:1 간선으로 연결 된 경우, 즉 연결 가능한 최대 간선 수를 가진 그래프
• 부분 그래프 : 원래 그래프에서 일부의 노드나 일부의 간선을 제외하면 만든 그래프를 부분 그래프라고한다.
• 다중 그래프; 두 노드 사이에 여러개의 간선이 있을 수 있는 그래프

3.Graph의 표현

인접 행렬 (Adjacency Matrix)

• 인접 행렬은 그래프의 정점들 간의 연결 관계를 2차원 배열 (v x v)로 표현하는 방식.
• 각 행렬의 원소 adjacencyMatrix[i][j]는 정점 i와 정점 j가 연결 되어있으면 1, 그렇지 않으면 0으로 표시합니다.
• 인접 행렬 표현 방법은 구현하기 쉽고, 두 정점 간의 연결 여부를 직관적으로 확인 할 수 있습니다.
• 단 정점은 많지만 간선이 적은 희소 그래프의 경우 비 효율적일 수 있습니다.

인접 리스트 (Adjacency List)

• 인접 리스트는 각 정점이 인접하고 있는 정점을 연결 리스트로 표현하는 방식입니다.
• 인접 행렬에서는 간선 저장을 통해 그래프를 표현 했다면, 인접 리스트는 각 정점마다 해당 점정과 연결된 정점들의 리스트를 가짐
• 연결 리스트를 이용하여 인접 노드를 저장하는 방식은 메모리를 절약 할 수 있습니다.
• 연결이 많아지면 효과과 떨어 질 수 있습니다.

4.Graph 구현하기

추상 데이터 타입

• 그래프를 사용해서 효율적인 알고리즘을 만들고 사용하기에 필요한 기본 적인 연산
• 데이터
  • numberOfVertices
  • numberOfEdges
  • LinkedList[] vertices
• 연산