Soru DFS kullanarak bir grafikte döngüleri tespit etme: 2 farklı yaklaşım ve fark nedir


Bir grafiğin bir bitişik liste olarak temsil edildiğini unutmayın.

Grafikte bir döngü bulmak için 2 yaklaşım duydum:

  1. Daha önce bir düğümü ziyaret edip etmediğinizi takip etmek için bir dizi boolean değerlerini saklayın. Gitmek için yeni düğümler tükenirseniz (zaten bir düğümünüze çarpmadan), daha sonra geriye dönüp farklı bir dalı deneyin.

  2. Cormen'in CLRS veya Skiena'sından biri: Doğrulanmamış grafiklerde derinlemesine ilk arama için iki tip kenar vardır, ağaç ve arka. Grafik, sadece bir arka kenar varsa ve varsa bir döngüye sahiptir.

Birisi bir grafiğin arka kenarlarının ne olduğunu ve yukarıdaki 2 yöntem arasındaki farkın ne olduğunu açıklayabilir.

Teşekkürler.

Güncelleştirme: Her iki durumda da döngüleri tespit etmek için kod. Grafik, tüm grafik düğümlerini basitlik için benzersiz sayılar olarak temsil eden basit bir sınıftır, her düğümün bitişik komşu düğümleri vardır (g.getAdjacentNodes (int)):

public class Graph {

  private int[][] nodes; // all nodes; e.g. int[][] nodes = {{1,2,3}, {3,2,1,5,6}...};

  public int[] getAdjacentNodes(int v) {
    return nodes[v];
  }

  // number of vertices in a graph
  public int vSize() {
    return nodes.length;
  }

}

Doğrulanmamış bir grafikte döngüleri tespit etmek için Java kodu:

    public class DFSCycle {

    private boolean marked[];
    private int s;
    private Graph g;
    private boolean hasCycle;

    // s - starting node
    public DFSCycle(Graph g, int s) {
        this.g = g;
        this.s = s;
        marked = new boolean[g.vSize()];
        findCycle(g,s,s);
    }

    public boolean hasCycle() {
        return hasCycle;
    }

    public void findCycle(Graph g, int v, int u) {

        marked[v] = true;

        for (int w : g.getAdjacentNodes(v)) {
            if(!marked[w]) {
                marked[w] = true;
                findCycle(g,w,v);
            } else if (v != u) {
                hasCycle = true;
                return;
            }
        }

    }  
}

Yönlendirilmiş bir grafikte döngüleri tespit etmek için Java kodu:

public class DFSDirectedCycle {

    private boolean marked[];
    private boolean onStack[];
    private int s;
    private Graph g;
    private boolean hasCycle;

    public DFSDirectedCycle(Graph g, int s) {
        this.s = s
        this.g = g;
        marked = new boolean[g.vSize()];
        onStack = new boolean[g.vSize()];
        findCycle(g,s);
    }

    public boolean hasCycle() {
        return hasCycle;
    }

    public void findCycle(Graph g, int v) {

        marked[v] = true;
        onStack[v] = true;

        for (int w : g.adjacentNodes(v)) {
            if(!marked[w]) {
                findCycle(g,w);
            } else if (onStack[w]) {
                hasCycle = true;
                return;
            }
        }

        onStack[v] = false;
    }
}

32
2017-10-01 09:55


Menşei


Sipariş edilen grafik kodunda bir hata olduğunu düşünüyorum. O'nun şeklindeki bir grafiğin geçişi durumunda, üstte ve tüm kenarlar aşağıya doğru yönlendirildiğinde, bu algoritma döngüsü algılayacaktır (önce O'nun sol tarafını alttan geçirecek ve tüm düğümleri işaretli olarak işaretleyecektir. O zaman ben işaretli olana kadar O'nun sağ kısmı, zaten işaretlenmiş olan). Orada eklenir [v] = false; findCycle'dan hemen sonra (g, w); Ne düşünüyorsun? - Matej Briškár
İçinde DFSCycle döngüsü kontrol etmek için koşul yanlıştır. Olmalı if(i != u) // If an adjacent is visited and not parent of current vertex, then there is a cycle. { hasCycle = true; return; } - i_am_zero
@IvanVoroshilin olmamalı } else if (v != u) { olmak } else if (w != u) {? - Etherealone


Cevaplar:


Sorumu cevaplayan:

Grafik, sadece bir arka kenar varsa ve varsa bir döngüye sahiptir. Bir arka kenar, DFS'nin bir döngü oluşturmasıyla üretilen ağaçtaki bir düğümden kendisine (özerk) veya atalarından biri olan bir kenardır.

Her iki yaklaşım da aslında aynı anlama gelir. Ancak, bu yöntem yalnızca yanlış grafikler.

Bu algoritmanın yönlendirilmiş grafikler için çalışmadığının nedeni, yönlendirilmiş bir grafikte aynı tepe noktasına 2 farklı yolun bir döngü oluşturmamasıdır. Örneğin: A -> B, B -> C, A -> C - Bir döngü yapmazken, tersi durumda: A - B, B - C, C - A yapar.

Doğrulanmamış grafiklerde bir döngü bulun 

Eğer bir derinlik-ilk arama (DFS) zaten ziyaret edilmiş bir vertex'e (bir arka kenara) işaret eden bir kenar bulursa, doğrulanmamış bir grafiğin bir döngüsü vardır.

Yönlendirilmiş grafiklerde bir döngü bulun 

Ziyaret edilen köşelere ek olarak, şu anda DFS geçişi için yineleme fonksiyonu yığınında bulunan köşe noktalarını takip etmeliyiz. Yineleme yığında zaten bulunan bir köşe noktasına ulaşırsak, ağaçta bir döngü vardır.

Güncelleştirme: Çalışma kodu yukarıdaki soru bölümünde yer almaktadır.


41
2017-10-01 11:34



Yönlendirilmemiş grafikte, sadece arka kenarın bulunduğu kenarın ebeveyni hariç bir arka kenar varsa, bir döngü vardır. Geriye doğru bir yön bulmada üst kenarı hariç tutmazsak, her doğrulanmamış grafik bir döngüdür. kenar. - crackerplace


Tamamlanması için, DFS kullanarak yönlendirilmiş bir grafikte döngüleri bulmak mümkündür wikipedia):

 L ← Empty list that will contain the sorted nodes
while there are unmarked nodes do
    select an unmarked node n
    visit(n) 
function visit(node n)
    if n has a temporary mark then stop (not a DAG)
    if n is not marked (i.e. has not been visited yet) then
        mark n temporarily
        for each node m with an edge from n to m do
            visit(m)
        mark n permanently
        unmark n temporarily
        add n to head of L

10
2017-12-18 17:45



Wiki kaynağı ekle! - alap
@alap - Wiki kaynak eklendi! - Igor Zelaya


Verilmiş olup olmadığını öğrenmek için DFS'ye dayalı olarak yazdığım kod İşte yanlış grafik bağlı / döngüsel veya değil. sonunda bazı örnek çıktı ile. Umarım yararlı olur :)

#include<stdio.h>
#include<stdlib.h>

/****Global Variables****/
int A[20][20],visited[20],count=0,n;
int seq[20],connected=1,acyclic=1;

/****DFS Function Declaration****/
void DFS();

/****DFSearch Function Declaration****/
void DFSearch(int cur);

/****Main Function****/
int main() 
   {    
    int i,j;

    printf("\nEnter no of Vertices: ");
    scanf("%d",&n);

    printf("\nEnter the Adjacency Matrix(1/0):\n");
    for(i=1;i<=n;i++)
            for(j=1;j<=n;j++)
        scanf("%d",&A[i][j]);

    printf("\nThe Depth First Search Traversal:\n");

    DFS();

    for(i=1;i<=n;i++)
        printf("%c,%d\t",'a'+seq[i]-1,i);

    if(connected && acyclic)    printf("\n\nIt is a Connected, Acyclic Graph!");
    if(!connected && acyclic)   printf("\n\nIt is a Not-Connected, Acyclic Graph!");
    if(connected && !acyclic)   printf("\n\nGraph is a Connected, Cyclic Graph!");
    if(!connected && !acyclic)  printf("\n\nIt is a Not-Connected, Cyclic Graph!");

    printf("\n\n");
    return 0;
   }

/****DFS Function Definition****/
void DFS()
    { 
    int i;
    for(i=1;i<=n;i++)
        if(!visited[i])
          {
        if(i>1) connected=0;
        DFSearch(i);    
              } 
    }

/****DFSearch Function Definition****/
void DFSearch(int cur) 
    {
    int i,j;
    visited[cur]=++count;

        seq[count]=cur; 
        for(i=1;i<count-1;i++)
                if(A[cur][seq[i]]) 
                   acyclic=0;

    for(i=1;i<=n;i++)
        if(A[cur][i] && !visited[i])
           DFSearch(i);

    }

Örnek çıktı:

majid@majid-K53SC:~/Desktop$ gcc BFS.c

majid@majid-K53SC:~/Desktop$ ./a.out
************************************

Enter no of Vertices: 10

Enter the Adjacency Matrix(1/0):

0 0 1 1 1 0 0 0 0 0 
0 0 0 0 1 0 0 0 0 0 
0 0 0 1 0 1 0 0 0 0 
0 0 0 0 0 0 0 0 0 0 
0 0 0 0 0 0 0 0 0 0 
0 1 0 0 1 0 0 0 0 0 
0 0 0 0 0 0 0 1 0 0 
0 0 0 0 0 0 0 0 1 0 
0 0 0 0 0 0 0 0 0 1 
0 0 0 0 0 0 1 0 0 0 

The Depdth First Search Traversal:
a,1 c,2 d,3 f,4 b,5 e,6 g,7 h,8 i,9 j,10    

It is a Not-Connected, Cyclic Graph!


majid@majid-K53SC:~/Desktop$ ./a.out
************************************

Enter no of Vertices: 4

Enter the Adjacency Matrix(1/0):
0 0 1 1
0 0 1 0
1 1 0 0
0 0 0 1

The Depth First Search Traversal:
a,1 c,2 b,3 d,4 

It is a Connected, Acyclic Graph!


majid@majid-K53SC:~/Desktop$ ./a.out
************************************

Enter no of Vertices: 5

Enter the Adjacency Matrix(1/0):
0 0 0 1 0
0 0 0 1 0
0 0 0 0 1
1 1 0 0 0 
0 0 1 0 0

The Depth First Search Traversal:
a,1 d,2 b,3 c,4 e,5 

It is a Not-Connected, Acyclic Graph!

*/

1
2018-05-17 00:42