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

Question

我试图在Python中找到一种方法，以在无方向的图中配对节点，以便达到最大量的节点，而没有一个节点出现不止一次。

示例：

Input1：图形带有3个节点和边缘[A，B]，[A，C]，[B，C]

输出1：应该为2，因为没有办法选择一个以上的边缘，因此不重复节点。

Input2：图形具有6个节点和边缘[A，B]，[A，C]，[A，D]，[B，D]，[B，E]，[B，F]，[C，D]，[C，D]， [C，F]，[E，F]

输出2：应该为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是一个单个变量，该变量是NODES 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