Grafik angeschlossen und angeschlossene Komponente

Question

Ich möchte herausfinden, ob ein Graph (Verbindungsmatrix) mit nur einer Komponente verbunden ist. Der Graph ist verbunden, wenn für alle zwei Ecken u und v einen Pfad von u zu v enthält. Mein Problem 3 Arten Verbindung (Hemmung (-1), Nicht-Verbindung (0), Aktivierung (1)) Ich nehme an, wenn Aij! = 0 hat Verbindung Ich benutze DFS, um zu suchen, wie viele Komponenten in der Matrix sind, aber er arbeitet in einigen Fällen und nicht zu anderen.

Ex meine Matrix (ersetzt -1 bis 1):

1, 0, 0, 1, 0, 
1, 0, 1, 1, 1, 
0, 0, 1, 1, 1, 
1, 0, 0, 0, 1, 
1, 0, 1, 1, 1, 

hier eine representation of graph. Wenn dieselbe Antwort (DFS) des Themas, das von Wisdom's Wind erstellt wurde, in 2 Komponenten zur Umgehung führt, fügen Sie Zeilen 39-47 hinzu, gibt es eine Möglichkeit, ohne die Zeilen 39-47 auszukommen?

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

#define _MIN -1 
#define _MAX 1 
#define TAM 5 
#define MAX TAM*TAM 
#define QNT_MATRIX 1 
#define SIZE_MATRIX MAX*QNT_MATRIX 

void DFS(int *matrix, int *marks, int vertex, int componentes){ 
    int i; 

    marks[vertex] = componentes; 
    for(i=0; i<TAM; i++){ 
     if(matrix[vertex*TAM+i] != 0){ 
      if(marks[i] == 0){ 
       DFS(matrix, marks, i, componentes); 
      } 
     } 
    } 
} 

int testDFS(int *matrix){ 
    int marks[TAM]; 
    int i, k, componentes=0, componentes_total=1; 

    memset(marks, 0, TAM*sizeof(int)); 

    for(i=0; i<TAM; i++){ 
     if(marks[i] == 0){ 
      ++componentes; 
      DFS(matrix, marks, i, componentes); 
     } 
    } 

    for(i=0; i<TAM-1; i++){//line 39 
     for(k=i+1; k<TAM; k++){ 
      if(marks[i] != marks[k]){ 
       if(matrix[i*TAM+k] == 0 && matrix[k*TAM+i] == 0){ 
        componentes_total++;//no have way connection     
       } 
      } 
     } 
    }//line47 
    printf("testDFS Componentes: %d\n", componentes); 
    printf("Componentes_total: %d\n", componentes_total); 

} 

int main(){ 
    int matrix[SIZE_MATRIX]; 
    int i; 


    srand(time(NULL)); 

    for(i=0; i<SIZE_MATRIX; i++){ 
     scanf("%d,", &matrix[i]); 
    } 
    //Print matrix 
    for(i=0; i<SIZE_MATRIX; i++){ 
     printf("%d ", matrix[i]); 
     if((i+1)%TAM==0){ 
      printf("\n"); 
     } 
     if((i+1)%(MAX)==0){ 
      printf("\n"); 
     } 
    } 

    testDFS(matrix); 
    return 0; 
} 

Answer 1

Nur ein kleines zwicken in Ihrem Code und es wird tun, war die Arbeit

void DFS(int *matrix, int *marks, int vertex, int& componentes){ 
int i; 

marks[vertex] = componentes; 
for(i=0; i<TAM; i++){ 
    if(matrix[vertex*TAM+i] != 0){ 
     if(marks[i] == 0){ 
      DFS(matrix, marks, i, componentes); 
     } 
     else if(marks[i] != marks[vertex]){ 
      marks[vertex] = marks[i]; 
      componentes = marks[i]; 
     } 
    } 
} 

}

tatsächlich Code der Fall ist, wie in Ihrem obigen Testfall right.But zu betrachten, Knoten 2 kann durch 3,4,5 besucht werden. Aber 2 kann von keinem wo aus besucht werden. Die verbundene Eigenschaft ist also 2 nach Ihrer Logik. Aber die Überprüfung, die ich hinzugefügt habe, stellte sicher, dass, wenn 'a' Knoten 'b' Knoten besucht und 'b' bereits besucht wurde, so 'a' mit 'b' verbunden wird und denselben verbundenen Wert hat.