圖的概念
圖是一種非線性的數(shù)據(jù)結(jié)構(gòu),一個圖中有兩類東西，一種是結(jié)點盯串，一種是邊.我們用V這個集合來表示節(jié)點（vertex）啡彬，還需要另一個集合來存儲所有的邊，我們用E來表示(Edge)娩嚼，那么一個圖就可以表示為：G=(V,E);
帶箭頭的稱為有向圖,否則稱為無向圖.
如果一個圖的任意兩個結(jié)點之間有且只有一條邊，則稱此圖為無向完全圖滴肿，若任意兩個結(jié)點之間有且只有方向相反的兩條邊岳悟，則稱為有向完全圖.
度是針對結(jié)點來說的， 又分為出度和入度,對于有向圖來說，出度就是指以這個結(jié)點為起始的邊的條數(shù)（箭頭向外），入度則是以這個點為終點的邊的條數(shù)（箭頭向內(nèi)）.
權(quán)是指一條邊所附帶的數(shù)據(jù)信息峻呕，比如說一個結(jié)點到另一個結(jié)點的距離，或者花費的時間等等都可以用權(quán)來表示滔灶。
圖的存儲結(jié)構(gòu)
存儲一個圖可以采用鄰接矩陣或者鄰接表.
一個無向圖的鄰接矩陣如下:
1
它消耗的空間為Θ|V|2,適合圖很稠密的時候.
同樣的無向圖用鄰接表表示如下
2
消耗的空間為O(|E|+|V|).適合圖稀疏的時候.
先來用代碼實現(xiàn)有向圖鄰接矩陣的圖模型,無向圖差不多的不寫了,根據(jù)下圖來實現(xiàn):
3
package com.fredal.structure;
import java.util.ArrayList;
public class MyGraphy {
private ArrayList vList;//用來存節(jié)點
private int[][] edges;//鄰接矩陣 用來存儲邊
private int numOfEdges;//邊的條數(shù)
public MyGraphy(int n){
//初始化矩陣
edges=new int[n][n];
vList=new ArrayList(n);
numOfEdges=0;
}
public int[][] getEdges() {
return edges;
}
//得到節(jié)點個數(shù)
public int getNumOfVertex(){
return vList.size();
}
//得到邊的個數(shù)
public int getNumOfEdges(){
return numOfEdges;
}
//返回節(jié)點i的值
public Object get(int i){
return vList.get(i);
}
//返回v1,v2節(jié)點之間邊的權(quán)值
public int getWeight(int v1,int v2){
return edges[v1][v2];
}
//插入節(jié)點
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++;
}
//刪除節(jié)點
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--;
}
//得到第一個鄰接節(jié)點的下標(biāo)
public int getFirstneighbor(int i){
for(int j=0;j<vList.size();j++){
if(edges[i][j]>0){
return j;
}
}
return -1;
}
//根據(jù)前一個鄰接節(jié)點的下標(biāo)來取得下一個鄰接節(jié)點
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"};//結(jié)點的標(biāo)識
MyGraphy g=new MyGraphy(4);
for(String label:labels) {
g.insertVertext(label);//插入結(jié)點
}
g.insertEdge(0, 1, 2);
g.insertEdge(0, 2, 5);
g.insertEdge(2, 3, 8);
g.insertEdge(3, 0, 7);
System.out.println("結(jié)點個數(shù)是："+g.getNumOfVertex());
System.out.println("邊的個數(shù)是："+g.getNumOfEdges());
g.deleteEdge(0, 1);//刪除<V1,V2>邊
System.out.println("刪除<V1,V2>邊后...");
System.out.println("結(jié)點個數(shù)是："+g.getNumOfVertex());
System.out.println("邊的個數(shù)是："+g.getNumOfEdges());
}
}
接下來我們用鄰接表來實現(xiàn)圖的存儲,同樣是前面那張圖
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;//邊的節(jié)點的值
private int weight;//權(quán)重
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;//存儲節(jié)點
private int numOfEdges;//邊的條數(shù)
public MyGraphyL(int n){
//初始化鄰接表
vertexs=new ArrayList<Vertex>(n);
numOfEdges=0;
}
public List<Vertex> getVertexs() {
return vertexs;
}
//得到節(jié)點個數(shù)
public int getNumOfVertex(){
return vertexs.size();
}
//得到邊的個數(shù)
public int getNumOfEdges(){
return numOfEdges;
}
//返回節(jié)點i的值
public Object get(int i){
Vertex vertex = vertexs.get(i);
if(vertex!=null){
return vertex.value;
}
return null;
}
//返回v1,v2節(jié)點之間邊的權(quán)值
public int getWeight(int v1,int v2){
Node search = search(v1, v2);
if(search!=null) return search.weight;
else return -1;
}
//搜索邊節(jié)點
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;
}
//插入節(jié)點
public void insertVertext(Object value,int vvalue){
Vertex vertex=new Vertex(value,vvalue);
vertexs.add(vertex);
}
//插入邊節(jié)點
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++;
}
//刪除節(jié)點
public void deleteVertex(int vvalue){
vertexs.remove(vvalue);
}
//刪除邊節(jié)點
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--;
}
//得到節(jié)點的第一個邊節(jié)點的下標(biāo)
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;
}
//根據(jù)前一個邊節(jié)點的下標(biāo)來取得下一個邊節(jié)點
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;//分別代表結(jié)點個數(shù)和邊的數(shù)目
String labels[]={"V1","V2","V3","V4"};//結(jié)點的標(biāo)識
MyGraphyL graph=new MyGraphyL(n);
for(String label:labels) {
graph.insertVertext(label, i);//插入結(jié)點
i++;
}
//插入四條邊
graph.insertEdge(0, 1, 2);
graph.insertEdge(0, 2, 5);
graph.insertEdge(2, 3, 8);
graph.insertEdge(3, 0, 7);
System.out.println("結(jié)點個數(shù)是："+graph.getNumOfVertex());
System.out.println("邊的個數(shù)是："+graph.getNumOfEdges());
// graph.deleteEdge(0, 1);//刪除<V1,V2>邊
// System.out.println("刪除<V1,V2>邊后...");
// System.out.println("結(jié)點個數(shù)是："+graph.getNumOfVertex());
// System.out.println("邊的個數(shù)是："+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);
}
}
}
}
深度優(yōu)先遍歷與廣度優(yōu)先遍歷
-
深度優(yōu)先遍歷
所謂深度優(yōu)先遍歷,就是首先訪問第一個鄰接結(jié) 點，然后再以這個被訪問的鄰接結(jié)點作為初始結(jié)點吼肥，訪問它 的第一個鄰接結(jié)點录平。總結(jié)起來可以這樣說：每次都在訪問完當(dāng)前結(jié)點后首先訪問當(dāng)前結(jié)點的第一個鄰接結(jié)點缀皱。
如下圖,深度優(yōu)先遍歷的順序為1->2->4->8->5->3->6->7
4
我們先用鄰接矩陣的形式實現(xiàn)上圖的深度優(yōu)先遍歷,圖結(jié)構(gòu)采用上面自己寫的
package com.fredal.structure;
public class DeepTravel {
//深度優(yōu)先遍歷 參數(shù)為要遍歷的圖,訪問過的標(biāo)記以及從哪開始遍歷
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"};//結(jié)點的標(biāo)識
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);
}
}
用鄰接表實現(xiàn)深度優(yōu)先遍歷并沒有多大區(qū)別:
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"};//結(jié)點的標(biāo)識
MyGraphyL a=new MyGraphyL(8);
int i=0;
for(String label:labels) {
a.insertVertext(label, i);//插入結(jié)點
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);
}
}
-
廣度優(yōu)先遍歷
廣度優(yōu)先遍歷(BFS)從根節(jié)點開始斗这，沿著樹的寬度遍歷樹的節(jié)點。如果所有節(jié)點均被訪問啤斗，則算法中止表箭。
上圖按廣度優(yōu)先遍歷的順序應(yīng)為: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();
//遍歷當(dāng)前層
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"};//結(jié)點的標(biāo)識
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);
}
}
用鄰接表實現(xiàn)廣度遍歷基本沒區(qū)別
public class WidthTravel {
public static void widthTravelL(MyGraphyL a,Set visited,List layer){
List<Vertex> vertexs = a.getVertexs();
//遍歷當(dāng)前層
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"};//結(jié)點的標(biāo)識
MyGraphyL a=new MyGraphyL(8);
int i=0;
for(String label:labels) {
a.insertVertext(label, i);//插入結(jié)點
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);
}
}
拓?fù)渑判?kahn&DFS)
關(guān)于拓?fù)渑判?是一種對于關(guān)聯(lián)性的排序,可以參考維基百科的解釋:
在圖論中，由一個有向無環(huán)圖的頂點組成的序列争占，當(dāng)且僅當(dāng)滿足下列條件時燃逻，稱為該圖的一個拓?fù)渑判颍═opological sorting）。
a. 每個頂點出現(xiàn)且只出現(xiàn)一次臂痕；
b. 若A在序列中排在B的前面伯襟，則在圖中不存在從B到A的路徑。
也可以定義為：拓?fù)渑判蚴菍τ邢驘o環(huán)圖的頂點的一種排序握童，它使得如果存在一條從頂點A到頂點B的路徑姆怪，那么在排序中B出現(xiàn)在A的后面
我們根據(jù)下圖進行排序
5
首先來最簡單的和自然的kahn算法,得出的結(jié)果應(yīng)該是
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;//入度數(shù)組
int [] tops;//拓?fù)渑判虻慕Y(jié)果數(shù)組
Queue<Integer> queue;//輔助隊列
int num=a.getNumOfVertex();//頂點個數(shù)
int index=0;
ins=new int[num];
tops=new int[num];
queue=new LinkedList<Integer>();
//統(tǒng)計每個頂點的入度數(shù)
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("有個環(huán)");
return;
}
//輸出排序結(jié)果
System.out.print("拓?fù)渑判? ");
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"};//結(jié)點的標(biāo)識
MyGraphyL a=new MyGraphyL(8);
int i=0;
for(String label:labels) {
a.insertVertext(label, i);//插入結(jié)點
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);
}
}
除了上面那種算法我們還可以基于深度優(yōu)先遍歷(DFS)進行拓?fù)渑判?同樣基于鄰接表,首先保證圖是有向無環(huán)圖
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++){//循環(huán)調(diào)用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方法快結(jié)束時壓入棧中
}
public static void main(String[] args) {
String labels[]={"1","2","3","4","5","6","7"};//結(jié)點的標(biāo)識
MyGraphyL a=new MyGraphyL(8);
int i=0;
for(String label:labels) {
a.insertVertext(label, i);//插入結(jié)點
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());
}
}
}
這種算法得出得到排序結(jié)果為5->1->6->4->2->7->3,與上面的有些區(qū)別,但是仍然是對的排序結(jié)果.
這有關(guān)到解的唯一性問題,有哈密頓路徑的圖,即每一對頂點都能確定向后關(guān)系的圖的解是唯一的.
至于如何確定有唯一解呢,最簡單的想法是把每一對頂點兩兩比較看看有無先后關(guān)系,但是這樣很低效,我們可以用類似插入排序的算法進行判斷.詳細的以后再講.
最短路徑問題(Dijkstra&Floyd)
最短路徑問題,先講單源最短路徑,就是求從指定頂點出發(fā)到其他各點的最短距離.經(jīng)典的算法有(Dijkstra)算法.
我們根據(jù)下圖來模擬該算法:
6
public class Dijstra {
public static void dijstra(MyGraphyL a,int k){
Map map=new HashMap();//存儲節(jié)點號--最小路徑值
List<Vertex> vertexs = a.getVertexs();
while(true){
int min=Integer.MAX_VALUE;
int min_no=-1;
Vertex first = vertexs.get(k);//獲得初始節(jié)點
Iterator<Node> iterator = first.elist.iterator();
while(iterator.hasNext()){
Node node = iterator.next();
//選出路徑最短的節(jié)點
if(map.get(node.getEvalue())==null&&node.getWeight()<min){
min_no=node.getEvalue();
min=node.getWeight();
}
}
Iterator it = map.keySet().iterator();
while(it.hasNext()){
//取出集合中存在的最短路徑節(jié)點
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();
//將集合中的節(jié)點自身的權(quán)值加上下一個節(jié)點的權(quán)值與外面非集合中的權(quán)值比較 取最小值 循環(huán)
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"};//結(jié)點的標(biāo)識
MyGraphyL a=new MyGraphyL(5);
int i=0;
for(String label:labels) {
a.insertVertext(label, i);//插入結(jié)點
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);
}
}
模擬結(jié)果為:
從0出發(fā)到1的最短路徑為：0-->1
從0出發(fā)到2的最短路徑為：0-->3-->2
從0出發(fā)到3的最短路徑為：0-->3
從0出發(fā)到4的最短路徑為：0-->3-->2-->4
從0出 發(fā)到1的最短距離為：10
從0出 發(fā)到2的最短距離為：50
從0出 發(fā)到3的最短距離為：30
從0出 發(fā)到4的最短距離為：60
對于最短路徑問題,還有著名的算法,Floyd算法,比起單源,它對于任意兩點間的最短路徑問題計算更方便.
通過Floyd計算圖G=(V,E)中各個頂點的最短路徑時，需要引入一個矩陣S澡绩，矩陣S中的元素a[i][j]表示頂點i(第i個頂點)到頂點j(第j個頂點)的距離稽揭。
基本思想:
假設(shè)圖G中頂點個數(shù)為N，則需要對矩陣S進行N次更新肥卡。初始時溪掀，矩陣S中頂點a[i][j]的距離為頂點i到頂點j的權(quán)值；如果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之間經(jīng)過第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的最短路徑經(jīng)過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++) {
// 如果經(jīng)過下標(biāo)為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" };// 結(jié)點的標(biāo)識
MyGraphy a = new MyGraphy(5);
for (String label : labels) {
a.insertVertext(label);// 插入結(jié)點
}
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);
}
}
運行結(jié)果為:
7
最小生成樹(Prim&Kruskal)
最小生成樹問題,在含有n個頂點的連通圖中選擇n-1條邊藐石，構(gòu)成一棵極小連通子圖，并使該連通子圖中n-1條邊上權(quán)值之和達到最小定拟，則稱其為連通網(wǎng)的最小生成樹于微。
普里姆(Prim)算法，是用來求加權(quán)連通圖的最小生成樹的算法青自。
基本思想為從一個起點開始,選取連接這個點的所有邊中權(quán)值最小的那條邊,然后把邊的終點當(dāng)成新的起點,繼續(xù)選取權(quán)值最小的邊,直到把所有頂點都選了一遍..
8
對于上圖而言,采用Prim算法生成最小生成樹的步驟為:
初始狀態(tài)：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)的權(quán)值最小吻育。將頂點B添加到U中；此時淤井，U={A,B}布疼。
第3步：將頂點F加入到U中。
上一步操作之后币狠，U={A,B}, V-U={C,D,E,F,G}游两；因此，邊(B,F)的權(quán)值最小漩绵。將頂點F添加到U中贱案；此時，U={A,B,F}渐行。
第4步：將頂點E加入到U中轰坊。
上一步操作之后，U={A,B,F}, V-U={C,D,E,G}祟印；因此肴沫，邊(F,E)的權(quán)值最小。將頂點E添加到U中蕴忆；此時颤芬，U={A,B,F,E}。
第5步：將頂點D加入到U中套鹅。
上一步操作之后站蝠，U={A,B,F,E}, V-U={C,D,G}；因此卓鹿，邊(E,D)的權(quán)值最小菱魔。將頂點D添加到U中；此時吟孙，U={A,B,F,E,D}澜倦。
第6步：將頂點C加入到U中。
上一步操作之后杰妓，U={A,B,F,E,D}, V-U={C,G}藻治；因此，邊(D,C)的權(quán)值最小巷挥。將頂點C添加到U中桩卵；此時，U={A,B,F,E,D,C}。
第7步：將頂點G加入到U中雏节。
上一步操作之后胜嗓，U={A,B,F,E,D,C}, V-U={G}；因此钩乍，邊(G,E)的權(quán)值最小兼蕊。將頂點G添加到U中；此時件蚕，U=V。
此時产禾，最小生成樹構(gòu)造完成排作！它包括的頂點依次是：A B F E D C G,權(quán)值為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();//頂點個數(shù)
int[][] edges = a.getEdges();
int index=0;//數(shù)組的索引
String[] prims=new String[num];//結(jié)果數(shù)組
int[] weight=new int[num];//頂點邊的權(quán)值
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樹中第一個數(shù)是"圖中第start個頂點"
prims[index++]= (String) a.get(start);
//將每個頂點的權(quán)值初始化為"第start個頂點"到"該定點"的權(quán)值
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){
//找到權(quán)值最小的頂點
if(weight[j]!=0&&weight[j]<min){
min =weight[j];
k=j;
}
j++;
}
//經(jīng)過上面的處理 權(quán)值最小的頂點是第k個頂點,將第k個頂點加入到最小生成樹的結(jié)果數(shù)組中
prims[index++]=(String) a.get(k);
//將第k個節(jié)點的權(quán)值標(biāo)記為0 意味著第k個頂點已經(jīng)排序了
weight[k]=0;
//更新下一輪節(jié)點的權(quán)值
for(j=0;j<num;j++){
if(weight[j]!=0&&edges[k][j]<weight[j]){
weight[j]=edges[k][j];
}
}
}
//計算最小生成樹的權(quán)值
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"};//結(jié)點的標(biāo)識
MyGraphy g=new MyGraphy(7);
for(String label:labels) {
g.insertVertext(label);//插入結(jié)點
}
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算法,基本思想是按照權(quán)值從小到大排列所有的邊,依次選取并且保證不構(gòu)成回路.
同樣根據(jù)上面的圖作為基礎(chǔ),步驟為:
第1步：將邊(E,F)加入R中亚情。
邊(E,F)的權(quán)值最小妄痪，因此將它加入到最小生成樹結(jié)果R中。
第2步：將邊(C,D)加入R中楞件。
上一步操作之后衫生，邊(C,D)的權(quán)值最小，因此將它加入到最小生成樹結(jié)果R中土浸。
第3步：將邊(D,E)加入R中罪针。
上一步操作之后，邊(D,E)的權(quán)值最小黄伊，因此將它加入到最小生成樹結(jié)果R中泪酱。
第4步：將邊(B,F)加入R中。
上一步操作之后还最，邊(C,E)的權(quán)值最小墓阀，但(C,E)會和已有的邊構(gòu)成回路；因此拓轻，跳過邊(C,E)斯撮。同理，跳過邊(C,F)扶叉。將邊(B,F)加入到最小生成樹結(jié)果R中勿锅。
第5步：將邊(E,G)加入R中。
上一步操作之后辜梳，邊(E,G)的權(quán)值最小粱甫，因此將它加入到最小生成樹結(jié)果R中。
第6步：將邊(A,B)加入R中作瞄。
上一步操作之后茶宵，邊(F,G)的權(quán)值最小，但(F,G)會和已有的邊構(gòu)成回路宗挥；因此乌庶，跳過邊(F,G)种蝶。同理，跳過邊(B,C)瞒大。將邊(A,B)加入到最小生成樹結(jié)果R中螃征。
此時，最小生成樹構(gòu)造完成透敌！它包括的邊依次是：(E,F) (C,D) (D,E) (B,F) (E,G) (A,B)盯滚。
我們還是選擇基于鄰接表實現(xiàn)該算法
首先為了方便,我們還往MyGraph類中增加一個內(nèi)部類和三個方法,方便邊的排序
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;
}
//按照權(quán)值從小到大排列
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;
}
}
}
}
//獲取節(jié)點i的通路的終點
public int getEnd(int[] ends,int i){
while(ends[i]!=0) i=ends[i];
return i;
}
該算法實現(xiàn)很簡單,主要在于如何判斷環(huán)路是否存在
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];//結(jié)果數(shù)組
Edge[] edges=a.getEgdes();//圖對應(yīng)的所有邊
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){//意味著通路的終點不一樣,即沒有形成環(huán)路
ends[m]=n;//設(shè)置m的通路的終點為n
res[index++]=edges[i];//保存結(jié)果
}
}
//打印最小生成樹
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"};//結(jié)點的標(biāo)識
MyGraphy g=new MyGraphy(7);
for(String label:labels) {
g.insertVertext(label);//插入結(jié)點
}
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);
}
}
更多文章與相關(guān)下載請看擴展閱讀
