with with

- 그래프 노드와 노드를 연결하는 간선들로 이루어진 비 선형 자료구조로 트리와 다르게 패턴이 없다. 모든 노드가 1-1로 연결되어 있는 그래프를 완전 그래프 (Complete Graph)라 부르고, 원래 그래프에서 일부 간선을 제외한 그래프를 부분 그래프 (Subgraph)라 부른다. 그래프의 표현 방법은 인접 행렬 (Adjacency Matrix)과 인접 리스트 (Adjacency List)로 표현할 수 있는데, 인접 행렬로 표현시 구현이 쉽고, 특정 노드간의 인접 여부 확인이 빠르다는 장점이 있지만, 특정 노드와 인접한 모든 노드를 알고자 할 때, 모든 간선을 확인해야 하고, 구현상의 이유로 메모리 낭비가 발생한다는 단점이 있다. 반면에 인접 리스트로 표현시 메모리 효율적이고, 인접한 노드를 효율적으..

Graph 그래프는 트리와 마찬가지로 비 선형적 자료구조로 node와 노드를 잇는 link의 집합으로 구성된다. 트리와 가장 큰 차이점은 그래프의 노드는 어떠한 패턴으로 연결되도 상관 없다는 것이다. (심지어 비어있거나, 연결이 아예 안된 노드도 존재할 수 있음) 노드의 구현과 탐색에 앞서 노드의 용어부터 정리하고 가자. Path: vertex들의 순서나열. e.g. path of v0 to v2: e0 e1 / e0 e2 e3 e5 / e4 e5 / e4 e3 e2 e1 Cycle: 출발 vertex = 도착 vertex인 path Multiple edges: 같은 두 vertex 사이 2개 이상의 edge가 연결된 것. Simple Graph: loop, multiple edges가 없는 graph ..