Cet article est une simple partie du graphique où nous faisons simplement du BFS et du DFS Traversal en utilisant les deux approches graphiques
- en utilisant la matrice adjacente (BFS)
- en utilisant une liste adjacente (DFS)
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 | 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++) {
if (adjMatrix[value][j] && visited.indexOf(j) < 0) {
q.push(j);
visited.push(j);
}
}
}
console.log(path);
}
BFS();
|
Copier après la connexion
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 | 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();
|
Copier après la connexion
Pour un article plus détaillé sur Graph, n'hésitez pas à consulter le lien ci-dessous.
Structure des données graphiques utilisant Javascript
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!