/* Description: This program perform a
Depth-first-Traversal. Also
removes the edge from vertex D to F
Vertex Adjacent Vertices
A B, C, D
B A, C, D
C A, B, D
D A, B, C, F
E F, G, H
F D, E, G
G E, F, H
H E, G
*/
public class Lab6
{
public static void main(String[] args)
{
int A = 0; int B = 1; int C = 2; int D = 3;
int E = 4; int F = 5; int G = 6; int H = 7;
Graph graph = new Graph(8);
//Vertices
graph.setLabel(A, new String("A"));
graph.setLabel(B, new String("B"));
graph.setLabel(C, new String("C"));
graph.setLabel(D, new String("D"));
graph.setLabel(E, new String("E"));
graph.setLabel(F, new String("F"));
graph.setLabel(G, new String("G"));
graph.setLabel(H, new String("H"));
//Edges
graph.addEdge(A, B); graph.addEdge(A, C); graph.addEdge(A, D);
graph.addEdge(B, A); graph.addEdge(B, C); graph.addEdge(B, D);
graph.addEdge(C, A); graph.addEdge(C, B); graph.addEdge(C, D);
graph.addEdge(D, A); graph.addEdge(D, B); graph.addEdge(D, C);
graph.addEdge(E, F); graph.addEdge(E, G); graph.addEdge(E, H);
graph.addEdge(F, D); graph.addEdge(F, E); graph.addEdge(F, G);
graph.addEdge(G, E); graph.addEdge(G, F); graph.addEdge(G, G);
graph.addEdge(H, E); graph.addEdge(H, G); graph.addEdge(D, F);
boolean[] mk1 = new boolean[graph.size()];
System.out.println("All Vertices in the Graph");
Graph.depthFirstRecurse(graph, A, mk1);
System.out.println("\n");
graph.removeEdge(D, F);
boolean[] mk2 = new boolean[graph.size()];
System.out.println("Vertices without edges from Vertex D to F");
Graph.depthFirstRecurse(graph, A, mk2);
}
}
/*---------------------------------------*/
public class Graph implements Cloneable
{ private boolean[ ][ ] edges;
private Object[ ] labels;
public Graph(int n)
{ edges = new boolean[n][n];
labels = new Object[n]; }
public void addEdge(int source, int target)
{ edges[source][target] = true; }
public Object clone( )
{ Graph answer;
try
{ answer = (Graph) super.clone( ); }
catch (CloneNotSupportedException e)
{ throw new InternalError(e.toString( )); }
answer.edges = (boolean [ ][ ]) edges.clone( );
answer.labels = (Object [ ]) labels.clone( );
return answer;
}
public static void depthFirstPrint(Graph g, int start)
{ boolean[ ] marked = new boolean [g.size( )];
depthFirstRecurse(g, start, marked); }
public static void depthFirstRecurse(Graph g, int v, boolean[ ] marked)
{ int[ ] connections = g.neighbors(v);
int i;
int nextNeighbor;
marked[v] = true;
System.out.print(g.getLabel(v)+"\t");
for (i = 0; i < connections.length; i++)
{
nextNeighbor = connections[i];
if (!marked[nextNeighbor])
depthFirstRecurse(g, nextNeighbor, marked);
}
}
public Object getLabel(int vertex)
{ return labels[vertex]; }
public boolean isEdge(int source, int target)
{ return edges[source][target]; }
public int[ ] neighbors(int vertex)
{ int i;
int count;
int[ ] answer;
count = 0;
for (i = 0; i < labels.length; i++)
{ if (edges[vertex][i])
count++; }
answer = new int[count];
count = 0;
for (i = 0; i < labels.length; i++)
{ if (edges[vertex][i])
answer[count++] = i; }
return answer;
}
public void removeEdge(int source, int target)
{ edges[source][target] = false; }
public void setLabel(int vertex, Object newLabel)
{ labels[vertex] = newLabel; }
public int size( )
{ return labels.length; }
}
/*
Z:\>javac main6.java
Z:\>java main6
All Vertices in the Graph
A
B
C
D
F
E
G
H
Vertices without edges from Vertex D to F
A
B
C
D
*/