すべてのノードをリストに、すべてのエッジをリストに格納するJavaのグラフ実装があります。グラフは、有向および無向にすることができます。
次に、与えられた 2 つのノード a、b が接続されているかどうかをテストするアルゴリズムを検索します。
public class Graph {
private List<Node> nodes;
private List<Edge> edges;
boolean hasConnection(Node a, Node b) {
// TODO implement some Algorithm
}
}
アルゴリズムは単純で、おそらく非常に複雑になる可能性があります。BFS や DFS は使いたくありませんが、それらのアルゴリズムよりも悪いものです。
ナイーブまたはブルートフォースの亜種はありますか?