java数据结构----带权图

1.带权图：要引入带权图，首先要引入最小生成树，当所有的边拥有相同的权值时。问题变得简单了，算法可以选择任意一条边加入最小生成树。但是当边有不同的权值时，需要用一些算法决策来选择正确的边。

2.带权图构建最小生成树算法：

　　2.1.从一个顶点开始，把它放入树的集合中，然后重复做下面的事情：

　　　　2.1.1.找到从最新的顶点到其他顶点的所有边，这些顶点不能在树的集合中，把这些边放入优先级队列，

　　　　2.1.2.找出权值最小的边，把它和它所到达的顶点放入树的集合中。重复直到所有顶点都在树的集合中。

3.实现代码：

　　3.1.Edge.java

package com.cn.powergraph;
/**
 * 带权图的边类
 * @author Administrator
 *
 */
public class Edge {
public int srcVert;
public int destVert;
public int distance;
public Edge(int sv,int dv,int d){
    srcVert = sv;
    destVert = dv;
    distance = d;
}
}

　　3.2.PriorityQ.java

package com.cn.powergraph;
/**
 * 优先级队列来实现带权图
 * @author Administrator
 *
 */
public class PriorityQ {
private final int SIZE = 20;
private Edge[] queArray;
private int size;
public PriorityQ(){
    queArray = new Edge[SIZE];
    size = 0;
}
public void insert(Edge item){
    int i;
    for ( i = 0; i < size; i++) {
        if (item.distance >= queArray[i].distance)
            break;
    }
    for (int j = size - 1; j >= i; j --) {
        queArray[j + 1] = queArray[j];
    }
    queArray[i] = item;
    size ++;
}
public Edge removeMin(){
    return queArray[-- size];
}
public void removeN(int n){
    for (int i = n; i < size - 1; i++) {
        queArray[i] = queArray[i + 1];
    }
    size --;
}
public Edge peekMin(){
    return queArray[size - 1];
}
public int size(){
    return size;
}
public boolean isEmpty(){
    return size == 0;
}
public Edge peekN(int n){
    return queArray[n];
}
public int find(int index){
    for (int i = 0; i < size; i++) {
        if (queArray[i].destVert == index)
            return i;
    }
    return -1;
}
}

　　3.3.Vertex.java

package com.cn.powergraph;
/**
 * 带权图顶点类
 * @author Administrator
 *
 */
public class Vertex {
public char lable;
public boolean isInTree;
public Vertex(char lab){
    lable = lab;
    isInTree = false;
}
}

　　3.4.Graph.java

package com.cn.powergraph;
/**
 * 带权图的类
 * @author Administrator
 *
 */
public class Graph {
private final int MAX_VERTS = 20;
private final int INFINITY = 1000000;
private Vertex[] vertList;
private int adjMat[][];
private int nVerts;
private int currentVert;
private PriorityQ thePQ;
private int nTree;
public Graph(){
    vertList = new Vertex[MAX_VERTS];
    adjMat = new int[MAX_VERTS][MAX_VERTS];
    nVerts = 0;
    for (int i = 0; i < MAX_VERTS; i++) {
        for (int j = 0; j < MAX_VERTS; j++) {
            adjMat[i][j] = INFINITY;
        }
    }
    thePQ = new PriorityQ();
}
public void addVertex(char lab){
    vertList[nVerts ++] = new Vertex(lab);
}
public void addEdge(int start,int end,int weight){
    adjMat[start][end] = weight;
    adjMat[end][start] = weight;
}
public void displayVertex(int v){
    System.out.print(vertList[v].lable);
}
public void mstw(){
    currentVert = 0;
    while (nTree < nVerts - 1){
        vertList[currentVert].isInTree = true;
        nTree ++;
        for (int i = 0; i < nVerts; i++) {
            if (i == currentVert)
                continue;
            if (vertList[i].isInTree)
                continue;
            int distance = adjMat[currentVert][i];
            if (distance == INFINITY)
                continue;
            putInPQ(i,distance);
        }
        if (thePQ.size() == 0)
        {
            System.out.println("GRAPH NOT CONNECTED");
            return;
        }
        Edge theedge = thePQ.removeMin();
        int sourceVert = theedge.srcVert;
        currentVert = theedge.destVert;
        System.out.print(vertList[sourceVert].lable);
        System.out.print(vertList[currentVert].lable);
        System.out.print("  ");
    }
    for (int i = 0; i < nVerts; i++) {
        vertList[i].isInTree = false;
    }
}
public void putInPQ(int newVert,int newDist){
    int queueIndex = thePQ.find(newDist);
    if (queueIndex != -1){
        Edge tempEdge = thePQ.peekN(queueIndex);
        int oldDist = tempEdge.distance;
        if (oldDist > newDist){
            thePQ.removeN(queueIndex);
            Edge theEdge = new Edge(currentVert, newVert,newDist);
            thePQ.insert(theEdge);
        }
    }
    else{
        Edge theEdge = new Edge(currentVert, newVert,newDist);
        thePQ.insert(theEdge);
    }
}
}

　　3.5.GTest.java

package com.cn.powergraph;
/**
 * 带权图的测试
 * @author Administrator
 *
 */
public class GTest {
public static void main(String[] args) {
    Graph g = new Graph();
    g.addVertex('a');
    g.addVertex('b');
    g.addVertex('c');
    g.addVertex('d');
    g.addVertex('e');
    g.addVertex('f');
    g.addEdge(0, 1, 3);
    g.addEdge(2, 1, 5);
    g.addEdge(3, 1, 8);
    g.addEdge(3, 2, 5);
    g.addEdge(5, 4, 4);
    g.addEdge(0, 4, 10);
    g.mstw();
}
}