用JavaScript最容易实现Barpartite图？

Question

我正在研究一个算法需要使用二部图的项目，而我想知道在javascript中创建这种数据结构的最佳或最简单方法是什么？

我还没有在网上找到任何好的解释，因此，如果有人可以帮助我自己或以正确的方式指出我，那将是很好的。

Answer 1

最简单的

最简单的一种可能是最明显的一种

您可以创建2个列表，其中每个列表代表二分图中的一个分区。该列表中的每个元素代表图中的一个顶点。

然后创建一个边列表，每个元素都像一对对（p1，p2）一样存储，其中p1是第一个数组的边索引，p2是第二个数组的边。

例如，代表上面的图形，您将编写

var partition1 = ['a', 'b', 'c', 'd', 'e'];
var partition2 = ['f', 'g', 'h', 'i', 'j'];

var edges      = [ [1,2], [3, 0], [1, 1] ];

这是“ 邻接表”图表示数据结构的修改版本。

一些具有这种表示形式的简单算法

function addEdge( vertexFrom1, vertexFrom2 ) {
    edges.push( [vertexFrom1, vertexFrom2] );
}

function connected( vertexFrom1, vertexFrom2 ) {
    for( var i =0, len=edges.length; i < len; i++ ) {
        if( edges[i][0] === vertexFrom1 && edges[i][1] === vertexFrom2 ) {
            return true;    
        }
    }

    return false;
}

如您所见，添加或删除边线非常容易，但是检查两个顶点是否已连接很慢。

也许是更好的方法

如果要实现更快的连接检查，可以执行类似的操作。

除了使用一对顶点索引，您还可以只存储第一个分区的传出连接，这是因为二部图在分区内部无法具有连接。

因此，以这种方式表示上面的图形，您可以这样写：

var partition1 = ['a', 'b', 'c', 'd', 'e'];
var partition2 = ['f', 'g', 'h', 'i', 'j'];

var edges      = [ [], [2,4], [], [0], [] ];

这样可以使连接检查更快，但需要更多内存来存储边缘。