[C언어] 그래프의 개요

그래프란?

연결되어 있는 객체 간의 관계를 표현할 수 있는 자료구소

[ex] 지하철 자료구조

 

그래프 용어

Vertex(정점): node를 나타냄

Edge(간선): Vertext간의 관계를 나타내는 선(Vertex를 연결해줌)

Adjacent vertex : 어느 vertex에 대해 edge 로 연결된 vertex(A's adjacent vertex ->B,C,D / B's adjacent vertex -> A, C)

Degree: edge의 개수

Cycle: 시작 vertex로 다시 돌아오는 그래프( 시작 vertex=도착vertex)

Completed Graph: 모든 vertex들이 다른 vertex들과 모두 연결된 그래프, edege의 개수=n(n-1)/2 (n은 vertex 개수)

그래프의 개요

그래프의 종류

Undirected Graph: 방향성이 없는 그래프

Directed Graph: 방향성이 있는 그래프

Weighed Graph: Edge 마다 가중치가 존재하는 그래프