はじめに
この記事は、Siv3D Advent Calendar 2023 5 日目の記事です。
こんにちは。Sapph (さふ) といいます。普段は競技プログラミングや楽曲制作をしています。絶賛受験期真っ只中であり、受験勉強の合間を縫って書いたので、拙い記事となってしまったことをご容赦ください。
さて、今回のテーマは アルゴリズムのビジュアライザ です。昨年の AdC で、セグメント木の可視化に関する記事 を投稿されている方がいましたが、これを他のアルゴリズムでもやってみました（昨年の私の記事 の最後の方にちょこっと触れています）。
いくつか実装しましたが、今回は幅優先探索 (BFS)・深さ優先探索 (DFS) について紹介しようと思います（実装にあたって、複数の方々にコードをレビューしていただきました。ありがとうございました！）。
実物
それっぽい二分木を用意して、頂点 0 を始点とし、探索可能な頂点を黄色で、探索済みの頂点を緑で色付けしました。
実装
BFS・DFS は「どの頂点を優先して探索するか」が違うだけなので、大部分の実装は同じです。以下は BFS での実装です。
Main 関数以外の部分です。グラフの描画に関する部分です。
using NodeID = int32;
// ノードの状態
enum class NodeState
{
/// @brief 未訪問
NotVisited,
/// @brief アクティブ
Active,
/// @brief アクティブなノードから行けるノード
Next,
/// @brief 訪問済みのノード
Visited,
};
// ノードの描画
struct Node
{
NodeID id;
Vec2 pos;
Circle getCircle() const
{
return Circle{ pos, 40 };
}
void draw(const Font& font, NodeState state) const
{
const Circle circle = getCircle();
circle.drawShadow(Vec2{ 1, 1 }, 8, 1);
if (state == NodeState::NotVisited)
{
circle.draw();
}
else if (state == NodeState::Active)
{
circle.draw(ColorF{ 1.0, 0.9, 0.8 });
}
else if (state == NodeState::Next)
{
circle.draw(Palette::Lemonchiffon);
}
else // NodeState::Visited
{
circle.draw(Palette::Lightgreen);
}
font(id).drawAt(pos, ColorF{ 0.25 });
}
};
struct Edge
{
NodeID from;
NodeID to;
};
// 2 つのノード間に線を引く関数
void DrawEdge(const Node& from, const Node& to)
{
Line{ from.pos, to.pos }.draw(3, ColorF{ 0.25 });
}
Main 関数です。グラフの構造の定義と、探索に必要な諸々のデータ構造の定義をしています（これは BFS の例なので、探索するノードの管理は Array を用いてキューの処理をしますが、Siv3D の Array は push_back() も push_front() もできるので、ノードの管理にスタックを用いる DFS でも Array を使用します）。
void Main()
{
Scene::SetBackground(ColorF{ 0.8, 0.9, 1.0 });
const Font font{ 40, Typeface::Bold };
//----------- BFS に使用するデータ構造・変数-------------
// 頂点
Array<Node> nodes =
{
Node{ 0, Vec2{ 400, 130 } },
Node{ 1, Vec2{ 200, 260 } },
Node{ 2, Vec2{ 600, 260 } },
Node{ 3, Vec2{ 100, 390 } },
Node{ 4, Vec2{ 300, 390 } },
Node{ 5, Vec2{ 500, 390 } },
Node{ 6, Vec2{ 700, 390 } },
Node{ 7, Vec2{ 50, 530 } },
Node{ 8, Vec2{ 150, 530 } },
Node{ 9, Vec2{ 250, 530 } },
Node{ 10, Vec2{ 350, 530 } },
Node{ 11, Vec2{ 450, 530 } },
Node{ 12, Vec2{ 550, 530 } },
Node{ 13, Vec2{ 650, 530 } },
Node{ 14, Vec2{ 750, 530 } },
};
// 無向辺
const Array<Edge> edges =
{
Edge{ 0, 2 },
Edge{ 0, 1 },
Edge{ 1, 4 },
Edge{ 1, 3 },
Edge{ 2, 6 },
Edge{ 2, 5 },
Edge{ 3, 8 },
Edge{ 3, 7 },
Edge{ 4, 10 },
Edge{ 4, 9 },
Edge{ 5, 12 },
Edge{ 5, 11 },
Edge{ 6, 14 },
Edge{ 6, 13 },
};
// 隣接リスト
Array<Array<NodeID>> grpah(nodes.size());
for (const auto& edge : edges)
{
grpah[edge.to].push_back(edge.from);
grpah[edge.from].push_back(edge.to);
}
// スタートからの距離
Array<NodeID> distances(nodes.size(), -1);
distances[0] = 0;
// 探索をスタートする頂点
NodeID start = 0;
// キュー
Array<NodeID> todo = { 0 };
while (System::Update())
{
// 別途記載
}
}
while 文の中身です。ボタンを押すごとに、探索が一回進む実装にしました。また、各データ構造の要素を左上に表示するようにしています。
while (System::Update())
{
ClearPrint();
Print << U"start：" << start;
Print << U"todo：" << todo;
Print << U"distances：" << distances;
// 辺の描画
for (const auto& edge : edges)
{
DrawEdge(nodes[edge.from], nodes[edge.to]);
}
// 頂点の描画
for (int32 i = 0; i < (int32)nodes.size(); ++i)
{
const auto& node = nodes[i];
if (todo.includes(i))
{
nodes[i].draw(font, NodeState::Next);
}
else if (distances[i] != -1)
{
nodes[i].draw(font, NodeState::Visited);
}
else
{
nodes[i].draw(font, NodeState::NotVisited);
}
}
if (SimpleGUI::Button(U"リセット", Vec2{ 500, 60 }))
{
start = 0;
distances.assign((int32)nodes.size(), -1);
distances[start] = 0;
todo.clear();
todo = { start };
}
if (SimpleGUI::Button(U"一手進める", Vec2{ 500, 20 }, none, (not todo.isEmpty())))
{
const auto pos = todo.back();
todo.pop_back();
for (const auto& to : grpah[pos])
{
// 探索済みであれば何もしない
if (distances[to] != -1)
{
continue;
}
// 最短距離の更新
distances[to] = (distances[pos] + 1);
todo.push_back(to);
}
}
}
終わりに
BFS 、DFS の可視化に挑戦してみました。実際に動きを見ることでアルゴリズムへの理解が深まりました。この両者は似ているので、比較をするととても面白いですよね。ダイクストラ法や Ford-Fulkerson 法といった、私がまだ全く理解できていないアルゴリズムも、いつか可視化して、理解を深められればと思います。
これは私事ですが、間もなく大学受験が始まるので応援していただけると力になります。一般なので周りがどんどん推薦で受かっていてつらいです><
最後までお読みいただきありがとうございました。よい年末をお過ごしください。