javascript - javascript中条形图的最简单实现？

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], [] ];

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