그래프

자료 구조 목차

• Data-Structure
  • Linear
    • Static
      • Array
    • Dynamic
      • Linked List
      • Stack
      • Queue
  • Non Linear
    • Tree
    • Graph

그래프(Graph)

자료 구조의 끝은 아니지만 처음에 적은 기본적인 자료 구조 중 마지막까지 왔다. 마지막으로는 그래프에 대해서 짧게 설명하고 이후에는 해당 자료 구조를 이용한 문제 풀이를 해나갈까한다.

그래프는 두 가지의 요소를 갖고 있는데 아래와 같다.

1. 유한한 정점(또는 노드)들의 모임
2. (u, v)의 형태로 짝을 이룬 유한한 모임을 엣지(edge)라고 한다. 엣지는 방향도 표현하기 때문에 유향 그래프에서는 (u, v)와 (v, u)는 다르다. (u, v)는 정점 u에서 다른 정점인 v까지 도달 할 수 있는 연결선인 것이다.

위와 같은 성질을 갖고 있다. 흔한 예를 들어본다면 웹사이트의 페이지끼리의 연관성을 표현할 때에도 자주 사용된다.

그래프의 종류

무방향 그래프(Undirected Graph)

방향 그래프(Directed Graph)

가중치 그래프(Weighted Graph)

연결 그래프(Connected Graph)

비연결 그래프(Disconnected Graph)

사이클(Cycle)

비순환 그래프(Acyclic Graph)

완전 그래프(Complete Graph)