图的概念
图是一种非线性的数据结构,一个图中有两类东西，一种是结点，一种是边.我们用V这个集合来表示节点（vertex），还需要另一个集合来存储所有的边，我们用E来表示(Edge)，那么一个图就可以表示为：G=(V,E);
带箭头的称为有向图,否则称为无向图.
如果一个图的任意两个结点之间有且只有一条边，则称此图为无向完全图，若任意两个结点之间有且只有方向相反的两条边，则称为有向完全图.
度是针对结点来说的， 又分为出度和入度,对于有向图来说，出度就是指以这个结点为起始的边的条数（箭头向外），入度则是以这个点为终点的边的条数（箭头向内）.
权是指一条边所附带的数据信息，比如说一个结点到另一个结点的距离，或者花费的时间等等都可以用权来表示。
图的存储结构
存储一个图可以采用邻接矩阵或者邻接表.
一个无向图的邻接矩阵如下:
1
它消耗的空间为Θ|V|²,适合图很稠密的时候.
同样的无向图用邻接表表示如下
2
消耗的空间为O(|E|+|V|).适合图稀疏的时候.
先来用代码实现有向图邻接矩阵的图模型,无向图差不多的不写了,根据下图来实现:
3
package com.fredal.structure;
import java.util.ArrayList;
public class MyGraphy {
private ArrayList vList;//用来存节点
private int[][] edges;//邻接矩阵 用来存储边
private int numOfEdges;//边的条数
public MyGraphy(int n){
//初始化矩阵
edges=new int[n][n];
vList=new ArrayList(n);
numOfEdges=0;
}
public int[][] getEdges() {
return edges;
}
//得到节点个数
public int getNumOfVertex(){
return vList.size();
}
//得到边的个数
public int getNumOfEdges(){
return numOfEdges;
}
//返回节点i的值
public Object get(int i){
return vList.get(i);
}
//返回v1,v2节点之间边的权值
public int getWeight(int v1,int v2){
return edges[v1][v2];
}
//插入节点
public void insertVertext(Object vertex){
vList.add(vList.size(),vertex);
edges=new int[vList.size()][vList.size()];
}
//插入边
public void insertEdge(int v1,int v2,int weight){
edges[v1][v2]=weight;
numOfEdges++;
}
//删除节点
public void deleteVertex(int v){
vList.remove(v);
for(int i=0;i<vList.size();i++){
edges[v][i]=0;
numOfEdges--;
}
}
//删除边
public void deleteEdge(int v1,int v2){
edges[v1][v2]=0;
numOfEdges--;
}
//得到第一个邻接节点的下标
public int getFirstneighbor(int i){
for(int j=0;j<vList.size();j++){
if(edges[i][j]>0){
return j;
}
}
return -1;
}
//根据前一个邻接节点的下标来取得下一个邻接节点
public int getNextNeighbor(int v1,int v2){
for(int j=v2+1;j<vList.size();j++){
if(edges[v1][j]>0){
return j;
}
}
return -1;
}
//测试程序
public static void main(String[] args) {
String labels[]={"V1","V2","V3","V4"};//结点的标识
MyGraphy g=new MyGraphy(4);
for(String label:labels) {
g.insertVertext(label);//插入结点
}
g.insertEdge(0, 1, 2);
g.insertEdge(0, 2, 5);
g.insertEdge(2, 3, 8);
g.insertEdge(3, 0, 7);
System.out.println("结点个数是："+g.getNumOfVertex());
System.out.println("边的个数是："+g.getNumOfEdges());
g.deleteEdge(0, 1);//删除<V1,V2>边
System.out.println("删除<V1,V2>边后...");
System.out.println("结点个数是："+g.getNumOfVertex());
System.out.println("边的个数是："+g.getNumOfEdges());
}
}
接下来我们用邻接表来实现图的存储,同样是前面那张图
package com.fredal.structure;
import java.util.ArrayList;
import java.util.Iterator;
import java.util.LinkedList;
import java.util.List;
import com.fredal.structure.MyGraphyL.Node;
import com.fredal.structure.MyGraphyL.Vertex;
public class MyGraphyL {
class Vertex{
private Object value;//顶点的名称
private int vvalue;//定点的额值
public LinkedList<Node> elist;//链表 用来存放边的信息
public Vertex(Object value,int vvalue){
this.value=value;
this.vvalue=vvalue;
elist=new LinkedList<Node>();
}
}
class Node{
private int evalue;//边的节点的值
private int weight;//权重
public Node(int evalue,int weight){
this.evalue=evalue;
this.weight=weight;
}
public int getEvalue() {
return evalue;
}
public int getWeight() {
return weight;
}
}
private List<Vertex> vertexs;//存储节点
private int numOfEdges;//边的条数
public MyGraphyL(int n){
//初始化邻接表
vertexs=new ArrayList<Vertex>(n);
numOfEdges=0;
}
public List<Vertex> getVertexs() {
return vertexs;
}
//得到节点个数
public int getNumOfVertex(){
return vertexs.size();
}
//得到边的个数
public int getNumOfEdges(){
return numOfEdges;
}
//返回节点i的值
public Object get(int i){
Vertex vertex = vertexs.get(i);
if(vertex!=null){
return vertex.value;
}
return null;
}
//返回v1,v2节点之间边的权值
public int getWeight(int v1,int v2){
Node search = search(v1, v2);
if(search!=null) return search.weight;
else return -1;
}
//搜索边节点
public Node search(int v1,int v2){
Iterator<Node> it = vertexs.get(v1).elist.iterator();
while(it.hasNext()){
Node node = (Node) it.next();
if(node.evalue==v2){
return node;
}
}
return null;
}
//插入节点
public void insertVertext(Object value,int vvalue){
Vertex vertex=new Vertex(value,vvalue);
vertexs.add(vertex);
}
//插入边节点
public void insertEdge(int v1,int v2,int weight){
LinkedList<Node> elist = vertexs.get(v1).elist;
Node node = new Node(v2, weight);
elist.add(node);
numOfEdges++;
}
//删除节点
public void deleteVertex(int vvalue){
vertexs.remove(vvalue);
}
//删除边节点
public void deleteEdge(int v1,int v2){
LinkedList<Node> elist = vertexs.get(v1).elist;
Node search = search(v1, v2);
if(search!=null) elist.remove(search);
numOfEdges--;
}
//得到节点的第一个边节点的下标
public int getFirstneighbor(int i){
LinkedList<Node> elist = vertexs.get(i).elist;
if(elist.size()==0) return -1;
Node node = elist.get(0);
if(node!=null)
return node.evalue;
return -1;
}
//根据前一个边节点的下标来取得下一个边节点
public int getNextNeighbor(int v1,int v2){
LinkedList<Node> elist = vertexs.get(v1).elist;
Iterator<Node> iterator = elist.iterator();
while(iterator.hasNext()){
Node next = iterator.next();
if (next.evalue==v2) {
try {
return iterator.next().evalue;
} catch (Exception e) {
System.out.println("没有下一个");
}
}
}
return -1;
}
//测试程序
public static void main(String args[]) {
int i=0;
int n=4,e=4;//分别代表结点个数和边的数目
String labels[]={"V1","V2","V3","V4"};//结点的标识
MyGraphyL graph=new MyGraphyL(n);
for(String label:labels) {
graph.insertVertext(label, i);//插入结点
i++;
}
//插入四条边
graph.insertEdge(0, 1, 2);
graph.insertEdge(0, 2, 5);
graph.insertEdge(2, 3, 8);
graph.insertEdge(3, 0, 7);
System.out.println("结点个数是："+graph.getNumOfVertex());
System.out.println("边的个数是："+graph.getNumOfEdges());
// graph.deleteEdge(0, 1);//删除<V1,V2>边
// System.out.println("删除<V1,V2>边后...");
// System.out.println("结点个数是："+graph.getNumOfVertex());
// System.out.println("边的个数是："+graph.getNumOfEdges());
System.out.println(graph.getFirstneighbor(0));
System.out.println(graph.getNextNeighbor(0, 1));
System.out.println("---------------------");
List<Vertex> vlist = graph.vertexs;
for(Vertex v:vlist){
System.out.println(v.value+" "+v.vvalue+":");
LinkedList<Node> elist = v.elist;
for (Node node : elist) {
System.out.println(" "+node.evalue+"--"+node.weight);
}
}
}
}
深度优先遍历与广度优先遍历
-
深度优先遍历
所谓深度优先遍历,就是首先访问第一个邻接结 点，然后再以这个被访问的邻接结点作为初始结点，访问它 的第一个邻接结点。总结起来可以这样说：每次都在访问完当前结点后首先访问当前结点的第一个邻接结点。
如下图,深度优先遍历的顺序为1->2->4->8->5->3->6->7
4
我们先用邻接矩阵的形式实现上图的深度优先遍历,图结构采用上面自己写的
package com.fredal.structure;
public class DeepTravel {
//深度优先遍历 参数为要遍历的图,访问过的标记以及从哪开始遍历
public static void deepTravel(MyGraphy a,boolean [] visited,int k){
int[][] edges = a.getEdges();
visited[k]=true;
System.out.println(a.get(k));
for(int i=0;i<edges[k].length;i++){
if(edges[k][i]==1&&visited[i]==false) deepTravel(a, visited, i);
}
}
public static void main(String[] args) {
String labels[]={"1","2","3","4","5","6","7","8"};//结点的标识
MyGraphy a=new MyGraphy(8);
for(String label:labels){
a.insertVertext(label);
}
a.insertEdge(0, 1, 1);
a.insertEdge(0, 2, 1);
a.insertEdge(1, 3, 1);
a.insertEdge(1, 4, 1);
a.insertEdge(3, 7, 1);
a.insertEdge(4, 7, 1);
a.insertEdge(2, 5, 1);
a.insertEdge(2, 6, 1);
a.insertEdge(5, 6, 1);
a.insertEdge(1, 0, 1);
a.insertEdge(2, 0, 1);
a.insertEdge(3, 1, 1);
a.insertEdge(4, 1, 1);
a.insertEdge(7, 3, 1);
a.insertEdge(7, 4, 1);
a.insertEdge(4, 2, 1);
a.insertEdge(5, 2, 1);
a.insertEdge(6, 5, 1);
boolean [] visited=new boolean[a.getNumOfVertex()];
deepTravel(a, visited, 0);
}
}
用邻接表实现深度优先遍历并没有多大区别:
public class DeepTravel {
public static void deepTravelL(MyGraphyL a,boolean [] visited,int k){
List<Vertex> vertexs = a.getVertexs();
visited[k]=true;
System.out.println(a.get(k));
LinkedList<Node> elist = vertexs.get(k).elist;
Iterator<Node> iterator = elist.iterator();
while(iterator.hasNext()){
Node node = iterator.next();
if(visited[node.getEvalue()]==false) deepTravelL(a, visited, node.getEvalue());
}
}
public static void main(String[] args) {
String labels[]={"1","2","3","4","5","6","7","8"};//结点的标识
MyGraphyL a=new MyGraphyL(8);
int i=0;
for(String label:labels) {
a.insertVertext(label, i);//插入结点
i++;
}
a.insertEdge(0, 1, 1);
a.insertEdge(0, 2, 1);
a.insertEdge(1, 3, 1);
a.insertEdge(1, 4, 1);
a.insertEdge(3, 7, 1);
a.insertEdge(4, 7, 1);
a.insertEdge(2, 5, 1);
a.insertEdge(2, 6, 1);
a.insertEdge(5, 6, 1);
a.insertEdge(1, 0, 1);
a.insertEdge(2, 0, 1);
a.insertEdge(3, 1, 1);
a.insertEdge(4, 1, 1);
a.insertEdge(7, 3, 1);
a.insertEdge(7, 4, 1);
a.insertEdge(4, 2, 1);
a.insertEdge(5, 2, 1);
a.insertEdge(6, 5, 1);
boolean [] visited=new boolean[a.getNumOfVertex()];
deepTravelL(a, visited, 0);
}
}
-
广度优先遍历
广度优先遍历(BFS)从根节点开始，沿着树的宽度遍历树的节点。如果所有节点均被访问，则算法中止。
上图按广度优先遍历的顺序应为:1->2->3->4->5->6->7->8
同样采用上面的图先使用邻接矩阵进行模拟
package com.fredal.structure;
import java.util.ArrayList;
import java.util.HashSet;
import java.util.List;
import java.util.Set;
public class WidthTravel {
public static void widthTravel(MyGraphy a,Set visited,List layer){
int[][] edges = a.getEdges();
//遍历当前层
for(int i=0;i<layer.size();i++){
System.out.println(a.get((Integer) layer.get(i)));
visited.add(layer.get(i));
}
//下一层
List next_layer=new ArrayList();
for(int i=0;i<layer.size();i++){
int node=(Integer) layer.get(i);
for(int j=0;j<edges[node].length;j++){
if(edges[node][j]==1&&next_layer.indexOf(j)<0) next_layer.add(j);
}
}
next_layer.removeAll(visited);
if(next_layer.isEmpty()==false) widthTravel(a, visited, next_layer);
}
public static void main(String[] args) {
String labels[]={"1","2","3","4","5","6","7","8"};//结点的标识
MyGraphy a=new MyGraphy(8);
for(String label:labels){
a.insertVertext(label);
}
a.insertEdge(0, 1, 1);
a.insertEdge(0, 2, 1);
a.insertEdge(1, 3, 1);
a.insertEdge(1, 4, 1);
a.insertEdge(3, 7, 1);
a.insertEdge(4, 7, 1);
a.insertEdge(2, 5, 1);
a.insertEdge(2, 6, 1);
a.insertEdge(5, 6, 1);
a.insertEdge(1, 0, 1);
a.insertEdge(2, 0, 1);
a.insertEdge(3, 1, 1);
a.insertEdge(4, 1, 1);
a.insertEdge(7, 3, 1);
a.insertEdge(7, 4, 1);
a.insertEdge(4, 2, 1);
a.insertEdge(5, 2, 1);
a.insertEdge(6, 5, 1);
Set visited=new HashSet();
List layer=new ArrayList();
layer.add(0);
widthTravel(a, visited, layer);
}
}
用邻接表实现广度遍历基本没区别
public class WidthTravel {
public static void widthTravelL(MyGraphyL a,Set visited,List layer){
List<Vertex> vertexs = a.getVertexs();
//遍历当前层
for(int i=0;i<layer.size();i++){
System.out.println(a.get((Integer) layer.get(i)));
visited.add(layer.get(i));
}
//下一层
List next_layer=new ArrayList();
for(int i=0;i<layer.size();i++){
int node=(Integer) layer.get(i);
LinkedList<Node> elist = vertexs.get(node).elist;
Iterator<Node> iterator = elist.iterator();
while(iterator.hasNext()){
Node next = iterator.next();
if(next_layer.indexOf(next.getEvalue())<0) next_layer.add(next.getEvalue());
}
}
next_layer.removeAll(visited);
if(next_layer.isEmpty()==false) widthTravelL(a, visited, next_layer);
}
public static void main(String[] args) {
String labels[]={"1","2","3","4","5","6","7","8"};//结点的标识
MyGraphyL a=new MyGraphyL(8);
int i=0;
for(String label:labels) {
a.insertVertext(label, i);//插入结点
i++;
}
a.insertEdge(0, 1, 1);
a.insertEdge(0, 2, 1);
a.insertEdge(1, 3, 1);
a.insertEdge(1, 4, 1);
a.insertEdge(3, 7, 1);
a.insertEdge(4, 7, 1);
a.insertEdge(2, 5, 1);
a.insertEdge(2, 6, 1);
a.insertEdge(5, 6, 1);
a.insertEdge(1, 0, 1);
a.insertEdge(2, 0, 1);
a.insertEdge(3, 1, 1);
a.insertEdge(4, 1, 1);
a.insertEdge(7, 3, 1);
a.insertEdge(7, 4, 1);
a.insertEdge(4, 2, 1);
a.insertEdge(5, 2, 1);
a.insertEdge(6, 5, 1);
Set visited=new HashSet();
List layer=new ArrayList();
layer.add(0);
widthTravelL(a, visited, layer);
}
}
拓扑排序(kahn&DFS)
关于拓扑排序,是一种对于关联性的排序,可以参考维基百科的解释:
在图论中，由一个有向无环图的顶点组成的序列，当且仅当满足下列条件时，称为该图的一个拓扑排序（Topological sorting）。
a. 每个顶点出现且只出现一次；
b. 若A在序列中排在B的前面，则在图中不存在从B到A的路径。
也可以定义为：拓扑排序是对有向无环图的顶点的一种排序，它使得如果存在一条从顶点A到顶点B的路径，那么在排序中B出现在A的后面
我们根据下图进行排序
5
首先来最简单的和自然的kahn算法,得出的结果应该是
1->5->2->4->6->7->3,基于邻接表
package com.fredal.structure;
import java.util.Iterator;
import java.util.LinkedList;
import java.util.Queue;
import com.fredal.structure.MyGraphyL.Node;
import com.sun.xml.internal.messaging.saaj.packaging.mime.util.QEncoderStream;
public class TopSort {
public static void topSort(MyGraphyL a){
int[] ins;//入度数组
int [] tops;//拓扑排序的结果数组
Queue<Integer> queue;//辅助队列
int num=a.getNumOfVertex();//顶点个数
int index=0;
ins=new int[num];
tops=new int[num];
queue=new LinkedList<Integer>();
//统计每个顶点的入度数
for(int i=0;i<num;i++){
LinkedList<Node> elist = a.getVertexs().get(i).elist;
Iterator<Node> iterator = elist.iterator();
while(iterator.hasNext()){
ins[iterator.next().getEvalue()]++;
}
}
//将入度为0的顶点入队列
for(int i=0;i<num;i++){
if(ins[i]==0) queue.offer(i);//入队列
}
while(!queue.isEmpty()){
int j=queue.poll().intValue();//出队列 j是顶点序号 tops[index++]=Integer.parseInt((String) a.get(j));
LinkedList<Node> elist = a.getVertexs().get(j).elist;
Iterator<Node> iterator = elist.iterator();
while(iterator.hasNext()){
Node node = iterator.next();
ins[node.getEvalue()]--;//将入度减一
if(ins[node.getEvalue()]==0) queue.offer(node.getEvalue());
}
}
if(index!=num){
System.out.println("有个环");
return;
}
//输出排序结果
System.out.print("拓扑排序: ");
for(int i=0;i<num;i++){
System.out.print(tops[i]+" ");
}
}
public static void main(String[] args) {
String labels[]={"1","2","3","4","5","6","7"};//结点的标识
MyGraphyL a=new MyGraphyL(8);
int i=0;
for(String label:labels) {
a.insertVertext(label, i);//插入结点
i++;
}
a.insertEdge(0, 1, 1);
a.insertEdge(0, 3, 1);
a.insertEdge(0, 5, 1);
a.insertEdge(1, 6, 1);
a.insertEdge(3, 2, 1);
a.insertEdge(4, 6, 1);
a.insertEdge(5, 6, 1);
a.insertEdge(6, 2, 1);
topSort(a);
}
}
除了上面那种算法我们还可以基于深度优先遍历(DFS)进行拓扑排序,同样基于邻接表,首先保证图是有向无环图
package com.fredal.structure;
import java.util.Iterator;
import java.util.LinkedList;
import java.util.List;
import java.util.Stack;
import com.fredal.structure.MyGraphyL.Node;
import com.fredal.structure.MyGraphyL.Vertex;
public class TopSort {
static boolean [] visited;
private static Stack<Integer> stack=new Stack<Integer>();
public static void topSortDFS(MyGraphyL a){
int num=a.getNumOfVertex();
visited=new boolean[num];
for(int i=0;i<num;i++){//循环调用DFS
if(!visited[i]) DFS(a, i);
}
}
private static void DFS(MyGraphyL a,int k){
visited[k]=true;
List<Vertex> vertexs = a.getVertexs();
LinkedList<Node> elist = vertexs.get(k).elist;
Iterator<Node> iterator = elist.iterator();
while(iterator.hasNext()){
Node node = iterator.next();
if(!visited[node.getEvalue()]) {
DFS(a, node.getEvalue());
}
}
stack.push(Integer.parseInt((String) a.get(k)));//在dfs方法快结束时压入栈中
}
public static void main(String[] args) {
String labels[]={"1","2","3","4","5","6","7"};//结点的标识
MyGraphyL a=new MyGraphyL(8);
int i=0;
for(String label:labels) {
a.insertVertext(label, i);//插入结点
i++;
}
a.insertEdge(0, 1, 1);
a.insertEdge(0, 3, 1);
a.insertEdge(0, 5, 1);
a.insertEdge(1, 6, 1);
a.insertEdge(3, 2, 1);
a.insertEdge(4, 6, 1);
a.insertEdge(5, 6, 1);
a.insertEdge(6, 2, 1);
topSortDFS(a);
while(!stack.isEmpty()){
System.out.println(stack.pop());
}
}
}
这种算法得出得到排序结果为5->1->6->4->2->7->3,与上面的有些区别,但是仍然是对的排序结果.
这有关到解的唯一性问题,有哈密顿路径的图,即每一对顶点都能确定向后关系的图的解是唯一的.
至于如何确定有唯一解呢,最简单的想法是把每一对顶点两两比较看看有无先后关系,但是这样很低效,我们可以用类似插入排序的算法进行判断.详细的以后再讲.
最短路径问题(Dijkstra&Floyd)
最短路径问题,先讲单源最短路径,就是求从指定顶点出发到其他各点的最短距离.经典的算法有(Dijkstra)算法.
我们根据下图来模拟该算法:
6
public class Dijstra {
public static void dijstra(MyGraphyL a,int k){
Map map=new HashMap();//存储节点号--最小路径值
List<Vertex> vertexs = a.getVertexs();
while(true){
int min=Integer.MAX_VALUE;
int min_no=-1;
Vertex first = vertexs.get(k);//获得初始节点
Iterator<Node> iterator = first.elist.iterator();
while(iterator.hasNext()){
Node node = iterator.next();
//选出路径最短的节点
if(map.get(node.getEvalue())==null&&node.getWeight()<min){
min_no=node.getEvalue();
min=node.getWeight();
}
}
Iterator it = map.keySet().iterator();
while(it.hasNext()){
//取出集合中存在的最短路径节点
int index=(Integer) it.next();
int weight=(Integer) map.get(index);
Iterator<Node> iterator2 = vertexs.get(index).elist.iterator();
while(iterator2.hasNext()){
Node node2 = iterator2.next();
//将集合中的节点自身的权值加上下一个节点的权值与外面非集合中的权值比较 取最小值 循环
if(map.get(node2.getEvalue())==null&&node2.getWeight()+weight<min){
min_no=node2.getEvalue();
min=node2.getWeight()+weight;
}
}
}
//出口
if(min<Integer.MAX_VALUE)
map.put(min_no, min);
else
break;
}
System.out.println(map);
}
public static void main(String[] args) {
String labels[]={"0","1","2","3","4"};//结点的标识
MyGraphyL a=new MyGraphyL(5);
int i=0;
for(String label:labels) {
a.insertVertext(label, i);//插入结点
i++;
}
a.insertEdge(0, 1, 10);
a.insertEdge(0, 3, 30);
a.insertEdge(0, 4, 100);
a.insertEdge(1, 2, 50);
a.insertEdge(2, 4, 10);
a.insertEdge(3, 2, 20);
a.insertEdge(3, 4, 60);
dijstra(a, 0);
}
}
模拟结果为:
从0出发到1的最短路径为：0-->1
从0出发到2的最短路径为：0-->3-->2
从0出发到3的最短路径为：0-->3
从0出发到4的最短路径为：0-->3-->2-->4
从0出 发到1的最短距离为：10
从0出 发到2的最短距离为：50
从0出 发到3的最短距离为：30
从0出 发到4的最短距离为：60
对于最短路径问题,还有著名的算法,Floyd算法,比起单源,它对于任意两点间的最短路径问题计算更方便.
通过Floyd计算图G=(V,E)中各个顶点的最短路径时，需要引入一个矩阵S，矩阵S中的元素a[i][j]表示顶点i(第i个顶点)到顶点j(第j个顶点)的距离。
基本思想:
假设图G中顶点个数为N，则需要对矩阵S进行N次更新。初始时，矩阵S中顶点a[i][j]的距离为顶点i到顶点j的权值；如果i和j不相邻，则a[i][j]=∞。 接下来开始，对矩阵S进行N次更新。第1次更新时，如果"a[i][j]的距离" > "a[i][0]+a[0][j]"(a[i][0]+a[0][j]表示"i与j之间经过第1个顶点的距离")，则更新a[i][j]为"a[i][0]+a[0][j]"。 同理，第k次更新时，如果"a[i][j]的距离" > "a[i][k]+a[k][j]"，则更新a[i][j]为"a[i][k]+a[k][j]"。更新N次之后，操作完成！
我们还是用代码模拟更易于理解,同样采用上面那张图,基于邻接矩阵:
package com.fredal.structure;
import java.util.ArrayList;
import java.util.List;
public class Floyd {
// path[i][j]=k表示 顶点i到顶点j的最短路径经过k
// dis[i][j]=s表示 顶点i到顶点j的最短路径长度为s
public static void floyd(MyGraphy a) {
int num = a.getNumOfVertex();
int[][] edges = a.getEdges();
int INF = Integer.MAX_VALUE;
int[][] dis = new int[num][num];
List[][] path = new List[num][num];//用list来存储具体的路径
// 初始化
for (int i = 0; i < num; i++) {
for (int j = 0; j < num; j++) {
dis[i][j] = ((edges[i][j] == 0) ? INF : edges[i][j]);//用inf表示没有通路
if (path[i][j] == null) {
path[i][j] = new ArrayList();
path[i][j].add(j);
}
}
}
// 计算最短路径
for (int k = 0; k < num; k++) {
for (int i = 0; i < num; i++) {
for (int j = 0; j < num; j++) {
// 如果经过下标为k的顶点路径比原来两点间的路径更短,则更新dis[i][j]和path[i][j]
int tmp = (dis[i][k] == INF || dis[k][j] == INF) ? INF
: (dis[i][k] + dis[k][j]);
if (dis[i][j] > tmp) {
dis[i][j] = tmp;//更新路径长度
//更新路径 用list存储
List list = new ArrayList();
list.addAll(path[i][k]);
list.addAll(path[k][j]);
path[i][j]=list;
}
}
}
}
//输出路径长度和具体的最短路径
System.out.println("floyd:");
for (int i = 0; i < num; i++) {
for (int j = 0; j < num; j++) {
System.out.print((dis[i][j]==INF?0:dis[i][j]) + " ");//INF太难看了 我还是换回0表示没有通路
}
System.out.println();
}
System.out.println("path:");
for (int i = 0; i < num; i++) {
for (int j = 0; j < num; j++) {
System.out.print(path[i][j] + " ");
}
System.out.println();
}
}
public static void main(String[] args) {
String labels[] = { "0", "1", "2", "3", "4" };// 结点的标识
MyGraphy a = new MyGraphy(5);
for (String label : labels) {
a.insertVertext(label);// 插入结点
}
a.insertEdge(0, 1, 10);
a.insertEdge(0, 3, 30);
a.insertEdge(0, 4, 100);
a.insertEdge(1, 2, 50);
a.insertEdge(2, 4, 10);
a.insertEdge(3, 2, 20);
a.insertEdge(3, 4, 60);
floyd(a);
}
}
运行结果为:
7
最小生成树(Prim&Kruskal)
最小生成树问题,在含有n个顶点的连通图中选择n-1条边，构成一棵极小连通子图，并使该连通子图中n-1条边上权值之和达到最小，则称其为连通网的最小生成树。
普里姆(Prim)算法，是用来求加权连通图的最小生成树的算法。
基本思想为从一个起点开始,选取连接这个点的所有边中权值最小的那条边,然后把边的终点当成新的起点,继续选取权值最小的边,直到把所有顶点都选了一遍..
8
对于上图而言,采用Prim算法生成最小生成树的步骤为:
初始状态：V是所有顶点的集合，即V={A,B,C,D,E,F,G}；U和T都是空！
第1步：将顶点A加入到U中。
此时，U={A}。
第2步：将顶点B加入到U中。
上一步操作之后，U={A}, V-U={B,C,D,E,F,G}；因此，边(A,B)的权值最小。将顶点B添加到U中；此时，U={A,B}。
第3步：将顶点F加入到U中。
上一步操作之后，U={A,B}, V-U={C,D,E,F,G}；因此，边(B,F)的权值最小。将顶点F添加到U中；此时，U={A,B,F}。
第4步：将顶点E加入到U中。
上一步操作之后，U={A,B,F}, V-U={C,D,E,G}；因此，边(F,E)的权值最小。将顶点E添加到U中；此时，U={A,B,F,E}。
第5步：将顶点D加入到U中。
上一步操作之后，U={A,B,F,E}, V-U={C,D,G}；因此，边(E,D)的权值最小。将顶点D添加到U中；此时，U={A,B,F,E,D}。
第6步：将顶点C加入到U中。
上一步操作之后，U={A,B,F,E,D}, V-U={C,G}；因此，边(D,C)的权值最小。将顶点C添加到U中；此时，U={A,B,F,E,D,C}。
第7步：将顶点G加入到U中。
上一步操作之后，U={A,B,F,E,D,C}, V-U={G}；因此，边(G,E)的权值最小。将顶点G添加到U中；此时，U=V。
此时，最小生成树构造完成！它包括的顶点依次是：A B F E D C G,权值为36。
我们采用代码模拟该步骤,基于邻接矩阵:
首先我们要在之前写的MyGraohy类中加一个方法
//返回顶点在的位置
public int getPosition(Object v){
return vList.indexOf(v);
}
开始模拟Prim算法
package com.fredal.structure;
public class Prim {
public static void prim(MyGraphy a,int start){
int num=a.getNumOfVertex();//顶点个数
int[][] edges = a.getEdges();
int index=0;//数组的索引
String[] prims=new String[num];//结果数组
int[] weight=new int[num];//顶点边的权值
int INF=Integer.MAX_VALUE;
//把0变成INF
for(int i=0;i<num;i++){
for(int j=0;j<num;j++){
edges[i][j]=(edges[i][j]==0?INF:edges[i][j]);
}
}
//prim树中第一个数是"图中第start个顶点"
prims[index++]= (String) a.get(start);
//将每个顶点的权值初始化为"第start个顶点"到"该定点"的权值
for(int i=0;i<num;i++)
weight[i]=edges[start][i];
//到自身的距离为0
weight[start]=0;
for(int i=0;i<num;i++){
if(start==i) continue;
int j=0;
int k=0;
int min=Integer.MAX_VALUE;
while(j<num){
//找到权值最小的顶点
if(weight[j]!=0&&weight[j]<min){
min =weight[j];
k=j;
}
j++;
}
//经过上面的处理 权值最小的顶点是第k个顶点,将第k个顶点加入到最小生成树的结果数组中
prims[index++]=(String) a.get(k);
//将第k个节点的权值标记为0 意味着第k个顶点已经排序了
weight[k]=0;
//更新下一轮节点的权值
for(j=0;j<num;j++){
if(weight[j]!=0&&edges[k][j]<weight[j]){
weight[j]=edges[k][j];
}
}
}
//计算最小生成树的权值
int sum=0;
for(int i=1;i<index;i++){
int min=Integer.MAX_VALUE;
int n=a.getPosition(prims[i]);
for(int j=0;j<i;j++){
int m=a.getPosition(prims[j]);
if(edges[m][n]<min) min=edges[m][n];
}
sum+=min;
}
//打印最小生成树
System.out.println("prim:");
System.out.println("sum:"+sum);
System.out.println("path:");
for(int i=0;i<index;i++){
System.out.print(prims[i]+" ");
}
}
public static void main(String[] args) {
String labels[]={"A","B","C","D","E","F","G"};//结点的标识
MyGraphy g=new MyGraphy(7);
for(String label:labels) {
g.insertVertext(label);//插入结点
}
g.insertEdge(0, 1, 12);
g.insertEdge(0, 5, 16);
g.insertEdge(0, 6, 14);
g.insertEdge(1, 0, 12);
g.insertEdge(1, 2, 10);
g.insertEdge(1, 5, 7);
g.insertEdge(2, 1, 10);
g.insertEdge(2, 3, 3);
g.insertEdge(2, 4, 5);
g.insertEdge(2, 5, 6);
g.insertEdge(3, 2, 3);
g.insertEdge(3, 4, 4);
g.insertEdge(4, 2, 5);
g.insertEdge(4, 3, 4);
g.insertEdge(4, 5, 2);
g.insertEdge(4, 6, 8);
g.insertEdge(5, 0, 16);
g.insertEdge(5, 1, 7);
g.insertEdge(5, 2, 6);
g.insertEdge(5, 4, 2);
g.insertEdge(5, 6, 9);
g.insertEdge(6, 0, 14);
g.insertEdge(6, 4, 8);
g.insertEdge(6, 5, 9);
prim(g, 0);
}
}
除了Prim算法外,还有一种思路迥异的kruskal算法,基本思想是按照权值从小到大排列所有的边,依次选取并且保证不构成回路.
同样根据上面的图作为基础,步骤为:
第1步：将边(E,F)加入R中。
边(E,F)的权值最小，因此将它加入到最小生成树结果R中。
第2步：将边(C,D)加入R中。
上一步操作之后，边(C,D)的权值最小，因此将它加入到最小生成树结果R中。
第3步：将边(D,E)加入R中。
上一步操作之后，边(D,E)的权值最小，因此将它加入到最小生成树结果R中。
第4步：将边(B,F)加入R中。
上一步操作之后，边(C,E)的权值最小，但(C,E)会和已有的边构成回路；因此，跳过边(C,E)。同理，跳过边(C,F)。将边(B,F)加入到最小生成树结果R中。
第5步：将边(E,G)加入R中。
上一步操作之后，边(E,G)的权值最小，因此将它加入到最小生成树结果R中。
第6步：将边(A,B)加入R中。
上一步操作之后，边(F,G)的权值最小，但(F,G)会和已有的边构成回路；因此，跳过边(F,G)。同理，跳过边(B,C)。将边(A,B)加入到最小生成树结果R中。
此时，最小生成树构造完成！它包括的边依次是：(E,F) (C,D) (D,E) (B,F) (E,G) (A,B)。
我们还是选择基于邻接表实现该算法
首先为了方便,我们还往MyGraph类中增加一个内部类和三个方法,方便边的排序
class Edge{
Object from;
Object to;
int weight;
public Edge(Object from, Object to, int weight) {
super();
this.from = from;
this.to = to;
this.weight = weight;
}
}
//得到图中的边
public Edge[] getEgdes(){
int index=0;
int num=getNumOfVertex();
Edge[] edgel=new Edge[numOfEdges/2];
for(int i=0;i<num;i++){
for(int j=i+1;j<num;j++){
if(edges[i][j]!=0){
edgel[index++]=new Edge(vList.get(i), vList.get(j), edges[i][j]);
}
}
}
return edgel;
}
//按照权值从小到大排列
public void sortEdges(Edge[] edgel,int elen){
for(int i=0;i<elen;i++){
for(int j=i+1;j<elen;j++){
if(edgel[i].weight>edgel[j].weight){
//交换
Edge temp=edgel[i];
edgel[i]=edgel[j];
edgel[j]=temp;
}
}
}
}
//获取节点i的通路的终点
public int getEnd(int[] ends,int i){
while(ends[i]!=0) i=ends[i];
return i;
}
该算法实现很简单,主要在于如何判断环路是否存在
package com.fredal.structure;
import com.fredal.structure.MyGraphy.Edge;
public class Kruskal {
public static void kruskal(MyGraphy a){
int index=0;
int num=a.getNumOfEdges()/2;
int[] ends=new int[num];
Edge[] res=new Edge[num];//结果数组
Edge[] edges=a.getEgdes();//图对应的所有边
a.sortEdges(edges, num);
for(int i=0;i<num;i++){
int p1=a.getPosition(edges[i].from);//第i条边的起点
int p2=a.getPosition(edges[i].to);//第i条边的终点
int m=a.getEnd(ends, p1);
int n=a.getEnd(ends, p2);
if(m!=n){//意味着通路的终点不一样,即没有形成环路
ends[m]=n;//设置m的通路的终点为n
res[index++]=edges[i];//保存结果
}
}
//打印最小生成树
int sum=0;
for(int i=0;i<index;i++){
sum+=res[i].weight;
}
System.out.println("kruskal:");
System.out.println("weight:"+sum);
System.out.println("path:");
for(int i=0;i<index;i++){
System.out.println(res[i].from+"-"+res[i].to);
}
}
public static void main(String[] args) {
String labels[]={"A","B","C","D","E","F","G"};//结点的标识
MyGraphy g=new MyGraphy(7);
for(String label:labels) {
g.insertVertext(label);//插入结点
}
g.insertEdge(0, 1, 12);
g.insertEdge(0, 5, 16);
g.insertEdge(0, 6, 14);
g.insertEdge(1, 0, 12);
g.insertEdge(1, 2, 10);
g.insertEdge(1, 5, 7);
g.insertEdge(2, 1, 10);
g.insertEdge(2, 3, 3);
g.insertEdge(2, 4, 5);
g.insertEdge(2, 5, 6);
g.insertEdge(3, 2, 3);
g.insertEdge(3, 4, 4);
g.insertEdge(4, 2, 5);
g.insertEdge(4, 3, 4);
g.insertEdge(4, 5, 2);
g.insertEdge(4, 6, 8);
g.insertEdge(5, 0, 16);
g.insertEdge(5, 1, 7);
g.insertEdge(5, 2, 6);
g.insertEdge(5, 4, 2);
g.insertEdge(5, 6, 9);
g.insertEdge(6, 0, 14);
g.insertEdge(6, 4, 8);
g.insertEdge(6, 5, 9);
kruskal(g);
}
}
更多文章与相关下载请看扩展阅读
