日本综合一区二区|亚洲中文天堂综合|日韩欧美自拍一区|男女精品天堂一区|欧美自拍第6页亚洲成人精品一区|亚洲黄色天堂一区二区成人|超碰91偷拍第一页|日韩av夜夜嗨中文字幕|久久蜜综合视频官网|精美人妻一区二区三区

審校 | 梁策 孫淑娟

創(chuàng)新互聯(lián)公司專注于懷遠(yuǎn)企業(yè)網(wǎng)站建設(shè),成都響應(yīng)式網(wǎng)站建設(shè)公司,商城網(wǎng)站建設(shè)。懷遠(yuǎn)網(wǎng)站建設(shè)公司,為懷遠(yuǎn)等地區(qū)提供建站服務(wù)。全流程按需求定制制作，專業(yè)設(shè)計，全程項目跟蹤，創(chuàng)新互聯(lián)公司專業(yè)和態(tài)度為您提供的服務(wù)

確定一個圖形是否是二分圖的問題不僅對面試非常重要，也有助于解決現(xiàn)實生活中的問題。比如，在舉辦足球聯(lián)賽時，用它來看看哪些球員為哪些組織效過力。這樣的例子比比皆是，本文也將就這一問題重點討論。

為了解決這個問題，我們需要深入了解二分圖、圖著色、BFS、DFS 和循環(huán)無環(huán)圖的知識。首先來看看定義：

循環(huán)圖和非循環(huán)圖：具有偶數(shù)個循環(huán)，以循環(huán)方式閉合的圖稱為循環(huán)圖。而如果圖中沒有閉合形狀，則稱為非循環(huán)圖。如果在無向圖中有一個封閉的形狀，它肯定是一個循環(huán)，而對于有向圖，就可能不是這樣。比如在下圖中：

該圖顯示，具有閉合形狀的無向圖將是循環(huán)的，但有向圖既可能循環(huán)也可能不循環(huán)。對于循環(huán)的有向圖，邊的方向應(yīng)以循環(huán)方式包圍。

可著色圖：如果我們只有兩種顏色(比如紅色和藍(lán)色)，并且我們可以為圖的每個頂點著色，從而讓圖形的每條邊的兩個頂點的顏色不同，那么該圖是 2-colorable (2-可著色)。簡單來說，我們可以說交替的頂點應(yīng)該有相同的顏色，或者兩個相鄰的頂點不應(yīng)該有相同的顏色。

在上圖中，第一個圖是 2-colorable ，因為沒有兩個相鄰頂點顏色相同。 在第二個圖中，相鄰的頂點 V1 和 V5 具有相同的顏色，因此 Graph 不是 2-colorable。

從上圖中，我們可以看到邊數(shù)為偶數(shù)的循環(huán)圖是 2-colorable 的，而邊數(shù)為奇數(shù)的循環(huán)圖不是 2-colorable 的。對于所有具有循環(huán)的圖都是如此，因為在偶數(shù)循環(huán)(具有偶數(shù)邊/頂點的循環(huán))的情況下，頂點被分成對(一個頂點是紅色，另一個是藍(lán)色)，但是當(dāng)我們有一個奇數(shù)大小的循環(huán)(具有奇數(shù)邊/頂點的循環(huán))時，一個頂點將被省略。

此外，對于具有多個循環(huán)的圖要成為 2-colorable ，所有循環(huán)必須是偶數(shù)大小的循環(huán)。 如下圖所示：

由于存在奇數(shù)循環(huán)，因此它是非二分圖。

上文介紹了循環(huán)圖的可著色性質(zhì)。那么非循環(huán)圖呢?讓我們看一些如下所示的示例：

這些圖顯示了各種非循環(huán)圖，它們都是 2-colorable。

通常，所有非循環(huán)圖都是 2-colorable 的。這背后的原因很簡單。當(dāng)一個圖是循環(huán)時，在兩個方向上都有相鄰的頂點，當(dāng)存在一個奇數(shù)大小的循環(huán)時，這些邊之一的相鄰頂點恰好是相同的顏色。

在無環(huán)圖中，可能有兩個方向的相鄰頂點，但無環(huán)圖中的方向往往線性相同。因此，我們可以說所有無環(huán)圖都是 2-colorable。

所以，最后我們可以根據(jù)觀察結(jié)果設(shè)置一些規(guī)則，讓圖形是 2-colorable：

• 如果一個圖形是循環(huán)的，那么它是一個 2-colorable 圖，它的所有循環(huán)都應(yīng)該是偶數(shù)大小的循環(huán)。
• 對上述觀點進行一些拓展，哪怕只有一個奇數(shù)循環(huán)的循環(huán)圖都將是非2-colorable 的。
• 所有的非循環(huán)圖都是 2-colorable。

現(xiàn)在，來談?wù)勎覀兊膯栴}，即二分圖。

二分圖：

如果一個圖的頂點可以分為兩個這樣的子集，它們是互斥(交集應(yīng)該是空集)且相互窮舉的(聯(lián)合是所有頂點的集合)，并且邊跨兩個集合而不是在同一個集合內(nèi)， 那么就說該圖形是二分的。

二分圖示例

非二分圖示例

如我們所見，有一條邊 V0-V4，其頂點位于同一集合中。你可以嘗試創(chuàng)建任何可能的集合，但總是會找到同一集合內(nèi)的邊。因此，上圖是非二分圖 。

那么，通過觀察上面的例子，你是否獲得了一些啟發(fā)呢?我們可以看到，第一個二分圖也是 2-colorable 。此外，第二張圖不是二分圖，也不是 2-colorable 。因此，我們可以說二分圖只不過是一個 2-colorable 圖。

快速觀察：

• 由于具有奇數(shù)循環(huán)的圖永遠(yuǎn)不會 2-colorable，因此可以說它永遠(yuǎn)不會是二分的。
• 此外，如果圖中有多個循環(huán)，則所有循環(huán)都必須是偶數(shù)循環(huán)(邊數(shù)應(yīng)該是偶數(shù))才能使圖成為二分圖。
• 如果一個圖是非循環(huán)的(沒有循環(huán))，它肯定是二分的，因為它總是 2-colorable。
• 如果一個圖形有一個自循環(huán) ，即一個圖的頂點有一條邊，那么它是非二分的，因為我們不能用兩種不同的顏色為同一個頂點著色。

方法 1：為每個頂點分配顏色 (BFS)

問題陳述：必須確定給我們的圖是否是二分的。

思維過程：上文已經(jīng)研究過，2-colorable圖是二分圖。那么，讓我們來給圖形的每個頂點逐一著色，注意相鄰的頂點不應(yīng)該有相同的顏色。如果我們能夠使用 2-colors成功地為圖形著色，則圖形將是二分的，否則不是。

算法：

• 選擇兩個數(shù)字，描述要在輸入圖的頂點上完成的兩種顏色。(假設(shè)數(shù)字是 1 和 2，未著色的頂點將由數(shù)字 0 表示)
• 選擇任何頂點作為圖形的源頂點，并使用第一種顏色(即 1)對其進行著色。
• 用第二種顏色為源頂點的所有相鄰頂點著色，并用第一種顏色再次著色它們的相鄰頂點，依此類推。(使用大小等于頂點數(shù)的顏色數(shù)組來保持哪個頂點具有什么顏色)。當(dāng)我們要為一個頂點著色時，這樣做是為了知道所有相鄰頂點的顏色。
• 如果所有的頂點都被成功著色而不違反2-colorable的圖形要求，即如果我們沒有出現(xiàn)2個相鄰頂點用相同顏色著色的情況，那么它是二分的，否則只要找到一個頂點與相鄰頂點有相同的顏色，那么返回 false， 表示該圖不是二分圖。
• 另外，不要忘記圖形是可以不連接的。因此，對圖形的每個組件都執(zhí)行此過程。

使用鄰接矩陣作為輸入的 C++ 代碼

輸入：圖將以大小為 V x V 的鄰接矩陣的形式輸入給我們，其中 V 是圖中的頂點數(shù)。它將是一個二進制矩陣，描述是否存在從頂點 V1 到另一個V2 的邊。輸入示例如下所示：

上圖描繪了輸入矩陣的示例。從 V0 到 V1 有一條邊，因此我們有 Matrix[V0][V1] = 1 等等。

#include
using namespace std;
// colors:
// red = 1 and blue = 2;
bool isBipartiteHelper(int graph[100][100],int vertices, int src, vector colors) {
    //coloring the source vertex red 
    colors[src] = 1;

    // queue needed for BFS Traversal
    queue que;
    que.push(src);

    while(!que.empty()) {
        int front = que.front();
        que.pop();

        // If self Loop exists, then adjacency matrix 
        // will have 1 in the diagonal element
        // and we have to return false in case of  adjacency matrix
        if(graph[front][front] == 1) return false;

        for(int i=0;i
            // edge exists and the adjacent vertex i is uncolored
            if(graph[front][i] == 1 && colors[i] == 0) {
                if(colors[front] == 1) colors[i] = 2; //color     alternatively
                else colors[i] = 1;
                que.push(i);
            } else if(graph[front][i] == 1 && colors[i] == colors[front]) { //edge exists and same color of adj vertex
                return false;
            }
        }
    }

    return true; //all vertices of this component can be colored
    // as per the rule of 2-colorable graph 
}

bool isBiPartite(int Graph[100][100], int vertices) {
    vector colors(vertices,0);

    // Assume i to be a source vertex of current component
    for(int i=0;i        // If i is uncolored
        if(colors[i] == 0) {
            // if any component is non bipartite, graph is also non bipartite
            if(isBipartiteHelper(Graph,vertices,i,colors) == false) return false;
        }
    }

    return true; //if all the components are bipartite then the entire graph is bipartite
}
int main() {
   
    int vertices;
    cin>>vertices;

    int Graph[100][100];

    for(int i=0;i        for(int j=0;j            cin >> Graph[i][j];
        }
    }

    cout<<"The given graph ";
    if(isBiPartite(Graph,vertices) == true) 
         cout<<"is bipartite\n";
    else cout<<"is not bipartite\n";
    return 0;
}

用 ??InterviewBit ??試試代碼

輸出：

方法分析：

該代碼涵蓋了具有自循環(huán)圖的極端情況，但該代碼不包括具有平行邊圖的情況，即同一對頂點之間的多條邊，如下所示：

該圖涵蓋了圖形劃分為多個未連接組件的情況。

時間復(fù)雜度：時間復(fù)雜度為 O(V2)，因為我們正在遍歷大小為 V x V 的鄰接矩陣。

空間復(fù)雜度：鄰接矩陣使用 O(V2) 空間表示圖，但這不是空間復(fù)雜度。除此之外，O(V) 空間是用于存儲每個頂點顏色的輔助空間。

(V 是上述復(fù)雜度中的頂點數(shù)。)

現(xiàn)在讓我們看一下上述相同的方法的優(yōu)化版。為了優(yōu)化解決方案，我們將使用鄰接列表代替矩陣作為輸入。

使用鄰接表的 C++ 代碼

輸入：輸入將是一個鄰接列表?，F(xiàn)在，用戶必須以源-目的地(source-destination)頂點對的形式輸入所有邊。此外，在這種情況下，我們認(rèn)為圖是無向的。因此，如果用戶輸入一條邊 V0-V1 并認(rèn)為有一條從 V0 到 V1 的邊，那么由于考慮到圖是無向的，也會有一條從 V1 到 V0 的邊自動插入。

#include 
using namespace std;

// colors: red = 1 and blue = 2
bool isGraphBipartite(vector list[], int vertices) {
    
    // make a vector for storing
    //  colors of all the vertices
    // Since all the vertices are 
    // initially uncolored,
    // fill the vector with 0s
 
    vector colors(vertices,0);

    // queue of pair will be made
    // as we will store the vertex
    // along with its color

    queue > que;
    
    // The same logic for non connected components
    // that we did using adjacency matrix
    // will be applied here

    for(int i=0;i
        // check whether the taken
        // source vertex for current
        // component is not colored
        // If found uncolored
        // apply BFS on the component

        if(colors[i] == 0) {
            
            pair srcVertex;
            srcVertex.first = i;
            srcVertex.second = 1;
            que.push(srcVertex);
            colors[i] = 1; //color the source vertex of current component red
            
            // BFS on current component of the graph
            while(!que.empty()) {
                pair front = que.front();
                que.pop();

                int currVertex = front.first;
                int currVertexColor = front.second;

               // traversing adjacent vertices of current vertex
                for(int adjVtx: list[currVertex]) {
                    if(colors[adjVtx] == currVertexColor) return false;
                    else if(colors[adjVtx] == 0) {
                        if(currVertexColor == 1) colors[adjVtx] = 2; //coloring alternatively
                        else colors[adjVtx] = 1;
                        
                        pair adjPair;  
                        adjPair.first = adjVtx;
                        adjPair.second = colors[adjVtx];
                        que.push(adjPair); 
                    }
                }
            }
        }
    }

    return true;
}
int main() {
   int vertices, edges;
   cin>>vertices>>edges;

   vector list[vertices];

   for(int i=0;i       int sv,av;
       cin>>sv>>av;

       list[sv].push_back(av);
       list[av].push_back(sv);
   }

   cout<<"The given graph is";
   if(isGraphBipartite(list,vertices) == true)       
        cout<<" bipartite\n";
   else cout<<" not bipartite\n";

   return 0;
}

輸出：

方法分析：

此代碼僅使用鄰接列表而不是矩陣。此代碼涵蓋了自循環(huán)情況，以及多個未連接組件的情況。但是，沒有涵蓋具有平行邊圖的情況。

時間復(fù)雜度：如上所述，時間復(fù)雜度為 O(V+E)。

空間復(fù)雜度：使用鄰接矩陣來存儲圖形，但輔助空間是 O(V)，即存儲每個頂點的顏色。

跟進此方法：嘗試通過相同的方法解決此問題，即為所有頂點著色，但是使用 DFS(遞歸)而不是 BFS。這意味著你必須應(yīng)用相同的方法為圖形著色，但我們使用了 BFS 來做到這一點，也建議你用遞歸 (DFS) 來嘗試一下。

方法 2：訪問級別方法 (BFS)

算法：

• 該方法基于檢查圖中的循環(huán)。如果圖是非循環(huán)的，我們將返回 true，因為非循環(huán)圖是 2-colorable 的，也就是二分的。但如果存在循環(huán)，我們需要找出它的長度是奇數(shù)還是偶數(shù)。
• 如果循環(huán)長度為奇數(shù)，則將在歐拉樹(遞歸樹)中的不同級別上再次訪問相同的頂點，而如果循環(huán)長度為偶數(shù)，則將在同一級別上再次訪問相同的頂點。

如上所示，我們正在使用 BFS 并探索源頂點的所有未訪問的相鄰頂點。在第一個圖的情況下，即具有奇數(shù)循環(huán)的圖，V4 在同一 BFS 樹的第 2 層和第 3 層上被訪問，而在具有偶數(shù)循環(huán)的圖的情況下，再次訪問的頂點(V3)在同一級別訪問。因此，在奇數(shù)長度循環(huán)的情況下，確定循環(huán)的頂點將處于兩個不同的級別，而在偶數(shù)長度循環(huán)的情況下，它將處于同一級別。

• 因此，一旦我們得到一個重復(fù)自身的頂點(它將發(fā)生在循環(huán)圖中)，我們就檢查該頂點最后一次訪問的時間，以及它的級別是否相同。
• 同樣，不要忘記該圖可以分為多個未連接的組件。因此，BFS 將應(yīng)用于每個組件。

第二種方法的 C++ 代碼

輸入：輸入將是一個鄰接列表?，F(xiàn)在，用戶必須以source-destination頂點對的形式輸入所有邊。此外，在這種情況下，我們認(rèn)為圖是無向的。因此，如果用戶輸入一條邊 V0-V1 并認(rèn)為有一條從 V0 到 V1 的邊，那么由于考慮到圖是無向的，也會有一條從 V1 到 V0 的邊自動插入。

思考過程：在應(yīng)用 BFS 時，我們不只是將頂點推送到隊列中，而是將其與正在訪問的 Level 一起推送，并且標(biāo)記為已訪問。因此，當(dāng)我們再次遇到相同的頂點時，我們將看到它之前訪問過的級別(Level)是什么。如果級別與當(dāng)前訪問的相同，則圖的分量是偶數(shù)循環(huán)的，那么該分量是二分的，但整個圖不是。為了使整個圖是二分的，所有組件都應(yīng)該是非循環(huán)的或偶數(shù)長度循環(huán)的。

#include
using namespace std;

bool isComponentBipartite(vector list[],int src,vector &visited) {
    queue > que; //this pair corresponds to vertex -> level
                               // which means vertex and the level in which
                              //  it appeared in the recursion tree
                              // of BFS

    pair srcPair;
    srcPair.first = src;
    srcPair.second = 0; //initially source is at 0 level in recursion tree
    que.push(srcPair);

    // Apply BFS
    while(!que.empty()) {
        pair front = que.front();
        que.pop();

        if(visited[front.first] != -1) { //if the vertex (i.e. front.first) is already visited 
            //since the vertex is already visited, check if the levels are not same
            if(visited[front.first] != front.second) { 
                return false; //odd length cycle detected
            }
        } else {
            visited[front.first] = front.second;
        }

        //now visit all the adjacent vertices
        for(int adj : list[front.first]) {
            if(visited[adj] == -1) {
                pair adjPair;
                adjPair.first = adj;
                adjPair.second = front.second + 1;
                que.push(adjPair);
            }
        }
    }

    return true; //either no cycle detected or all cycles were even length
}

int main() {
    int vertices,edges;
    cin>>vertices>>edges;

    vector list[vertices];
    
    for(int i=0;i        int sv;
        int dv;
        cin>>sv>>dv;

        //since non-directed graph, edges will be bi-directional
        list[sv].push_back(dv);
        list[dv].push_back(sv);
    }

    //initially no vertex is visited and hence all are at level -1
    vector visited(vertices,-1);
  
  //for non connected components as we need to check whether every component is bipartite or not
  for(int i=0;i    if(visited[i] == -1){
        bool ans=isComponentBipartite(list,i,visited);
        if(ans == false){
            cout<<"The graph is not bipartite";
                return 0;
        }
      }  
    }
      
    cout<<"Graph is bipartite";
    return 0;
}

輸出：

簡要說明：此代碼不涵蓋圖形劃分為多個組件的情況。

時間復(fù)雜度：由于我們使用鄰接表進行圖遍歷(BFS)，時間復(fù)雜度為 O(V + E)。這與著色方法相同，即如果我們使用鄰接矩陣，復(fù)雜度將是 O(V2)。所以，我們這次直接使用鄰接表來優(yōu)化方案。

空間復(fù)雜度：在 BFS 中，我們使用的隊列最多可以存儲所有 V 個頂點。因此，空間復(fù)雜度可以稱為 O(V)。 O(V + E) 是鄰接表的空間，但不是輸入空間的空間復(fù)雜度。

結(jié)論

我們學(xué)習(xí)了兩種不同的方法來檢測圖形是否為二分圖。你可以選自己順手的方法，因為兩者在復(fù)雜性(時間和空間)方面是相同的。不過，由于圖著色方法更容易理解詮釋，在顯示二分圖與 2-colorable 圖的關(guān)系時也更清晰，所以這種方法也更常見。

譯者介紹

朱鋼，社區(qū)編輯，2021年IT影響力專家博主，阿里云專家博主，2019年CSDN博客之星20強，2020年騰訊云+社區(qū)優(yōu)秀作者，11年一線開發(fā)經(jīng)驗，曾參與獵頭服務(wù)網(wǎng)站架構(gòu)設(shè)計，企業(yè)智能客服以及大型電子政務(wù)系統(tǒng)開發(fā)，主導(dǎo)某大型央企內(nèi)部防泄密和電子文檔安全監(jiān)控系統(tǒng)的建設(shè)，目前在北京圖伽健康從事醫(yī)療軟件研發(fā)工作。

原文標(biāo)題：??How to Check if a Graph is Bipartite in C++??，作者：Prashanth

本文題目：如何在C++中確定一個二分圖？
URL鏈接：http://www.dlmjj.cn/article/dhieedg.html