Mendekati Struktur Data Graf menggunakan Javascript-tutorial js-php.cn

Mendekati Struktur Data Graf menggunakan Javascript

WBOY

Lepaskan： 2024-08-12 18:43:23

asal

514 orang telah melayarinya

Approaching Graphs Data Structure using Javascript

Satu senarai bersebelahan dan matriks bersebelahan ialah dua cara biasa untuk mewakili graf dalam sains komputer.

Senarai Bersebelahan:

Senarai bersebelahan mewakili graf sebagai tatasusunan senarai terpaut.
Indeks tatasusunan mewakili bucu dan setiap elemen dalam senarai terpautnya mewakili bucu lain yang membentuk tepi dengan bucu.

Kebaikan:

Cekap ruang untuk mewakili graf jarang (graf dengan tepi yang lebih sedikit).
Menambah bucu adalah lebih mudah.

Keburukan:

Kurang cekap untuk beberapa jenis pertanyaan, seperti menyemak sama ada tepi wujud antara dua bucu. Struktur data yang lebih kompleks.

Matriks Bersebelahan:

Matriks bersebelahan mewakili graf sebagai tatasusunan dua dimensi, di mana sel pada baris ke-i dan lajur ke-j menunjukkan tepi antara bucu i dan j.

Kebaikan:

Mudah untuk difahami dan dilaksanakan.
Cekap untuk graf padat (graf dengan lebih banyak tepi).
Cepat untuk menyemak sama ada satu tepi wujud antara dua bucu.

Keburukan:

Memerlukan lebih banyak ruang (O(V^2), dengan V ialah bilangan bucu). Menambah bucu ialah O(V^2), yang boleh menjadi lebih perlahan daripada senarai bersebelahan.

nota penting

Maklumkan penemuduga terlebih dahulu pendekatan mana yang akan anda ikuti dan beritahu dia kebaikan dan keburukan.

Graf Traversal

DFS (Carian Pertama Kedalaman) (Timbunan)
BFS (Breath First Search) (Baris Beratur)

Mencari jalan terpendek BFS adalah lebih baik

*Graf Berarah vs Tidak Berarah: *

Graf terarah, juga dipanggil digraf, ialah graf di mana setiap tepi mempunyai arah. Tepi menghala dari satu bucu ke bucu yang lain.
Graf tidak terarah ialah graf di mana tepi tidak mempunyai orientasi. Tepi (x, y) adalah sama dengan tepi (y, x).

Graf Berwajaran vs Tidak Berwajaran:

Graf berwajaran ialah graf di mana setiap tepi diberi pemberat atau kos. Ini berguna dalam masalah di mana bahagian tepi tertentu mempunyai kepentingan atau panjang yang berbeza.
Graf tidak berwajaran ialah graf di mana semua tepi mempunyai berat atau kos yang sama.

Gelung Kendiri:

Gelung kendiri ialah tepi yang menghubungkan bucu pada dirinya sendiri.

Graf Jarang lwn Padat:

A graf jarang ialah graf yang bilangan tepinya hampir dengan bilangan tepi minima. Dalam erti kata lain, terdapat sedikit tepi antara bucu.
Graf padat ialah graf yang bilangan tepinya hampir dengan bilangan tepi maksimum yang mungkin. Dalam erti kata lain, terdapat banyak tepi antara bucu.

Graf Kitaran lwn Asiklik:

Graf kitaran ialah graf yang mengandungi sekurang-kurangnya satu kitaran (laluan tepi dan bucu di mana bucu boleh dicapai dari dirinya sendiri).
Graf asiklik ialah graf tanpa kitaran. Jenis graf akiklik khas yang dipanggil pokok, ialah graf bersambung, tidak berarah tanpa kitaran.

// Weighted graph adjacency list would look like

{
1: [ {node: 2, weight: 50}, {node: 3, weight: 60}]
...
6: [{node: 1, weight: 40}, {node:5, weight:30 }, {node:4, weight: 90}]
}

Salin selepas log masuk

class Graph {
    constructor() {
        this.adjList = {};
    }

    addNode(value) {
        this.adjList[value] = []
    }

    addEdge(node1, node2) {
        this.adjList[node1].push(node2);
        this.adjList[node2].push(node1);
    }

    removeEdge(node1, node2) {
        this.removeElement(node1, node2);
        this.removeElement(node2, node1);
    }

    removeElement(node, value) {
        const index = this.adjList[node].indexOf(value);
        this.adjList[node] = [...this.adjList[node].slice(0, index), ...this.adjList[node].slice(index+1)];
    }

    removeNode(node) {
        const connectedNodes = this.adjList[node];

        for (let connectedNode of connectedNodes) {
            this.removeElement(connectedNode, node);
        }

        delete this.adjList[node];
    }
depthFirstTraversal(startNode) {
        const stack = [];
        const visited = {};

        stack.push(startNode);
        visited[startNode] = true;

        while(stack.length > 0) {
            const currentNode = stack.pop();
            const connectedNodes = this.adjList[currentNode];
            console.log(currentNode);
            connectedNodes.forEach(connectedNode => {
                if (!visited[connectedNode]) {
                    visited[connectedNode] = true;
                    stack.push(connectedNode);
                }
            })
        }
    }

    breathFirstTraversal(startNode) {
        const queue = [];
        const visited = {}

        queue.push(startNode);
        visited[startNode] = true;

        while(queue.length > 0) {
            const currentElement = queue.shift();
            const connectedNodes = this.adjList[currentElement];
            console.log(currentElement);
            connectedNodes.forEach(connectedNode => {
                if (!visited[connectedNode]) {
                    visited[connectedNode]=true;
                    queue.push(connectedNode);
                }
            });
        }
    }
}

const test = new Graph();

test.addNode(1);
test.addNode(2);
test.addNode(3);
test.addNode(4);
test.addNode(5);
test.addNode(6);
test.addEdge(1,2)
test.addEdge(1,3)
test.addEdge(1,6)
test.addEdge(2, 3);
test.addEdge(2, 5);
test.addEdge(2, 4);
test.addEdge(3, 4);
test.addEdge(3, 5);
test.addEdge(4, 5);
test.addEdge(4, 6);
test.addEdge(5, 6);
console.log('After adding all node and Edge --> ', test.adjList)

test.removeNode(4);

console.log('After Removing node 4 --> ', test.adjList)
console.log('----------Depth First Traversal -------------')
test.depthFirstTraversal(1);
console.log('----------Breath First Traversal -------------')
test.breathFirstTraversal(1);

/*
After adding all node and Edge -->  {
  '1': [ 2, 3, 6 ],
  '2': [ 1, 3, 5, 4 ],
  '3': [ 1, 2, 4, 5 ],
  '4': [ 2, 3, 5, 6 ],
  '5': [ 2, 3, 4, 6 ],
  '6': [ 1, 4, 5 ]
}
After Removing node 4 -->  {
  '1': [ 2, 3, 6 ],
  '2': [ 1, 3, 5 ],
  '3': [ 1, 2, 5 ],
  '5': [ 2, 3, 6 ],
  '6': [ 1, 5 ]
}
----------Depth First Traversal -------------
1
6
5
3
2
----------Breath First Traversal -------------
1
2
3
6
5
*/

Salin selepas log masuk

Atas ialah kandungan terperinci Mendekati Struktur Data Graf menggunakan Javascript. Untuk maklumat lanjut, sila ikut artikel berkaitan lain di laman web China PHP!