Графы - JavaScript

Алгоритмы на графах.

Обход в глубину.

function dfs(graph, startVertex){
    length = Object.keys(graph).length;
    
    let visited = new Array(length);
    let parent = new Array(length);
    
    for(let index = 0; index < length; index++){
        visited[index] = false;
        parent[index] = null;
    }
    
    let stack = new Array();
    
    visited[startVertex] = true;
    stack.push(startVertex);
        
    while(stack.length > 0){
        vertex = stack.pop()
        graph[vertex].forEach(
            function(neighbor){
                if(!visited[neighbor]){
                    visited[neighbor] = true;
                    parent[neighbor] = vertex;
                    stack.push(neighbor);
                }
            }
        )
    }
    visited[startVertex] = false;
    return [visited, parent];
}

graph = {
    0: [1],
    1: [],
    2: [4, 5],
    3: [1],
    4: [],
    5: [3],
    6: [2, 5],
    7: [5]
}


console.log(dfs(graph, 2));

Ответ:

[ [ false, true, false, true, true, true, false, false ],
  [ null, 3, null, 5, 2, 2, null, null ] ]

Обход в ширину

function bfs(graph, startVertex){
    let length = Object.keys(graph).length;
    let visited = new Array(length);
    let parent = new Array(length);
    let stack = new Array();
    
    for(let index = 0; index < length; index++){
        visited[index] = false;
        parent[index] = null;
    }
    
    visited[startVertex] = true;
    stack.push(startVertex);
    while(stack.length){
        vertex = stack.shift();
        graph[vertex].forEach(neighbor => {
            if(!visited[neighbor]){
                visited[neighbor] = true;
                parent[neighbor] = vertex;
                stack.push(neighbor);
            }
        })
    }
    visited[startVertex] = false;
    return [visited, parent];
}

graph = {
    0: [1],
    1: [],
    2: [4, 5],
    3: [1],
    4: [],
    5: [3],
    6: [2, 5],
    7: [5]
}

console.log(bfs(graph, 2));

Ответ:

[ [ false, true, false, true, true, true, false, false ],
  [ null, 3, null, 5, 2, 2, null, null ] ]