存儲(chǔ)結(jié)構(gòu)
要存儲(chǔ)一個(gè)圖颂跨，我們知道圖既有結(jié)點(diǎn)秕脓，又有邊，對(duì)于有權(quán)圖來(lái)說(shuō)搓译，每條邊上還帶有權(quán)值。常用的圖的存儲(chǔ)結(jié)構(gòu)主要有以下二種：
- 鄰接矩陣
- 鄰接表
上一篇文章《圖的理解：存儲(chǔ)結(jié)構(gòu)與鄰接矩陣的Java實(shí)現(xiàn)》用的是鄰接矩陣的形式實(shí)現(xiàn)的锋喜，這次用鄰接表來(lái)存儲(chǔ)
30adcbef76094b36d054d85ba0cc7cd98c109d46.jpg
就如上圖所示侥衬，表頭節(jié)點(diǎn)表示源節(jié)點(diǎn)，后面跟的就是他能到達(dá)的節(jié)點(diǎn)，比如A,他能到達(dá)1,2,3節(jié)點(diǎn)轴总，而有向圖和無(wú)向圖最大的區(qū)別直颅，就是方向，無(wú)向圖A->B怀樟，也一定有B->A,在有向圖中就不一定功偿，這次介紹帶權(quán)重的有向圖的鄰接表表示。
首先要表示圖往堡，首先要定義圖的邊
//帶權(quán)重的有向圖
public class DirectedEdge {
private int v; //邊的起點(diǎn)
private int w; //邊的終點(diǎn)
private double weight;//邊的權(quán)重
public DirectedEdge(int v,int w,double weight){
this.v=v;
this.w=w;
this.weight=weight;
}
public int from(){
return v;
}
public int to(){
return w;
}
public double weight(){
return weight;
}
@Override
public String toString() {
return String.format("%d->%d% .2f",v,w,weight);
}
}
這里跟上圖表示的有點(diǎn)不一樣械荷，我把兩個(gè)頂點(diǎn)都保留下來(lái)啦，如果不需要權(quán)重虑灰，去掉weight就行
定義完圖的邊吨瞎，就需要定義圖
public class EdgeWeightDigraph {
public int v;//頂點(diǎn)的個(gè)數(shù)
public int e; //邊的個(gè)數(shù)
public ArrayList<DirectedEdge> [] adj; //鄰接表
public EdgeWeightDigraph(int v){
this.v=v;
this.e=e;
adj=new ArrayList[v];
for(int i=0;i<v;i++){
adj[i]=new ArrayList<DirectedEdge>();
}
}
/**
* 添加邊
* @param e
*/
public void addEdge(DirectedEdge e){
adj[e.from()].add(e);
this.e++;
}
public void printEdge(){
for(int i=0;i<v;i++){
for(DirectedEdge e:adj[i]){
System.out.println(e+" ");
}
}
}
public static void main(String[] args){
EdgeWeightDigraph graph=new EdgeWeightDigraph(5);
DirectedEdge e=new DirectedEdge(0,1,1);
DirectedEdge e1=new DirectedEdge(0,2,1);
DirectedEdge e2=new DirectedEdge(1,2,1);
DirectedEdge e3=new DirectedEdge(2,3,1);
DirectedEdge e4=new DirectedEdge(3,4,1);
graph.addEdge(e);
graph.addEdge(e1);
graph.addEdge(e2);
graph.addEdge(e3);
graph.addEdge(e4);
graph.printEdge();
}
}
這里我用list集合來(lái)表示鄰接表，添加邊時(shí)穆咐，e.from表示源邊颤诀，在它的集合里保存邊即可
控制臺(tái)輸出結(jié)果如下圖所示：
result.png
