[code]class StackX
{
private final int SIZE = 20;
private int[] st;
private int top;
public StackX()
{
st = new int[SIZE];
top = -1;
}
public void push(int j)
{ st[++top] = j; }
public int pop()
{ return st[top–]; }
public int peek()
{ return st[top]; }
public boolean isEmpty()
{ return (top == -1); }
} // Fim da classe StackX
class Vertex
{
public char label;
public boolean wasVisited;
public Vertex(char lab)
{
label = lab;
wasVisited = false;
}
} // Fim da classe Vertex
class Graph
{
private final int MAX_VERTS = 20;
private Vertex vertexList[];
private int adjMat[][];
private int nVerts;
private StackX theStack;
public Graph()
{
vertexList = new Vertex[MAX_VERTS];
adjMat = new int[MAX_VERTS][MAX_VERTS];
nVerts = 0;
for(int y=0; y<MAX_VERTS; y++)
for(int x=0; x<MAX_VERTS; x++)
adjMat[x][y] = 0;
theStack = new StackX();
}
public void addVertex(char lab)
{ vertexList[nVerts++] = new Vertex(lab);
}
public void addEdge(int start, int end)
{
adjMat[start][end] = 1;
adjMat[end][start] = 1;
}
public void displayVertex(int v)
{
System.out.print(vertexList[v].label);
}
public void dfs() // depth-first search
{
vertexList[0].wasVisited = true;
displayVertex(0);
theStack.push(0);
while( !theStack.isEmpty() )
{
int v = getAdjUnvisitedVertex( theStack.peek() );
if(v == -1)
theStack.pop();
else
{
vertexList[v].wasVisited = true;
displayVertex(v);
theStack.push(v);
}
}
for(int j=0; j<nVerts; j++)
vertexList[j].wasVisited = false;
}
public int getAdjUnvisitedVertex(int v)
{
for(int j=0; j<nVerts; j++)
if(adjMat[v][j]==1 && vertexList[j].wasVisited==false)
return j;
return -1;
}
}
class DFSApp
{
public static void main(String[] args)
{
Graph theGraph = new Graph();
theGraph.addVertex(‘A’);
theGraph.addVertex(‘B’);
theGraph.addVertex(‘C’);
theGraph.addVertex(‘D’);
theGraph.addVertex(‘E’);
theGraph.addVertex(‘F’);
theGraph.addVertex(‘G’);
theGraph.addEdge(0, 1);
theGraph.addEdge(1, 2);
theGraph.addEdge(0, 3);
theGraph.addEdge(3, 4);
theGraph.addEdge(0, 5);
theGraph.addEdge(5, 6); System.out.print("Visits: ");
theGraph.dfs();
System.out.println();
}
} // Fim da classe DFSApp