Program To Check Whether A Graph (Undirected) Is Connected Or Not

---

Connected Component

---

For a undirected graph it is easy to check that if the graph is connected or not. To check that a graph is connected or not. We can simply do a depth-first traversal or a breadth first-first traversal on the graph and if the traversal successfully traversal all the nodes in the graph then we can conclude that the graph is connected else the graph has components. This way we can also count the number of components.

For Example:

G	G'

Here G is connected and has one component. But G' is not connected and has two component. 

---

C Implementation

---

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88

#include <stdio.h> #include <stdlib.h> #define TRUE 1 #define FALSE 0 //Function to create a graph... void createGraph(int G[][50], int v) { int i, j; printf("\nEnter The Adjacency Matrix: \n"); for(i = 0; i < v; i++) { for(j = 0; j < v; j++) { scanf("%d",&G[i][j]); } } } //Function to print the graph... void printGraph(int G[][50], int v) { int i, j; for(i = 0; i < v; i++) { putchar('['); for (j = 0; j < v; j++) printf("%3d ",G[i][j]); putchar(']'); putchar('\n'); } } //Function for Depth first search... void DFS(int G[][50], int i, int visited[], int v) { int u; visited[i] = TRUE; for(u = 0; u < v; u++) if(G[i][u] == TRUE && visited[u] != TRUE) DFS(G, u, visited, v); } //Call DFS on each single vertex and count the " #(calls) = #(components) "... int visitAll(int G[][50], int v) { int i, visited[50], count = 0; for(i = 0; i < v; i++) visited[i] = FALSE; for(i = 0; i < v; i++) { if(visited[i] != TRUE) { ++count; DFS(G, i, visited, v); } } return count; } //Checks if the graph is connected or not... int isConnected(int G[][50], int v) { return ((visitAll(G, v) > 1)? FALSE : TRUE); } int main() { int G[50][50], v, e; printf("Enter The Number Of Vertices: "); scanf("%d",&v); createGraph(G, v); printf("\nThe Adjacency Matrix:\n\n"); printGraph(G, v); printf("\n\nThe Given Graph Is%sConnected.",isConnected(G, v)?" ":" Not "); printf("\n\nThere Are %d Components.",visitAll(G, v)); return 0; }

---

Output

---

First Run(G):

Enter The Number Of Vertices: 4

Enter The Adjacency Matrix:

0 1 1 1

1 0 1 1

1 1 0 1

1 1 1 0

The Adjacency Matrix:

[  0   1   1   1 ]

[  1   0   1   1 ]

[  1   1   0   1 ]

[  1   1   1   0 ]

The Given Graph Is Connected.

There Are 1 Components.

Second Run(G'):

Enter The Number Of Vertices: 4

Enter The Adjacency Matrix:
0 0 0 0
0 0 0 1
0 0 0 1
0 1 1 0

The Adjacency Matrix:

[  0   0   0   0 ]
[  0   0   0   1 ]
[  0   0   0   1 ]
[  0   1   1   0 ]


The Given Graph Is Not Connected.

There Are 2 Components.

Kruskal's MST Algorithm

Kruskal's algorithm is a greedy algorithm in graph theory that finds a minimum spanning tree for a connected weighted graph.
It works by growing forest. Kruskal's algorithm finds a safe edge to add to the growing forest by finding an edge with least weight that connects two tree in the forest.

Algorithm

# here + means union of twp sets
KRUSKAL(G):
  A = NULL
  foreach v in G.V:
  MAKE-SET(v)
  foreach (u, v) ordered by weight(u, v), increasing:
    if FIND-SET(u) != FIND-SET(v):
      A = A + {(u, v)}
      UNION(u, v)
  return A

C Implementation Using Disjoint Set Data Structure

/* Kruskals MST Algorithm Implemented Using Disjoint Set Data Structure (Union & Find).....
 * Where Graph Is Represented In Adjacency Matrix Structure "AdjMa".....
 * Each Cell Has Two Members weight and visited.....
 * For Sorting The Edges WRT Its Weight A Edge: Structure Is Considered.....
 * Where 'u' & 'v' are each end of a vertex with corresponding 'weight'......
 */

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

#define TRUE 1
#define FALSE 0
#define N 4
#define INF 9999

typedef struct
{
    int weight;
    int visited;
}AdjMatrix;

typedef struct
{
    int weight;
    int u;
    int v;
}Edge;

void takeInput(AdjMatrix graph[][N])
{
    int i,j;
    printf("Enter The Matrix:\n");

for(i = 0; i < N; i++)
    {
        for (j = 0; j < N; j++)
        {
            scanf("%d",&graph[i][j].weight);
            if(graph[i][j].weight == 0) graph[i][j].weight = INF;
            graph[i][j].visited = FALSE;
        }
    }
}

void printGraph(AdjMatrix graph[][N])
{
    int i,j;
    for(i = 0; i < N; i++)
    {
        putchar('[');
        for (j = 0; j < N; j++)
        {   if(graph[i][j].weight == INF)
                printf("%3d ",0);
            else
                printf("%3d ",graph[i][j].weight);
        }
        putchar(']');
        putchar('\n');
    }
}

int find(int set[], int i)
{

    if (set[i] == -1)
        return i;
    else
        return find(set, set[i]);
}

//Function to union two sets...
void Union(int set[], int u, int v)
{
    int uset = find(set, u);
    int vset = find(set, v);
    set[uset] = vset;
}

//A comparison function for built-in qsort()...
int myComp(const void* a, const void* b)
{
    Edge *a1 = (Edge *)a;
    Edge *b1 = (Edge *)b;

    if (a1->weight > b1->weight)
        return 1;
    else
        return -1;
}

//Function for finding MST using Kruskal's Algorithm....
void kruskalMST(AdjMatrix graph[][N])
{
    int i, j, k=0, x, y, set[20], cost = 0, e=0;
    AdjMatrix tree[N][N];
    Edge edge[20];

    //Picking The Edges...
    for(i = 0; i < N; i++)
    {
        for (j = 0; j < N; j++)
        {
            tree[i][j].weight = 0;
            if(graph[i][j].visited != TRUE)
            {
                edge[k].weight = graph[i][j].weight;
                edge[k].u = i;
                edge[k++].v = j;
                graph[j][i].visited = TRUE;

            }
        }
    }

    //Sorting the edges using quicksort()....
    qsort(edge, k, sizeof(Edge), myComp);

    //Setting all elements of parent = -1
    //each element of parent is a disjoint set..
    memset(set, -1, N * sizeof(set[0]));

    i = 0;
    //Loops untill all vertices are considered that is e = #(vertices) - 1
    while (e < N - 1)
    {
        x = find(set, edge[i].u);
        y = find(set, edge[i].v);

        if (x != y)
        {
            cost = cost + edge[i].weight;
            tree[x][y].weight = edge[i].weight;
            tree[y][x].weight = edge[i].weight;
            Union(set, x, y);
            e++;
        }
        i++;
    }

    puts("\nAdjMatrix For MST:\n");
    printGraph(tree);
    printf("\n\nMST Cost = %d",cost);
}


int main()
{
    AdjMatrix graph[N][N];
    system("cls");
    takeInput(graph);
    printf("\nGiven Graph In AdjMatrix Representation:\n");
    printGraph(graph);
    kruskalMST(graph);
    return 0;
}

Output

Enter The Matrix:
0 7 5 2
7 0 4 3
5 4 0 1
2 3 1 0

Given Graph In AdjMatrix Representation:
[  0   7   5   2 ]
[  7   0   4   3 ]
[  5   4   0   1 ]
[  2   3   1   0 ]

AdjMatrix For MST:
[  0   0   0   2 ]
[  0   0   0   3 ]
[  0   0   0   1 ]
[  2   3   1   0 ]

MST Cost = 6
--------------------------------
Process exited after 50.48 seconds with return value 0
Press any key to continue . . .

Discussion

• Time Complexity: Time complexity of Kruskals algorithm depends on how we implement each operation like cycle detection and union and sorting etc
• It can be shown to run in O(ElogE) time or equivalently O(ElogV)
• It can be shown to run in O(ElogE) time or equivalently O(ElogV)
• WE can use Union-Find for cycle detection to keep track of which vertices are in which component, Which has at most e iterations. Union Find by rank or path compression take O(log(v)) time.
  • Total = O(ElogE + ElogV) = O(Elog E) or O(ElogV)