package com.cn;
/**
*
* @author wangjian520@gmail.com
* @since 1.5
* @date Jul 28, 2008
* description
*/
public class Graph {
private final int max_size=20;
private Vertex verList[];
private int edge[][];
private int currNode;
Stack stack;
Queue queue;
public Graph(){
verList=new Vertex[max_size];
edge=new int[max_size][max_size];
for (int i = 0; i < max_size; i++) {
for (int j = 0; j < max_size; j++) {
edge[i][j]=0;
}
}
stack=new Stack(max_size);
queue=new Queue(max_size);
currNode=0;
}
public void addVertex(String lable){
verList[currNode]=new Vertex(lable,currNode);
currNode++;
}
public void addEdge(int start,int end){
edge[start][end]=1;
edge[end][start]=1;
}
public void disVertex(int v){
System.out.println(verList[v].getLable());
}
public int getUnvisited(int v){
for (int i = 0; i <= currNode; i++) {
if(edge[v][i]==1 && !verList[i].isWasVisited()){
return i;
}
}
return -1;
}
public void serarch(){
int s=0;
verList[s].setWasVisited(true);
disVertex(s);
stack.push(verList[s]);
while(!stack.isEmpty()){
int v=this.getUnvisited(stack.getElementPointer());
if(v !=-1){
verList[v].setWasVisited(true);
disVertex(v);
stack.push(verList[v]);
}else{
stack.pop();
}
}
for (int i = 0; i < currNode; i++) {
verList[i].setWasVisited(false);
}
}
public void search(int s){
verList[s].setWasVisited(true);
disVertex(s);
queue.add(verList[s]);
while(!queue.isEmpty()){
Vertex v=queue.remove();
int tepm=-1;
while((tepm=this.getUnvisited(v.getP())) != -1){
disVertex(tepm);
verList[tepm].setWasVisited(true);
queue.add(verList[tepm]);
}
}
}
}
评论0