참고
그래프 (Graph)
NOTE
그래프 ⇒ 객체 간의 관계를 정점(Vertext)과 간선(Edge)으로 나타내는 자료구조!
ex) 지하철 노선도 (지하철역(정점), 선로(간선))
•
트리 구조에서 볼 수 있는 명확한 부모-자식 관계는 존재하지 않으며, 각 정점은 그 자체로 독립적인 존재로 다른 정점들과의 연결성을 통해 표현될 수 있다.
◦
ex) 소셜 네트워크 (사용자, 관계), 도로 네트워크, 인터넷
•
요약하면, 그래프는 정점(Vertext)와 간선(Edge)의 집합이다!
그래프 용어
NOTE
•
인접 (Adjacent)
◦
두 노드(정점) 사이에 간선이 존재할 경우, 두 노드는 서로 ‘인접’되어 있다고 말한다.
◦
ex) 노드 0과 1은 간선(0-1)에 의해 연결되므로 인접해 있다.
•
부속 (Incident)
◦
두 노드를 연결하는 간선은 해당 두 노드에 ‘부속’되어 있다고 한다.
◦
간선(0-1)은 노드 0과 1에 부속되어 있다.
•
차수 (Degree)
◦
하나의 노드에 부속된 간선의 개수를 그 노드의 차수라고 한다.
▪
무 방향 그래프 ⇒ 노드에 연결된 간선의 개수
▪
유 방향 그래프 ⇒ 노드로 들어오는 간선의 개수(진입차수), 노드로 나가는 간선의 개수(진출 차수)
•
경로 (Path)
◦
정점 A(출발지)에서 정점 B(목적지)로 이어지는 일련의 간선들을 의미한다.
◦
경로를 구성하는 간선의 개수를 경로의 길이라고 한다.
◦
단순 경로 ⇒ 동일한 노드를 중복하지 않는 경로
◦
사이클(Cycle) ⇒ 출발 노드와 도착 노드가 동일한 단순 경로를 의미한다.
•
루프 (Loop)
◦
그래프 내의 특정 노드에서 시작해서 동일한 노드로 끝나는 간선을 의미한다.
◦
단일 노드를 연결하는 간선
그래프 종류
NOTE
그래프의 종류는 정말로 다양하며, 일반적으로 간선의 특성에 따라 구분된다!
그래프의 종류는 정말로 다양하다.
무방향 그래프 & 방향 그래프
NOTE
간선에 방향이 있는가?
•
무방향 그래프
◦
간선에 방향이 없는 그래프다. (양방향)
◦
두 노드 A와 B 사이에 간선이 있다면, A B 로 볼 수 있다.
B 로 볼 수 있다.•
방향 그래프
◦
간선에 방향이 있는 그래프다. (단방향)
◦
두 노드 A와 B 사이에 간선이 있다면, A → B 또는 A ← B 로 볼 수 있다.
비가중 그래프 & 가중 그래프
NOTE
간선에 가중치(값)이 있는가?
•
비가중 그래프
◦
모든 간선들이 동일한 값을 가진 그래프다.
◦
보통 간선의 가중치에 대한 정보가 없거나 필요하지 않은 경우 사용된다.
•
가중 그래프
◦
간선이 가중치(값)을 가지는 그래프다.
◦
가중치는 비용, 길이, 거리 등 다양한 것을 나타낼 수 있다.
◦
일반적으로 방향 가중 그래프를 네트워크(Network)라고 부른다.
비순환 그래프 & 순환 그래프
NOTE
그래프에 Cycle이 있는가?
•
비순환 그래프(Acyclic Graph)
◦
그래프 내에 어떠한 사이클도 포함되어 있지 않은 그래프다.
◦
ex) Tree는 대표적인 비순환 그래프다. 모든 노드 사이에는 정확히 하나의 경로만 존재한다.
◦
의존성 구조, 계층 구조 등에서 비순환 그래프가 자주 사용된다.
•
순환 그래프(Cyclic Graph)
◦
그래프 내에 하나 이상의 사이클이 포함되어 있는 그래프다.
◦
ex) 소셜 네트워크 ( A-B , B-C, C-A 의 관계는 A-B-C-A 사이클이 형성된다.)
◦
ex) 통신 네트워크
그래프 표현
NOTE
그래프를 구현하는 대표적인 자료구조로는 인접 리스트(연결 리스트)와 인접 행렬(2차원 배열) 방식이 있다.
인접 행렬(Adjacency Matrix) 구현
NOTE
정점 * 정점 크기의 2차원 배열로 표현한다.
public class UndirectedGraph {
private int numberOfVertical;
private int[][] matrix;
public UndirectedGraph(int numberOfVertical) {
this.numberOfVertical = numberOfVertical;
this.matrix = new int[numberOfVertical][numberOfVertical];
}
public void addEdge(int start, int end){
matrix[start][end] = 1;
matrix[end][start] = 1;
}
public void removeEdge(int start, int end){
matrix[start][end] = 0;
matrix[end][start] = 0;
}
}
Java
복사
각 행렬의 원소 Matrix[i][j]는 i-j가 연결되어 있다면 1, 아니면 0으로 표시한다.
•
장점
◦
구현하기 쉽고, 두 정점 간의 연결 여부를 직관적으로 확인할 수 있다.
•
단점
◦
정점(Vertext)는 많지만 간선(Edge)가 적은 희소 그래프의 경우 비효율적이다.
◦
정점이 100개인데, 간선이 1개라면 1만개의 크기에서 단 하나만 사용하기 때문.
인접 리스트(Adjacency LIst) 구현
NOTE
정점 크기의 1차원 배열에, 연결 리스트 사용해서 표현한다.
public class UndirectedGraph {
private int numberOfVertical;
private List<Integer>[] matrix;
public UndirectedGraph(int numberOfVertical) {
this.numberOfVertical = numberOfVertical;
this.matrix = new LinkedList[numberOfVertical];
}
public void addEdge(int start, int end){
if(!matrix[start].contains(end)){
matrix[start].add(end);
matrix[end].add(start);
}
}
public void removeEdge(int start, int end){
if(matrix[start].contains(end)){
matrix[start].remove(end);
matrix[end].remove(start);
}
}
}
Java
복사
인접 리스트는 각 정점마다 해당 정점과 연결된 정점들의 리스트를 가진다.
•
장점
◦
연결리스트를 이용하여 인접 노드를 저장하는 방식은 메모리를 절약할 수 있다.
•
단점
◦
연결이 많아지면 효과가 떨어질 수 있다.
◦
모든 정점이 연결되어있다면 인접 리스트보다 더 많은 메모리를 사용할 수도 있다.
방향 가중치 그래프 (인접 리스트) 구현
NOTE
public class Graph {
private List<Vertex> vertices;
public Graph() {
this.vertices = new ArrayList<>();
}
public Vertex addvertex(int value){
Vertex vertex = new Vertex(value);
this.vertices.add(vertex);
return vertex;
}
public void addEdge(Vertex source, Vertex destination, int weight){
if(vertices.contains(source) || vertices.contains(destination)){
source.addEdge(destination, weight);
}
}
}
public class Vertex {
private int value;
private LinkedList<Edge> edges;
public Vertex(int value) {
this.value = value;
this.edges = new LinkedList<>();
}
public void addEdge(Vertex target, int weight){
Edge edge = new Edge(this, target, weight);
edges.add(edge);
}
}
public class Edge {
public Vertex source;
public Vertex destination;
public int weight;
public Edge(Vertex source, Vertex destination, int weight) {
this.source = source;
this.destination = destination;
this.weight = weight;
}
}
Java
복사
구조가 복잡하므로 클래스를 분리해서 구현한다.