Bir grafiğin bir bitişik liste olarak temsil edildiğini unutmayın.
Grafikte bir döngü bulmak için 2 yaklaşım duydum:
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.
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;
}
}
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.
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
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!
*/