0
116
ViewsMatriz de JavaScript DFS pero siempre vuelve a la raíz después de buscar
Me gustaría obtener la salida de la entrada.
Se debe pasar de todas las formas posibles, pero no se debe pasar por el camino que ya se visitó.
Se parece a la búsqueda primero en profundidad, pero esto debe devolverse al nodo principal y luego buscar nuevamente.
La lógica es que el último elemento de un nodo debe ser el mismo que el primer elemento de otro nodo.
Y debe comenzar con 0 y terminar cuando no haya más nodos para buscar.
input = [ [0, 1], [0, 2], [1, 5], [2, 6], [2, 12], [5, 29], [6, 29], [9, 30], [12, 18], [18, 29], [29, 9], [29, 12], [29, 18] ]; output = [ [0,1,5,29,9,30], [0,1,5,29,12,18,29,18], [0,1,5,29,12,18,29,9,30], [0,1,5,29,18,29,9,30], [0,1,5,29,18,29,12,18], [0,2,6,29,9,30], [0,2,6,29,12,18,29,9,30], [0,2,6,29,12,18,29,18], [0,2,6,29,18,29,9,30], [0,2,6,29,18,29,12,18], [0,2,12,18,29,9,30], [0,2,12,18,29,12], [0,2,12,18,29,18] ] Intenté la recursividad como se muestra a continuación y se mostró indefinida. La configuración para el objeto visitado parece indefinida, pero mostró la pila de llamadas máxima si la edité.
(No importa las formas recursivas o iterativas de resolver este problema).
Por favor, ayuda. Cualquier comentario sería útil.
const seeds = input.filter( ele => ele[0] === 0); const nodes = input.filter( ele => ele[0] !== 0); const visited = {}; function chain(seed, nodes){ let result = nodes.map(node => { if(node[0] === seed[seed.length - 1]){ while(!visited[node]){ visited[node]= true; return chain([...seed, node[0]], nodes) } } }) return result; } function getResult(seeds, nodes){ let result = seeds.map( seed => { visited[seed] = true; return chain(seed, nodes); }).flat(); return result; }1 answers
Answer question0
Supongo que su gráfico es un gráfico dirigido, y una "vía" usará un borde en particular solo una vez.
Sugeriría construir una lista de adyacencia primero. Uno que está marcado por vértices, y para cada uno de ellos tiene una matriz de aristas (no solo vértices vecinos).
Luego, en el DFS, puede recopilar los bordes que visita a medida que profundiza en el árbol y luego probar que solo se puede agregar un nuevo borde a esa lista cuando aún no aparece en esa cadena. Esta es la principal diferencia con el procedimiento DFS "normal", donde recopilaría vértices (en lugar de bordes) a medida que construye una ruta.
Aquí está la implementación con un generador:
function* dfs(adj, vertex=0, path=[]) { let leaf = true; for (let edge of adj[vertex]) { if (!path.includes(edge)) { yield* dfs(adj, edge[1], path.concat([edge])); leaf = false; } } if (leaf) yield path.map(edge => edge[0]).concat(vertex); } const input = [[0, 1], [0, 2], [1, 5], [2, 6], [2, 12], [5, 29], [6, 29], [9, 30], [12, 18], [18, 29], [29, 9], [29, 12], [29, 18]]; // Build adjacency list as key/value pairs, where key=vertex, // and value=array of outgoing edges (not just the neighbors) const adj = {}; for (let edge of input) { (adj[edge[0]] ??= []).push(edge); adj[edge[1]] ??= []; } // Output paths for (let path of dfs(adj)) console.log(JSON.stringify(path));El gráfico de entrada es su gráfico:
La salida es:
[0,1,5,29,9,30] [0,1,5,29,12,18,29,9,30] [0,1,5,29,12,18,29,18] [0,1,5,29,18,29,9,30] [0,1,5,29,18,29,12,18] [0,2,6,29,9,30] [0,2,6,29,12,18,29,9,30] [0,2,6,29,12,18,29,18] [0,2,6,29,18,29,9,30] [0,2,6,29,18,29,12,18] [0,2,12,18,29,9,30] [0,2,12,18,29,12] [0,2,12,18,29,18]