C LANGUAGE TECHNOLOGY

【C言語】有向非巡回グラフ(DAG:Directed Acyclic Graph)とトポロジカルソート【幅優先探索,深さ優先探索】【仮想通貨で利用】

悩んでいる人

C言語で有向非巡回グラフ(DAG:Directed Acyclic Graph)とトポロジカルソートを教えて!

こういった悩みにお答えします.

本記事の信頼性

  • リアルタイムシステムの研究歴12年.
  • 東大教員の時に,英語でOSの授業.
  • 2012年9月~2013年8月にアメリカのノースカロライナ大学チャペルヒル校コンピュータサイエンス学部2021年の世界大学学術ランキングで20位)で客員研究員として勤務.C言語でリアルタイムLinuxの研究開発
  • プログラミング歴15年以上,習得している言語: C/C++Solidity/Vyper,Java,Python,Ruby,HTML/CSS/JS/PHP,MATLAB,Assembler (x64,ARM).
  • 東大教員の時に,C++言語で開発した「LLVMコンパイラの拡張」,C言語で開発した独自のリアルタイムOS「Mcube Kernel」GitHubにオープンソースとして公開

こういった私から学べます.

有向非巡回グラフ(DAG:Directed Acyclic Graph)

有向非巡回グラフ(DAG:Directed Acyclic Graph)は,グラフ理論における閉路のない有向グラフのことです.

有向グラフとは,頂点(vertex)と有向辺(方向を示す矢印付きの辺)(edge)からなります.

辺は頂点同士をつなぐが,ある頂点vから出発し,辺eを通り,頂点vに戻ってこないのが有向非巡回グラフです.

※頂点に戻ってくる(巡回する)のは巡回グラフです.

また,DAGは仮想通貨で利用されていて,ブロックチェーンキラーと呼ばれています.

DAGを利用する仮想通貨を知りたいあなたはこちらからどうぞ.

DAG 仮想通貨
有向非巡回グラフ(DAG:Directed Acyclic Graph)を利用する仮想通貨【ブロックチェーンキラー】

こういった悩みにお答えします. 目次1 有向非巡回グラフ(DAG:Directed Acyclic Graph)を利用する仮想通貨1.1 DAGとブロックチェーンの構造1.2 DAGとブロックチェーン ...

続きを見る

DAGの解説動画はこちらです.

DAGとトポロジカルソート【幅優先探索,深さ優先探索】

DAGとトポロジカルソートの関係を紹介します.

トポロジカルソートは,グラフ理論において,DAGの各ノードを順序付けして,どのノードもその出力辺の先のノードより前にくるように並べることです.

DAGは必ずトポロジカルソートすることができるという特徴があります.

トポロジカルソートの解説動画はこちらです.

トポロジカルソートには,幅優先探索(BFS:Breadth-First Search)深さ優先探索(DFS:Depth-First Search)の2種類があります.

BFSは探索を開始する頂点からの距離が近い順(同じ深さ順)に探索する方式で,DFSは探索を開始する頂点からの距離が遠い順(深さが深い順)に探索する方式です.

BFSとDFSの解説動画はこちらです.

C言語でDAGを利用した幅優先探索のトポロジカルソート

C言語でDAGを利用した幅優先探索のトポロジカルソートは以下になります.

実行結果は以下になります.

BFSでは「0 4 1 3 2」の順番でソートされていることがわかります.

C言語でDAGを利用した深さ優先探索のトポロジカルソート

C言語でDAGを利用した深さ優先探索のトポロジカルソートは以下になります.

実行結果は以下になります.

BFSとは異なり,DFSでは「0 1 4 3 2」の順番でソートされていることがわかります.

まとめ

C言語で有向非巡回グラフ(DAG:Directed Acyclic Graph)とトポロジカルソートを紹介しました.

具体的には,DAGで幅優先探索と深さ優先探索のトポロジカルソートを解説しました.

C言語を独学で習得することは難しいです.

私にC言語の無料相談をしたいあなたは,公式LINE「ChishiroのC言語」の友だち追加をお願い致します.

私のキャパシティもあり,一定数に達したら終了しますので,今すぐ追加しましょう!

友だち追加

独学が難しいあなたは,元東大教員がおすすめするC言語を学べるオンラインプログラミングスクール5社で自分に合うスクールを見つけましょう.後悔はさせません!

-C LANGUAGE, TECHNOLOGY
-, , , , , , ,