Annäherung an die Datenstruktur von Diagrammen mit Javascript

Eine Adjazenzliste und eine Adjazenzmatrix sind zwei gängige Methoden zur Darstellung eines Graphen in der Informatik.

Adjazenzliste:

1. Eine Adjazenzliste stellt ein Diagramm als Array verknüpfter Listen dar.
2. Der Index des Arrays stellt einen Scheitelpunkt dar und jedes Element in seiner verknüpften Liste stellt die anderen Scheitelpunkte dar, die mit dem Scheitelpunkt eine Kante bilden.

Vorteile:

1. Platzsparend für die Darstellung dünn besetzter Diagramme (Diagramme mit weniger Kanten).
2. Das Hinzufügen eines Scheitelpunkts ist einfacher.

Nachteile:

1. Weniger effizient für einige Arten von Abfragen, z. B. die Überprüfung, ob eine Kante zwischen zwei Scheitelpunkten vorhanden ist. Komplexere Datenstruktur.

Adjazenzmatrix:

1. Eine Adjazenzmatrix stellt einen Graphen als zweidimensionales Array dar, wobei die Zelle in der i-ten Zeile und j-ten Spalte eine Kante zwischen den Eckpunkten i und j angibt.

Vorteile:

1. Einfach zu verstehen und umzusetzen.
2. Effizient für dichte Diagramme (Diagramme mit mehr Kanten).
3. Schnell prüfen, ob eine Kante zwischen zwei Eckpunkten vorhanden ist.

Nachteile:

1. Benötigt mehr Platz (O(V^2), wobei V die Anzahl der Eckpunkte ist). Das Hinzufügen eines Scheitelpunkts ist O(V^2), was langsamer sein kann als eine Adjazenzliste.

Wichtiger Hinweis

1. Informieren Sie den Interviewer vorab, welchen Ansatz Sie verfolgen werden und nennen Sie ihm/ihr die Vor- und Nachteile.

Graph Traversal

1. DFS (Depth First Search) (Stapel)
2. BFS (Breath First Search) (Warteschlange)

Es wäre besser, den kürzesten Weg BFS zu finden

*Gerichtete vs. ungerichtete Diagramme: *

1. Ein gerichteter Graph, auch Digraph genannt, ist ein Graph, bei dem jede Kante eine Richtung hat. Die Kanten zeigen von einem Scheitelpunkt zum anderen.

2. Ein ungerichteter Graph ist ein Graph, in dem Kanten keine Orientierung haben. Die Kante (x, y) ist identisch mit der Kante (y, x).

Gewichtete vs. ungewichtete Diagramme:

1. Ein gewichteter Graph ist ein Graph, in dem jeder Kante ein Gewicht oder Kosten zugewiesen wird. Dies ist nützlich bei Problemen, bei denen bestimmte Kanten unterschiedliche Bedeutung oder Länge haben.

2. Ein ungewichteter Graph ist ein Graph, in dem alle Kanten das gleiche Gewicht oder die gleichen Kosten haben.

Selbstschleife:

1. Eine Selbstschleife ist eine Kante, die einen Scheitelpunkt mit sich selbst verbindet.

Spärliche vs. dichte Diagramme:

1. Ein sparse Graph ist ein Graph, in dem die Anzahl der Kanten nahe an der minimalen Anzahl von Kanten liegt. Mit anderen Worten: Es gibt nur sehr wenige Kanten zwischen den Eckpunkten.

2. Ein dichter Graph ist ein Graph, in dem die Anzahl der Kanten nahe an der maximal möglichen Anzahl von Kanten liegt. Mit anderen Worten, es gibt viele Kanten zwischen den Eckpunkten.

Zyklische vs. azyklische Diagramme:

1. Ein zyklischer Graph ist ein Graph, der mindestens einen Zyklus enthält (einen Pfad aus Kanten und Scheitelpunkten, wobei ein Scheitelpunkt von sich selbst aus erreichbar ist).

2. Ein azyklischer Graph ist ein Graph ohne Zyklen. Eine besondere Art eines azyklischen Graphen, der Baum genannt wird, ist ein zusammenhängender, ungerichteter Graph ohne Zyklen.
   

// 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}]
}

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
*/

Das obige ist der detaillierte Inhalt vonAnnäherung an die Datenstruktur von Diagrammen mit Javascript. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!