Finden Sie den Weg zwischen zwei Knoten in JavaScript auf benutzerdefinierte Datenstruktur

Question

Hallo Ich habe eine Verbindung Array wie folgt:

var connections =[ 

    { 
     "source": "l1", 
     "target": "l2" 
    }, 
    { 
     "source": "l2", 
     "target": "l4" 
    }, 
    { 
     "source": "l2", 
     "target": "l3" 
    }, 
    { 
     "source": "l4", 
     "target": "l5" 
    }, 

] 

Es geht weiter mit Quelle und Ziel. Jetzt wollen Sie den Pfad zwischen zwei Knoten mit einer Funktion finden. sagen wir mal Funktion findConnections("l2", "l5") wie das Array zurück unter

var answer =[ 

     { 
      "source": "l2", 
      "target": "l4" 
     }, 
     { 
      "source": "l4", 
      "target": "l5" 
     }, 
] 

ich keine Ahnung, wie ich das erreichen kann? Ich habe versucht, einfaches JavaScript, aber gescheitert. Ich denke, mit Underscore.js oder lodash.js wir dies erreichen können? Es wird wirklich hilfreich sein, wenn jemand eine Lösung anbietet oder Hinweise gibt?

Answer 1

Verwenden Rekursion und geht die „Liste“

function find(list, from, to) { 
    // find the current "source" 
    let current = list.find(v => v.source === from); 

    if (!current) // no current? u got problems 
     throw new Error("No from in list"); 

    // are we there yet? 
    if (current.target === to) 
     return current; 

    // no we're not ... so keep searching with new "source" 
    return [current].concat(find(list, current.target, to)); 
} 

Answer 2

Im Folgenden wird ein JSON-Objekt zurück, wie in der Frage angegeben wurde. Es wird auch überprüft, ob beide Argumente sowie die Verbindung zwischen ihnen im JSON vorhanden sind. Ich überlasse es dem Autor, andere Randfälle zu testen.

var findConnections = function(json,from,to) { 
 

 
    // JSON is an unordered structure, so let's compile two arrays for ease of searching 
 
    var sources = [], targets = []; 
 
    for (node of json) { 
 
    sources.push(node.source); 
 
    targets.push(node.target); 
 
    } 
 

 
    // Select each 'from' element from the 'sources' array, get its target... 
 
    for(var i=0;i<sources.length;i++) { 
 
    if((fromIndex = sources.indexOf(from,i)) < 0) { throw new Error('Connection could not be established.'); } 
 
    var fromTarget = targets[fromIndex]; 
 

 
    // ...then look for the connected 'to' in the 'targets' array 
 
    for(var j=0;j<sources.length;j++) { 
 
     if((toIndex = sources.indexOf(fromTarget,j)) < 0) { continue; } 
 

 
     // If we have a match, compile and return a JSON object. If not, we'll keep looping and if we loop out, an error will be thrown below 
 
     if(targets[toIndex] == to) { 
 
     return [ 
 
       { 
 
        'source':sources[fromIndex], 
 
        'target':targets[fromIndex] 
 
       }, 
 
       { 
 
        'source':sources[toIndex], 
 
        'target':targets[toIndex]     
 
       } 
 
       ]; 
 
     }   
 
    } 
 
    } 
 

 
    throw new Error('Connection could not be established.'); 
 
}

Testen Sie, wie folgend:

var answer = findConnections(connections,'l2','l5'); console.log(answer);

Answer 3

ich auf diese waaaaay zu viel Zeit damit verbracht, und ich bin ziemlich sicher, es gibt eine elegantere Lösung, aber ich Ich werde sehen, ob ich Kommentare hinzufügen und mich erklären kann.

// Add some more connections. Make some of them out 
 
// of order just for fun 
 
let connections = [{ 
 
    source: 'l1', 
 
    target: 'l2' 
 
    }, 
 
    { 
 
    source: 'l1', 
 
    target: 'l3' 
 
    }, 
 
    { 
 
    source: 'l2', 
 
    target: 'l4' 
 
    }, 
 
    { 
 
    source: 'l2', 
 
    target: 'l3' 
 
    }, 
 
    { 
 
    source: 'l4', 
 
    target: 'l5' 
 
    }, 
 
    { 
 
    source: 'l3', 
 
    target: 'l6' 
 
    }, 
 
    { 
 
    source: 'l3', 
 
    target: 'l5' 
 
    }, 
 
    { 
 
    source: 'l4', 
 
    target: 'l6' 
 
    } 
 
]; 
 

 
// I just realized that I didn't call this 
 
// function what you wanted it called but 
 
// it should be fine 
 

 
let answers = findPaths(connections, 'l1', 'l5'); 
 
console.log(JSON.stringify(answers, null, 2)); 
 

 
function findPaths(connections, start, end) { 
 
    // first, build a tree, for loads of connections, 
 
    // this is probably slow as hell 
 
    let tree = buildTree(
 
    connections, 
 
    findConnection(connections, start), 
 
    null 
 
); 
 
    
 
    // make the tree into all the different paths 
 
    // also probably slow as hell. Could prune the 
 
    // tree if I could figure out how to implement 
 
    // a backtracking algoritm in javascript but 
 
    // I couldn't figure it out from the wikipedia 
 
    // article so I skipped it 
 
    let allPaths = buildPaths(tree, []); 
 
    
 
    // pare down the paths to ones that fit the start 
 
    // and end points 
 
    let goodPaths = verifyPaths(allPaths, start, end); 
 
    
 
    // reformat that thing to match what you wanted 
 
    return format(goodPaths); 
 
} 
 

 
// so this thing just runs through the connections 
 
// array and returns an array of elements where the 
 
// source property matches the source argument 
 
function findConnection(connections, source) { 
 
    return connections.filter(conn => conn.source === source); 
 
} 
 

 
// So this returns an array that contains a tree 
 
// Probably a better way to do this, but... 
 
function buildTree(connections, nodes, parent) { 
 
    // for each node... 
 
    return nodes.map(node => { 
 
    // had to cheat here, just add the node's parent 
 
    // to the node. That way, we don't have to think 
 
    // about it later 
 
    node.parent = parent; 
 
    
 
    // find any other connections whose source property 
 
    // matches our target property. 
 
    node.path = findConnection(connections, node.target); 
 
    
 
    // if some were found, then... 
 
    if (node.path && node.path.length > 0) { 
 
     // build that sub-tree. Here, I cheated big-time 
 
     // and made the third param (parent) an object 
 
     // that had the properties I wanted later. 
 
     // It's just easier. 
 
     buildTree(connections, node.path, { 
 
     source: node.source, 
 
     target: node.target, 
 
     parent: node.parent 
 
     }); 
 
    } 
 
    // done slapping this around, return it 
 
    return node; 
 
    }); 
 
} 
 

 
// so this is a part could be better. Probably could be 
 
// replaced by Array.reduce, but I'm too lazy. This 
 
// turns the "tree" into an array of all of the paths 
 
// from beginning to end. Many of the paths will be 
 
// filtered out later so it could be made more efficient 
 
function buildPaths(tree, prev) { 
 
    tree.forEach(step => { 
 
    if (step.path.length > 0) { 
 
     buildPaths(step.path, prev); 
 
    } else { 
 
     prev.push(step); 
 
    } 
 
    }); 
 
    return prev; 
 
} 
 

 
// filter out the paths that don't match the specified 
 
// start and end. We should have good paths now...in 
 
// the wrong format, but we'll fix that up later... 
 
function verifyPaths(paths, start, end) { 
 
    return paths.filter(path => path.target === end).filter(path => { 
 
    while (path.parent) { 
 
     path = path.parent; 
 
    } 
 
    return path.source == start; 
 
    }); 
 
} 
 

 
// alright, go ahead and flatten out the good paths 
 
// into the requested format 
 
function format(arr) { 
 
    return arr.map(el => { 
 
    let temp = []; 
 
    temp.unshift({ 
 
     source: el.source, 
 
     target: el.target 
 
    }); 
 
    while (el.parent) { 
 
     el = el.parent; 
 
     temp.unshift({ 
 
     source: el.source, 
 
     target: el.target 
 
     }); 
 
    } 
 
    return temp; 
 
    }); 
 
}

Answer 4

Ich bin ein bisschen spät, um die Partei, aber hier ist eine einfache Lösung:

1. ein Diagramm aus den gegebenen Kanten bauen:

   

2. Einsatz einfache breadth-first-search einen Pfad

const addNode = (graph, node) => { 
 
    graph.set(node, {in: new Set(), out: new Set()}); 
 
}; 
 

 
const connectNodes = (graph, source, target) => { 
 
    graph.get(source).out.add(target); 
 
    graph.get(target).in.add(source); 
 
}; 
 

 
const buildGraphFromEdges = (edges) => edges.reduce(
 
    (graph, {source, target}) => { 
 
    if (!graph.has(source)) { 
 
     addNode(graph, source); 
 
    } 
 

 
    if (!graph.has(target)) { 
 
     addNode(graph, target); 
 
    } 
 

 
    connectNodes(graph, source, target); 
 

 
    return graph; 
 
    }, 
 
    new Map() 
 
); 
 

 
const buildPath = (target, path) => { 
 
    const result = []; 
 

 
    while (path.has(target)) { 
 
    const source = path.get(target); 
 
    result.push({source, target}); 
 
    target = source; 
 
    } 
 

 
    return result.reverse(); 
 
}; 
 

 
const findPath = (source, target, graph) => { 
 
    if (!graph.has(source)) { 
 
    throw new Error('Unknown source.'); 
 
    } 
 

 
    if (!graph.has(target)) { 
 
    throw new Error('Unknown target.'); 
 
    } 
 

 
    const queue = [source]; 
 
    const visited = new Set(); 
 
    const path = new Map(); 
 

 
    while (queue.length > 0) { 
 
    const start = queue.shift(); 
 

 
    if (start === target) { 
 
     return buildPath(start, path); 
 
    } 
 

 
    for (const next of graph.get(start).out) { 
 
     if (visited.has(next)) { 
 
     continue; 
 
     } 
 

 
     if (!queue.includes(next)) { 
 
     path.set(next, start); 
 
     queue.push(next); 
 
     } 
 
    } 
 

 
    visited.add(start); 
 
    } 
 

 
    return null; 
 
}; 
 

 
// A --* B 
 
// /| \ 
 
//  * | * 
 
// C | D --* E 
 
//  \ |/ * 
 
//  * * * /
 
//  F------/ 
 

 
const graph = buildGraphFromEdges([ 
 
    { source: 'A', target: 'B' }, 
 
    { source: 'B', target: 'C' }, 
 
    { source: 'B', target: 'D' }, 
 
    { source: 'B', target: 'F' }, 
 
    { source: 'C', target: 'F' }, 
 
    { source: 'D', target: 'E' }, 
 
    { source: 'D', target: 'F' }, 
 
    { source: 'F', target: 'E' }, 
 
]); 
 

 
console.log('A -> A', findPath('A', 'A', graph)); // [] 
 
console.log('A -> F', findPath('A', 'F', graph)); // [{source: 'A', target: 'B'}, {source: 'B', target: 'F'}] 
 
console.log('A -> E', findPath('A', 'E', graph)); // [{source: 'A', target: 'B'}, {source: 'B', target: 'D'}, {source: 'D', target: 'E'}] 
 
console.log('E -> A', findPath('E', 'A', graph)); // null

Hinweis finden, dass ich Ihre Eingabe versteht man eine directed graph zu bilden. Wenn stattdessen ein ungerichteter Graph gemeint ist, könnte die Lösung ein wenig vereinfacht werden.