2

2 部グラフの接続を表す正方バイナリ マトリックスがあります。問題は、すべての行から列への 1 対 1 のマッピングが存在するかどうかです。(明確にするために、言語を間違って使用している場合、完全に接続されたグラフは、1 対 1 のマッピングのみに制限されていないため、この要件を満たします)。

以下を書きました。これを達成するためのとてつもなく速い方法はありますか？

/* Is there a one-to-one mapping possible with the given bipartite graph?
   input:  graph[a][b] = connected (1) or not (0)
   return: 0=no 1=yes */
int one_to_one(int graph[SIZE][SIZE], int rows_checked /* =0 */, int col_chosen /* =0 */)
{
    int my_graph[SIZE][SIZE], i, j, retval;
    memcpy(my_graph, graph, sizeof(graph[0][0]) * SIZE * SIZE);

    if (rows_checked > 0) 
        for (i=rows_checked; i<SIZE; i++)
            my_graph[i][col_chosen] = -1; /* flag for "this column done" */

    retval=1;
    for (i=0; i<SIZE; i++) {
        if (my_graph[rows_checked][i] == -1)
                    continue;
        retval=0;
        if (my_graph[rows_checked][i] == 1)
            if (one_to_one(my_graph, rows_checked+1, i))
                return 1;
    }
    return retval;
}
4

1 に答える 1

1

あなたの表現では、両方の「辺」が同じ数のノードを持つ2部グラフがあることを意味し、graph [A] [B]は、「各パーティションのすべてのノードが垂直線上に配置されている場合は、「左」から「右」のノードBに移動します。

グラフがまばらであれば、アルゴリズムは実際にはそれほど悪くはなく、単純であるという利点があります。

より密度の高いグラフの場合、それは指数関数的であり、そのためのコードを作成する意思がある場合は、より適切に実行できます。すべての「左」ノードに接続されたグラフにソースノードを追加し、すべての「右」ノードに接続されたシンクを追加し、新しいエッジを含むすべてのエッジに容量1を割り当てると、ソースから1対1のペアリングがある場合に限り、シンクはSIZEに等しくなります。Ford-Fulkursonなどのアルゴリズムを使用してフローを計算する場合、各ループは追加のノードペアを接続し、それが不可能になるまで、必要に応じて既存の接続を再配置します。ランタイムはSIZE^3以内になります。

これは、2部グラフの表現と一致のペアの再配置の観点から直接実装することもできますが、ネットワークフローの実装として構築し、そこから開始してリファクタリングする方が最も理解しやすいと思います。2部グラフで一致するペアの最大数を見つける場合のわずかに一般的な問題に関する情報については、グラフの一致の問題に関するWikipediaページの「2部グラフの最大一致」セクションを参照してください。これは、フローベースのソリューションが実際に行うものです。解決します。

本当にスピードが欲しいのなら、私がまだ実装しておらず、今自分自身について読んでいるHopcroft-Kampを見てください。リンクされたページには、SIZE ^（5/2）の最悪のケース（この例では）があり、Ford-Fulkersonと同じかそれ以上のスパースグラフの最適化が優れていると記載されています。

于 2011-05-05T02:00:00.760 に答える