c++ - 1つの頂点で区切られたグラフ内の頂点を見つける

Question

1つの頂点で区切られ、互いに接続されていないグラフ内の頂点を見つけることができるアルゴリズム（ブルートフォースよりも優れている）を知っていますか。例：

このグラフで見つかったパスは次のようになります。

• 1 - 4
• 2 - 4
• 3 - 5

stl リストの配列をグラフ表現として使用する C++ コードが最適ですが、他の手続き型言語または疑似コードのコードでも問題ありません。

Answer 1

1 つの方法は幅優先スタイルの検索に基づくものでi、グラフ内の各頂点について、隣接する頂点に隣接する頂点をスキャンしiます (つまり、2 レベルの隣接関係!)。

mark = array[0..n-1] of 0
flag = 1

for i = nodes in graph do

// mark pattern of nodes adjacent to i 
    mark[i] = flag
    for j = nodes adjacent to i do
        mark[j] = flag
    endfor

// scan nodes adjacent to those adjacent to i
// (separated by one vertex!)
    for j = nodes adjacent to i do
    for k = nodes adjacent to j do
        if mark[k] != flag  and k > i then
        // i,k are separated by another vertex
        // and there is no edge i,k

        // prevent duplicates
            mark[k] = flag
        endif
    endfor
    endfor

// implicit unmarking of current pattern
    flag += 1

endfor

グラフにm頂点ごとにエッジがある場合、これは余分なスペースO(n * m^2)を必要とするアルゴリズムになります。O(n)

Answer 2

この問題に対する単純で直感的な解決策の 1 つは、隣接行列にあります。ご存知のように、隣接行列の n 乗の (i,j) 番目の要素には、i と j の間の長さが正確に n のすべてのパスがリストされます。
したがって、隣接行列である A を読み込んで、A^2 を計算します。最後に、長さ 2 のパスが 1 つだけあるすべてのペアをリストします。

//sg
#include<stdio.h>
#define MAX_NODE 10
int main()
{
    int a[MAX_NODE][MAX_NODE],c[MAX_NODE][MAX_NODE];
    int i,j,k,n;
    printf("Enter the number of nodes : ");
    scanf("%d",&n);
    for(i=0;i<n;i++)
    for(j=0;j<=i;j++)
    {
        printf("Edge from %d to %d (1 yes/0 no) ? : ",i+1,j+1);
        scanf("%d",&a[i][j]);
        a[j][i]=a[i][j]; //undirected graph
    }
    //dump the graph
    for(i=0;i<n;i++)
    {
    for(j=0;j<n;j++)
    {
        c[i][j]=0;
        printf("%d",a[i][j]);
    }
    printf("\n");
    }
    printf("\n");

    //multiply
    for(i=0;i<n;i++)
    for(j=0;j<n;j++)
    for(k=0;k<n;k++)
    {
        c[i][j]+=a[i][k]*a[k][j];
    }
    //result of the multiplication
    for(i=0;i<n;i++)
    {
    for(j=0;j<n;j++)
    {
        printf("%d",c[i][j]);
    }
    printf("\n");
    }
    for(i=0;i<n;i++)
    for(j=0;j<=i;j++)
    {
        if(c[i][j]==1&&(!a[i][j])&&(i!=j)) //list the paths
        {
            printf("\n%d - %d",i+1, j+1 );

        }
    }
    return 0;
}

グラフのサンプル実行

[aman@aman c]$ ./Adjacency2 
Enter the number of nodes : 5
Edge from 1 to 1 (1 yes/0 no) ? : 0
Edge from 2 to 1 (1 yes/0 no) ? : 1
Edge from 2 to 2 (1 yes/0 no) ? : 0
Edge from 3 to 1 (1 yes/0 no) ? : 1
Edge from 3 to 2 (1 yes/0 no) ? : 1
Edge from 3 to 3 (1 yes/0 no) ? : 0
Edge from 4 to 1 (1 yes/0 no) ? : 0
Edge from 4 to 2 (1 yes/0 no) ? : 0
Edge from 4 to 3 (1 yes/0 no) ? : 1
Edge from 4 to 4 (1 yes/0 no) ? : 0
Edge from 5 to 1 (1 yes/0 no) ? : 0
Edge from 5 to 2 (1 yes/0 no) ? : 0
Edge from 5 to 3 (1 yes/0 no) ? : 0
Edge from 5 to 4 (1 yes/0 no) ? : 1
Edge from 5 to 5 (1 yes/0 no) ? : 0
01100
10100
11010
00101
00010

21110
12110
11301
11020
00101

4 - 1
4 - 2
5 - 3

n 個の頂点の分析:

• 時間: O(n^3) . O(n^2.32)に減らすことができます。これは非常に優れています。

• スペース : O(n^2)。