C++ を使用してグラフ内のシンク ノードの数を見つける

この記事では、グラフ内のシンク ノードの数を解決するための重要な情報について説明します。この問題では、N 個のノード (1 ～ N) と M 個のエッジを持つ有向非巡回グラフがあります。目標は、特定のグラフ内にシンク ノードがいくつあるかを確認することです。シンク ノードは、出力エッジを生成しないノードです。これは簡単な例です -

Input : n = 4, m = 2

Edges[] = {{2, 3}, {4, 3}}
Output : 2

解決策を見つける簡単な方法

このアプローチでは、グラフのエッジをトラバースして、エッジが指すセットからさまざまな要素をグラフにプッシュします。存在するノードの総数からセットのサイズを減算します。

例

#include 
using namespace std;
int main(){
    int n = 4; // number of nodes.
    int m = 2; // number of edges.
    vector> edges = {{2, 3}, {4, 3}}; // the edges going from first to second.
    set s;
    for(int i = 0; i < m; i++){
        s.insert(edges[i].first); // will keep value of
                               // distinct node from which edges are going out.
    }
    cout << n - s.size(); // answer is the total number of nodes - number of non sink nodes.
    return 0;
}

出力

2

上記のコードの説明

このコードでは、ベクトルのエッジを反復処理し、最初のエッジを追加します。ペア要素がコレクションに挿入されます。個別の要素のみを保持するため、ノードの総数からコレクションの特定のサイズを減算します。上に示したプログラムの時間計算量は O(N) です。ここで、N はグラフ内に存在するエッジの数を表します。

結論

この記事では、セットの助けを借りて、O(N) 時間計算量でグラフ内に存在するシンク ノードの数を見つける問題を解決しました。また、この問題を解決するための C プログラムと、この問題を解決するための完全な方法も学びました。同じプログラムを C、Java、Python などの他の言語で書くことができます。この記事がお役に立てば幸いです。

以上がC++ を使用してグラフ内のシンク ノードの数を見つけるの詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。