[Algorithm] Graphs - Topological Sorting Algorithm - 하고싶은거하는

토폴로지 정렬 (Topological Sorting)

토폴로지 정렬(Topological Sorting)은 유향 비순환 그래프(DAG, Directed Acyclic Graph)에서 정점들을 순서대로 나열하는 방법입니다. 이 정렬 방식은 그래프의 간선이 u -> v일 때, 항상 정렬 순서에서 u가 v보다 앞에 나오는 것을 보장합니다. 즉, 그래프의 선행 관계를 유지하면서 모든 노드를 나열하는 것입니다.

주요 특징:

유향 그래프에서 사용되며, 사이클이 없는 그래프에서만 동작합니다.
프로세스 간의 의존성을 표현하거나, 과목 수강 순서와 같은 우선순위가 있는 작업을 나열할 때 사용됩니다.

JavaScript 예제 코드

// 위상 정렬을 수행하는 함수 (깊이 우선 탐색 방식)
function topologicalSortUtil(v, visited, stack, graph) {
  visited[v] = true;

  // 현재 노드의 모든 인접 노드를 탐색
  for (let i = 0; i < graph[v].length; i++) {
    const adjacent = graph[v][i];
    if (!visited[adjacent]) {
      topologicalSortUtil(adjacent, visited, stack, graph);
    }
  }

  // 탐색이 완료된 노드를 스택에 삽입
  stack.push(v);
}

// 그래프에 대한 위상 정렬 함수
function topologicalSort(graph) {
  const stack = [];
  const visited = new Array(graph.length).fill(false);

  // 모든 노드에 대해 위상 정렬 수행
  for (let i = 0; i < graph.length; i++) {
    if (!visited[i]) {
      topologicalSortUtil(i, visited, stack, graph);
    }
  }

  // 스택에서 요소를 역순으로 출력하여 위상 정렬 순서 얻기
  while (stack.length) {
    console.log(stack.pop() + " ");
  }
}

// 그래프 정의 (유향 비순환 그래프)
const graph = [
  [2, 3], // 노드 0에서 2, 3으로 가는 간선
  [3], // 노드 1에서 3으로 가는 간선
  [3], // 노드 2에서 3으로 가는 간선
  [], // 노드 3은 종착점
];

topologicalSort(graph);

Rust 예제 코드

use std::collections::VecDeque;

// 깊이 우선 탐색을 수행하여 위상 정렬 순서를 계산하는 함수
fn topological_sort_util(v: usize, visited: &mut Vec<bool>, stack: &mut VecDeque<usize>, graph: &Vec<Vec<usize>>) {
    visited[v] = true;

    // 현재 노드의 인접한 노드들을 모두 탐색
    for &adj in &graph[v] {
        if !visited[adj] {
            topological_sort_util(adj, visited, stack, graph);
        }
    }

    // 스택에 노드를 삽입 (후입선출 방식)
    stack.push_front(v);
}

// 위상 정렬을 수행하는 함수
fn topological_sort(graph: &Vec<Vec<usize>>) -> Vec<usize> {
    let mut stack = VecDeque::new();
    let mut visited = vec![false; graph.len()];

    // 각 노드에 대해 DFS를 수행
    for i in 0..graph.len() {
        if !visited[i] {
            topological_sort_util(i, &mut visited, &mut stack, graph);
        }
    }

    // 스택에 저장된 위상 정렬 순서를 벡터로 반환
    stack.into_iter().collect()
}

fn main() {
    // 그래프 정의 (유향 비순환 그래프)
    let graph = vec![
        vec![2, 3],    // 노드 0에서 2, 3으로 가는 간선
        vec![3],       // 노드 1에서 3으로 가는 간선
        vec![3],       // 노드 2에서 3으로 가는 간선
        vec![]         // 노드 3은 종착점
    ];

    let result = topological_sort(&graph);
    for node in result {
        print!("{} ", node);
    }
}

사용처:

작업 스케줄링: 여러 작업 간의 의존 관계가 있는 프로젝트에서 각 작업을 어떤 순서로 해야 할지를 결정할 때 유용합니다.
컴파일러 최적화: 컴파일러는 코드가 실행되기 전에 변수나 함수의 의존성을 분석하고, 어떤 순서로 코드를 실행해야 할지를 결정할 때 사용합니다.
수강 과목 결정: 학문의 이수 조건이 있을 때, 어떤 과목을 먼저 들어야 할지 정하는데 유용합니다.

토폴로지 정렬은 의존 관계가 존재하는 여러 작업을 적절한 순서로 배치해야 할 때 필수적으로 사용됩니다.

Topological Sorting

Topological sorting is a way to arrange vertices in a directed acyclic graph (DAG) in a linear order, such that for every directed edge u -> v, vertex u comes before vertex v. It ensures that precedence relationships between vertices (or tasks) are preserved.

Key Characteristics:

Used for directed acyclic graphs (DAG).
Commonly applied to problems where tasks have dependencies, like task scheduling, course prerequisites, or process execution.

JavaScript Example Code

// Function to perform topological sorting using DFS
function topologicalSortUtil(v, visited, stack, graph) {
  visited[v] = true;

  // Visit all the adjacent vertices
  for (let i = 0; i < graph[v].length; i++) {
    const adjacent = graph[v][i];
    if (!visited[adjacent]) {
      topologicalSortUtil(adjacent, visited, stack, graph);
    }
  }

  // Push the current node to the stack after visiting all its adjacent nodes
  stack.push(v);
}

// Main function to perform topological sorting
function topologicalSort(graph) {
  const stack = [];
  const visited = new Array(graph.length).fill(false);

  // Perform the sort for each unvisited vertex
  for (let i = 0; i < graph.length; i++) {
    if (!visited[i]) {
      topologicalSortUtil(i, visited, stack, graph);
    }
  }

  // Print the topological order by reversing the stack
  while (stack.length) {
    console.log(stack.pop() + " ");
  }
}

// Graph representation (DAG)
const graph = [
  [2, 3], // Node 0 -> Nodes 2, 3
  [3], // Node 1 -> Node 3
  [3], // Node 2 -> Node 3
  [], // Node 3 has no outgoing edges
];

topologicalSort(graph);

Rust Example Code

use std::collections::VecDeque;

// Function to perform DFS for topological sorting
fn topological_sort_util(v: usize, visited: &mut Vec<bool>, stack: &mut VecDeque<usize>, graph: &Vec<Vec<usize>>) {
    visited[v] = true;

    // Visit all adjacent vertices
    for &adj in &graph[v] {
        if !visited[adj] {
            topological_sort_util(adj, visited, stack, graph);
        }
    }

    // Push the vertex to the stack once all its adjacent vertices are visited
    stack.push_front(v);
}

// Main function for topological sorting
fn topological_sort(graph: &Vec<Vec<usize>>) -> Vec<usize> {
    let mut stack = VecDeque::new();
    let mut visited = vec![false; graph.len()];

    // Call DFS for each unvisited vertex
    for i in 0..graph.len() {
        if !visited[i] {
            topological_sort_util(i, &mut visited, &mut stack, graph);
        }
    }

    // Convert the stack into a vector to return the topological order
    stack.into_iter().collect()
}

fn main() {
    // Define a directed acyclic graph (DAG)
    let graph = vec![
        vec![2, 3],    // Node 0 -> Nodes 2, 3
        vec![3],       // Node 1 -> Node 3
        vec![3],       // Node 2 -> Node 3
        vec![]         // Node 3 has no outgoing edges
    ];

    let result = topological_sort(&graph);
    for node in result {
        print!("{} ", node);
    }
}

Use Cases:

Task Scheduling: When tasks have dependencies, topological sorting helps determine the order in which tasks should be completed.
Compiler Optimization: Compilers analyze variable and function dependencies to determine the order of code execution.
Course Prerequisites: In education, topological sorting can help determine the sequence of courses to be taken based on prerequisite dependencies.

Topological sorting is essential when you need to organize tasks with dependencies into a valid sequence for execution.

[Algorithm] Graphs - Topological Sorting Algorithm

그레프 - 토폴로지 알고리즘