자료구조/그래프

그래프의 표현 그래프를 표현하는 방법에는 여러 가지가 있다. 그래프의 크기가 어느 정도인지, 그리고 그래프를 어떻게 처리하는지에 따라 알맞은 자료 구조가 결정된다. 인접 리스트 인접 리스트(Adgacency list) 표현법은 그래프의 각 노드 x에 대한 인접 리스트, 즉 x에서 출발하는 간선이 있는 노드의 리스트를 관리한다. 인접 리스트는 그래프를 나타내는 가장 대중적인 방법이다. 인접 리스트를 ArrayList를 이중으로 이용하여 구현할 수있다. import java.util.ArrayList; public class GraphBasic { public static void main(String[] args) { ArrayList adj = new ArrayList(); for(int i = 0 ; ..

그래프(Graph)란? 그래프는 노드(node, 혹은 정점(vertex))와 그들을 잇는 간선(edge)으로 구성되어 있다. 경로(path)는 한 노드에서 그래프의 간선을 지나 다른 노드까지 가는 길을 의미한다. 경로의 길이는 경로에 포함된 간서의 개수이다. 예를 들어 1번 노드에서 5번 노드로 가는 길이가 3인 경로( 1 -> 3 -> 4 -> 5)가 나와 있다. 사이클(Cycle)은 처음 노드와 마지막 노드가 같은 경로를 의미한다. 예를 들어 1 -> 3 -> 4 -> 1로 구성된 사이클이 존재한다. 그래프의 모든 노드 간에 경로가 있는 경우를 연결 그래프(connected graph)라고 한다. 연결 그래프 연결 그래프가 아님 그래프의 연결된 부분을 컴포넌트(component)라고 표현한다. 연결 ..