2つの頂点間のグラフ接続をチェックする方法

Question

私は遺伝的アルゴリズムを実装して、グラフを切断するエッジのセットを見つけようとしています。より具体的には、私は頂点とエッジからなる有向非循環グラフを使用しています。各エッジにはコストまたは重量があります。遺伝的アルゴリズムは、多くのセットCを生成する（すなわち、2つの頂点の間のいくつかのエッジを選択する）。今私の問題は、この一連のエッジがカットセットを表すかどうか、またはグラフを切断するかどうかをチェックすることです。次に、遺伝的アルゴリズムは、カットセットに含まれるエッジコストの可能な最小合計を探している。

私は、接続アルゴリズムをテストするために、「グラフアルゴリズムと最適化のJavaライブラリ」という本から取られたConnected Graph Testingというメソッドを使用しました。これは、頂点の隣人だけをスキャンするので、私のためには機能しません。我々は次のエッジ削除する場合

number of vertices = 4 
number of edges = 5 
1->2 
1->3 
1->4 
2->4 
3->4 

：そして

1->2 
1->3 
2->4 

を、方法がまだある間、このグラフが切断されていることを返し、次の非循環有向グラフを考える

public static boolean isConnected(Individual ind) 
{ 
    int n= Settings.numOfNodes; 
    int m= Settings.numOfEdges-ind.cutSet.size(); 
    int nodei[]= new int[m+1]; 
    int nodej[]= new int[m+1]; 

    int tempi[]= new int[m]; 
    int tempj[]= new int[m]; 

    int[] temp= (int[])Settings.nodei.clone(); 

    for(int edg:ind.cutSet) 
     temp[edg]= -1; 

     int count=0; 
     for(int i=0; i<Settings.numOfEdges; i++) 
    { 
     if(temp[i]!=-1) 
     { 
     tempi[count]=Settings.nodei[i]; 
     tempj[count]=Settings.nodej[i];    
     count++; 
     } 
    } 
    nodei[0]=0; 
    nodej[0]=0; 
    for(int i=0; i<tempi.length;i++) 
     { 
      nodei[i+1]=tempi[i]; 
      nodej[i+1]=tempj[i]; 
     } 



    int i,j,k,r,connect; 
    int neighbor[] = new int[m + m + 1]; 
    int degree[] = new int[n + 1]; 
    int index[] = new int[n + 2]; 
    int aux1[] = new int[n + 1]; 
    int aux2[] = new int[n + 1]; 
    for (i=1; i<=n; i++) 
    degree[i] = 0; 
    for (j=1; j<=m; j++) { 
     degree[nodei[j]]++; 
     degree[nodej[j]]++; 
    } 
    index[1] = 1; 
    for (i=1; i<=n; i++) { 
     index[i+1] = index[i] + degree[i]; 
     degree[i] = 0; 
    } 
    for (j=1; j<=m; j++) { 
     neighbor[index[nodei[j]] + degree[nodei[j]]] = nodej[j]; 
     degree[nodei[j]]++; 
     neighbor[index[nodej[j]] + degree[nodej[j]]] = nodei[j]; 
     degree[nodej[j]]++; 
    } 
    for (i=2; i<=n; i++) 
     aux1[i] = 1; 
     aux1[1] = 0; 
     connect = 1; 
     aux2[1] = 1; 
     k = 1; 
     while (true) { 
       i = aux2[k]; 
       k--; 
       for (j=index[i]; j<=index[i+1]-1; j++) { 
        r = neighbor[j]; 
        if (aux1[r] != 0) { 
         connect++; 
        if (connect == n) { 
         connect /= n; 
        if (connect == 1) return true; 
         return false; 
        } 
        aux1[r] = 0; 
        k++; 
       aux2[k] = r; 
     } 
    } 
     if (k == 0) { 

    connect /= n; 
    if (connect == 1) return true; 
    return false; 
    } 
    } 
    } 

間のパス：

1->4 

私はいくつかのエッジを削除するかどうかを確認するアルゴリズムや方法を探していますが、グラフはまだ開始点と目標点の間に接続されています。言い換えると、グラフにはまだこれらの2つの頂点の間に他のいくつかのパスが存在しています。

グラフが接続されていない取り除か有効なセットの例：

1->2 
1->3 
1->4 

または

2->4 
1->4 
3->4 

してください、私はこの問題を解決するための任意の考えやアイデアを開いています。

おかげ接続の確認

Answer 1

：

あなたのグラフは、このようにあなたは、プロセスを事前とPaths = { (u,v) | there is a path from u to v }を見つけることができ、環状に向けられています。

各辺を削除/追加した後に、(u,v)を行う必要がある場合は、それに応じてPathsをリセットしてください。 v'の場合、(u,v')はPathsにあり、u'が存在し、(u,u')が依然としてグラフの端であり、Pathsにある場合に限り、表示されます。
の親のそれぞれに対して、再帰的にPathsの修正を再帰的に呼び出すことを忘れないでください。
最悪の場合、このソリューションはBFSより優れていませんが、各変更後にグラフ全体を探索する必要がないため、平均的な場合は改善する必要があります。

編集：例
たとえば、グラフ、Path={(1,2),(1,3),(1,4),(2,4),(3,4)}に - 2〜3を除くすべての「前進」の頂点へのすべての頂点へのパスがあります。
今度は、エッジ(1,4)を取り除くと、Path={(1,2),(1,3),(1,4),(2,4),(3,4)}が得られます。は、そこにはエッジ（1,2）があり、（2,4）はPathにあるので、まだそこにあることに注意してください。
(2,4)を削除すると、結果はPath={(1,2),(1,3),(1,4),(3,4)}になります。再び、がまだ端であり、(3,4)がPathにあるので、(1,4)は依然として存在します。
(3,4)を削除します。 3から4にパスが残っていないので、(3,4)を削除します。さて、3の両親を再帰的に変更してください。 1は3の親であるため、彼を呼び出すと、(u,4)がまだパスに入っているエッジ(1,u)が見つからないので、Pathから削除すると、Path={(1,2),(1,3)}になります。

削除するエッジのセットを見つける：

を私はすべてのエッジの除去からスタートをいただきたい、と代わりにそれらを除去する、エッジを追加します。グラフを接続しないエッジのみを追加できます。この方法では、エッジを最小化するのではなく、を追加するエッジの値を最大化しようとします。
解決策が実現可能であることを確認してください。、グラフは実際には接続されていません。