Simple GUI Notepad Using Ruby

GUI Notepad Using Ruby Code require 'tk' class Notepad def saveFile file = File.open("note", "w") ...

Tuesday, February 17, 2015

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.

at
Labels: ,