ALGORITHM Order in which vertices are first encountered. Assume that the vertice

Question

ALGORITHM Order in which vertices are first encountered. Assume that the vertices are visited in numerical order when no other order is specified by the search. The number of connected components in the graph. . Tree edges. . Cross edges. For the graph in Figure 1, the program should generate the following vertex ordering (count value for vertices): The number of connected components is 1. The tree edges and cross edges are given by two adjacency matrices: Tree edges 0 0 0 000 1 0 0 00 1 0 0 0 0 Cross edges 0001 000 0

Explanation / Answer

/*

* To change this template, choose Tools | Templates

* and open the template in the editor.

*/

package javaapplication2;

import java.util.*;

/**

*

* @author CS_Nishtha

*/

public class Main {

private int V; // No. of vertices

int no_cc;

int size_cc[];

int adj[][];

static int k=0;

int dead[],mark[];

int tree_edge[][],back_edge[][];

// Constructor

Main(int v)

{

V = v;

adj = new int[v][v];

tree_edge = new int[v][v];

back_edge = new int[v][v];

for (int i=0; i<v; i++)

for(int j=0; j<v;j++)

{

adj[i][j]=0;

tree_edge[i][j]=0;

back_edge[i][j]=0;

}

dead=new int[v];

mark=new int[v+1];

size_cc=new int[v];

no_cc=0;

for (int i=0; i<v; i++)

size_cc[i]=1;

for (int i=0; i<v+1; i++)

mark[i]=-1;

}

//Function to add an edge into the graph

void addEdge(int v, int w)

{

adj[v][w]=adj[w][v]=1; // Add w to v's list.

}

// A function used by DFS

void DFSUtil(int v,boolean visited[])

{

// Mark the current node as visited and print it

int k=0,k1=0;

boolean flag=false;

for(k=0;k<V+1;k++)

mark[k]=-1;

k=0;

mark[k]=v;

while(mark[k]!=-1)

{

v=mark[k];

visited[v] = true;

System.out.print((v+1)+" ");

for(int n=0;n<V;n++)

{

if (adj[v][n]==1&&!visited[n])

{

tree_edge[v][n]=1;

size_cc[no_cc]++;

visited[n]=true;

mark[++k1]=n;

flag=true;

}

}

k++;

}

}

// The function to do DFS traversal. It uses recursive DFSUtil()

void DFS(int v)

{

// Mark all the vertices as not visited(set as

// false by default in java)

boolean visited[] = new boolean[V];

System.out.print(" Vertex Encountered:");

DFSUtil(v, visited);

for(int i=0;i<V;i++)

{

if(!visited[i])

{

k=0;

System.out.print(" Vertex Encountered:");

no_cc++;

DFSUtil(i, visited);

}

}

  

for(int j=0;j<=no_cc;j++)

System.out.print(" ConnComponenet:"+(j+1)+"Size"+size_cc[j]+" ");

}

void display()

{

int i,j;

System.out.print("Tree Edge: ");

for(i=0;i<V;i++)

{

for(j=0;j<V;j++)

System.out.print(tree_edge[i][j]+" ");

System.out.println();

}

System.out.print("Cross Edge: ");

for(i=0;i<V;i++)

{

for(j=0;j<V;j++)

back_edge[i][j]= adj[i][j]-tree_edge[i][j];

  

}

for(i=0;i<V;i++)

for(j=0;j<V;j++)

if(tree_edge[i][j]==1)

back_edge[j][i]=0;

for(i=0;i<V;i++)

{

for(j=0;j<V;j++)

System.out.print(back_edge[i][j]+" ");

System.out.println();

}

}

public static void main(String args[])

{

Main g = new Main(8);

g.addEdge(0, 1);

g.addEdge(0, 4);

g.addEdge(0, 5);

g.addEdge(1, 6);

g.addEdge(1, 5);

g.addEdge(4, 5);

g.addEdge(2, 6);

g.addEdge(2, 3);

g.addEdge(6, 7);

g.addEdge(7, 3);

System.out.println("Following is Depth First Traversal ");

g.DFS(0);

g.display();

}

}

Related Questions

Navigate

• Browse (All)
• Browse A
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.