圖的概念
圖是一種非線性的數(shù)據(jù)結(jié)構(gòu),一個(gè)圖中有兩類東西，一種是結(jié)點(diǎn)，一種是邊.我們用V這個(gè)集合來表示節(jié)點(diǎn)（vertex），還需要另一個(gè)集合來存儲(chǔ)所有的邊，我們用E來表示(Edge)，那么一個(gè)圖就可以表示為：G=(V,E);
帶箭頭的稱為有向圖,否則稱為無向圖.
如果一個(gè)圖的任意兩個(gè)結(jié)點(diǎn)之間有且只有一條邊，則稱此圖為無向完全圖，若任意兩個(gè)結(jié)點(diǎn)之間有且只有方向相反的兩條邊，則稱為有向完全圖.
度是針對(duì)結(jié)點(diǎn)來說的， 又分為出度和入度,對(duì)于有向圖來說，出度就是指以這個(gè)結(jié)點(diǎn)為起始的邊的條數(shù)（箭頭向外），入度則是以這個(gè)點(diǎn)為終點(diǎn)的邊的條數(shù)（箭頭向內(nèi)）.
權(quán)是指一條邊所附帶的數(shù)據(jù)信息，比如說一個(gè)結(jié)點(diǎn)到另一個(gè)結(jié)點(diǎn)的距離，或者花費(fèi)的時(shí)間等等都可以用權(quán)來表示。
圖的存儲(chǔ)結(jié)構(gòu)
存儲(chǔ)一個(gè)圖可以采用鄰接矩陣或者鄰接表.
一個(gè)無向圖的鄰接矩陣如下:
1
它消耗的空間為Θ|V|2,適合圖很稠密的時(shí)候.
同樣的無向圖用鄰接表表示如下
2
消耗的空間為O(|E|+|V|).適合圖稀疏的時(shí)候.
先來用代碼實(shí)現(xiàn)有向圖鄰接矩陣的圖模型,無向圖差不多的不寫了,根據(jù)下圖來實(shí)現(xiàn):
3
package com.fredal.structure;
import java.util.ArrayList;
public class MyGraphy {
private ArrayList vList;//用來存節(jié)點(diǎn)
private int[][] edges;//鄰接矩陣 用來存儲(chǔ)邊
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é)點(diǎn)個(gè)數(shù)
public int getNumOfVertex(){
return vList.size();
}
//得到邊的個(gè)數(shù)
public int getNumOfEdges(){
return numOfEdges;
}
//返回節(jié)點(diǎn)i的值
public Object get(int i){
return vList.get(i);
}
//返回v1,v2節(jié)點(diǎn)之間邊的權(quán)值
public int getWeight(int v1,int v2){
return edges[v1][v2];
}
//插入節(jié)點(diǎn)
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é)點(diǎn)
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--;
}
//得到第一個(gè)鄰接節(jié)點(diǎn)的下標(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ù)前一個(gè)鄰接節(jié)點(diǎn)的下標(biāo)來取得下一個(gè)鄰接節(jié)點(diǎn)
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é)點(diǎn)的標(biāo)識(shí)
MyGraphy g=new MyGraphy(4);
for(String label:labels) {
g.insertVertext(label);//插入結(jié)點(diǎn)
}
g.insertEdge(0, 1, 2);
g.insertEdge(0, 2, 5);
g.insertEdge(2, 3, 8);
g.insertEdge(3, 0, 7);
System.out.println("結(jié)點(diǎn)個(gè)數(shù)是："+g.getNumOfVertex());
System.out.println("邊的個(gè)數(shù)是："+g.getNumOfEdges());
g.deleteEdge(0, 1);//刪除<V1,V2>邊
System.out.println("刪除<V1,V2>邊后...");
System.out.println("結(jié)點(diǎn)個(gè)數(shù)是："+g.getNumOfVertex());
System.out.println("邊的個(gè)數(shù)是："+g.getNumOfEdges());
}
}
接下來我們用鄰接表來實(shí)現(xiàn)圖的存儲(chǔ),同樣是前面那張圖
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;//頂點(diǎn)的名稱
private int vvalue;//定點(diǎn)的額值
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é)點(diǎn)的值
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;//存儲(chǔ)節(jié)點(diǎn)
private int numOfEdges;//邊的條數(shù)
public MyGraphyL(int n){
//初始化鄰接表
vertexs=new ArrayList<Vertex>(n);
numOfEdges=0;
}
public List<Vertex> getVertexs() {
return vertexs;
}
//得到節(jié)點(diǎn)個(gè)數(shù)
public int getNumOfVertex(){
return vertexs.size();
}
//得到邊的個(gè)數(shù)
public int getNumOfEdges(){
return numOfEdges;
}
//返回節(jié)點(diǎn)i的值
public Object get(int i){
Vertex vertex = vertexs.get(i);
if(vertex!=null){
return vertex.value;
}
return null;
}
//返回v1,v2節(jié)點(diǎn)之間邊的權(quán)值
public int getWeight(int v1,int v2){
Node search = search(v1, v2);
if(search!=null) return search.weight;
else return -1;
}
//搜索邊節(jié)點(diǎn)
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é)點(diǎn)
public void insertVertext(Object value,int vvalue){
Vertex vertex=new Vertex(value,vvalue);
vertexs.add(vertex);
}
//插入邊節(jié)點(diǎn)
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é)點(diǎn)
public void deleteVertex(int vvalue){
vertexs.remove(vvalue);
}
//刪除邊節(jié)點(diǎn)
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é)點(diǎn)的第一個(gè)邊節(jié)點(diǎn)的下標(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ù)前一個(gè)邊節(jié)點(diǎn)的下標(biāo)來取得下一個(gè)邊節(jié)點(diǎn)
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("沒有下一個(gè)");
}
}
}
return -1;
}
//測試程序
public static void main(String args[]) {
int i=0;
int n=4,e=4;//分別代表結(jié)點(diǎn)個(gè)數(shù)和邊的數(shù)目
String labels[]={"V1","V2","V3","V4"};//結(jié)點(diǎn)的標(biāo)識(shí)
MyGraphyL graph=new MyGraphyL(n);
for(String label:labels) {
graph.insertVertext(label, i);//插入結(jié)點(diǎn)
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é)點(diǎn)個(gè)數(shù)是："+graph.getNumOfVertex());
System.out.println("邊的個(gè)數(shù)是："+graph.getNumOfEdges());
// graph.deleteEdge(0, 1);//刪除<V1,V2>邊
// System.out.println("刪除<V1,V2>邊后...");
// System.out.println("結(jié)點(diǎn)個(gè)數(shù)是："+graph.getNumOfVertex());
// System.out.println("邊的個(gè)數(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)先遍歷,就是首先訪問第一個(gè)鄰接結(jié) 點(diǎn)，然后再以這個(gè)被訪問的鄰接結(jié)點(diǎn)作為初始結(jié)點(diǎn)，訪問它 的第一個(gè)鄰接結(jié)點(diǎn)。總結(jié)起來可以這樣說：每次都在訪問完當(dāng)前結(jié)點(diǎn)后首先訪問當(dāng)前結(jié)點(diǎn)的第一個(gè)鄰接結(jié)點(diǎn)。
如下圖,深度優(yōu)先遍歷的順序?yàn)?code>1->2->4->8->5->3->6->7
4
我們先用鄰接矩陣的形式實(shí)現(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é)點(diǎn)的標(biāo)識(shí)
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);
}
}
用鄰接表實(shí)現(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é)點(diǎn)的標(biāo)識(shí)
MyGraphyL a=new MyGraphyL(8);
int i=0;
for(String label:labels) {
a.insertVertext(label, i);//插入結(jié)點(diǎn)
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é)點(diǎn)開始，沿著樹的寬度遍歷樹的節(jié)點(diǎn)。如果所有節(jié)點(diǎn)均被訪問，則算法中止。
上圖按廣度優(yōu)先遍歷的順序應(yīng)為:1->2->3->4->5->6->7->8
同樣采用上面的圖先使用鄰接矩陣進(jìn)行模擬
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é)點(diǎn)的標(biāo)識(shí)
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);
}
}
用鄰接表實(shí)現(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é)點(diǎn)的標(biāo)識(shí)
MyGraphyL a=new MyGraphyL(8);
int i=0;
for(String label:labels) {
a.insertVertext(label, i);//插入結(jié)點(diǎn)
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ù)渑判?是一種對(duì)于關(guān)聯(lián)性的排序,可以參考維基百科的解釋:
在圖論中，由一個(gè)有向無環(huán)圖的頂點(diǎn)組成的序列，當(dāng)且僅當(dāng)滿足下列條件時(shí)，稱為該圖的一個(gè)拓?fù)渑判颍═opological sorting）。
a. 每個(gè)頂點(diǎn)出現(xiàn)且只出現(xiàn)一次；
b. 若A在序列中排在B的前面，則在圖中不存在從B到A的路徑。
也可以定義為：拓?fù)渑判蚴菍?duì)有向無環(huán)圖的頂點(diǎn)的一種排序，它使得如果存在一條從頂點(diǎn)A到頂點(diǎn)B的路徑，那么在排序中B出現(xiàn)在A的后面
我們根據(jù)下圖進(jìn)行排序
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;//輔助隊(duì)列
int num=a.getNumOfVertex();//頂點(diǎn)個(gè)數(shù)
int index=0;
ins=new int[num];
tops=new int[num];
queue=new LinkedList<Integer>();
//統(tǒng)計(jì)每個(gè)頂點(diǎn)的入度數(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的頂點(diǎn)入隊(duì)列
for(int i=0;i<num;i++){
if(ins[i]==0) queue.offer(i);//入隊(duì)列
}
while(!queue.isEmpty()){
int j=queue.poll().intValue();//出隊(duì)列 j是頂點(diǎn)序號(hào) 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("有個(gè)環(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é)點(diǎn)的標(biāo)識(shí)
MyGraphyL a=new MyGraphyL(8);
int i=0;
for(String label:labels) {
a.insertVertext(label, i);//插入結(jié)點(diǎn)
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)進(jìn)行拓?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é)束時(shí)壓入棧中
}
public static void main(String[] args) {
String labels[]={"1","2","3","4","5","6","7"};//結(jié)點(diǎn)的標(biāo)識(shí)
MyGraphyL a=new MyGraphyL(8);
int i=0;
for(String label:labels) {
a.insertVertext(label, i);//插入結(jié)點(diǎn)
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ū)別,但是仍然是對(duì)的排序結(jié)果.
這有關(guān)到解的唯一性問題,有哈密頓路徑的圖,即每一對(duì)頂點(diǎn)都能確定向后關(guān)系的圖的解是唯一的.
至于如何確定有唯一解呢,最簡單的想法是把每一對(duì)頂點(diǎn)兩兩比較看看有無先后關(guān)系,但是這樣很低效,我們可以用類似插入排序的算法進(jìn)行判斷.詳細(xì)的以后再講.
最短路徑問題(Dijkstra&Floyd)
最短路徑問題,先講單源最短路徑,就是求從指定頂點(diǎn)出發(fā)到其他各點(diǎn)的最短距離.經(jīng)典的算法有(Dijkstra)算法.
我們根據(jù)下圖來模擬該算法:
6
public class Dijstra {
public static void dijstra(MyGraphyL a,int k){
Map map=new HashMap();//存儲(chǔ)節(jié)點(diǎn)號(hào)--最小路徑值
List<Vertex> vertexs = a.getVertexs();
while(true){
int min=Integer.MAX_VALUE;
int min_no=-1;
Vertex first = vertexs.get(k);//獲得初始節(jié)點(diǎn)
Iterator<Node> iterator = first.elist.iterator();
while(iterator.hasNext()){
Node node = iterator.next();
//選出路徑最短的節(jié)點(diǎn)
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é)點(diǎn)
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é)點(diǎn)自身的權(quán)值加上下一個(gè)節(jié)點(diǎn)的權(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é)點(diǎn)的標(biāo)識(shí)
MyGraphyL a=new MyGraphyL(5);
int i=0;
for(String label:labels) {
a.insertVertext(label, i);//插入結(jié)點(diǎn)
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
對(duì)于最短路徑問題,還有著名的算法,Floyd算法,比起單源,它對(duì)于任意兩點(diǎn)間的最短路徑問題計(jì)算更方便.
通過Floyd計(jì)算圖G=(V,E)中各個(gè)頂點(diǎn)的最短路徑時(shí)，需要引入一個(gè)矩陣S，矩陣S中的元素a[i][j]表示頂點(diǎn)i(第i個(gè)頂點(diǎn))到頂點(diǎn)j(第j個(gè)頂點(diǎn))的距離。
基本思想:
假設(shè)圖G中頂點(diǎn)個(gè)數(shù)為N，則需要對(duì)矩陣S進(jìn)行N次更新。初始時(shí)，矩陣S中頂點(diǎn)a[i][j]的距離為頂點(diǎn)i到頂點(diǎn)j的權(quán)值；如果i和j不相鄰，則a[i][j]=∞。 接下來開始，對(duì)矩陣S進(jìn)行N次更新。第1次更新時(shí)，如果"a[i][j]的距離" > "a[i][0]+a[0][j]"(a[i][0]+a[0][j]表示"i與j之間經(jīng)過第1個(gè)頂點(diǎn)的距離")，則更新a[i][j]為"a[i][0]+a[0][j]"。 同理，第k次更新時(shí)，如果"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表示 頂點(diǎn)i到頂點(diǎn)j的最短路徑經(jīng)過k
// dis[i][j]=s表示 頂點(diǎn)i到頂點(diǎn)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來存儲(chǔ)具體的路徑
// 初始化
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);
}
}
}
// 計(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的頂點(diǎn)路徑比原來兩點(diǎn)間的路徑更短,則更新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存儲(chǔ)
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é)點(diǎn)的標(biāo)識(shí)
MyGraphy a = new MyGraphy(5);
for (String label : labels) {
a.insertVertext(label);// 插入結(jié)點(diǎn)
}
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);
}
}
運(yùn)行結(jié)果為:
7
最小生成樹(Prim&Kruskal)
最小生成樹問題,在含有n個(gè)頂點(diǎn)的連通圖中選擇n-1條邊，構(gòu)成一棵極小連通子圖，并使該連通子圖中n-1條邊上權(quán)值之和達(dá)到最小，則稱其為連通網(wǎng)的最小生成樹。
普里姆(Prim)算法，是用來求加權(quán)連通圖的最小生成樹的算法。
基本思想為從一個(gè)起點(diǎn)開始,選取連接這個(gè)點(diǎn)的所有邊中權(quán)值最小的那條邊,然后把邊的終點(diǎn)當(dāng)成新的起點(diǎn),繼續(xù)選取權(quán)值最小的邊,直到把所有頂點(diǎn)都選了一遍..
8
對(duì)于上圖而言,采用Prim算法生成最小生成樹的步驟為:
初始狀態(tài)：V是所有頂點(diǎn)的集合，即V={A,B,C,D,E,F,G}；U和T都是空！
第1步：將頂點(diǎn)A加入到U中。
此時(shí)，U={A}。
第2步：將頂點(diǎn)B加入到U中。
上一步操作之后，U={A}, V-U={B,C,D,E,F,G}；因此，邊(A,B)的權(quán)值最小。將頂點(diǎn)B添加到U中；此時(shí)，U={A,B}。
第3步：將頂點(diǎn)F加入到U中。
上一步操作之后，U={A,B}, V-U={C,D,E,F,G}；因此，邊(B,F)的權(quán)值最小。將頂點(diǎn)F添加到U中；此時(shí)，U={A,B,F}。
第4步：將頂點(diǎn)E加入到U中。
上一步操作之后，U={A,B,F}, V-U={C,D,E,G}；因此，邊(F,E)的權(quán)值最小。將頂點(diǎn)E添加到U中；此時(shí)，U={A,B,F,E}。
第5步：將頂點(diǎn)D加入到U中。
上一步操作之后，U={A,B,F,E}, V-U={C,D,G}；因此，邊(E,D)的權(quán)值最小。將頂點(diǎn)D添加到U中；此時(shí)，U={A,B,F,E,D}。
第6步：將頂點(diǎn)C加入到U中。
上一步操作之后，U={A,B,F,E,D}, V-U={C,G}；因此，邊(D,C)的權(quán)值最小。將頂點(diǎn)C添加到U中；此時(shí)，U={A,B,F,E,D,C}。
第7步：將頂點(diǎn)G加入到U中。
上一步操作之后，U={A,B,F,E,D,C}, V-U={G}；因此，邊(G,E)的權(quán)值最小。將頂點(diǎn)G添加到U中；此時(shí)，U=V。
此時(shí)，最小生成樹構(gòu)造完成！它包括的頂點(diǎn)依次是：A B F E D C G,權(quán)值為36。
我們采用代碼模擬該步驟,基于鄰接矩陣:
首先我們要在之前寫的MyGraohy類中加一個(gè)方法
//返回頂點(diǎn)在的位置
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();//頂點(diǎn)個(gè)數(shù)
int[][] edges = a.getEdges();
int index=0;//數(shù)組的索引
String[] prims=new String[num];//結(jié)果數(shù)組
int[] weight=new int[num];//頂點(diǎn)邊的權(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樹中第一個(gè)數(shù)是"圖中第start個(gè)頂點(diǎn)"
prims[index++]= (String) a.get(start);
//將每個(gè)頂點(diǎn)的權(quán)值初始化為"第start個(gè)頂點(diǎn)"到"該定點(diǎn)"的權(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)值最小的頂點(diǎn)
if(weight[j]!=0&&weight[j]<min){
min =weight[j];
k=j;
}
j++;
}
//經(jīng)過上面的處理 權(quán)值最小的頂點(diǎn)是第k個(gè)頂點(diǎn),將第k個(gè)頂點(diǎn)加入到最小生成樹的結(jié)果數(shù)組中
prims[index++]=(String) a.get(k);
//將第k個(gè)節(jié)點(diǎn)的權(quán)值標(biāo)記為0 意味著第k個(gè)頂點(diǎn)已經(jīng)排序了
weight[k]=0;
//更新下一輪節(jié)點(diǎn)的權(quán)值
for(j=0;j<num;j++){
if(weight[j]!=0&&edges[k][j]<weight[j]){
weight[j]=edges[k][j];
}
}
}
//計(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é)點(diǎn)的標(biāo)識(shí)
MyGraphy g=new MyGraphy(7);
for(String label:labels) {
g.insertVertext(label);//插入結(jié)點(diǎn)
}
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)會(huì)和已有的邊構(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)會(huì)和已有的邊構(gòu)成回路；因此，跳過邊(F,G)。同理，跳過邊(B,C)。將邊(A,B)加入到最小生成樹結(jié)果R中。
此時(shí)，最小生成樹構(gòu)造完成！它包括的邊依次是：(E,F) (C,D) (D,E) (B,F) (E,G) (A,B)。
我們還是選擇基于鄰接表實(shí)現(xiàn)該算法
首先為了方便,我們還往MyGraph類中增加一個(gè)內(nèi)部類和三個(gè)方法,方便邊的排序
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é)點(diǎn)i的通路的終點(diǎn)
public int getEnd(int[] ends,int i){
while(ends[i]!=0) i=ends[i];
return i;
}
該算法實(shí)現(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();//圖對(duì)應(yīng)的所有邊
a.sortEdges(edges, num);
for(int i=0;i<num;i++){
int p1=a.getPosition(edges[i].from);//第i條邊的起點(diǎn)
int p2=a.getPosition(edges[i].to);//第i條邊的終點(diǎn)
int m=a.getEnd(ends, p1);
int n=a.getEnd(ends, p2);
if(m!=n){//意味著通路的終點(diǎn)不一樣,即沒有形成環(huán)路
ends[m]=n;//設(shè)置m的通路的終點(diǎn)為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é)點(diǎn)的標(biāo)識(shí)
MyGraphy g=new MyGraphy(7);
for(String label:labels) {
g.insertVertext(label);//插入結(jié)點(diǎn)
}
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)下載請(qǐng)看擴(kuò)展閱讀
