График подключен и подключен компонент

Question

Я хочу узнать, связан ли граф (матрица соединения) только с одним компонентом. График связан, когда для всех двух вершин u и v содержит путь от u до v. Моя проблема 3 типа соединения (торможение (-1), non-connection (0), активация (1)) Я полагаю, если Aij! = 0 имеет соединение Я использую DFS для поиска количества компонентов в матрице, но он работает для некоторых случаев, а не для других.

Ex моя матрица (вместо -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. При применении того же ответа (DFS) темы, созданной Wisdom's Wind, получается 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

Просто небольшая подстройка в вашем коде, и он будет делать работу

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

}

на самом деле ваш код был right.But рассмотреть случай, как в вашем выше теста, узел 2 можно посетить на 3,4,5. Но 2 нельзя посещать ни с кем. Таким образом, его связанное свойство будет 2 по вашей логике. Но, добавленная проверка, гарантировала, что если узел «a» посещает узел «b», а «b» уже посещен, значит «a» подключается к «b» и имеет такое же значение соединения.