CODEWITHSUNDEEP
cgraphdepth-first-search
Alexandra Cardoso
Alexandra Cardoso

Reputation: 71

Connected Components of a Graph in C

I'm creating a program where I give it a graph where input is:

(Ignore first input line please) The second line will always be input two integers V (1 ≤ V ≤ 1000) and E (1 ≤ E ≤ 5000), respectively corresponding to the number of vertices and edges of the graph. And the following are lines each indicating the format BPA there is an edge from A to B with the entire weight P (1 ≤ P ≤ 10000).

The goal is to calculate the number of connected components. But I'm having an error: array type 'int [vertices]' is not assignable visitados=dfs(1, vertices, visitados, matriz);

I think it is beacause I'm calling dfs with the argument "visitados" and I'm trying to use it to save the return of dfs too. But I'm not sure and I can't solve this by myself. Can you help me please? Thanks so much!

Here is my code:

int dfs(int v, int nv, int visited[], int matrix[nv][nv]){
    int i;
    visited[v]=1;
    for(i=1;i<=nv;i++){
            if(matrix[v][i] && !visited[i]){
                visited[i]=1;
                dfs(i, nv, visited, matrix);
            }
    }
    return *visited;
}

int main(){
    int flag;
    scanf("%d", &flag);


    //Number of vertex and edges
    int vertices, arestas;
    scanf("%d %d", &vertices, &arestas);

    //Initialization of matrix
    int i, j, matriz[vertices+1][vertices+1];
    for(i=1;i<=vertices;i++){
        for(j=1;j<=vertices;j++){
            matriz[i][j]=0;
        }
    }

    //Filling of matrix
    int v1, v2, p;
    for(i=0;i<arestas;i++){
        scanf("%d %d %d", &v1, &v2, &p);
        matriz[v1][v2]=p;
    }

    //Initialization of array visitados 
    int visitados[vertices];
    for(i=1;i<=vertices;i++){
        visitados[i]=0;
    }

    //Call of DFS while vertex are not all visited
    int componentes=0;
    for(i=1;i<=vertices;i++){
        if(visitados[i]==0){
            visitados=dfs(1, vertices, visitados, matriz);
            componentes = componentes+1; //Count of calls of DFS
        }
    }

    //Print of number of connected components
    printf("%d", componentes);


    return 0;
}

Upvotes: 0

Views: 2650

Answers (2)

PropaneAccessories
PropaneAccessories

Reputation: 88

The problem is that dfs is returning an int, and then you're trying to assign that int to an array. Try:

visitados[i] = dfs(1, vertices, visitados, matriz);

Upvotes: 0

R Sahu
R Sahu

Reputation: 206577

This following line is not correct:

        visitados=dfs(1, vertices, visitados, matriz);

The LHS of the assignment operator is an array of ints while the RHS evaluates to an int. Something like:

        visitados[i]=dfs(1, vertices, visitados, matriz);

would work.

Upvotes: 1

Related Questions