Graph
🍵 그래프 표현
인접 리스트로 그래프 표현
인접 리스트는 그래프를 표현하는 가장 효율적인 방법 중 하나로, 각 노드에 연결된 이웃 노드를 리스트로 저장합니다.
// 무방향 그래프
List<List<Integer>> graph = new ArrayList<>();
// n개의 노드를 가진 그래프 초기화
int n = 5;
for (int i = 0; i < n; i++) {
graph.add(new ArrayList<>());
}
// 간선 추가 (노드 1과 2가 연결)
graph.get(1).add(2);
graph.get(2).add(1);인접 행렬로 그래프 표현
인접 행렬은 노드 간의 연결 상태를 2차원 배열로 나타냅니다.
// n개의 노드를 가진 그래프 초기화
int n = 5;
int[][] graph = new int[n][n];
// 간선 추가 (노드 1과 2가 연결)
graph[1][2] = 1;
graph[2][1] = 1;🍵 DFS (Depth-First Search, 깊이 우선 탐색)
재귀를 사용한 DFS 구현:
void dfs(int node, boolean[] visited, List<List<Integer>> graph) {
visited[node] = true; // 현재 노드 방문 처리
System.out.println("Visited: " + node);
// 현재 노드에 연결된 다른 노드들을 재귀적으로 방문
for (int neighbor : graph.get(node)) {
if (!visited[neighbor]) {
dfs(neighbor, visited, graph);
}
}
}DFS 호출 예시:
int n = 5; // 노드 수
boolean[] visited = new boolean[n];
dfs(0, visited, graph); // 0번 노드부터 탐색 시작🍵 BFS (Breadth-First Search, 너비 우선 탐색)
큐를 사용한 BFS 구현:
void bfs(int start, List<List<Integer>> graph) {
Queue<Integer> queue = new LinkedList<>();
boolean[] visited = new boolean[graph.size()];
queue.add(start);
visited[start] = true;
while (!queue.isEmpty()) {
int node = queue.poll();
System.out.println("Visited: " + node);
for (int neighbor : graph.get(node)) {
if (!visited[neighbor]) {
visited[neighbor] = true;
queue.add(neighbor);
}
}
}
}🍵 사이클 찾기 (Cycle Detection in Graphs)
DFS를 사용한 사이클 찾기 (무방향 그래프)
boolean hasCycle(int node, int parent, boolean[] visited, List<List<Integer>> graph) {
visited[node] = true;
for (int neighbor : graph.get(node)) {
if (!visited[neighbor]) {
if (hasCycle(neighbor, node, visited, graph)) {
return true;
}
} else if (neighbor != parent) {
return true;
}
}
return false;
}🍵 최단 경로 (Shortest Path), Dijkstra
다익스트라 알고리즘 (Dijkstra's Algorithm)
우선순위 큐를 이용한 최단 경로 탐색:
public int[] dijkstra(int start, List<List<int[]>> graph, int n) {
int[] dist = new int[n];
Arrays.fill(dist, Integer.MAX_VALUE);
dist[start] = 0;
PriorityQueue<int[]> pq = new PriorityQueue<>((a, b) -> a[1] - b[1]);
pq.add(new int[] {start, 0});
while (!pq.isEmpty()) {
int[] current = pq.poll();
int node = current[0];
int distance = current[1];
if (distance > dist[node]) continue;
for (int[] neighbor : graph.get(node)) {
int nextNode = neighbor[0];
int weight = neighbor[1];
if (dist[node] + weight < dist[nextNode]) {
dist[nextNode] = dist[node] + weight;
pq.add(new int[] {nextNode, dist[nextNode]});
}
}
}
return dist;
}🍵 위상 정렬 (Topological Sorting)
BFS를 이용한 위상 정렬:
void topologicalSort(List<List<Integer>> graph, int n) {
int[] indegree = new int[n];
for (int i = 0; i < n; i++) {
for (int neighbor : graph.get(i)) {
indegree[neighbor]++;
}
}
Queue<Integer> queue = new LinkedList<>();
for (int i = 0; i < n; i++) {
if (indegree[i] == 0) {
queue.add(i);
}
}
List<Integer> topoOrder = new ArrayList<>();
while (!queue.isEmpty()) {
int node = queue.poll();
topoOrder.add(node);
for (int neighbor : graph.get(node)) {
indegree[neighbor]--;
if (indegree[neighbor] == 0) {
queue.add(neighbor);
}
}
}
// 위상 정렬 결과 출력
for (int node : topoOrder) {
System.out.print(node + " ");
}
}🍵 최소 신장 트리 (Minimum Spanning Tree)
크루스칼 알고리즘 (Kruskal's Algorithm)
Union-Find를 이용한 크루스칼 알고리즘 구현:
class Edge {
int src, dest, weight;
Edge(int src, int dest, int weight) {
this.src = src;
this.dest = dest;
this.weight = weight;
}
}
int find(int[] parent, int i) {
if (parent[i] == i) {
return i;
}
return parent[i] = find(parent, parent[i]);
}
void union(int[] parent, int[] rank, int x, int y) {
int rootX = find(parent, x);
int rootY = find(parent, y);
if (rank[rootX] > rank[rootY]) {
parent[rootY] = rootX;
} else if (rank[rootX] < rank[rootY]) {
parent[rootX] = rootY;
} else {
parent[rootY] = rootX;
rank[rootX]++;
}
}
void kruskal(List<Edge> edges, int n) {
Collections.sort(edges, (a, b) -> a.weight - b.weight);
int[] parent = new int[n];
int[] rank = new int[n];
for (int i = 0; i < n; i++) {
parent[i] = i;
rank[i] = 0;
}
List<Edge> mst = new ArrayList<>();
for (Edge edge : edges) {
int root1 = find(parent, edge.src);
int root2 = find(parent, edge.dest);
if (root1 != root2) {
mst.add(edge);
union(parent, rank, root1, root2);
}
}
// MST 결과 출력
for (Edge edge : mst) {
System.out.println(edge.src + " -- " + edge.dest + " == " + edge.weight);
}
}🍵 플로이드-워셜 알고리즘 (Floyd-Warshall Algorithm)
모든 쌍 최단 경로 탐색:
void floydWarshall(int[][] graph, int n) {
int[][] dist = new int[n][n];
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
dist[i][j] = graph[i][j];
}
}
for (int k = 0; k < n; k++) {
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
if (dist[i][k] != Integer.MAX_VALUE && dist[k][j] != Integer.MAX_VALUE
&& dist[i][k] + dist[k][j] < dist[i][j]) {
dist[i][j] = dist[i][k] + dist[k][j];
}
}
}
}
// 최단 경로 결과 출력
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
if (dist[i][j] == Integer.MAX_VALUE) {
System.out.print("INF ");
} else {
System.out.print(dist[i][j] + " ");
}
}
System.out.println();
}
}Last updated