Dowemo

1. Algorithm description.

algorithm needs to access the edge of the graph, so the time complexity of the algorithm is only with the edge and can prove that the complexity is o ( eloge ).

2. Algorithm idea.

1. Sorts the edges of the chart by weight.

2. Iterate through the diagram and find the smallest edge of the weight, ( condition: The edges can't be combined with the edges of the minimum spanning tree set. If the condition is satisfied, the minimum spanning tree is added. Don't match the chart to find the edge of the next minimum weight.

3. Repeat step 1 until you find n 1 edge ( with n nodes, the minimum number of sides of the minimum spanning tree should be n 1 bars ), and the algorithm ends. It's the smallest spanning tree.


3. Java code.

1 ) structural definition

//边的结构体


class ENode {


 char start;//边的起点


 char end;//边的终点


 int weight;//边的权重



 public ENode(char start, char end, int weight) {


 this.start = start;


 this.end = end;


 this.weight = weight;


 }


};



//邻接表中表的顶点


class VNode {


 char data;//顶点信息


 ENode firstEdge;//指向第一条依附该顶点的弧


};



class Graph {


 private static final int INF = Integer.MAX_VALUE;//最大值



 char[] vertexs;//顶点集合


 int[][] matrix;//邻接矩阵



//得到当前有向图中的所有边信息


 public List<ENode> getEdges() {


 List<ENode> edges = new ArrayList<ENode>();


 for (int i = 0; i <vertexs.length; i++) {


 for (int j = 0; j <vertexs.length; j++) {


 if (matrix[i][j]!= INF) {


 ENode edge = new ENode(vertexs[i], vertexs[j], matrix[i][j]);


 edges.add(edge);


 }


 }


 }



 return edges;


 }


}






2 ) kruskal algorithm

 private static final int INF = Integer.MAX_VALUE;//最大值



 static void qSort(List<ENode> edges, int low, int high) {


 if (low <high) {


 int i = low, j = high;


 ENode edge = edges.get(low);


 while (i <j) {


 while (edge.weight <edges.get(j).weight && i <j)


 j--;


 edges.set(i, edges.get(j));


 while (edge.weight> edges.get(i).weight && i <j)


 i++;


 edges.set(j, edges.get(j));


 }


 edges.set(i, edge);


 qSort(edges, low, i - 1);


 qSort(edges, i + 1, high);


 }


 }



 public static void kruskal(Graph G) {


//1.拿到有向图中所有边


 List<ENode> edges = G.getEdges();


 int edgeNum = edges.size();



//2.对所有有向边进行排序


 qSort(edges, 0, edgeNum - 1);



 ENode[] minTree = new ENode[G.vertexs.length - 1];//结果数组,保存kruskal最小生成树的边


 int index = 0;//minTree数组的索引



//用于保存"已有最小生成树"中每个顶点(以数组下标表示) 与 其经过"最短边"的邻接顶点 (以对应下标的值表示)的并查集


 int[] start2end = new int[G.vertexs.length]; 



//3.依次将最短且不与T构成回路的边加入T集合


 for (int i = 0; i <edgeNum; i++) {


//得到当前最短边 在有向图G中的起始顶点与终结顶点的 下标


 int p1 = getIndex(G, edges.get(i).start);//获取第i条边的"起点"的序号


 int p2 = getIndex(G, edges.get(i).end);//获取第i条边的"终点"的序号



//分别得到在T集合中沿当前最短边的"起点"与"终点"遍历到的最后节点,


//若加入当前最短边后T集合存在回路,则"起点"与"终点"遍历到的最后节点一定是同一节点


 int m = getEnd(start2end, p1);//获取p1在"已有的最小生成树"中的终点


 int n = getEnd(start2end, p2);//获取p2在"已有的最小生成树"中的终点



//当前最短边加入T集合后没有有回路 则将当前最短边加入T集合,并且记录当前最短边的"起点"与"终点"


 if (m!= n) {


 start2end[m] = n;//"起点"即vends的数组下标与"终点"即vends的对应下标的值


 minTree[index++] = edges.get(i);//保存结果


 }


 }



 }



 static int getIndex(Graph G, char ch) {


 int i = 0;


 for (; i <G.vertexs.length; i++)


 if (G.vertexs[i] == ch)


 return i;


 return -1;


 }



 static int getEnd(int start2end[], int i) {


 while (start2end[i]!= 0)


 i = start2end[i];


 return i;


 }













Copyright © 2011 Dowemo All rights reserved.    Creative Commons   AboutUs