September 16, 2019
Графы - JavaScript
Алгоритмы на графах.
Обход в глубину.
function dfs(graph, startVertex){ length = Object.keys(graph).length; let visited = new Array(length); let parent = new Array(length); for(let index = 0; index < length; index++){ visited[index] = false; parent[index] = null; } let stack = new Array(); visited[startVertex] = true; stack.push(startVertex); while(stack.length > 0){ vertex = stack.pop() graph[vertex].forEach( function(neighbor){ if(!visited[neighbor]){ visited[neighbor] = true; parent[neighbor] = vertex; stack.push(neighbor); } } ) } visited[startVertex] = false; return [visited, parent]; } graph = { 0: [1], 1: [], 2: [4, 5], 3: [1], 4: [], 5: [3], 6: [2, 5], 7: [5] } console.log(dfs(graph, 2));
Ответ:
[ [ false, true, false, true, true, true, false, false ], [ null, 3, null, 5, 2, 2, null, null ] ]
Обход в ширину
function bfs(graph, startVertex){ let length = Object.keys(graph).length; let visited = new Array(length); let parent = new Array(length); let stack = new Array(); for(let index = 0; index < length; index++){ visited[index] = false; parent[index] = null; } visited[startVertex] = true; stack.push(startVertex); while(stack.length){ vertex = stack.shift(); graph[vertex].forEach(neighbor => { if(!visited[neighbor]){ visited[neighbor] = true; parent[neighbor] = vertex; stack.push(neighbor); } }) } visited[startVertex] = false; return [visited, parent]; } graph = { 0: [1], 1: [], 2: [4, 5], 3: [1], 4: [], 5: [3], 6: [2, 5], 7: [5] } console.log(bfs(graph, 2));
Ответ:
[ [ false, true, false, true, true, true, false, false ], [ null, 3, null, 5, 2, 2, null, null ] ]
September 16, 2019, 09:49
0 views
0 reactions