グラフが接続され、接続されたコンポーネント

Question

グラフ（接続マトリックス）が1つのコンポーネントだけに接続されているかどうかを調べたいと思います。グラフは、2つの頂点uとvがすべてuからvへのパスを含む場合に接続されます。 問題3タイプの接続（禁止（-1）、非接続（0）、起動（1））Aij！ = 0接続がありますDFSを使ってマトリックスに含まれているコンポーネントの数を調べますが、いくつかのケースでは動作しますが、他のコンポーネントでは動作しません。

例私の行列（交換-1 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, 

はrepresentation of graphを持っています。 Wisdom's Windによって作成されたトピックの同じ回答（DFS）を適用すると、2つのコンポーネントが回避され、39〜47行が追加されますが、39〜47行は行なわれません。

#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

あなたのコードでほんの少しの微調整と、それは実際にあなたのコードはright.Butあなたの上記のテストケースのように、ケースを考えてみた仕事

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]; 
     } 
    } 
} 

}

を行います、ノード2は3,4,5で訪問することができます。しかし、どこからでも2人を訪問することはできません。その接続プロパティは、あなたのロジックによって2になります。しかし、私が追加したチェックでは、 'a'ノードが 'b'ノードを訪れていて、 'b'が既に訪問されている場合、 'a'は 'b'と接続され、