[javascript] javascript 위상정렬 알고리즘

위상정렬 알고리즘 with javascript

위상정렬 알고리즘?

위상 정렬(Topological Sort)은 사이클이 없는 방향 그래프(DAG, Directed Acyclic Graph)의 모든 노드(정점)를 방향성(간선)에 거스르지 않도록 순서대로 나열하는 알고리즘

• 주요 특징:
  • 사이클이 없는 방향 그래프 에서만 가능합니다 (사이클이 있으면 순서를 정할 수 없음).
    결과가 유일하지 않을 수 있음. (동시에 여러 개의 노드가 다음 순서로 올 수 있을 때)
  • 활용 예시: 작업 스케줄링(선행 작업이 있는 경우), 수강 순서, 빌드 시스템의 종속성 처리

위상 정렬 알고리즘 (BFS 기반)

• 위상 정렬은 주로 진입 차수(Indegree) 개념을 활용하는 Kahn의 알고리즘(큐 기반)으로 구현

• 진입 차수(Indegree): 특정 노드로 들어오는 간선의 개수. 즉, 그 노드가 처리되기 위해 완료되어야 하는 선행 작업의 개수

• 진입 차수 계산: 그래프의 모든 노드에 대해 진입 차수를 계산

• 초기 큐 삽입: 진입 차수가 0인 모든 노드를 큐(Queue)에 삽입합니다. 이 노드들은 선행 작업 없이 바로 시작할 수 있는 노드들

• 반복: 큐가 빌 때까지 다음을 반복

• 노드 추출: 큐에서 노드 u를 꺼냄. 이 노드 u는 위상 정렬 순서에 추가

• 간선 제거 효과: 노드 u에서 나가는 모든 간선 $(u, v)$에 대해, 간선이 제거되었다고 가정하고 노드 v의 진입 차수를 1 감소

• 새로운 시작 노드: 진입 차수가 0이 된 노드 v가 있다면, 이 노드 v를 큐에 삽입

• 결과 확인: 위상 정렬의 결과는 큐에서 노드를 꺼낸 순서.

• 만약 큐에서 꺼낸 노드의 개수가 전체 노드의 개수보다 적다면, 그래프에 사이클이 존재함을 의미.

function topologicalSort(numNodes, edges) {
    
    // 노드 번호가 1부터 시작한다고 가정하고, 크기를 numNodes + 1로 설정
    const adj = Array.from({ length: numNodes + 1 }, () => []); 
    
    // 진입 차수 배열: 각 노드로 들어오는 간선의 개수
    const indegree = new Array(numNodes + 1).fill(0);
    
    // 2. 그래프 및 진입 차수 구성
    for (const [u, v] of edges) {
        // u에서 v로 간선 추가
        adj[u].push(v);
        // v의 진입 차수 증가
        indegree[v]++;
    }

    // 3. 초기 큐 설정 (진입 차수가 0인 노드를 큐에 삽입)
    const queue = [];
    for (let i = 1; i <= numNodes; i++) {
        if (indegree[i] === 0) {
            queue.push(i);
        }
    }
    
    // 위상 정렬 결과 배열
    const result = [];
    let head = 0; // 큐의 인덱스를 관리 (shift() 대신 사용하여 성능 최적화)
    
    // 4. 위상 정렬 수행 (BFS)
   
    while (head < queue.length) {
        // 큐에서 노드 u를 꺼냄
        const u = queue[head++];
        // 결과를 저장
        result.push(u);
        
        // u와 연결된 모든 노드(v)에 대해
        for (const v of adj[u]) {
            // 간선 제거 효과: v의 진입 차수 감소
            indegree[v]--;
            
            // 진입 차수가 0이 되면 큐에 삽입 (이제 v를 처리할 수 있음)
            if (indegree[v] === 0) {
                queue.push(v);
            }
        }
    }

    // 5. 사이클 검증 및 결과 반환
    // 큐에서 꺼낸 노드(result.length)의 개수가 전체 노드 개수(numNodes)와 같지 않다면 사이클 존재
    if (result.length !== numNodes) {
        // 사이클이 존재하여 위상 정렬 불가능
        return null; 
    }
    
    // 위상 정렬 결과 반환
    return result;
}

// --- 예시 사용 ---
const numNodes = 7; // 노드 1부터 7까지
const edges = [
    [1, 2], [1, 5], 
    [2, 3], 
    [5, 6], 
    [3, 4], 
    [6, 4], 
    [4, 7]
];

const sortedOrder = topologicalSort(numNodes, edges);

if (sortedOrder) {
    console.log("위상 정렬 순서:", sortedOrder.join(" -> "));
    // 가능한 출력: 1 -> 2 -> 5 -> 3 -> 6 -> 4 -> 7
    // 또는 1 -> 5 -> 2 -> 6 -> 3 -> 4 -> 7 등 여러 순서가 가능
} else {
    console.log("사이클이 존재하여 위상 정렬을 수행할 수 없습니다.");
}

// --- 사이클이 있는 경우 테스트 ---
const numNodesWithCycle = 3;
const cycleEdges = [
    [1, 2],
    [2, 3],
    [3, 1] // 3 -> 1 간선이 사이클을 만듦
];

const sortedOrderCycle = topologicalSort(numNodesWithCycle, cycleEdges);
if (sortedOrderCycle === null) {
    console.log("사이클 테스트: 사이클이 존재하여 위상 정렬을 수행할 수 없습니다. (정상 동작)");
}