在二分圖中查找映射

存在表示二分圖中的連接的正方形二元矩陣。問題是：是否存在所有行到列的一對一映射？（要清楚的是，如果我使用的語言錯誤，完全連接的圖滿足此要求，因爲我們不僅限於一對一映射）。在二分圖中查找映射

我寫了以下內容。有沒有一個可笑的更快的方法來完成這個？

/* 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; 
}

來源

2011-05-05 Full Decent

我假定你的表現，你的意思是你有一個二分圖，其中既有「雙方」有相同數量的節點，而圖[A] [B]意味着有一個如果每個分區中的所有節點均以垂直線排列，則從「左」上的節點A到「右」上的節點B的連接。

你的算法實際上並不是那麼糟糕，如果圖很稀疏，並且它具有簡單性的優點。

對於更密集的圖，它是指數型的，如果你願意爲它編寫代碼，你可以做得更好。如果向連接到所有「左」節點的圖形和連接到所有「右」節點的接收器添加一個源節點，並將容量1分配給包括新節點在內的所有邊，則最大網絡流量將從源到當且僅當存在一對一配對時，水槽等於SIZE。如果您使用算法（如Ford-Fulkurson）來計算流量，則每個循環都會連接另一對節點，根據需要重新排列現有連接以實現此目的，直到不再可能爲止。運行時間將在SIZE^3之內。

這也可以直接用二分圖表示來實現，並重新排列兩個匹配對，但是我覺得最容易理解的是，如果將它構建爲網絡流實現以便從那裏開始然後重構。請參閱the "Maximum matchings in bipartite graphs" section of the Wikipedia page on graph matching problems瞭解有關稍微更一般的問題的信息，如果在二分圖中找到最大數量的匹配對，這是基於流的解決方案實際解決的問題。

如果你真的想要速度，看看我還沒有實現的Hopcroft-Kamp，現在我只是在讀我自己。鏈接的頁面表明它在SIZE ^（5/2）中的最壞情況（在這個例子中），並且在對Ford-Fulkerson進行稀疏圖優化方面同樣好或者更好。

來源

2011-05-05 02:00:00

謝謝，這清除它，並給我一些選擇。我打算玩，看看什麼能夠提供最好的表現。 – 2011-05-06 22:11:25

在二分圖中查找映射

回答

相關問題