1

レモンには検索アルゴリズムと最短経路アルゴリズムが含まれているため、パスファインディングを処理するためにレモンを探しています。

問題は、私はレモンがどのように機能するかを理解するのに最初から立ち往生していて、彼らにはチュートリアルがありますが、質問するフォーラムがありません。

有向グラフについての私の理解は、あなたにはノードがあり、それは別のノードにリンクすることもリンクしないこともでき、それからあなたはそれに重みを持っているということです。

例：

     A    B    C
A    0    1    0
B    1    0    5
C    0    0    0

この場合、AはB1の重みでC接続され、何にも接続されません（したがって、一度到達するCとスタックします）、1の値でB接続し、5の値で接続します。ABC

チュートリアルでは、次のようなことを行うように指示されています。

ListDigraph g;
ListDigraph::Node A = g.addNode();
ListDigraph::Node B = g.addNode();
ListDigraph::Node C = g.addNode();

これgで、3つのノードを持つグラフができました。それで？接続情報と重み値をどこに/どのように追加しますか？

4

2 に答える 2

4

レモンチュートリアルから

  ListDigraph g;

  ListDigraph::Node x = g.addNode();
  ListDigraph::Node y = g.addNode();
  ListDigraph::Node z = g.addNode();

  g.addArc(x,y);
  g.addArc(y,z);
  g.addArc(z,x);

このライブラリマインドを使用したことはありません。私が読んだものを引用しているだけです。

于 2012-08-07T20:21:26.633 に答える
0

LEMONは、ほとんどのグラフ理論のテキストとは少し異なる用語を使用していますが、私の意見では、ライブラリの使用が少し簡単になります。

まず、LEMONのエッジとアークの違いは、エッジが2つのノード間の無向エッジであり、アークが有向エッジであるということです。

エッジや重みなどの追加に関しては、グラフ自体はノードとエッジ/アークのみを管理し、それぞれに関連付けられているデータは整数識別子のみです。

この識別子は、次を使用して見つけることができます。

graph.id(node);

データをノード/エッジにアタッチするには、マップを使用します。マップにはいくつかの異なるタイプがありますが、一般的には、、、NodeMapまたはEdgeMap-に要約さArcMapれます。おそらくお察しのとおり、これらはそれぞれ、、およびの連想マップです<Node, V>。<Edge, V>ここ<Arc, V>でV、は値タイプです（デフォルトのコンストラクター）。

エッジ（無向グラフの場合）または円弧（有向グラフの場合）を追加するには、2つのノードを作成してから、.addEdge(n1, n2)またはを使用します.addArc(n1, n2)。

例えば：

ListDigraph graph;

ListDigraph::Node n1 = graph.addNode();
ListDigraph::Node n2 = graph.addNode();

ListDigraph::Arc a = graph.addArc(n1, n2);

そして、ある値をそのアークに関連付けるには、次のようにします。

ArcMap<std::string> arcMap;

arcMap[a] = "This is an arc value!";
于 2016-03-07T03:41:26.303 に答える