Approche de la structure de données des graphiques à l'aide de Javascript

Une liste de contiguïté et une matrice de contiguïté sont deux façons courantes de représenter un graphique en informatique.

Liste de contiguïté :

1. Une liste de contiguïté représente un graphique sous la forme d'un tableau de listes chaînées.
2. L'index du tableau représente un sommet et chaque élément de sa liste chaînée représente les autres sommets qui forment une arête avec le sommet.

Avantages :

1. Espace efficace pour représenter des graphiques clairsemés (graphiques avec moins d'arêtes).
2. Ajouter un sommet est plus facile.

Inconvénients :

1. Moins efficace pour certains types de requêtes, comme vérifier si une arête existe entre deux sommets. Structure de données plus complexe.

Matrice de contiguïté :

1. Une matrice de contiguïté représente un graphique sous la forme d'un tableau bidimensionnel, où la cellule de la ième ligne et de la jième colonne indique une arête entre les sommets i et j.

Avantages :

1. Simple à comprendre et à mettre en œuvre.
2. Efficace pour les graphes denses (graphiques avec plus d'arêtes).
3. Vérifie rapidement si une arête existe entre deux sommets.

Inconvénients :

1. Nécessite plus d'espace (O(V^2), où V est le nombre de sommets). L'ajout d'un sommet est O(V^2), ce qui peut être plus lent qu'une liste de contiguïté.

note importante

1. Informez au préalable l'enquêteur quelle approche vous allez suivre et dites-lui les avantages et les inconvénients.

Traversée graphique

1. DFS (Recherche en profondeur d'abord) (Pile)
2. BFS (Recherche Breath First) (File d'attente)

Trouver le chemin le plus court BFS serait mieux

*Graphiques dirigés ou non : *

1. Un graphe orienté, également appelé digraphe, est un graphe où chaque arête a une direction. Les arêtes pointent d'un sommet à un autre.

2. Un graphe non orienté est un graphe dans lequel les arêtes n'ont pas d'orientation. Le bord (x, y) est identique au bord (y, x).

Graphiques pondérés et non pondérés :

1. Un graphique pondéré est un graphique dans lequel chaque arête se voit attribuer un poids ou un coût. Ceci est utile dans les problèmes où certaines arêtes ont une importance ou une longueur différente.

2. Un graphique non pondéré est un graphique dans lequel toutes les arêtes ont le même poids ou le même coût.

Auto-boucle :

1. Une auto-boucle est une arête qui relie un sommet à lui-même.

Graphiques clairsemés ou denses :

1. Un graphe clairsemé est un graphe dans lequel le nombre d'arêtes est proche du nombre minimal d'arêtes. En d'autres termes, il y a très peu d'arêtes entre les sommets.

2. Un graphe dense est un graphe dans lequel le nombre d'arêtes est proche du nombre maximum d'arêtes possible. En d'autres termes, il y a de nombreuses arêtes entre les sommets.

Graphiques cycliques vs acycliques :

1. Un graphe cyclique est un graphe qui contient au moins un cycle (un chemin d'arêtes et de sommets dans lequel un sommet est accessible depuis lui-même).

2. Un graphe acyclique est un graphe sans cycles. Un type spécial de graphe acyclique appelé arbre est un graphe connecté et non orienté sans cycles.
   

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

Ce qui précède est le contenu détaillé de. pour plus d'informations, suivez d'autres articles connexes sur le site Web de PHP en chinois!