檢查由多個不連通圖組成的大圖中的二分性？

我在SPOJ上做了一個問題SPOJ:BUGLIFE 它需要我檢查圖形是否是二分圖。我知道單個連通圖的方法，但對於不連通圖的組合，我的方法給出超時時間限制的錯誤。這是我的方法 - 廣度優先搜索，使用圓形隊列和由鄰接表實現的圖形。方法 - >選擇一個源，並且如果該源頂點=未訪問，則開始一個寬度優先搜索，假定它是源。如果我在BFS中發現了衝突，那麼我會放棄整個事情。否則，我會轉移到另一個未訪問的來源。如何讓這個更快？或更好？檢查由多個不連通圖組成的大圖中的二分性？

P.S.我是圖論新手，所以請詳細解釋。

來源

2013-06-23 user1733947

我不知道什麼是時限錯誤，但如果你知道如何檢查bipartiteness一個連通圖，那麼你應該檢查bipartiteness所有連接的子圖，如果通過了所有測試，然後你的圖是二分。 –

時間限制錯誤意味着程序需要更多時間來執行給定的輸入（這是相當大的）比允許的。 – user1733947

以下實現（C++版本）在非常大的數據集（edages> 1000）中測試時足夠快。希望能幫助到你。

struct NODE 
{ 
    int color; 
    vector<int> neigh_list; 
}; 

bool checkAllNodesVisited(NODE *graph, int numNodes, int & index); 

bool checkBigraph(NODE * graph, int numNodes) 
{ 
    int start = 0; 

    do 
    { 
     queue<int> Myqueue; 
     Myqueue.push(start); 
     graph[start].color = 0; 

     while(!Myqueue.empty()) 
     { 
      int gid = Myqueue.front(); 
      for(int i=0; i<graph[gid].neigh_list.size(); i++) 
      { 
       int neighid = graph[gid].neigh_list[i]; 
       if(graph[neighid].color == -1) 
       { 
        graph[neighid].color = (graph[gid].color+1)%2; // assign to another group 
        Myqueue.push(neighid); 
       } 
       else 
       { 
        if(graph[neighid].color == graph[gid].color) // touble pair in the same group 
         return false; 
       } 
      } 
      Myqueue.pop(); 
     } 
    } while (!checkAllNodesVisited(graph, numNodes, start)); // make sure all nodes visited 
              // to be able to handle several separated graphs, IMPORTANT!!! 

    return true; 
} 

bool checkAllNodesVisited(NODE *graph, int numNodes, int & index) 
{ 
    for (int i=0; i<numNodes; i++) 
    { 
     if (graph[i].color == -1) 
     { 
      index = i; 
      return false; 
     } 
    } 

    return true; 
}

來源

2013-09-20 09:57:07 herohuyongtao

檢查由多個不連通圖組成的大圖中的二分性？

回答

相關問題