《数据结构与算法》学习笔记29 最小生成树

<pre name="code" class="java">public class vertex {
  public boolean visit;
  private char label;

  public vertex(char a){
  label=a;
  visit=false;
  }

  public char getLabel(){
  return label;
  }
}

//图中的节点

</pre><pre code_snippet_id="1894337" snippet_file_name="blog_20160922_3_5998616" name="code" class="java"><pre name="code" class="java">public class stack {
  private final int size=20;
  private int top;
  private int[] st;

  public stack(){
  st=new int[size];
  top=-1;
  }

  public void push(int data){
  st[++top]=data;
  }

  public int pop(){
  return st[top--];
  }

  public int peek(){
  return st[top];
  }

  public boolean isEmpty(){
  return top==-1;
  }
}

//栈，用来存储点

</pre><pre code_snippet_id="1894337" snippet_file_name="blog_20160922_7_7362602" name="code" class="java">

<pre name="code" class="java">public class Graph {  private final int max_vertex=20;  private vertex[] verList;  private int[][] matrix;  private int currentsize;  private stack thestack;    public Graph(){  verList=new vertex[max_vertex];  matrix=new int[max_vertex][max_vertex];  currentsize=0;  for(int i=0;i<max_vertex;i++){  for(int j=0;j<max_vertex;j++){  matrix[i][j]=0;  }  }  thestack=new stack();  }    public void addvertex(char a){  verList[currentsize++]=new vertex(a);  }    public void addEdge(int start,int end){  matrix[start][end]=1;  matrix[end][start]=1;  }    public void displayvertex(int v){  System.out.print(verList[v].getLabel());  }    public void mst(){  verList[0].visit=true;  thestack.push(0);  while(!thestack.isEmpty()){  int current=thestack.peek();  int v=getUnvisit(current);  if(v==-1) thestack.pop();  else{  verList[v].visit=true;  thestack.push(v);  displayvertex(current);  displayvertex(v);  System.out.print(" ");  }  }  for(int i=0;i<currentsize;i++){  verList[i].visit=false;  }  }    public int getUnvisit(int v){  for(int i=0;i<currentsize;i++){  if(matrix[v][i]==1 && verList[i].visit==false){  return i;  }  }  return -1;  }}

//生成图以及最小生成树算法（和深度优先搜索一样）

</pre><pre code_snippet_id="1894337" snippet_file_name="blog_20160922_8_884613" name="code" class="java"><pre name="code" class="java">public class mstApp {
   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.addEdge(0, 1); //ab
   thegraph.addEdge(0, 2); //ac
   thegraph.addEdge(0, 3); //ad
   thegraph.addEdge(0, 4);  //ae
   thegraph.addEdge(1, 2);  //
   thegraph.addEdge(1, 2);
   thegraph.addEdge(1, 3);
   thegraph.addEdge(1, 4);
   thegraph.addEdge(2, 3);
   thegraph.addEdge(2, 4);
   thegraph.addEdge(3, 4);
   thegraph.mst();

   }
}

//main函数