C program that uses depth-first search to count the number of distinct graphs represented by an adjacency matrix

Question

The code below uses depth-first search over all elements of an adjacency matrix to count how many graphs are represented in the adjacency matrix.

For some reason this code works only for some test cases but not for others, and I'd like to fix this.

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

//depth-first search
void dfs(int start, int n, int * visited, int ** family){
    int current;
    visited[start] = 1;
    for(current=0;current<n;++current)
        if(visited[current] == 0 && family[start][current] == 1) dfs(current, n, visited, family);
}

//set all visited[i] array integers to zero
void zero(int n, int * visited){
    int i;
    for(i=0;i<n;++i){
        visited[i] = 0;
    }
}

int main(){
    int ** family;
    int * visited;
    int ** all_visited;
    int n, k;
    int i, j, x, y;
    int counter = 0;
    int familycount = 0;

    // n == number of elements
    // k == number of lines to be read
    scanf("%i %i", &n, &k);

    //memory allocation
    family = (int**) malloc(sizeof(int*) * n);
    for(i=0;i<n;++i){
        family[i] = (int*) malloc(sizeof(int) * n);
    }
    all_visited = (int**) malloc(sizeof(int*) * n);
    for(i=0;i<n;++i){
        all_visited[i] = (int*) malloc(sizeof(int) * n);
    }

    visited = (int*) malloc(sizeof(int) * n);
    zero(n, visited);

    //receive input pairs and build adjacency matrix for the graph
    for(i=0;i<k;++i){
        scanf("%i %i", &x, &y);
        --x;
        --y;
        family[x][y] = 1;
    }

    //Perform depth-first search for each element in adjacency matrix.
    //If dfs() returns a visited[] array that has never been seen before,
    // add +1 to familycount.
    for(i=0;i<n;++i){
            dfs(i,n,visited,family);
            for(j=0;j<n;++j){
                all_visited[i][j] = visited[j];
            }
            for(x=0;x<i;++x){
                for(y=0;y<n;++y){
                    if(all_visited[x][y] == 1 && visited[y] == 1) break;
                }
                if(y == n) ++counter;
            }
            if(counter == i ) ++familycount;
            zero(n, visited);
            counter = 0;
        }
    printf("%i\n",familycount);
    return 0;
}

For instance, if we take the following test case:

9 8
1 2
2 3
3 6
4 3
6 5
7 8
1 4
6 2

First line ( "9 8" ) means we have nine possible elements ( integers ranging from 1 to 9 ) and that eight lines of input will follow below.

Possible means that I may or may not input 9 vertexes but never more than 9. If I don't input a vertex, it's ignored.

All following lines mean "X is related to Y", "X belongs to the same family as Y", or more formally, "X and Y belong to the same graph".

As you can see below, this test case has two families or two graphs, so program output should be "2".

Answer 1

This code is a lot more expensive than the problem you're trying to solve.

This problem is knows as graph connectivity in graph theory and you can solve it via a simple DFS for each node; we'll then use the visited array as a storage of the current DFS exploration.

For any vertex v:

• visited[v] = 0 <--> v has not been explorated yet

• visited[v] < 0 <--> v has an ongoing exploration but it isn't finished yet

• visited[v] > 0 <--> v has finished its exploration

Starting from v, we'll mark every reachable vertex from it with the same ongoing value for counter, and once the DFS returns, we'll simply swap sign of the visited[v] value, meaning its exploration is now over.

To get the number of unconnected graphs, you only need to count how many different values are in the visited array.

Here's the code:

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

void dfs(int start, int n, int *visited, int **family, int counter) {
    if (visited[start] > 0)
        return;
    else if (visited[start] == 0)
        visited[start] = -counter;

    for (int i = 0; i < n; i++) {
        if (family[start][i] == 1 && visited[i]==0) {
            dfs(i, n, visited, family, counter);
        }
    }
    visited[start] = -visited[start];

    return;
}

//set all visited[i] array integers to zero
void zero(int n, int * visited) {
    int i;
    for (i = 0; i<n; ++i) {
        visited[i] = 0;
    }
}

int main() {
    int ** family;
    int * visited;
    int n, k;
    int i, x, y;
    int counter = 1;
    int familycount = 0;
    int last = -1;

    // n == number of elements
    // k == number of lines to be read
    printf("Insert vertex# and edge#\n");
    scanf("%i %i", &n, &k);

    //memory allocation
    family = (int**)malloc(sizeof(int*) * n);
    for (i = 0; i<n; ++i) {
        family[i] = (int*)malloc(sizeof(int) * n);
    }

    visited = (int*)malloc(sizeof(int) * n);
    zero(n, visited);

    //receive input pairs and build adjacency matrix for the graph
    printf("Now insert all the edges, once at time\nFor edge (a,b), insert a b and press Enter\n");
    for (i = 0; i<k; ++i) {
        scanf("%i %i", &x, &y);
        --x;
        --y;
        family[x][y] = 1;
    }

    zero(n, visited);

    //Perform depth-first search for each element in adjacency matrix.
    //If dfs() returns a visited[] array that has never been seen before,
    // add +1 to familycount.
    for (i = 0; i<n; ++i) {
        dfs(i,n,visited,family,counter);
        counter++;
    }

    for (i = 0; i < n; i++) {
        if (visited[i] != last) {
            familycount++;
            last = visited[i];
        }
    }

    printf("Graph #: %i\n", familycount);
    return 0;
}

Instead of giving 9 8 as first input, you'll need to enter 8 8, meaning 8 vertexes and 8 edges, respectively.

Answer 2

What I don't see in your code, nor in the code of a proposed solutuon, is the counting of the unconnected components. I won't give the algoithm in code, just verbally.

• Take a random node to start with and apply dfs to mark its nodes. You now have 1 component.

• While there are still unmarked nodes, take the node and apply dfs. Add 1 to the number of components.

• If there are no unmarked nodes anymore, you have the number of unconnected components of the graph.