package com.guge.test.graph;
import java.util.Stack;
/**
* Created by Guge on 2017/6/8.
*/
public class Graph {
private int maxVerts;
private Vertex[] vertexList;
private int[][] adjMat;
private int nVerts;
private Stack<Integer> theStack;
private Queue queue;
public Graph(int size){
this.maxVerts=size;
vertexList=new Vertex[maxVerts];
adjMat=new int[maxVerts][maxVerts];
nVerts=0;
queue=new Queue();
theStack=new Stack<>();
for (int i = 0; i < maxVerts; i++) {
for (int j = 0; j < maxVerts; j++) {
adjMat[i][j]=0;
}
}
}
public void addVertex(char label){
vertexList[nVerts++]=new Vertex(label);
}
public void addEdge(int start,int end){
adjMat[start][end]=1;
adjMat[end][start]=1;
}
public void displayVertext(int v){
System.out.print(vertexList[v].label);
}
private int getAdjUnvisitedVertex(int v){
for (int i = 0; i < nVerts; i++) {
if(adjMat[v][i]==1&&!vertexList[i].wasVisited){
return i;
}
}
return -1;
}
/**
* 深度优先
*/
public void dfs(){
vertexList[0].wasVisited=true;
displayVertext(0);
theStack.push(0);
while (!theStack.isEmpty()){
int v=getAdjUnvisitedVertex(theStack.peek());
if(v==-1)
theStack.pop();
else {
vertexList[v].wasVisited=true;
displayVertext(v);
theStack.push(v);
}
}
for (int i = 0; i <nVerts ; i++) {
vertexList[i].wasVisited=false;
}
}
/**
* 广度优先
*/
public void bfs(){
vertexList[0].wasVisited=true;
displayVertext(0);
queue.insert(0);
int v2;
while (!queue.isEmpty()){
int v1=queue.remove();
while ((v2=getAdjUnvisitedVertex(v1))!=-1){
vertexList[v2].wasVisited=true;
displayVertext(v2);
queue.insert(v2);
}
}
for (int i = 0; i <nVerts ; i++) {
vertexList[i].wasVisited=false;
}
}
/**
* 最小生成树
*/
public void mst(){
vertexList[0].wasVisited=true;
// displayVertext(0);
theStack.push(0);
while (!theStack.isEmpty()){
int currentVert=theStack.peek();
int v=getAdjUnvisitedVertex(currentVert);
if(v==-1)
theStack.pop();
else {
vertexList[v].wasVisited=true;
theStack.push(v);
displayVertext(currentVert);
displayVertext(v);
System.out.print(" ");
}
}
for (int i = 0; i <nVerts ; i++) {
vertexList[i].wasVisited=false;
}
}
}
class Vertex{
public char label;
public boolean wasVisited;
public Vertex(char label){
this.label=label;
wasVisited=false;
}
}
class Queue{
private final int SIZE=20;
private int[] queArr;
private int front;
private int rear;
public Queue(){
queArr=new int[SIZE];
front=0;
rear=-1;
}
public void insert(int key){
if(rear==SIZE-1)
rear=-1;
queArr[++rear]=key;
}
public int remove(){
int temp=queArr[front++];
if(front==SIZE)
front=0;
return temp;
}
public boolean isEmpty(){
return (rear+1==front||front+SIZE-1==rear);
}
}
class GraphApp{
public static void main(String[] args) {
Graph graph=new Graph(20);
graph.addVertex('A');
graph.addVertex('B');
graph.addVertex('C');
graph.addVertex('D');
graph.addVertex('E');
graph.addEdge(0,1);
graph.addEdge(0,2);
graph.addEdge(0,3);
graph.addEdge(0,4);
graph.addEdge(1,2);
graph.addEdge(1,3);
graph.addEdge(1,4);
graph.addEdge(2,3);
graph.addEdge(2,4);
graph.addEdge(3,4);
// graph.addEdge(0,1);
// graph.addEdge(1,2);
// graph.addEdge(0,3);
// graph.addEdge(3,4);
graph.mst();
}
}
