Graph란,
연결되어 있는 객체 간의 관계를 표현하는
비선형 자료구조
가장 일반적인 자료구조 형태
그래프의 예
트리(Tree)
지도, 지하철 노선도
전기회로의 연결 상태
OS의 프로세스와 자원 관계
인맥지도
그래프 역사
오일러 문제 (1800년대)
다리를 한 번만 건너서 처음 출발했던 장소로 돌아오는 문제
위치: 정점(node) / 다리: 간선(edge)
오일러 정리
모든 정점에 연결된 간선의 수가 짝수이면 오일러 경로가 존재함.
그래프 정의
그래프 G는 (V, E)로 표시함 : G = (V, E)
정점(Vertices) 또는 노드(Node)
여러 가지 특성을 가질 수 있는 객체 의미
(그래프 구성 기본단위)
자료 저장 • 객체 표현
V(G) : 그래프 G의 정점들의 집합
간선(Edge) 또는 링크(Link)
정점들 간의 관계
를 의미함.
방향, 가중치를 가질 수 있음.
E(G) : 그래프 G의 간선들의 집합
그래프 종류
간선의 종류에 따라
무방향 그래프 (Undirected Graph)
방향 그래프 (Directed Graph)
간선을 통해서 양방향으로 갈 수 있음.
간선을 통해서 한 쪽 방향으로만 갈 수 있음. (일방통행)
(A, B)로 표현
<A, B>로 표현
(A, B) = (B, A)
<A, B> ≠ <B, A>
가중치 그래프 (Weighted Graph)
네트워크(Network)
간선에 비용(Cost)이나 가중치(Weight)가 할당된 그래프
부분 그래프
정점 집합 V(G)와 간선 집합 E(G)의 부분 집합으로 이루어진 그래
그래프 표현
