[TIL] 그래프- 개념

그래프(Graph)

• 실제 세계의 현상이나 사물을 정점Vertex(노드)와 간선Edge으로 표현하기 위해 사용
• 루트 노드, 부모/자식의 개념이 존재하지 않음

 

용어

• 정점(Vertex)/노드(Node) : 위치
• 간선(Edge)/link/branch : 위치 간의 관계를 표시한 선
• 인접 정점(Adjacent Vertex) : 간선으로 직접 연결된 정점
• 정점의 차수(Degree) : 무방향 그래프에서 하나의 정점에 인접한 정점의 수
• 진입 차수(In-Degree) : 방향 그래프에서 외부에서 오는 간선의 수
• 진출 차수(Out-Degree) : 방향 그래프에서 외부로 향하는 간선의 수
• 경로 길이(Path Length) : 경로를 구성하기 위해 사용된 간선의 수
• 단순 경로(Simple Path) : 처음/끝 정점을 제외하고 중복된 정점이 없는 경로
• 사이클(Cycle) : 단순경로에서 시작/종료 정점이 동일한 경우

 

종류

1. 무방향 그래프(Undirected Graph) : 방향X, 노드의 양방향 이동 가능

  * A,B가 연결되어 있을 경우 (A,B) 또는 (B,A)

    1-1. 연결그래프(Connected Graph): 모든 노드에 대해 항상 경로가 존재

    1-2. 비연결 그래프(Disconnected Graph) : 특정 노드에 대해 경로가 존재하지 않음

 

2. 방향 그래프(Directed Graph) : 방향O

  * A->B가 연결되어 있을 경우 <A,B>

3. 가중치 그래프(Weighted Graph)/네트워크(Network) : 간선에 비용/가중치가 할당

4. 비순환 그래프(Acyclic Graph) : 사이클이 없는 그래프

5. 완전 그래프(Complete Graph) : 그래프의 모든 노드가 서로 연결