与えられたグラフ、隣接行列を使用して深さ優先検索 (DFS) トラバーサルを実装する C プログラム

＃＃＃＃＃＃＃＃＃＃＃＃＃＃＃導入＃＃＃

グラフ理論を使用すると、オブジェクトまたはエンティティ間の関係を研究および視覚化できます。現在のコンピューター サイエンス テクノロジでは、グラフ トラバーサルは、さまざまな種類のデータ構造を探索および分析する際に重要な役割を果たしています。グラフ上で実行される重要な操作の 1 つはトラバーサルです。つまり、特定のパスをたどってすべての頂点またはノードを訪問します。深さ優先アプローチに基づく DFS トラバーサルにより、バックトラックして他のブランチを探索する前に、グラフの深さを探索できます。この記事では、C で隣接行列表現を使用して DFS トラバーサルを実装します。

DFS トラバーサルに隣接マトリックスを使用する

グラフは 2 つの主要コンポーネントで構成されます。つまり、エンティティまたは要素を表す頂点またはノードと、これらの頂点を接続し、それらの頂点間の関係を記述するエッジです。

加重グラフまたは加重なしグラフの頂点間の関係を表す唯一の方法は、隣接行列を使用することです。通常、これは正方行列の形式をとり、行はソース頂点を表し、列はターゲット頂点を表し、各セルには対応するペア間のエッジの存在または重みに関する情報が含まれます。

＃＃＃例＃＃＃

入力は、グラフの 4 つの頂点を使用する特定の要素セットを通じて与えられます。入力は次のとおりです。

リーリー

グラフの開始頂点が 2 であるとします。グラフは頂点「2」から開始してトラバースされます。頂点「2」の隣接する頂点は明らかに 1 と 3 です。開始頂点は 2 であるため、トラバース中に再度アクセスすることはできません。頂点 2 の後に頂点 3 が訪問されるので、頂点 3 の隣接する頂点 1 と 2 をチェックする必要があります。頂点 1 と頂点 2 が訪問され、トラバースが停止します。

方法 1: 隣接行列を指定されたグラフの入力として使用する DFS トラバーサルを含む C プログラム

入力はいくつかの数値で定義され、for ループを使用して隣接行列を反復し、DFS トラバーサルを返します。

＃＃＃アルゴリズム＃＃＃

ステップ 1

: プログラムはまず、指定されたグラフ内のノードの最大数を表す定数「MAX」を定義し、「visited」という名前の配列を初期化して、実行中に特定のノードが存在するかどうかを追跡します。トラバースが訪問されました。

ステップ 2

: 「dfs()」関数はパラメータとして正方隣接行列を受け取ります。「adjMatrix」はグラフを表します。頂点の総数は「vCount」、開始頂点は次のとおりです。 「開始」。この関数は、指定されたグラフの再帰的深さ優先検索トラバーサルを実行します。

ステップ 3

: 「dfs()」関数では、ブールベースの「visited[]」配列のインデックスを使用して、現在処理されている各頂点を「visited」としてマークし、その値を出力します。それに応じて。

ステップ 4

: 「dfs()」内のループは、現在のノードに接続されている頂点を取得できなくなるまで、現在のノードの未訪問の隣接ノードをすべて再帰的に繰り返します。

ステップ 5

: main() では、ネストされたループを使用して、「vCount」の頂点の数や隣接行列への対応する接続​​などのユーザー入力を読み取ります。

ステップ 6

: 次に、ユーザーに希望の開始頂点の入力を求め、「visited[]」配列の各要素をゼロに初期化します (まだ訪問したノードがないため)。

ステップ 7

: 最後に、プログラムは適切なパラメーターを指定して「dfs()」関数を呼び出し、深さ優先検索の走査を開始し、DFS 走査パスを出力します。 ＃＃＃例＃＃＃ リーリー ＃＃＃出力＃＃＃ リーリー ＃＃＃結論は＃＃＃ グラフの表現として隣接行列を使用することにより、大規模または複雑なデータ セットに対して DFS を効率的に実行できます。この論文では、これを詳細に説明し、隣接行列ベースの表現を使用して深さ優先検索トラバーサルを実装する C プログラムを提案します。深さ優先検索は、グラフ構造を探索および分析するための強力なアルゴリズムです。

以上が与えられたグラフ、隣接行列を使用して深さ優先検索 (DFS) トラバーサルを実装する C プログラムの詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。