C言語で有向非巡回グラフ（DAG：Directed Acyclic Graph）とトポロジカルソートを教えて！
こういった悩みにお答えします．
本記事の信頼性
- リアルタイムシステムの研究歴12年．
- 東大教員の時に，英語でOS（Linuxカーネル）の授業．
- 2012年9月～2013年8月にアメリカのノースカロライナ大学チャペルヒル校（UNC）コンピュータサイエンス学部で客員研究員として勤務．C言語でリアルタイムLinuxの研究開発．
- プログラミング歴15年以上，習得している言語: C/C++，Python，Solidity/Vyper，Java，Ruby，Go，Rust，D，HTML/CSS/JS/PHP，MATLAB，Assembler (x64，ARM)．
- 東大教員の時に，C++言語で開発した「LLVMコンパイラの拡張」，C言語で開発した独自のリアルタイムOS「Mcube Kernel」をGitHubにオープンソースとして公開．
- 2020年1月～現在はアメリカのノースカロライナ州チャペルヒルにあるGuarantee Happiness LLCのCTOとしてECサイト開発やWeb/SNSマーケティングの業務．2022年6月～現在はアメリカのノースカロライナ州チャペルヒルにあるJapanese Tar Heel, Inc.のCEO兼CTO．
- 最近は自然言語処理AIとイーサリアムに関する有益な情報発信に従事．
- （AI全般を含む）自然言語処理AIの論文の日本語訳や，AIチャットボット（ChatGPT，Auto-GPT，Gemini（旧Bard）など）の記事を50本以上執筆．アメリカのサンフランシスコ（広義のシリコンバレー）の会社でプロンプトエンジニア・マネージャー・Quality Assurance（QA）の業務委託の経験あり．
- （スマートコントラクトのプログラミングを含む）イーサリアムや仮想通貨全般の記事を200本以上執筆．イギリスのロンドンの会社で仮想通貨の英語の記事を日本語に翻訳する業務委託の経験あり．
こういった私から学べます．
C言語を独学で習得することは難しいです．
私にC言語の無料相談をしたいあなたは，公式LINE「ChishiroのC言語」の友だち追加をお願い致します．
私のキャパシティもあり，一定数に達したら終了しますので，今すぐ追加しましょう！
独学が難しいあなたは，元東大教員がおすすめするC言語を学べるオンラインプログラミングスクール5社で自分に合うスクールを見つけましょう．後悔はさせません！
有向非巡回グラフ（DAG：Directed Acyclic Graph）
有向非巡回グラフ（DAG：Directed Acyclic Graph）は，グラフ理論における閉路のない有向グラフのことです．
有向グラフとは，頂点（vertex）と有向辺（方向を示す矢印付きの辺）（edge）からなります．
辺は頂点同士をつなぐが，ある頂点vから出発し，辺eを通り，頂点vに戻ってこないのが有向非巡回グラフです．
※頂点に戻ってくる（巡回する）のは巡回グラフです．
また，DAGは仮想通貨で利用されていて，ブロックチェーンキラーと呼ばれています．
DAGを利用する仮想通貨を知りたいあなたはこちらからどうぞ．
DAGの解説動画はこちらです．
DAGとトポロジカルソート【幅優先探索，深さ優先探索】
DAGとトポロジカルソートの関係を紹介します．
トポロジカルソートは，グラフ理論において，DAGの各ノードを順序付けして，どのノードもその出力辺の先のノードより前にくるように並べることです．
DAGは必ずトポロジカルソートすることができるという特徴があります．
トポロジカルソートの解説動画はこちらです．
トポロジカルソートには，幅優先探索（BFS：Breadth-First Search）と深さ優先探索（DFS：Depth-First Search）の2種類があります．
BFSは探索を開始する頂点からの距離が近い順（同じ深さ順）に探索する方式で，DFSは探索を開始する頂点からの距離が遠い順（深さが深い順）に探索する方式です．
BFSとDFSの解説動画はこちらです．
C言語でDAGを利用した幅優先探索のトポロジカルソート
C言語でDAGを利用した幅優先探索のトポロジカルソートは以下になります．
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 |
/* * Author: Hiroyuki Chishiro * License: 2-Clause BSD */ #include <stdio.h> #include <stdlib.h> #include <stdbool.h> #define N 5 int n; int adjacent[N][N] = { {0, 1, 0, 0, 1}, {0, 0, 1, 1, 0}, {0, 0, 0, 0, 0}, {0, 0, 1, 0, 0}, {0, 0, 0, 1, 0} }; bool visited[N]; int depth[N]; int result[N]; int idx = 0; int next_vertex(void) { int i; for (i = 0; i < N; i++) { if (!visited[i]) { visited[i] = true; return i; } } return -1; } void bfs(void) { int i; int v; while ((v = next_vertex()) != -1) { result[idx++] = v; for (i = 0; i < N; i++) { if (adjacent[v][i] == 1) { adjacent[v][i] = 0; depth[i]--; if (depth[i] == 0) { result[idx++] = i; visited[i] = true; } } } } } int main(void) { int i, j; printf("adjacency matrix:\n"); printf(" |"); for (i = 0; i < N; i++) { printf(" %2d", i); } printf("\n"); for (i = 0; i <= N; i++) { printf("---"); } printf("\n"); for (i = 0; i < N; i++) { printf("%2d|", i); depth[i] = 0; for (j = 0; j < N; j++) { printf(" %2d", adjacent[i][j]); if (adjacent[i][j] == 1) { depth[i]++; } } printf("\n"); } for (i = 0; i < N; i++) { visited[i] = false; } bfs(); printf("result: "); for (i = 0; i < N; i++) { printf("%d ", result[i]); } printf("\n"); return 0; } |
実行結果は以下になります．
BFSでは「0 4 1 3 2」の順番でソートされていることがわかります．
|
1 2 3 4 5 6 7 8 9 10 11 |
$ gcc topological_sort_bfs.c $ a.out adjacency matrix: | 0 1 2 3 4 ------------------ 0| 0 1 0 0 1 1| 0 0 1 1 0 2| 0 0 0 0 0 3| 0 0 1 0 0 4| 0 0 0 1 0 result: 0 4 1 3 2 |
C言語でDAGを利用した深さ優先探索のトポロジカルソート
C言語でDAGを利用した深さ優先探索のトポロジカルソートは以下になります．
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 |
/* * Author: Hiroyuki Chishiro * License: 2-Clause BSD */ #include <stdio.h> #include <stdlib.h> #include <stdbool.h> #define N 5 enum {NEVER, JUST, ONCE}; int n; int adjacent[N][N] = { {0, 1, 0, 0, 1}, {0, 0, 1, 1, 0}, {0, 0, 0, 0, 0}, {0, 0, 1, 0, 0}, {0, 0, 0, 1, 0} }; int visited[N]; int result[N]; int idx = 0; void dfs(int i) { int j; visited[i] = JUST; for (j = 0; j < N; j++) { if (!adjacent[j][i]) { continue; } if (visited[j] == NEVER) { dfs(j); } else if (visited[j] == JUST) { fprintf(stderr, "Error: No DAG!n"); exit(1); } } visited[i] = ONCE; result[idx++] = i; } int main(void) { int i, j; printf("adjacency matrix:\n"); printf(" |"); for (i = 0; i < N; i++) { printf(" %2d", i); } printf("\n"); for (i = 0; i <= N; i++) { printf("---"); } printf("\n"); for (i = 0; i < N; i++) { printf("%2d|", i); for (j = 0; j < N; j++) { printf(" %2d", adjacent[i][j]); } printf("\n"); } for (i = 0; i < N; i++) { visited[i] = NEVER; } for (i = 0; i < N; i++) { if (visited[i] == NEVER) { dfs(i); } } printf("result: "); for (i = 0; i < N; i++) { printf("%d ", result[i]); } printf("\n"); return 0; } |
実行結果は以下になります．
BFSとは異なり，DFSでは「0 1 4 3 2」の順番でソートされていることがわかります．
|
1 2 3 4 5 6 7 8 9 10 11 |
$ gcc topological_sort_dfs.c $ a.out adjacency matrix: | 0 1 2 3 4 ------------------ 0| 0 1 0 0 1 1| 0 0 1 1 0 2| 0 0 0 0 0 3| 0 0 1 0 0 4| 0 0 0 1 0 result: 0 1 4 3 2 |
まとめ
C言語で有向非巡回グラフ（DAG：Directed Acyclic Graph）とトポロジカルソートを紹介しました．
具体的には，DAGで幅優先探索と深さ優先探索のトポロジカルソートを解説しました．
C言語を独学で習得することは難しいです．
私にC言語の無料相談をしたいあなたは，公式LINE「ChishiroのC言語」の友だち追加をお願い致します．
私のキャパシティもあり，一定数に達したら終了しますので，今すぐ追加しましょう！
独学が難しいあなたは，元東大教員がおすすめするC言語を学べるオンラインプログラミングスクール5社で自分に合うスクールを見つけましょう．後悔はさせません！
