[C언어] graph - 개념편

Graph

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

G(V, E) 그래프에서의 표현으로 V는 정점 혹은 노드라고 불리며, E 노드간의 연결을 해주는 간선으로 나타난다.

 

그래프의 종류를 나뉘는 것을 보면

• 간선의 방향치양방향 혹은 한쪽 방향으로만 이동이 가능 
• 간선의 가중치간선마다 비용이나 가중치를 책정

 

방향 그래프 : G2, G4 와 같은 그래프로 모든 간선은 방향을 가지고 두 정점의 쌍으로 표현

무방향 그래프 : G1, G3 와 같은 그래프로 간선을 표현하는 두 정점의 쌍에 순서가 없다. 방향이 없는 그래프

 

 

인접 : 무방향 그래프 G1 에서 간선 (V0, V1)가 노드 V0와 V1은 서로 인접

부속 : 무방향 그래프 G1 에서 간선 (V0, V1)가 간선 (V0, V1)은 정점 V0와 V1의 부속이 됨

차수 : 하나의 정점에 연결되어 있는 간선의 개수

 

경로 : 간선을 따라갈 수 있는 길

단순 경로 : 모두 상이한 간선으로 이어져 있는 그래프

 

연결 : 방향 그래프 G에서 V(G)에 있는 서로 다른 모든 정점의 쌍u와 v에 대해 u에서 v까지의 방향 경로와 v에서 u까지의 방항경로가 있을때 강한 연결이라고 한다.  만일 이 때 u에서 v까지나 v에서 u까지 어느 하나의 경로만 있다면 약한 연결