3

無向グラフが二部かどうかを判断するアルゴリズムを実装しています。この疑似コードに基づいて、接続されたグラフで機能する実装を作成しましたが、接続されていない場合、プログラムは単に間違った答えを示します。接続されていない場合は、バラバラのサブグラフごとにもう1つのループが必要だと思います。しかし、私はこれにこだわっています。正しい答えを印刷するためにコードを解決するにはどうすればよいですか?

#include <cstdio>
#include <vector>
#include <queue>
#include <iostream>
using namespace std;

#define MAX 1000

int numberVertex, numberEdges;
int particion[MAX], visited[MAX];
vector< int > adjacencyMatrix[MAX];

bool bfs()
{
    int i, origin, destination, begin;
    queue< int > queueVertex;
    begin = 0;
    queueVertex.push(begin);
    particion[begin] = 1; // 1 left,
    visited[begin] = 1; // set adjacencyMatrixray

    while(!queueVertex.empty())
    {
        origin = queueVertex.front(); queueVertex.pop();
        for(i=0; i < adjacencyMatrix[origin].size(); i++)
        {
            destination = adjacencyMatrix[origin][i];
            if(particion[origin] == particion[destination])
            {
                return false;
            }
            if(visited[destination] == 0)
            {
                visited[destination] = 1;
                particion[destination] = 3 - particion[origin]; // alter 1 and 2 subsets
                queueVertex.push(destination);
            }
        }
    }
    return true;
}

int main()
{
 freopen("tarea2.in", "r", stdin);
    int i,j, nodeOrigin, nodeDestination;
    scanf("%d %d", &numberVertex, &numberEdges);
    for(i=0; i<numberEdges; i++)
    {
        scanf("%d %d", &nodeOrigin, &nodeDestination);
        adjacencyMatrix[nodeOrigin].push_back(nodeDestination);
        adjacencyMatrix[nodeDestination].push_back(nodeOrigin);
    }
    if(bfs()) {

        printf("Is bipartite\n");
          for (j=0; j<numberVertex; j++){
        cout<<j<<" "<<particion[j]<<endl;
        }

    }
    else {printf("Is not bipartite\n");}





    return 0;
}

たとえば、この入力の場合

6 4
3 0
1 0
2 5
5 4

出力は次のようになります。

Is bipartite
0 1
1 2
2 1
3 2
4 1
5 2

代わりに私に出力をスローします：

0 1
1 2
2 0
3 2
4 0
5 0

これは、グラフが連結グラフではない、つまり 2 つの連結要素があるために発生します。数日間この問題に悩まされていたので、助けていただければ幸いです。

4

3 に答える 3

7

接続されたすべてのコンポーネントで bfs を実行する必要があります。これを行う最も簡単な方法は、すべての頂点を反復処理し、それらがアクセスされていない場合は、それらに対して bfs を呼び出すことです。

bool is_bipartite()
{
    for(int i = 0; i < numberVertex; i++)
    {
       if (visited[i] == 0 && !bfs(i)) {
           return false;
       }
    } 
    return true;
}

接続されたすべてのコンポーネントで bfs を 1 回実行するため、依然として線形です。

#include <cstdio>
#include <vector>
#include <queue>
#include <iostream>
using namespace std;

#define MAX 1000

int numberVertex, numberEdges;
int particion[MAX], visited[MAX];
vector< int > adjacencyMatrix[MAX];

bool bfs(int begin)
{
    int i, origin, destination;
    queue< int > queueVertex;
    queueVertex.push(begin);
    particion[begin] = 1; // 1 left,
    visited[begin] = 1; // set adjacencyMatrixray

    while(!queueVertex.empty())
    {
        origin = queueVertex.front(); queueVertex.pop();
        for(i=0; i < adjacencyMatrix[origin].size(); i++)
        {
            destination = adjacencyMatrix[origin][i];
            if(particion[origin] == particion[destination])
            {
                return false;
            }
            if(visited[destination] == 0)
            {
                visited[destination] = 1;
                particion[destination] = 3 - particion[origin]; // alter 1 and 2 subsets
                queueVertex.push(destination);
            }
        }
    }
    return true;
}

bool is_bipartite()
{
    for(int i=0; i< numberVertex; i++)
    {
       if (visited[i] == 0 && !bfs(i)) {
           return false;
       }
    } 
    return true;
}

int main()
{
    //freopen("tarea2.in", "r", stdin);
    int i,j, nodeOrigin, nodeDestination;
    scanf("%d %d", &numberVertex, &numberEdges);
    for(i=0; i<numberEdges; i++)
    {
        scanf("%d %d", &nodeOrigin, &nodeDestination);
        adjacencyMatrix[nodeOrigin].push_back(nodeDestination);
        adjacencyMatrix[nodeDestination].push_back(nodeOrigin);
    }
    if(is_bipartite()) {

        printf("Is bipartite\n");
          for (j=0; j<numberVertex; j++){
        cout<<j<<" "<<particion[j]<<endl;
        }

    }
    else {printf("Is not bipartite\n");}

    return 0;
}
于 2012-03-27T05:05:49.483 に答える
1

2 部グラフは 2 色グラフとも呼ばれます。つまり、2 部グラフのすべてのノードを 2 色だけで色付けして、隣接する 2 つのノードが同じ色にならないようにすることができます。

  • 最初に、すべての頂点に色がないようにします。

  • 任意の頂点から開始し、RED で色付けします。次に、隣接するすべての頂点を赤以外の色で色付けします。たとえば、黒とします。

  • すべてのノードに色が付くまでこれを繰り返します。任意の時点で、隣接する 2 つのノードが同じ色であることがわかった場合。その場合、それは二部グラフではありません。

C++ 実装

于 2016-11-15T13:26:59.967 に答える