`
chengyue2007
  • 浏览: 1493405 次
  • 性别: Icon_minigender_1
  • 来自: 大连
社区版块
存档分类
最新评论

java中图的遍历

阅读更多

/*class Queue {
 private int[] values;
 private int begin = -1;
 private int end = -1;
 Queue(int size) {
  values = new int[size];
 }
 void push(int value) {values[++begin] = value;}
 int pop() { return values[++end]; }
 boolean isEmpty() { return begin == end; }
}*/

class Vertex {
 private Object value;
 private boolean isVisited;
 private int weight;
 Vertex(Object value) {
  this.value = value;
 }

 void visit() { isVisited = true; print(); }
 //void clean() { isVisited = false; }
 boolean isVisited() { return isVisited; }
 void print() { System.out.print(value+"→"); }
}

public  class Graph {
 private Vertex[] vertexs;
 private int[][] adjMat;
 private int pos = -1;
 int sum=0;
 int last=0;
 Graph(int size) {
  vertexs = new Vertex[size];
  adjMat = new int[size][size];
 }

 void add(Object value) {
  //assert pos < vertexs.length;
  vertexs[++pos] = new Vertex(value);
  adjMat[pos][pos]=10000;
 }

 void connect(int from, int to,int weight) {
  adjMat[from][to] = weight;
  adjMat[to][from] = weight;
 }

 /*void disConnect(int from, int to) {
  adjMat[from][to] = 0;
  adjMat[to][from] = 0;
 }*/

 int findNeighbor(int index) {
  int min=10000,i,j=0;
  for( i=0; i<=pos;i++ )
   if(!(vertexs[i].isVisited()))
    if(adjMat[index][i]<min){
     min=adjMat[index][i];
     j=i;
    }
     return j;   
      
  
 }

/* void bfs(int index) { //从指定下标的节点开始广度优先遍历
  if(vertexs[index] == null) return; //如果图中没有指定下标节点,则退出
  Queue q=new Queue(vertexs.length); //创建队列存放访问过的节点
  vertexs[index].visit(); //访问指定节点
  q.push(index); //将节点推入队列中
  while(!q.isEmpty()) { //队列为空则表示遍历结束
   index = q.pop(); //取出队头
   int i;
   while(((i=findNeighbor(index)) != -1)&&(!(vertexs[i].isVisited()))) { //寻找头节点的所有邻接节点
    vertexs[i].visit(); //标记访问过的邻接节点
    q.push(i); //放入队列中
   }
  }
 }*/
/* void routsum(Graph g,int index){
  
  int i, sum=0;
  for()
  while(((i=findNeighbor(index)) != -1)&&(!(vertexs[i].isVisited()))){
   sum+=g.adjMat[index][i];
  }
  System.out.println(sum);
 }*/
 void dfs(Graph g,int index){ //从指定下标的节点开始深度优先遍历
  vertexs[index].visit();
  int i=0 ;
  while(((i=findNeighbor(index)) != -1)&&(!(vertexs[i].isVisited()))){
    sum += g.adjMat[index][i];
   dfs(g,i); 
   if(findNeighbor(i)==index)last=i;
   i=findNeighbor(i);
   
  }
  
  
 }

 //void clean() { for(Vertex v: vertexs) if(v != null)v.clean(); }

 

 public static void main(String[] args) {
  Graph g = new Graph(20);
  g.add('a');
  //System.out.println(g.adjMat[0][0]);
  g.add('b');
  g.add('c');
  g.add('d');
  g.add('e');
  g.connect(0, 1, 4);
  g.connect(0, 2, 6);
  g.connect(0, 3, 7);
  g.connect(0, 4, 16);
  g.connect(1, 2, 3);
  g.connect(1, 3, 4);
  g.connect(1, 4, 19);
  g.connect(2, 3, 11);
  g.connect(2, 4, 10);
  g.connect(3, 4, 3);
  g.dfs(g,0);
  g.vertexs[0].visit();
  System.out.print("所走路程共:"+(g.sum+g.adjMat[0][g.last])+"单位");
  
  //System.out.print(g.adjMat[0][g.last]);
 }
}

分享到:
评论

相关推荐

Global site tag (gtag.js) - Google Analytics