Data Structures using C PlusPlus: Chapter 7: Graphs

Graphs: Connected Components

Data Structures using C++ Program

Home | Department: ECE Department | Ist Year | Subject: Data Structures using CPlusPlus |

<< Previous

Next >>

Question: 1. Write an algorithm to test whether a given graph is connected or not.

Connected Components

Definition : In undirected graph, two vertices are connected if they have a path connecting them.

For example:

The connected components of graph G are

• In order to determine whether or not the graph is connected the DFS is called. The algorithm to find whether or not the graph is connected is as shown below.

Algorithm

connected_ Comp (G, n)

{

// Problem Description: This algorithm determines

// The connected components of graph

// Input: Graph G represented using adjacency

// matrix

// Output: Prints connected components of G

// visited [ ] is an array that keeps track

//of visited vertices from G.

for i = 1 to n do

visited [i] = 0; // initialize

for i = 1 to n do

if (visited [i] = 0)

Dfs (i);

}

• Thus connected components of graph are those components in which there is a path between every pair of vertices. Finding the connected components of graph is one of the applications of graph.

Review Question

1. Write an algorithm to test whether a given graph is connected or not.

Data Structures using C PlusPlus: Chapter 7: Graphs : Tag: Data Structure, C++ Programing : Data Structures using C++ Program - Graphs: Connected Components

Home | Department: ECE Department | Ist Year | Subject: Data Structures using CPlusPlus |

<< Previous

Next >>