如何找到图中可以匹配的最大节点对数?

Question

我正在尝试在Python中找到一种方法来配对无向图中的节点，以便达到最大数量的节点，而没有节点出现超过一次。

的例子:

Input1: 3个节点和边的图[A, B]， [A, C]， [B, C]

Output1:应该是2，因为没有办法选择一条以上的边，这样就没有重复的节点。

Input2:图6节点和边[A, B], [A、C], [A, D], [B, D], [B, E], [B, F], [C, D], [C、F], [E, F]

Output2:应该是6，因为所有节点都可以配对。例如,使用边缘[A, B], C, D, E, F。

Answer 1

LOOP N1N2 over edges
C = Count of unique nodes connected to the two nodes connected by edge
Store N1N2 in MM, a multimap keyed by C
LOOP N1N2 over MM, from smallest C
Add N1N2 to RESULT
Remove all edges connecting N1 or N2 from MM
OUTPUT RESULT

N1N2是索引节点N1和N2之间的边的单变量

下面是该算法的c++实现

void cGraph::solve()
{
myResult.clear();
std::multimap <int, int > edgeMap;
// loop over edges
int i = -1;
for (auto &n1n2 : vEdge)
{
i++;
int c = countNeighbors(n1n2);
// store edge index keyed by count of neigbors
edgeMap.insert({ c, i });
}
// while edges remain unassigned
while( edgeMap.size() )
{
// assign pair with fewest neigbors to result
auto pair =  vEdge[ edgeMap.begin()->second ];
myResult.push_back( pair );
// remove edges that connect nodes in result
bool done = false;
while( ! done )
{
done = true;
// loop over edges in map
for(
std::multimap <int, int >::iterator it = edgeMap.begin();
it != edgeMap.end();
it++ )
{
// check for edge connecting node just added to result
auto e = vEdge[it->second];
if( e.n1 == pair.n1 ||
e.n2 == pair.n1 ||
e.n1 == pair.n2 ||
e.n2 == pair.n2 ) {
// remove the edge, to prevent duplicate nodes in result
edgeMap.erase( it );
// continue search for edges that connect edges in result
done = false;
break;
}
}
}
}
}

输出为

test 1
2 paired nodes found
1 2
test 2
6 paired nodes found
1 4
2 5
3 6

应用程序的完整代码在这里https://gist.github.com/JamesBremner/266e273899df4ca2815762d4bc803474