将顶点和边分组以在 JavaScript 中分隔图形

Question

这个问题有一个任意的有向边数组，例如，

let pairs = [[9, 6], [10, 2], [2, 1], [7, 1], [5, 6], [1, 10], [8, 11], [10, 4], [9, 0], [12, 0], [3, 9], [0, 6]];

数组一次可以包含一张或多张图表。任务是遍历这些对并将它们分成组，在这种特殊情况下，结果应该是

let output = [

    [0, 3, 5, 6, 9, 12],
    [1, 2, 4, 7, 10],
    [8, 11] 

]; //please

let pairs = [[9, 6], [10, 2], [2, 1], [7, 1], [5, 6], [1, 10], [8, 11], [10, 4], [9, 0], [12, 0], [3, 9], [0, 6]];

let groups = [];

for(let i = 0; i < pairs.length; i++){

        if(groups.length == 0){
    
            groups.push([]);
        groups[0].push(pairs[i][0]);
        groups[0].push(pairs[i][1]);
    
    }
    else{

                let parentGroup = getParentGroup(groups, pairs[i]);
        
        if(parentGroup == null){
        
                groups.push([]);
                groups[groups.length - 1].push(pairs[i][0]);
                groups[groups.length - 1].push(pairs[i][1]);
        
        }
        else{
        
                if(parentHasNode(groups[parentGroup], pairs[i][0])){ if(!parentHasNode(groups[parentGroup], pairs[i][1])) { groups[parentGroup].push(pairs[i][1]); } }
            if(parentHasNode(groups[parentGroup], pairs[i][1])){ if(!parentHasNode(groups[parentGroup], pairs[i][0])) { groups[parentGroup].push(pairs[i][0]); } }
        
        }
                
    
    }


}

console.log(groups);

function parentHasNode(group, left){

        for(let i = 0; i < group.length; i++){
    
            if(group[i] == left) { return true; }
    
    }
    
    return false;

}

function getParentGroup(groups, pair){

        let out = null;
    
    for(let i = 0; i < groups.length; i++){
    
            for(let j = 0; j < groups[i].length; j++){
        
                if(pair[0] == groups[i][j] || pair[1] == groups[i][j]) { out = i; break; }
        
        }
    
    }
    
    return out;

}

忽略排序

这些顶点在视觉上排列成如下所示的三个图形

到目前为止，我不需要算法来绘制这些图，而是将顶点分组为单独的顶点。

我附上了当前的代码，但并不是每次都能正常工作。

let pairs = [[25, 15], [22, 6], [6, 15], [15, 9], [9, 6], [16, 9], [7, 29], [2, 5], [26, 24], [24, 29], [5, 24], [29, 5], [1, 18], [13, 12], [19, 30], [30, 18], [12, 30], [18, 12], [8, 20], [11, 3], [28, 23], [20, 3], [3, 23], [23, 20], [4, 10], [14, 27], [21, 17], [10, 17], [17, 27], [27, 10], [0, 31]];

不正确

let output =     [
    [25, 15], 
    [22, 6, 15, 9, 16], 
    [7, 29], 
    [2, 5], 
    [26, 24, 29, 5], 
    [1, 18], 
    [13, 12], 
    [19, 30, 18, 12], 
    [8, 20], 
    [11, 3, 20], 
    [28, 23, 3, 20], 
    [4, 10], 
    [14, 27], 
    [21, 17, 10, 27], 
    [0, 31]
];

第一组有3个和第6个等错误。一定是这样的

output =   [

    [25, 15, 22, 6, 9, 16],
    [26, 24, 29, 5, 2, 7],
    [19, 30, 18, 12, 1, 13], 
    [28, 23, 3, 20, 8, 11],
    [21, 17, 10, 27, 4, 14], 
    [0, 31]

  ];

Answer 1

由于 pairs 数组表示有向图，因此建立组涉及遍历数组以寻找匹配对链。

下面提出的算法有一个建立当前边对的外循环，在边数组的剩余部分中寻找匹配项，如果找到任何匹配项，则将这些匹配项合并到当前边对中，当然, 正在演化为一个边集。然后清除找到的匹配项，因为它们已与当前边集合并，并且一直持续到外循环到达边数组的末尾。

最终得到的数组是合并集和清除集的组合，所以结果returns只有非空集。

function groupEdges( edges ) {

  // Turn the edge pairs into Set objects.
  temp = edges.map( po => new Set( po ) );
 
  // Loop through each edge set...
  for ( let i = 0; i < temp.length; i++ ) {
    let currentEdgeSet = temp[ i ];
    if ( currentEdgeSet ) {
      // Loop through each edge...
      let a = Array.from( currentEdgeSet );
      for ( let pi = 0; pi < a.length; pi++ ) {
        // ...and now loop through the remaining edges, seeking a match with
        // the current edge.  Include any found matching edges in with the
        // currentEdgeSet, clear the found matches (as they have been included
        // with the currentEdgeSet), and then re-establish the list of edges
        // being sought from the currentEdgeSet.
        for ( let j = i + 1; j < temp.length; j++ ) {
          if ( temp[ j ] && temp[j].has( a[ pi ] ) ) {
            temp[ j ].forEach( currentEdgeSet.add, currentEdgeSet );
            temp[ j ] = null;
            a = Array.from( currentEdgeSet );
          }
        }
      }
    }
  }
  
  // Finally, only return the non-null edge sets.
  return temp.filter( es => es );
  
}

console.log( groupEdges( [[9, 6], [10, 2], [2, 1], [7, 1], [5, 6], [1, 10], [8, 11], [10, 4], [9, 0], [12, 0], [3, 9], [0, 6]] ).map( s => Array.from( s ) ) );
console.log( groupEdges( [[25, 15], [22, 6], [6, 15], [15, 9], [9, 6], [16, 9], [7, 29], [2, 5], [26, 24], [24, 29], [5, 24], [29, 5], [1, 18], [13, 12], [19, 30], [30, 18], [12, 30], [18, 12], [8, 20], [11, 3], [28, 23], [20, 3], [3, 23], [23, 20], [4, 10], [14, 27], [21, 17], [10, 17], [17, 27], [27, 10], [0, 31]] ).map( s => Array.from( s ) ) );

请注意与遍历 currentEdgeSet 中的值相关的细微差别。 JavaScript 保留添加到 Set 对象的条目的顺序，因此能够使用索引 pi 进入 currentEdgeSet，以及有序边列表（即，按进入集合）通过 a = Array.from( currentEdgeSet ) 重新建立，只要任何新的匹配被合并到 currentEdgeSet.

将顶点和边分组以在 JavaScript 中分隔图形

Group vertices and edges to separate graphs in JavaScript

javascript

graph

grouping

edges

vertices