Nur BFS und DFS in Graph mit Javascript

Dieser Artikel ist ein einfacher Teil des Diagramms, in dem wir lediglich BFS- und DFS-Traversal unter Verwendung beider Diagrammansätze durchführen

1. unter Verwendung der angrenzenden Matrix (BFS)
2. Verwenden einer Adjacent List (DFS)

const adjMatrix = [
    [0, 1, 1, 0, 0],
    [1, 0, 0, 1, 0],
    [1, 0, 0, 0, 1],
    [0, 1, 0, 0, 1],
    [0, 0, 1, 1, 0]
];

const BFS = () => {
    const q = [0];
    const visited = [0];
    let path = '';

    while(q.length) {
        const value = q.shift();
        path += value;

        for(let j = 0; j< adjMatrix.length; j++) {
// j Means the Node present / not in visited List
            if (adjMatrix[value][j] && visited.indexOf(j) < 0) {
                q.push(j);
                visited.push(j);
            }
        }
    }
    console.log(path);
}

BFS();

// 01234

const adjList = {
    0: [1, 2],
    1: [0, 3],
    2: [0, 4],
    3: [1, 4],
    4: [2, 3]
}

const DFS = () => {
    const stack = [0];
    const visited = [0];
    let path = '';

    while(stack.length) {
        const value = stack.pop();
        path += value;

        for(let item of adjList[value]) {
            if (visited.indexOf(item) < 0) {
                stack.push(item);
                visited.push(item);
            }
        }
    }
    console.log(path);
}

DFS();// 02431

Einen ausführlicheren Artikel über Graph finden Sie unter dem folgenden Link.

Diagrammdatenstruktur mit Javascript

Das obige ist der detaillierte Inhalt vonNur BFS und DFS in Graph mit Javascript. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!