고양이 두 잔

자료구조에서의 그래프는 굉장히 일반적인 개념이고 그 예가 많지만, 특정 기준을 이용해 둘로 나누면 아래와 같이 구분할 수 있다. 바로 무방향 그래프(G1)와 방향 그래프(G2)인데, 이와 같은 자료구조를 자바에 구현하는 방법은 크게 두 가지가 존재한다. 하나씩 알아보자. Adjacency Matrix 인접 행렬은 말 그대로 노드간의 관계를 행렬로 나타낸 것이다. 노드가 n개인 그래프의 인접행렬은 n X n 정사각 행렬이 되며, 인접한 경우엔 1, 그렇지 않은 경우엔 0을 채워 넣는다. 추가로 무방향 그래프의 경우엔 인접 행렬이 대칭을 이루고 있는 것이 특징이다. 방향 그래프의 경우엔 반드시 대칭 행렬을 이루지는 않는다. 인접 행렬의 장점은 노드 사이의 빠른 경로를 찾기 편하다는 점이며 단점은 간선의 유무..

Graph(그래프)는 노드 사이의 연결 관계를 표현할 수 있는 자료구조이다. 앞서 보았던 트리구조 역시 사실은 그래프의 일종인데, 두 구조의 차이는 아래와 같다. 구분 그래프(Graph) 트리(Tree) 정의 객체 혹은 노드(Node)와 그것을 연결하는 간선(Edge)으로 모인 구조 그래프의 한 종류 방향성이 없으며 순환하지 않음 방향성 무방향 혹은 유방향으로 가능 단방향 그래프 순환성 순환 가능 자기 자신을 연결하는 간선(Self-Loop) 가능 순환(Cyclic), 비순환(Acyclic) 그래프 모두 가능 순환 불가능 자기 자신을 연결하는 간선(Self-Loop) 불가능 비순환 그래프(Acyclic Graph) 루트 루트의 개념이 있거나 없을 수 있음 하나의 루트 노드 존재 모델 네트워크 모델 계층 ..