图的建立(邻接矩阵)+深度优先遍历+广度优先遍历+Prim算法构造最小生成树(Java语言描述)

主要参考资料：数据结构(C语言版)严蔚敏   ，http://blog.chinaunix.net/uid-25324849-id-2182922.html   代码测试通过。

package 图的建立与实现;

import java.util.*;

public class MGraph {
final int MAXVEX = 100;
final int INFINITY = 65535;
int[] vexs = new int[MAXVEX];           //顶点表
int[][] arc = new int[MAXVEX][MAXVEX];  //边表
boolean[] visited = new boolean[this.MAXVEX];
int numVertexes,numEdges;
public MGraph(){}

public void CreateMGraph(){
int i,j,k,w;
System.out.println("请输入顶点数和边数：");
Scanner scan = new Scanner(System.in);
this.numVertexes = scan.nextInt();
this.numEdges = scan.nextInt();
System.out.println("请输入顶点信息，建立顶点表：");
for(i=0; i<this.numVertexes; i++){
this.vexs[i] = scan.nextInt();
}
//邻接矩阵的初始化
for(i=0; i<this.numVertexes; i++){
for(j=0; j<this.numVertexes; j++){
    this.arc[i][j] = INFINITY;
}
}
System.out.println("请输入边的上标、下标、权值：");
for(k=0; k<this.numEdges; k++){
i = scan.nextInt();
j = scan.nextInt();
w = scan.nextInt();
this.arc[i][j] = w;
this.arc[j][i] = this.arc[i][j];//如果是无向图，矩阵对称
}

}

//图的深度优先遍历
public void DFS(int i){
int j;
this.visited[i] = true;
System.out.println(this.vexs[i]);
for(j=0; j<this.numVertexes; j++){
if(this.arc[i][j] < INFINITY && this.visited[j] == false){
this.DFS(j);
}
}
}

public void DFSTraverse(){
int i;
for(i=0; i<this.numVertexes; i++){
this.visited[i] = false;
} 
for(i=0; i<this.numVertexes; i++){
if(this.visited[i] == false){
this.DFS(i);
}
}
}

//图的广度优先遍历
public void BFSTraverse(){
int i,j;
Queue<Integer> queue = new ArrayDeque<Integer>();
for(i=0; i<this.numVertexes; i++){
this.visited[i] = false;
}
for(i=0; i<this.numVertexes; i++){
if(this.visited[i] == false){
this.visited[i] = true;
System.out.println(this.vexs[i]);
queue.add(i);
while(queue.isEmpty() != true){
i = queue.remove();
for(j=0; j<this.numVertexes; j++){
if(this.arc[i][j] < INFINITY  &&  visited[j] == false){
visited[j] = true;
System.out.println(this.vexs[j]);
queue.add(j);
}
}
}
}
}
}

//Prim算法构造最小生成树
public void MinSpanTree_Prim(){
 int min,i,j,k = 0;
 int[] adjvex = new int[MAXVEX];
 int[] lowcost = new int[MAXVEX];
 lowcost[0] = 0;
 adjvex[0] = 0;
 for(i=1; i<this.numVertexes; i++){
 lowcost[i] = this.arc[0][i];
 adjvex[i] = 0;
 //System.out.println(lowcost[i] + " ###");
 }
 for(i=1; i<this.numVertexes; i++){
 min = INFINITY;
 j = 1; k = 0;
 while(j < this.numVertexes){
 if(lowcost[j]!=0 && lowcost[j]<min){
 min = lowcost[j];
 k = j;
 //System.out.println(k+ " $");
 }
 j++;
 }
System.out.printf("(%d,%d)\n",adjvex[k],k);
 lowcost[k] = 0;
 for(j=1; j<this.numVertexes; j++){
 if(lowcost[j]!=0 && this.arc[k][j]<lowcost[j]){
 lowcost[j] = this.arc[k][j];
 adjvex[j] = k;
 }
   }
 }
}
}

 

package 图的建立与实现;

public class TestGraph {

public static void main(String[] args) {
MGraph G = new MGraph();
G.CreateMGraph();
System.out.println("深度优先遍历");
G.DFSTraverse();
System.out.println("广度优先遍历");
G.BFSTraverse();
System.out.println("Prim算法构造最小生成树");
G.MinSpanTree_Prim();
}

}