JSFiddle - React, Tailwind, and code Playground

by Svetlana

JavaScript

function findNodes(edges) {
  let nodes = [];
  edges.forEach(edge => {
    for (i in [0,1]) {
      const node = edge[0].charAt(i);
      if (!nodes.includes(node)) {
        nodes.push(node);
      }
    }
  })
  return nodes;
}

function deleteFromArr(arr, elemIdx) {
  return arr.splice(elemIdx, 1);
}
  
function makeSpanningTree(edges, t) {
  let nodesInTree = [];
  let spanningTree = [];
  
  const MIN = 'min';
  const MAX = 'max';
  
  let arr = findNodes(edges);
  let nodesNotInTree = findNodes(edges);
  let keys = t === MIN ? nodesNotInTree.map(()=>Infinity) : nodesNotInTree.map(()=>-Infinity);
  keys[0] = 0;
  let parents = nodesNotInTree.map(()=>undefined);
  
  while (nodesNotInTree.length !== 0) {
    const neededKeyIdx = t === MIN ? keys.indexOf(Math.min(...keys)) : keys.indexOf(Math.max(...keys));
    
    const curNode = nodesNotInTree[neededKeyIdx];
    nodesInTree.push(curNode);
    
    let adjucentEdges = edges.filter(edge => edge[0].includes(curNode));
    
    let neededAdjucentEdge;
    let startingComparisonW = t === MIN ? Infinity : -Infinity;
    
    adjucentEdges.forEach(edge => {
      const nodeIdxEdge = edge[0].charAt(0) === curNode ? 1 : 0;
      const nodeIdxArr = arr.indexOf(edge[0].charAt(nodeIdxEdge));
      keys[nodeIdxArr] = edge[1];
      if (t === MIN) {
        if (edge[1] < startingComparisonW) {
          neededAdjucentEdge = edge;
        }
      }
      else {
        if (edge[1] > startingComparisonW) {
          neededAdjucentEdge = edge;
        }
      }
    })
    spanningTree.push(neededAdjucentEdge);
    keys = deleteFromArr(keys, neededKeyIdx);
    nodesNotInTree = deleteFromArr(nodesNotInTree, neededKeyIdx);
  }
  return spanningTree;
}

let edges = [
    ['AB', 1], ['AE', 1], ['BA', 1], ['EA', 1], ['GH', 1], ['HG', 1], ['AF', 2], ['DE', 2],
    ['DH', 2], ['ED', 2], ['FG', 2], ['FA', 2], ['GF', 2], ['HD', 2], ['BE', 3], ['CD', 3],
    ['DC', 3], ['EB', 3], ['DG', 4], ['EF', 4], ['FE', 4], ['GD', 4], ['AH', 5],...