algorithm - 接続されたサブグラフを見つけるにはどうすればよいですか?

Question

ネットワークがありますが、このネットワークは接続されていません。このネットワークで最大の連結グラフを見つける方法を知りたいですか?

Answer 1

グラフを a[n][n] とし、i,j が接続されている場合は a[i][j]=1 とします。

次のことができます。

count=0;/global


void dfs(int i)
{

int k;
for(k=0;k<n;k++)
    if(A[i][k]==1 && !visited[k])
    {
        count++;
        visited[k]=1;
        dfs(k);
    }
}
for(i=0; i < n;i++)
    {
        if(!visited[i])
        {
            count=1;
            visited[i]=1;
            dfs(i);
                            // map i with count .. here

        }
    }

そのため、ネットワーク内のノードのカウントをそのノードの 1 つにマッピングしたら、.

あとは、マップ内で最大数のノードを見つけるだけです。

それで、 count map(i) を持つ大きなネットワークのノードである key を取得します。

訪問したすべてのノードを 0 にして、dfs(i) を再度適用すると、ネットワーク全体を接続できます

私とあなたはとにかく数を持っています。

Answer 2

もう 1 つの簡単な方法は、union-findを使用することです。

S = array filled with 1s (|V| elements)

for each edge (u,v) in E:
    if find_set(u) != find_set(v):
        sum = S[find_set(u)] + S[find_set(v)]
        S[find_set(v)] = sum
        S[find_set(u)] = sum
        union_set(u, v)

最後に、S[find_set(u)] はノード u が属する連結成分のサイズになります。最大のものを見つけるには、find max(S) が必要です。

find_set と union_set はどちらも実装が簡単なので (それぞれ C++ で 2 行)、この方法は DFS や BFS よりもずっときれいです。