質問をすることでしか得られない、回答やアドバイスがある。

15分調べてもわからないことは、質問しよう!

新規登録して質問してみよう
ただいま回答率
85.50%
C++

C++はC言語をもとにしてつくられた最もよく使われるマルチパラダイムプログラミング言語の1つです。オブジェクト指向、ジェネリック、命令型など広く対応しており、多目的に使用されています。

Q&A

1回答

2043閲覧

こちらのサイトにある「各種アルゴリズムのC++による実装」の使い方について

minagawa72

総合スコア8

C++

C++はC言語をもとにしてつくられた最もよく使われるマルチパラダイムプログラミング言語の1つです。オブジェクト指向、ジェネリック、命令型など広く対応しており、多目的に使用されています。

0グッド

0クリップ

投稿2015/12/06 09:02

http://www.prefield.com/algorithm/index.html
こちらのサイトにある「各種アルゴリズムのC++による実装」の使い方について知りたく、質問させていただきました。

グラフ、全域木のところにある「最小全域有向木」のプログラムの使い方がわからず困っております。

ソースコードは

・テンプレート

C++

1#define _GLIBCXX_DEBUG 2#include <iostream> 3#include <vector> 4 5using namespace std; 6 7#define REP(i,n) for(int i=0;i<(int)n;++i) 8#define FOR(i,c) for(__typeof((c).begin())i=(c).begin();i!=(c).end();++i) 9#define ALL(c) (c).begin(), (c).end() 10 11int main() { 12 13}

・最小全域有向木

C++

1void visit(Graph &h, int v, int s, int r, 2 vector<int> &no, vector< vector<int> > &comp, 3 vector<int> &prev, vector< vector<int> > &next, vector<Weight> &mcost, 4 vector<int> &mark, Weight &cost, bool &found) { 5 const int n = h.size(); 6 if (mark[v]) { 7 vector<int> temp = no; 8 found = true; 9 do { 10 cost += mcost[v]; 11 v = prev[v]; 12 if (v != s) { 13 while (comp[v].size() > 0) { 14 no[comp[v].back()] = s; 15 comp[s].push_back(comp[v].back()); 16 comp[v].pop_back(); 17 } 18 } 19 } while (v != s); 20 FOR(j,comp[s]) if (*j != r) FOR(e,h[*j]) 21 if (no[e->src] != s) e->weight -= mcost[ temp[*j] ]; 22 } 23 mark[v] = true; 24 FOR(i,next[v]) if (no[*i] != no[v] && prev[no[*i]] == v) 25 if (!mark[no[*i]] || *i == s) 26 visit(h, *i, s, r, no, comp, prev, next, mcost, mark, cost, found); 27} 28Weight minimumSpanningArborescence(const Graph &g, int r) { 29 const int n = g.size(); 30 Graph h(n); 31 REP(u,n) FOR(e,g[u]) h[e->dst].push_back(*e); 32 33 vector<int> no(n); 34 vector< vector<int> > comp(n); 35 REP(u, n) comp[u].push_back(no[u] = u); 36 37 for (Weight cost = 0; ;) { 38 vector<int> prev(n, -1); 39 vector<Weight> mcost(n, INF); 40 41 REP(j,n) if (j != r) FOR(e,g[j]) 42 if (no[e->src] != no[j]) 43 if (e->weight < mcost[ no[j] ]) 44 mcost[ no[j] ] = e->weight, prev[ no[j] ] = no[e->src]; 45 46 vector< vector<int> > next(n); 47 REP(u,n) if (prev[u] >= 0) 48 next[ prev[u] ].push_back(u); 49 50 bool stop = true; 51 vector<int> mark(n); 52 REP(u,n) if (u != r && !mark[u] && !comp[u].empty()) { 53 bool found = false; 54 visit(h, u, u, r, no, comp, prev, next, mcost, mark, cost, found); 55 if (found) stop = false; 56 } 57 if (stop) { 58 REP(u,n) if (prev[u] >= 0) cost += mcost[u]; 59 return cost; 60 } 61 } 62}

と書いてありました。

最小全域有向木を求めるプログラムを使うために自分で用意しなければならない変量はどれでしょうか?またどういった形式の変量を用意すれば良いのでしょうか?

よろしくお願いいたします。

気になる質問をクリップする

クリップした質問は、後からいつでもMYページで確認できます。

またクリップした質問に回答があった際、通知やメールを受け取ることができます。

バッドをするには、ログインかつ

こちらの条件を満たす必要があります。

guest

回答1

0

ざっと見てみました。
アルゴリズムの中身は全く分かりませんが、下記のことが分かりました。

まず、問題はこれですね?

重み付き有向グラフG(V,E) について、頂点rを根とする最小全域有向木の辺の重みの総和を求めて下さい。

であれば、下記がこの問題を解く関数ではないかと思います。

Weight minimumSpanningArborescence(const Graph &g, int r)

Graphが重み付き有向グラフG(V,E)、rが頂点r、「戻り値が最小全域有向木の辺の重みの総和」だろうと思います。 本当にそうなのかはこのサイトの著者に聞くしかないですが。

Graph型はここで定義されてます。
恐らく、Graph g;の時、g[i]が頂点iの情報で、g[i]は「頂点iを始点とする辺の情報をリストとして格納」しているのだと思います。
つまり、型Edgesが頂点の型ですね。EdgesはEdge(辺)の集まりであり、かつ、GraphはEdgesの集まりになってますから。

ということは、Graph gを適切に定義して頂点rを決めて、minimumSpanningArborescence()を呼び出せば、答えを計算してくれそうです。

下記イメージですね。ここの入力例1のケースで書いてます。

C++

1Graph g; 2 3// 頂点0 4Edges p0; 5p0.push_back(0, 1, 3); 6p0.push_back(0, 2, 2); 7g.push_back(p0); 8 9// 頂点1 10Edges p1; 11g.push_back(p1); 12 13// 頂点2 14Edges p2; 15p2.push_back(2, 0, 1); 16p2.push_back(2, 3, 1); 17g.push_back(p2); 18 19// 頂点3 20Edges p2; 21p3.push_back(3, 0, 1); 22p3.push_back(3, 1, 5); 23g.push_back(p3); 24 25std::cout << "result=" << minimumSpanningArborescence(g, 0);

かなり推測を含んでます。また、上記はコンパイルもしてませんので、それなりに間違いがあるかも知れません。

投稿2015/12/06 13:41

編集2015/12/06 13:44
Chironian

総合スコア23272

バッドをするには、ログインかつ

こちらの条件を満たす必要があります。

minagawa72

2015/12/07 06:33

ありがとうございました。
guest

あなたの回答

tips

太字

斜体

打ち消し線

見出し

引用テキストの挿入

コードの挿入

リンクの挿入

リストの挿入

番号リストの挿入

表の挿入

水平線の挿入

プレビュー

まだベストアンサーが選ばれていません

会員登録して回答してみよう

アカウントをお持ちの方は

15分調べてもわからないことは
teratailで質問しよう!

ただいまの回答率
85.50%

質問をまとめることで
思考を整理して素早く解決

テンプレート機能で
簡単に質問をまとめる

質問する

関連した質問