algorithm 알고리즘 Graphs 그래프 Eulerian Path Algorithm 오일러 회로 알고리즘

[Algorithm] Graphs - Eulerian Path Algorithm

그레프 - 오일러 회로 알고리즘

Posted by lim.Chuck on October 11, 2024

Eulerian Path?

Eulerian Path는 그래프 이론에서, 그래프의 모든 간선을 정확히 한 번씩만 통과하는 경로를 의미합니다. 만약 출발점과 도착점이 동일하고 모든 간선을 한 번씩만 지나는 경우, 이를 Eulerian Circuit(오일러 회로)라고 부릅니다.

Eulerian Path가 존재하기 위한 조건은:

  1. 모든 정점은 연결되어 있어야 합니다.
  2. 차수가 홀수인 정점이 2개이거나, 홀수 차수의 정점이 없으면 오일러 경로가 존재합니다.
    • 차수가 홀수인 정점이 2개면 그 두 정점이 출발점과 도착점이 됩니다.
    • 차수가 모두 짝수면 그 경로는 Eulerian Circuit입니다.

사용 사례:

  • 우편 배달 경로 최적화: 모든 길을 정확히 한 번씩만 지나도록 배달 경로를 최적화하는 경우.
  • 도로 네트워크 관리: 유지보수를 위해 모든 도로를 한 번씩만 통과하는 경로 찾기.
  • 전기 회로: 회로 내 모든 연결을 한 번씩만 점검하는 패턴을 설계하는 데 사용.

JavaScript 코드 예제

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47

// 그래프의 모든 간선을 한 번씩만 통과하는 Eulerian Path를 찾는 함수
function findEulerianPath(graph) {
  const degrees = new Array(graph.length).fill(0);
  let oddCount = 0,
    startNode = 0;

  // 각 정점의 차수를 계산
  for (let u = 0; u < graph.length; u++) {
    for (let v of graph[u]) {
      degrees[u]++;
    }
    if (degrees[u] % 2 !== 0) {
      oddCount++;
      startNode = u;
    }
  }

  // 홀수 차수 정점이 0 또는 2개일 경우에만 Eulerian Path가 존재함
  if (oddCount !== 0 && oddCount !== 2) {
    return "Eulerian Path does not exist";
  }

  // DFS를 이용하여 Eulerian Path 찾기
  const result = [];
  function dfs(node) {
    while (graph[node].length > 0) {
      const nextNode = graph[node].pop();
      dfs(nextNode);
    }
    result.push(node);
  }

  dfs(startNode);
  return result.reverse();
}

// 예제 그래프: [정점1과 연결된 정점들]
const graph = [
  [1, 2], // 정점 0
  [0, 2, 3], // 정점 1
  [0, 1], // 정점 2
  [1, 4], // 정점 3
  [3], // 정점 4
];

const path = findEulerianPath(graph);
console.log("Eulerian Path:", path);

Rust 코드 예제

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50

use std::collections::HashMap;
use std::collections::VecDeque;

fn find_eulerian_path(graph: &mut HashMap<usize, VecDeque<usize>>) -> Vec<usize> {
    let mut degrees = vec![0; graph.len()];
    let mut odd_count = 0;
    let mut start_node = 0;

    // 각 정점의 차수를 계산
    for (&u, adj) in graph.iter() {
        degrees[u] = adj.len();
        if degrees[u] % 2 != 0 {
            odd_count += 1;
            start_node = u;
        }
    }

    // 홀수 차수 정점이 0 또는 2개일 경우에만 Eulerian Path가 존재함
    if odd_count != 0 && odd_count != 2 {
        return vec![]; // Eulerian Path가 존재하지 않음
    }

    let mut result = vec![];
    fn dfs(node: usize, graph: &mut HashMap<usize, VecDeque<usize>>, result: &mut Vec<usize>) {
        while let Some(next_node) = graph.get_mut(&node).unwrap().pop_front() {
            dfs(next_node, graph, result);
        }
        result.push(node);
    }

    dfs(start_node, graph, &mut result);
    result.reverse();
    result
}

fn main() {
    let mut graph = HashMap::new();
    graph.insert(0, VecDeque::from(vec![1, 2]));
    graph.insert(1, VecDeque::from(vec![0, 2, 3]));
    graph.insert(2, VecDeque::from(vec![0, 1]));
    graph.insert(3, VecDeque::from(vec![1, 4]));
    graph.insert(4, VecDeque::from(vec![3]));

    let path = find_eulerian_path(&mut graph);
    if path.is_empty() {
        println!("Eulerian Path does not exist");
    } else {
        println!("Eulerian Path: {:?}", path);
    }
}

사용 사례:

  1. 우편 배달 경로 최적화: 모든 길을 한 번씩만 지나가도록 경로를 구성하는 데 유용합니다.
  2. 네트워크 최적화: 전기 회로나 통신망에서 모든 연결을 한 번씩만 방문해야 할 때 사용합니다.
  3. 그래프 이론 연구: 그래프의 구조적 특성 분석에 활용됩니다.

Eulerian Path ?

The Eulerian Path in graph theory is a path that visits every edge of a graph exactly once. If the path starts and ends at the same vertex while visiting every edge exactly once, it is called an Eulerian Circuit.

Conditions for the existence of an Eulerian Path:

  1. All vertices must be connected.
  2. An Eulerian Path exists if the graph has exactly 0 or 2 vertices with an odd degree (the number of edges connected to a vertex).
    • If there are exactly 2 vertices with an odd degree, the path starts at one and ends at the other.
    • If all vertices have an even degree, the path is an Eulerian Circuit.

Use Cases:

  • Postal Route Optimization: Optimizing routes to ensure every street is visited exactly once.
  • Network Maintenance: Finding paths that visit every road or connection exactly once for maintenance.
  • Electrical Circuit Design: Ensuring all connections in a circuit are tested or used exactly once.

JavaScript Code Example

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47

// Function to find an Eulerian Path in a graph
function findEulerianPath(graph) {
  const degrees = new Array(graph.length).fill(0);
  let oddCount = 0,
    startNode = 0;

  // Calculate degrees of each vertex
  for (let u = 0; u < graph.length; u++) {
    for (let v of graph[u]) {
      degrees[u]++;
    }
    if (degrees[u] % 2 !== 0) {
      oddCount++;
      startNode = u;
    }
  }

  // Eulerian Path exists only if there are 0 or 2 odd degree vertices
  if (oddCount !== 0 && oddCount !== 2) {
    return "Eulerian Path does not exist";
  }

  // Use DFS to find Eulerian Path
  const result = [];
  function dfs(node) {
    while (graph[node].length > 0) {
      const nextNode = graph[node].pop();
      dfs(nextNode);
    }
    result.push(node);
  }

  dfs(startNode);
  return result.reverse();
}

// Example graph: [Vertices and their connections]
const graph = [
  [1, 2], // Vertex 0
  [0, 2, 3], // Vertex 1
  [0, 1], // Vertex 2
  [1, 4], // Vertex 3
  [3], // Vertex 4
];

const path = findEulerianPath(graph);
console.log("Eulerian Path:", path);

Rust Code Example

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50

use std::collections::HashMap;
use std::collections::VecDeque;

fn find_eulerian_path(graph: &mut HashMap<usize, VecDeque<usize>>) -> Vec<usize> {
    let mut degrees = vec![0; graph.len()];
    let mut odd_count = 0;
    let mut start_node = 0;

    // Calculate degrees of each vertex
    for (&u, adj) in graph.iter() {
        degrees[u] = adj.len();
        if degrees[u] % 2 != 0 {
            odd_count += 1;
            start_node = u;
        }
    }

    // Eulerian Path exists only if there are 0 or 2 odd degree vertices
    if odd_count != 0 && odd_count != 2 {
        return vec![]; // Eulerian Path does not exist
    }

    let mut result = vec![];
    fn dfs(node: usize, graph: &mut HashMap<usize, VecDeque<usize>>, result: &mut Vec<usize>) {
        while let Some(next_node) = graph.get_mut(&node).unwrap().pop_front() {
            dfs(next_node, graph, result);
        }
        result.push(node);
    }

    dfs(start_node, graph, &mut result);
    result.reverse();
    result
}

fn main() {
    let mut graph = HashMap::new();
    graph.insert(0, VecDeque::from(vec![1, 2]));
    graph.insert(1, VecDeque::from(vec![0, 2, 3]));
    graph.insert(2, VecDeque::from(vec![0, 1]));
    graph.insert(3, VecDeque::from(vec![1, 4]));
    graph.insert(4, VecDeque::from(vec![3]));

    let path = find_eulerian_path(&mut graph);
    if path.is_empty() {
        println!("Eulerian Path does not exist");
    } else {
        println!("Eulerian Path: {:?}", path);
    }
}

Use Cases:

  1. Postal Route Optimization: Finding a route to visit every street exactly once.
  2. Network Optimization: Useful in circuits or communication networks to visit each connection exactly once.
  3. Graph Theory Research: Used to analyze the structural properties of graphs.
FEATURED TAGS
git 알고리즘 algorithm js 기초 js 기초 문법 js 문법 자료구조 Data Structure Graphs React 그래프 러스트 rust 집합 Sets front 수학 정렬 Math Sorting 간단예제 문자열 Strings github AWS 이벤트 버블링 이벤트 캡처링 탐색 LLM MCP Searches 컴파일러 트리 AI Cloud Front Cursor MCP 사용법 bubbling capturing s3 개발자도구 광고 구글 자동색인 깃허브 광고 라이브러리 러스트 설치 리엑트 버킷 비교 사이트맵 아마존 예제 웹 접근성 이미지 업로드 최장 공통 부분수열 캐시 텍스트 프레임워크 AI통합 API Adsense Claude Compiler SQL SWC Speedy Web Compiler Trees js 변수 js 생성자함수 npm nuxt pipeline project management robots rust 구축 rust setting rust setup text utterances
FRIENDS