[자료구조] Graph

윤석진·2022년 1월 27일
0
post-thumbnail

🖇 Graph

  • 연결되어 있는 객체 간의 관계를 표현하는 자료구조

Graph의 구조

  • vertices(정점)
    = node
    여러 가지 특성을 가질 수 있는 객체

    V(G): 그래프 G정점들의 집합

  • edge(간선)
    = link
    정점들 간의 관계

    E(G): 그래프 G간선들의 집합

Graph vs Tree

GraphTree
방향성방향, 무방향방향
순환가능불가능
루트 노드루트 노드의 개념이 없음한 개의 루트 노드만 존재
부모-자식부모-자식의 개념이 없음부모-자식 관계
모델네트워크 모델계층 모델
순회DFS, BFSDFS, BFS 안의 Pre-, In-, Post-order
간선의 수그래프의 따라 다름노드가 N인 트리는 항상 N-1의 간선을 가짐

Graph의 종류

  • 무방향 그래프
  • 방향 그래프

Graph의 경로

  • 무방향 그래프의 정점 s부터 e까지의 경로
  • simple path
    경로 중에서 반복되는 간선이 없는 경로
  • cycle
    단순 경로의 시작 정점과 종료 정점이 동일한 경로

Graph의 차수

무방향 그래프의 차수

  • 하나의 정점에 연결된 다른 정점의 수

방향 그래프의 차수

  • 진입 차수(in-degree): 외부에서 가리키는 간선의 수
  • 진출 차수(out-degree): 외부로 향하는 간선의 수
  • 방향 그래프의 모든 진입(진출) 차수의 합 = 간선의 수

Weighted Graph

= Network

  • 간선에 비용(cost)이나 가중치(weight)가 할당된 그래프

Subgraph

  • 본래의 그래프의 일부 정점 및 간선으로 이루어진 그래프

Connected Graph

  • 모든 정점쌍에 대하여 항상 경로가 존재하는 무방향 그래프

Complete Graph

  • 모든 정점이 연결되어 있는 그래프
  • n개의 정점을 가진 무방향 완전그래프의 간선의 수: n * (n - 1) / 2

Graph의 구현

adjacent matrix

  • 간선(i, j)가 그래프에 존재하면 M[i][j] = 1,
    그렇지 않으면 M[i][j] = 0으로 표현한다.
0111
1010
1101
1010

adjacent list

  • 각 정점에 인접한 정점들을 연결 리스트로 표현한다.

0 → 1 → 2 → 3
1 → 1 → 2
2 → 0 → 1 → 3
3 → 0 → 2

profile
공부하며 쓰는 블로그

0개의 댓글