k個の接続された頂点とワイト・サム・ベローズを見つける

Question

私は、頂点に重み付けされた無向グラフG（E、V）を持っています。私は、それらの重みの合計が数値tより小さくなるように、k個の接続された頂点を見つける必要があります。 私が持っている大きな問題はサークルを扱うことです。 は、これまでのところ、私は（動作しない）、次のアイデアを持っていた編集-----

-----

algorithnたとえその完全ではありません...任意のアイデアを得るために幸せになります...そのツリー（T下の合計がk個の頂点の木）の私は、ルート（R）上で見たときに、各componnentは、拡散ツリーを持っていることを知っている

1. を、私は次のオプションがあります。Rはあり息子であり、彼はk-1個の頂点を持つそのような樹木の根である|| Rには2人の息子がいます.1つはk-2の木の根であり、もう1人の息子の根は1つの頂点（息子そのもの）です... Rを見つけるには動的なプログラムを使いたいと思いました。最初にvの各vについて、vがその根である1つの頂点を持つ最小の木を見つける。そして2。そして上のアイデアによって、病気の残りの部分が見つかります。 問題は、例：Rが唯一の息子uを持ち、uがその根であるk-1個の頂点の最小の木がRを含む場合、Rがk個の頂点の木の根ではないことがわかる。 uがRとW（T（k-1））+ W（R）を含むk-1ツリーの根であるというオプションです。< ...

2. 私はこの問題は、Vでeac vのkレイヤーを持つBFSツリーを構築することで問題になりますが、BFSツリーのすべてのエッジが含まれているため、オプションが失われると思います。

3.この問題を最大フロー問題に変換するにはどうすればよいのですか？

Answer 1

重みの合計がソース（「s」で示される）の距離が「t」以上の場合、幅優先検索およびノー​​ド処理を停止することができます。これらのライン（ジャワスタイルコード）に沿って

何か：

private void bfs(Graph G, int s) { 
    Queue<Integer> q = new Queue<>(); 
    for (int v = 0; v < G.V(); v++) 
     distTo[v] = INFINITY; 
    distTo[s] = 0; 
    marked[s] = true; 
    q.enqueue(s); 

    while (!q.isEmpty()) { 
     int v = q.dequeue(); 

     for (int w : G.adj(v)) { 
      if (!marked[w] && distTo[v] + weights[v] < t) { // preventing going beyond accumulated weight 't' 
       distTo[w] = distTo[v] + weights[v]; 
       marked[w] = true; 
       q.enqueue(w); 
       edgeTo[w] = v; 
      } 
     } 
    } 
} 

Iが上記で使用したフィールドはほとんど配列であり、それらのインデックスは頂点vであるべきである（グラフ内のすべてのノードが整数数字であると仮定0〜n-1）：

private boolean[] marked; // marked[v] = is node v already visited ? 
private int[] edgeTo;  // edgeTo[v] = previous edge on shortest s-v path 
private int[] distTo;  // distTo[v] = number of edges shortest weights s-v path 
private int[] weights;  // weights[v] = weight of v 

bfsルーチンを処理した後、マークされたノードのすべての距離はt未満になります。

ノードをマークしてサークルを処理して、ノードを再訪問しないようにすることができます。