コース: 試験対策：基本情報技術者試験 データ構造とアルゴリズム
今すぐ登録して、24,700件以上登録されている、業界エキスパート指導のコースを受講しましょう。
無向グラフを表現する
このレッスンでは、 無向グラフの基本概念と、 それを表現するための ２つの主要な方法である 隣接行列とエッジリストについて学びます。 無向グラフは、 特定の方向性がない関係性を モデル化するのに非常に適しており、 ソーシャルネットワークや コンピューターネットワークなど、 様々な分野で広く使用されています。 無向グラフとは、 グラフ理論における グラフの種類のひとつで、 ノードとそれらをつなぐ エッジで構成されます。 エッジは無向であり、 ２つのノードを結ぶ線に方向がありません。 無向グラフを作成する方法には いくつかありますが、 このレッスンでは、 隣接行列とエッジリストを取り上げます。 隣接行列は、 ノード間の接続を行列で表現する方法で、 各セルに、 ノード間のエッジの有無を示す 値が入ります。 行と列は、それぞれノードを表します。 要素が１の場合、 その行と列に対応するノード間に エッジが存在することを示し、 ０の場合は、 エッジが存在しないことを示します。 例えば、この隣接行列は、 図の無向グラフを表しています。 ノード１は、ノード３とノード４と 接続されています。 ノード２はノード４と、 ノード３は、ノード１とノード４と、 ノード４は ノード１、２、３、５と 接続されています。 そしてノード５は ノード４と接続されています。 今度はエッジリストについて 説明しましょう。 エッジリストは、ノード間の接続を エッジのリストとして表現する方法で、 各エッジをノードのペアとして記録します。 各エッジを u と v という形式で表し、 ノード u とノード v の間に エッジが存在することを示します。 エッジリストは 無向グラフに対応しているため、 {u,v} と {v,u} は同一視されます。 例えば、このエッジリストは 図の無向グラフに対応しています。 ノード１とノード３、 ノード１とノード４、 ノード３とノード４、 ノード２とノード４、 ノード４とノード５、 それぞれが接続されていることが わかります。 では、与えられてエッジリストを使って 隣接行列を作成するプログラムを 確認してみましょう。 このプログラムは、 引数で渡されたノード間のエッジを示す 整数型配列の配列の エッジリストとノードの総数を表す nodeNum をもとに 隣接行列を作成し、…
コースをダウンロードして学習しましょう。
ラーニングコースをダウンロードしてオフラインで視聴しましょう。ダウンロードしたコースはLinkedInラーニングのモバイルアプリ (iOSまたはAndroid) で視聴できます。