[CS - 자료구조] 그래프 (Graph)

그래프 (Graph)

• 개념
  • 요소들이 서로 복잡하게 얽혀있는 연결 관계를 정점(vertex)과 간선(edge)으로 표현한 자료구조
  • 스택, 큐처럼 CS의 대표적인 자료구조 중 하나
  • 현실 세계의 많은 것들을 그래프로 나타낼 수 있어서 알고리즘 문제에 그래프 유형이 많음
  • cf) 트리 또한 그래프의 한 종류이며, 사이클이 허용되지 않는 그래프를 의미함

 

• 용어
  • 정점 (Vertex, Node)
    • 데이터가 저장되는 기본 원소
  • 간선 (Edge, Link)
    • 정점간의 관계를 나타내는 선
  • 인접 정점 (Adjacent Vertex)
    • 하나의 정점에서 간선으로 직접적으로 연결된 정점
  • 차수 (degree)
    • 각 정점에 연결되어 있는 간선의 수
    • 진입 차수 (in-degree) : 방향 그래프에서 해당 정점으로 외부에서 오는 간선의 수 진출 차수 (out-degree) : 방향 그래프에서 해당 정점에서 외부로 나가는 간선의 수
    • 간선 : 전지적 시점, 그래프 전체 선 개수 차수 : 1인칭 시점, 각 정점에 연결된 선 개수
  • 경로 (path)
    • 간선을 통해 갈 수 있는 길, 정점을 나열해서 표현
  • 경로의 길이 (length)
    • 경로를 구성하는 데 사용된 간선의 수
  • 단순 경로 (simple path)
    • 경로 중 반복되는 간선이 없는 경로
  • 사이클 (cycle)
    • 경로 중 시작 정점과 종료 정점이 같고, 단순 경로인 경로
    • 자기 자신한테 되돌아오면서, 중복되는 간선이 없어야 함

 

• 그래프 종류
  • 무방향 그래프 (Undirected Graph)
    • 정점과 간선 간에 방향성이 없는 그래프 → 양방향 이동 가능
  • 방향 그래프 (Directed Graph, Digraph)
    • 정점과 간선 간에 방향성이 존재하는 그래프 → 간선의 방향으로만 이동 가능
    • 방향 그래프에선 차수(degree)가 두 가지 종류(indegree & outdegree) 로 나뉨
  • 가중치 그래프 (Weighted Graph)
    • 간선에 비용(cost) 또는 가중치(weight) 정보가 담긴 그래프
    • 반대로 모든 간선의 가중치가 동일한 비가중치 그래프도 존재
  • 완전 그래프 (Complete Graph)
    • 모든 정점끼리 서로 간선으로 연결된 그래프

 

• 구현

각각 인접 행렬과 인접 리스트

 

• 그래프 탐색
  • 깊이 우선 탐색 (DFS, Depth First Search)
    • 그래프를 탐색하는 방법 중 하나로, 임의의 정점에 연결된 정점을 우선적으로 탐색해나가는 방식
    • 특정 노드에서 시작하여, 다음 분기(branch)로 넘어가기 전에 해당 분기를 완벽하게 (끝까지) 탐색하는 방식
    • 스택 (Stack)으로 구현
    • 시간복잡도 : O(V+E)
  • 너비 우선 탐색 (BFS, Breadth First Search)
    • 그래프를 탐색하는 방법 중 하나로, 임의의 정점에서 인접한 정점을 우선적으로 탐색해나가는 방식
    • BFS로 구한 경로가 최단 경로 (단, 모든 간선에 가중치가 없거나 같은 경우)
    • 큐 (Queue)로 구현
    • 시간복잡도 : O(V+E)

• •