利用邻接二维矩阵来做图
package cn.itcast_01;
public class Vertex {
private char label;
public boolean wasVisited;
public Vertex( char label){
this.label=label;
}
/**
* @return the label
*/
public char getLabel() {
return label;
}
/**
* @param label the label to set
*/
public void setLabel(char label) {
this.label = label;
}
/* (non-Javadoc)
* @see java.lang.Object#toString()
*/
@Override
public String toString() {
return "Vertex [label=" + label + "]";
}
}
package cn.itcast_01;
/*明确一个图 包括 顶点（几个顶点，顶点之间的关系，边的构造，图的初始化）
* 优化一：用一个list列表来存储顶点
* 优化二：用递归来进行深度遍历
*
* */
import java.util.LinkedList;
import java.util.Queue;
import java.util.Stack;
public class Graph {
private Vertex[] vertexlist;//邻点矩阵
private int[][] adjMat;//邻点二维数组
private int Maxnum;
private int nVertex;
public Graph(int Maxnum){
vertexlist=new Vertex[Maxnum];
adjMat =new int[Maxnum][Maxnum];
for(int i=0;i<Maxnum;i++){
for(int j=0;j<Maxnum;j++){
adjMat[i][j]=0;
}
}
nVertex=0;
}
public void addVertex(char label){
vertexlist[nVertex++] =new Vertex(label);
}
public void addEdge(int start,int end){
adjMat[start][end]=1;
adjMat[end][start]=1;
}
public int getadjUnvisitedVertex(int v){
for(int i=0;i<nVertex;i++){
if(adjMat[v][i]==1 && (vertexlist[i].wasVisited==false)){
return i;
}
}
return -1;
}
/* public void dfs(){ //用栈的方式来遍历深度优先搜索
Stack<Integer> stack=new Stack<Integer>();
vertexlist[0].wasVisited=true;
displayVertex(0);
stack.push(0);
while(!stack.isEmpty()){
int v=getadjUnvisitedVertex(stack.peek());
if(v==-1){
stack.pop();
}else{vertexlist[v].wasVisited=true;
displayVertex(v);
stack.push(v);}
}
for(int i=0;i<nVertex;i++){
vertexlist[i].wasVisited=true;
}}
*/
public void dfsDigui(){ //用递归的方式来深度优先搜索，好处是能对连通图和非连通图都能搜索
for(int i=0;i<nVertex;i++){
vertexlist[i].wasVisited=false; //首先将所有点都设置为未访问状态
}
for(int i=0;i<nVertex;i++){ //开始从第一个顶点A开始搜索，如果它是未访问状态的则开始递归
if(!vertexlist[i].wasVisited){
dfs(i);
}
}
}
public void dfs(int vertex){
vertexlist[vertex].wasVisited=true; //先把当前顶点标记为访问状态并打印
displayVertex(vertex);
for(int j=0;j<nVertex;j++){ //将它的相邻节点都找出来
if(adjMat[vertex][j]==1 && !vertexlist[j].wasVisited){
dfs(j);
}
}
}
public void BFS(){
Queue<Integer> Q = new LinkedList<Integer>();
for(int i=0;i<nVertex;i++){
vertexlist[i].wasVisited=false; //首先将所有点都设置为未访问状态
}
for(int i = 0; i < nVertex;i++){ //对每一个顶点都进行循环
if(!vertexlist[i].wasVisited){
vertexlist[i].wasVisited = true;
displayVertex(i);
Q.offer(i);
while(Q != null){
if(Q.peek() != null){
i = Q.poll(); //将队首元素赋值给i 然后出队列
}else{
return ;
}
for(int j = 0;j < nVertex;j++){
//判断其他顶点与当前顶点存在边但未被访问过
if(adjMat[i][j]==1 && !vertexlist[j].wasVisited){
vertexlist[j].wasVisited=true;
displayVertex(j);
Q.offer(j);
}
}
}
}
}
}
public void mst(){ //用栈的方式来生成最小生成树
Stack<Integer> stack=new Stack<Integer>();
vertexlist[0].wasVisited=true;
stack.push(0);
while(!stack.isEmpty()){
int currentVertex=stack.peek();//当前顶点
int v=getadjUnvisitedVertex(currentVertex);
if(v==-1){
stack.pop();
}else{vertexlist[v].wasVisited=true;
stack.push(v);
displayVertex(currentVertex);
System.out.print("-");
displayVertex(v);
System.out.println(" ");}
}
for(int i=0;i<nVertex;i++){
vertexlist[i].wasVisited=true;
}}
public void displayVertex(int v){
System.out.print(vertexlist[v].getLabel());
}
}
public static void main(String[] args) {
Graph graph=new Graph(7);
graph.addVertex('A');
graph.addVertex('B');
graph.addVertex('C');
graph.addVertex('D');
graph.addVertex('E');
graph.addVertex('F');
graph.addVertex('G');
graph.addEdge(0,1);
graph.addEdge(0,2);
graph.addEdge(3,1);
graph.addEdge(4,1);
graph.addEdge(2,5);
graph.addEdge(2,6);
/*graph.addEdge(0,1);
graph.addEdge(0,2);
graph.addEdge(1,6);
graph.addEdge(2,4);
graph.addEdge(2,3);
graph.addEdge(5,4);
graph.addEdge(6,4);*/
//graph.dfsDigui();
//graph.BFS();
graph.mst();
}
