그래프 Graph
Graph
-
Graph는노드(정점)와엣지(간선)로 구성된 추상적인 자료 구조입니다. 그래프는 노드 간의 관계를 표현하며, 실제 세계의 다양한 현상을 모델링하는 데 사용됩니다. -
Graph는 데이터 구조에서 매우 중요합니다. 그래프를 사용하면 네트워크, 지도, 소셜 네트워크 등 다양한 실제 세계 문제를 해결할 수 있습니다. 따라서 그래프를 이해하고 구현하는 것은 데이터 구조와 알고리즘을 이해하는 데 매우 중요합니다. -
Graph는 다양한 용어로 구성됩니다.-
노드(정점)는 그래프의 꼭짓점입니다. -
엣지(간선)는 노드 간의 관계를 나타냅니다. -
방향성 그래프, 무방향성 그래프, 가중치 그래프, 비가중치 그래프 등 다양한 유형의 그래프가 있습니다.
-
-
Graph는인접 행렬과인접 리스트를 사용하여 표현할 수 있습니다.-
인접 행렬은이차원 배열로 표현됩니다. -
인접 리스트는연결 리스트로 표현됩니다.
-
Graph의 종류
-
방향성 그래프와무방향성 그래프-
그래프는
방향성이 있는 경우와 없는 경우로 구분할 수 있습니다. -
방향성 그래프는 엣지의 방향성이 정해져 있습니다. -
무방향성 그래프는 엣지의 방향성이 없습니다.
-
-
가중치 그래프와비가중치 그래프-
가중치 그래프는 엣지에 가중치(비용, 거리 등)가 할당된 그래프입니다. -
비가중치 그래프는 엣지에 가중치가 할당되지 않은 그래프입니다.
-
알고리즘
-
깊이 우선 탐색
DFSDepth-First Search-
그래프나 트리에서 깊이를 우선적으로 탐색하는 알고리즘입니다.
-
시작 노드에서 출발하여, 현재 방문한 노드와 인접한 노드들 중 한 개의 노드를 선택하여 깊이 들어가면서 탐색합니다.
-
선택한 노드에 더 이상 인접한 노드가 없으면 이전 노드로 돌아와서 다른 노드를 선택합니다.
-
이를 반복하여 모든 노드를 방문합니다.
-
스택
Stack이나 재귀 함수Recursive function를 이용하여 구현할 수 있습니다.
-
-
너비 우선 탐색
BFSBreadth-First Search-
그래프나 트리에서 너비를 우선적으로 탐색하는 알고리즘입니다.
-
시작 노드에서 출발하여, 현재 방문한 노드와 인접한 모든 노드를 큐
Queue에 넣습니다. -
큐에서 하나씩 꺼내면서 해당 노드와 인접한 노드를 다시 큐에 넣습니다.
-
이를 반복하여 큐가 비어질 때까지 모든 노드를 방문합니다.
-
-
최단 경로 알고리즘
-
최단 경로 알고리즘은
두 노드 간의 최단 경로를 찾는 알고리즘입니다. -
다익스트라 알고리즘과 벨만-포드 알고리즘 등이 있습니다.
-
-
다익스트라 알고리즘
Dijkstra's Algorithm-
최단 경로를 구하는 알고리즘 중 하나로, 음의 가중치가 없는 그래프에서 사용됩니다.
-
시작점으로부터 각 정점까지의 최단 경로를 구합니다.
-
다익스트라 알고리즘은 시작점에서 가장 가까운 노드부터 선택하면서 탐색을 진행합니다.
-
각 노드의 최단 거리를 저장하는 배열을 유지하면서, 아직 방문하지 않은 노드들 중에서 가장 최단 거리가 짧은 노드를 선택합니다.
-
선택한 노드와 연결된 모든 노드들의 최단 거리를 갱신합니다. 이를 모든 노드를 방문할 때까지 반복합니다.
-
다익스트라 알고리즘은 우선순위 큐(Priority Queue)를 이용하여 구현할 수 있습니다.
-
이 알고리즘은 음의 가중치가 없는 그래프에서 사용할 수 있기 때문에, 음의 가중치가 있는 경우에는 벨만-포드 알고리즘이나 A* 알고리즘을 사용해야 합니다.
-
구현
-
그래프 클래스 구현
- 그래프를 구현하기 위해 노드 클래스와 그래프 클래스를 구현해야 합니다.
- 노드 클래스는 노드의 값을 저장합니다.
- 그래프 클래스는 인접 리스트를 사용하여 그래프를 저장합니다.
-
DFS 구현
- 깊이 우선 탐색을 구현하기 위해 재귀 함수를 사용할 수 있습니다.
- 방문한 노드를 체크하기 위해 visited 배열을 사용합니다.
-
BFS 구현
- 너비 우선 탐색을 구현하기 위해 큐를 사용합니다.
- 방문한 노드를 체크하기 위해 visited 배열을 사용합니다.
-
최단 경로 알고리즘 구현
- 다익스트라 알고리즘을 구현하기 위해 우선순위 큐를 사용합니다.
DFS Depth-First Search
import java.util.ArrayList;
import java.util.Stack;
public class Graph {
private int V; // 정점의 개수
private ArrayList<Integer>[] adj; // 인접 리스트
// 생성자
public Graph(int v) {
V = v;
adj = new ArrayList[v];
for (int i = 0; i < v; ++i) {
adj[i] = new ArrayList<Integer>();
}
}
// 노드를 연결하는 함수
public void addEdge(int u, int v) {
adj[u].add(v);
}
// DFS 탐색
public void DFS(int v) {
boolean[] visited = new boolean[V];
Stack<Integer> stack = new Stack<Integer>();
visited[v] = true;
stack.push(v);
System.out.println("DFS 탐색 결과:");
while (!stack.isEmpty()) {
v = stack.pop();
System.out.print(v + " ");
for (int i : adj[v]) {
if (!visited[i]) {
visited[i] = true;
stack.push(i);
}
}
}
}
public static void main(String[] args) {
Graph g = new Graph(4);
g.addEdge(0, 1);
g.addEdge(0, 2);
g.addEdge(1, 2);
g.addEdge(2, 0);
g.addEdge(2, 3);
g.addEdge(3, 3);
g.DFS(2);
}
}BFS Breadth-First Search
import java.util.ArrayList;
import java.util.LinkedList;
import java.util.Queue;
public class Graph {
private int V; // 정점의 개수
private ArrayList<Integer>[] adj; // 인접 리스트
// 생성자
public Graph(int v) {
V = v;
adj = new ArrayList[v];
for (int i = 0; i < v; ++i) {
adj[i] = new ArrayList<Integer>();
}
}
// 노드를 연결하는 함수
public void addEdge(int u, int v) {
adj[u].add(v);
}
// BFS 탐색
public void BFS(int v) {
boolean[] visited = new boolean[V];
Queue<Integer> queue = new LinkedList<Integer>();
visited[v] = true;
queue.add(v);
System.out.println("BFS 탐색 결과:");
while (!queue.isEmpty()) {
v = queue.poll();
System.out.print(v + " ");
for (int i : adj[v]) {
if (!visited[i]) {
visited[i] = true;
queue.add(i);
}
}
}
}
public static void main(String[] args) {
Graph g = new Graph(4);
g.addEdge(0, 1);
g.addEdge(0, 2);
g.addEdge(1, 2);
g.addEdge(2, 0);
g.addEdge(2, 3);
g.addEdge(3, 3);
g.BFS(2);
}
}Dijkstra's Algorithm
import java.util.ArrayList;
import java.util.Arrays;
import java.util.PriorityQueue;
public class DijkstraAlgorithm {
private int V; // 정점의 개수
private ArrayList<Node>[] adj; // 인접 리스트
private int[] dist; // 최단 거리
// 노드 클래스
static class Node implements Comparable<Node> {
int v, weight;
public Node(int v, int weight) {
this.v = v;
this.weight = weight;
}
public int compareTo(Node n) {
return weight - n.weight;
}
}
// 생성자
public DijkstraAlgorithm(int v) {
V = v;
adj = new ArrayList[v];
for (int i = 0; i < v; ++i) {
adj[i] = new ArrayList<Node>();
}
dist = new int[v];
}
// 노드를 연결하는 함수
public void addEdge(int u, int v, int weight) {
adj[u].add(new Node(v, weight));
adj[v].add(new Node(u, weight));
}
// 다익스트라 알고리즘
public void dijkstra(int start) {
Arrays.fill(dist, Integer.MAX_VALUE); // 초기값으로 최대값을 지정
PriorityQueue<Node> pq = new PriorityQueue<Node>();
pq.add(new Node(start, 0));
dist[start] = 0;
System.out.println("다익스트라 알고리즘 결과:");
while (!pq.isEmpty()) {
int u = pq.poll().v;
for (Node n : adj[u]) {
int v = n.v;
int weight = n.weight;
if (dist[v] > dist[u] + weight) {
dist[v] = dist[u] + weight;
pq.add(new Node(v, dist[v]));
}
}
}
// 결과 출력
for (int i = 0; i < V; ++i) {
System.out.println("노드 " + i + "까지의 최단 거리: " + dist[i]);
}
}
public static void main(String[] args) {
DijkstraAlgorithm g = new DijkstraAlgorithm(6);
g.addEdge(0, 1, 5);
g.addEdge(0, 2, 1);
g.addEdge(1, 2, 2);
g.addEdge(1, 3, 3);
g.addEdge(2, 3, 6);
g.addEdge(2, 4, 4);
g.addEdge(3, 4, 2);
g.addEdge(3, 5, 7);
g.addEdge(4, 5, 1);
g.dijkstra(0);
}
}