《數(shù)據(jù)結構》 (java版) 課件 6-1圖的基本概念與鄰接表和矩陣實現(xiàn)的實現(xiàn)10-27

圖(Graph)的數(shù)學定義G=(V,E,)V：頂點(vertex、node)的集合例如，V={A,B,C,D}E：邊(edge、arc)的集合例如，E={e1,e2,e3,e4}：E{<v1,v2>|v1,v2V}例如：={(e1,<A,B>),(e2,<B,C>),(e3,<C,D>),(e4,<D,B>)}圖的數(shù)據(jù)結構課的定義G=(V,E)V：頂點的集合例如，V={A,B,C,D}E：邊的集合例如，E={<A,B>,<B,C>,<C,D>,<D,B>}有向圖、無向圖EACBDBCAFEDdirectedgraphundirectedgraphACDFEB鄰接點(adjacentvertex)、度(degree)EACBDin-degreeout-degree子圖(subgraph)EACBDCBD沒有嚴格的定義，一般指：稠密圖：|E|=Θ(|V|2)稀疏圖：非稠密圖，或者|E|<<|V|2(遠遠小于)稀疏圖(sparsegraph)、稠密圖(densegraph)路徑(path)和路徑長度(pathlength)A->B->C->DA->E->C->DEACBD簡單路徑(simplepath)A->B->C->D√A->E->C->D->B->C->DEACBDBACDFE連通圖(connectedgraph)a、連通圖BACDFEb、非連通圖強連通圖(stronglyconnectedgraph)a、強連通圖b、非強連通圖ABECDABECDBACDFEBACDFE生成樹(spanningtree)圖的規(guī)模兩個參數(shù)：V、E有向圖：|E|≤|V|*(|V|-1)=O(|V|2)無向圖：|E|≤(|V|*(|V|-1))/2=O(|V|2)圖的基本內(nèi)容本章的主要內(nèi)容：圖的存儲圖的遍歷及應用有向圖的拓撲排序問題帶權有向圖的最短路徑問題帶權無向圖的最小生成樹問題圖的存儲G=(V,E)V：頂點的集合。例如，V={A,B,C,D}E：邊的集合。例如，E={<A,B>,<B,C>,<C,D>,<D,B>,<D,A>}兩種觀點：把E視為頂點之間的關系，則存儲V和V上的關系(即E)把V和E視為2個集合，則分別存儲V和E，再存儲V和E之間的鄰接關系無向圖-鄰接矩陣(adjacencymatrix)BACDFEABCDEFABCDEF010010100011000101001001110000011100012345012345010010100011000101001001110000011100012345ABCDEF無向圖-鄰接表(adjacencylist)鄰接表：使用線性表存儲鄰接點01234514043525011253BACDFE鏈表中的數(shù)字是頂點的編號。1條邊存了2次012345ABCDEFlist:鏈表無向圖-鄰接多重表(adjacencymultilist)例aecbd^^^^^1234acdb5e121434323552課堂練習V1V2V3V4V51、鄰接矩陣2、鄰接表3、鄰接多重表ABECD有向圖-鄰接矩陣ABCDEABCDE010010010000010110000010001234ABCDEABECD012341430122有向圖-鄰接表01234ABCDEABECD320030123414有向圖-逆鄰接表(inverseadjacencylist)01234ABCDE有向圖-十字鏈表ABCABC∧0121∧02∧

∧20∧

∧012V2V1V4V31、鄰接矩陣2、鄰接表3、十字鏈表課堂練習帶權重有向圖-鄰接矩陣ABECD9876543ABCDEABCDE987654301234ABCDE帶權重有向圖-鄰接表01234ABCDEABECD9876543012341,94,83,60,51,42,32,7總結鄰接矩陣比較適合稠密圖，空間復雜度O(|V|2)鄰接表比較適合稀疏圖，空間復雜度O(|V|+|E|)無論是鄰接矩陣還是鄰接表，邊都使用了頂點的下標(引用)：簡單、易行改變了頂點的編號必須改變鄰接矩陣和鄰接表也可以考慮其它的數(shù)據(jù)結構：例如Map等圖的類型public

enumGraphKind{

UnDirectedGraph,

DirectedGraph,

WeightedUnDirectedGraph,

WeightedDirectedGraph}圖的接口public

interfaceIGraph<T>{

publicGraphKindgetGraphKind();//圖的類型

public

intnumberOfVertices();//頂點的個數(shù)

public

intnumberOfEdges();//邊數(shù)

public

intindex(Tx);//值等于x的頂點編號，-1，表示沒找到

publicTvalue(int

v);//編號為v的頂點的值

public

intinDegree(int

v);//有向圖的編號為v的頂點的入度

public

intoutDegree(int

v);//有向圖的編號為v的頂點的出度

public

intdegree(int

v);//無向圖的編號為v的頂點的度

public

booleanaddEdge(int

u,int

v);//加入邊<u,v>

public

booleanremoveEdge(int

u,int

v);//刪除邊<u,v>

public

voidaddWeightedEdge(int

u,int

v,double

w);//設置邊<u,v>的權重

public

doublegetWeight(int

u,int

v);//獲取邊<u,v>的權重

publicIterator<Integer>iterator(int

v);//用于迭代訪問頂點v的鄰接點}基于鄰接矩陣的有向圖實現(xiàn)01234ABCDEABCDEABCDE0000000000000000000000000public

classAjacencyMatrixDirectedGraph<T>implementsIGraph<T>{

public

final

staticGraphKindgraghKind=GraphKind.DirectedGraph;

privateObject[]vertices;

private

int[][]edges;

private

int

e;

private

final

int

n;

publicAjacencyMatrixDirectedGraph(T[]data){

n=data.length;

vertices=newObject[n]; System.arraycopy(data,0,vertices,0,n);

edges=new

int[n][n]; }基于鄰接矩陣的有向圖實現(xiàn)

publicGraphKindgetGraphKind(){

return

graghKind; }

private

voidrangeCheck(int

v){

if(v<0||v>=n)

throw

newIndexOutOfBoundsException(); }

public

intnumberOfVertices(){

return

n; }

public

intnumberOfEdges(){

return

e; }基于鄰接矩陣的有向圖實現(xiàn)

public

intindex(Tx){

for(inti=0;i<n;i++){

if(vertices[i].equals(x)) returni; }

return-1; }

publicTvalue(int

v){ rangeCheck(v);

return

vertices[v]; }基于鄰接矩陣的有向圖實現(xiàn)

public

intinDegree(int

v){ rangeCheck(v);

int

count=0;

for(int

i=0;i<n;++i)

count+=edges[i][v];

return

count; }

public

intoutDegree(int

v){ rangeCheck(v);

int

count=0;

for(int

i=0;i<n;++i)

count+=edges[v][i];

return

count; }

public

intdegree(int

v){

throw

newUnsupportedOperationException(); }ABCDEABCDE0100100100000101100000100ABECD基于鄰接矩陣的有向圖實現(xiàn)

public

booleanaddEdge(int

u,int

v){ rangeCheck(u); rangeCheck(v);

if(edges[u][v]==0){

edges[u][v]=1; ++e;

return

true; }

return

false; }ABCDEABCDE0100100100000101100000100ABECD基于鄰接矩陣的有向圖實現(xiàn)

public

booleanremoveEdge(int

u,int

v){ rangeCheck(u); rangeCheck(v);

if(edges[u][v]!=0){

edges[u][v]=0; --e;

return

true; }

return

false; }ABCDEABCDE0100100100000101100000100ABECD基于鄰接矩陣的有向圖實現(xiàn)

public

voidaddWeightedEdge(int

u,int

v,double

w){

throw

newUnsupportedOperationException(); }

public

doublegetWeight(int

u,int

v){

throw

newUnsupportedOperationException(); }基于鄰接矩陣的有向圖實現(xiàn)

publicIterator<Integer>iterator(int

v){ rangeCheck(v);

return

newItr(v); }

private

classItrimplementsIterator<Integer>{

private

int

vertex;

private

int

curPos;

publicItr(int

v){

vertex=v; }

public

booleanhasNext(){

for(;curPos<n;curPos++){

if(edges[vertex][curPos]!=0)

break; }

return

curPos==n?false:true; }

publicIntegernext(){

return

curPos++; } }ABCDEABCDE0100100100000101100000100ABECD基于鄰接矩陣的有向圖實現(xiàn)

public

static

voidmain(String[]args){ Character[]data={'a','b','c','d','e','f'}; AjacencyMatrixDirectedGraph<Character>graph=newAjacencyMatrixDirectedGraph<>(data); System.out.println("nodes="+graph.numberOfVertices());

graph.addEdge(0,2);

graph.addEdge(1,2);

graph.addEdge(1,4);

graph.addEdge(1,5);

graph.addEdge(2,3);

graph.addEdge(3,5);

graph.addEdge(4,3);

graph.addEdge(4,5); System.out.println("edges="+graph.numberOfEdges()); System.out.println("outdegreeof1="+graph.outDegree(1)); System.out.println("indegreeof5="+graph.inDegree(5));nodes=6edges=8outdegreeof1=3indegreeof5=3基于鄰接矩陣的有向圖實現(xiàn)

graph.removeEdge(1,4); System.out.println(graph.numberOfEdges()); System.out.println("outdegreeof1="+graph.outDegree(1)); System.out.println("valueof4="+graph.value(4)); System.out.println("subscriptofc="+graph.index('c')); System.out.println("---------"); Iterator<Integer>it=graph.iterator(1);

while(it.hasNext()){ System.out.println(it.next()); } }7outdegreeof1=2valueof4=esubscriptofc=2---------25基于鄰接表的有向圖實現(xiàn)012341430122public

classLinkedListDirectedGraph2<T>implementsIGraph<T>{

public

final

staticGraphKindgraghKind=GraphKind.DirectedGraph;

privateObject[]vertices;

privateList<Integer>[]edges;//線性表數(shù)組，比Object[]edges更清晰一些

private

int

e;

private

final

int

n;

publicLinkedListDirectedGraph2(T[]data){

n=data.length;

vertices=newObject[n]; System.arraycopy(data,0,vertices,0,n);

//創(chuàng)建數(shù)組時必須使用具體類型。List<?>是具體類型，而List<Integer>不是

edges=(List<Integer>[])newList<?>[n];

for(int

i=0;i<n;i++)

edges[i]=newLinkedList<>(); }ABECD基于鄰接表的有向圖實現(xiàn)

public

intinDegree(int

v){ rangeCheck(v);

int

count=0;

for(int

u=0;u<n;u++){

if(edges[u].indexOf(v)!=-1) ++count; }

return

count; }

public

intoutDegree(int

v){ rangeCheck(v);

int

count=edges[v].size();

return

count; }012341430122ABECD基于鄰接表的有向圖實現(xiàn)012341430122ABECD

public

booleanaddEdge(int

u,int

v){ rangeCheck(u); rangeCheck(v);

if(edges[u].indexOf(v)==-1){//頂點u的鄰接點是否包含頂點v

edges[u].add(v);//將頂點v添加到頂點u的鄰接點鏈表 ++e;

return

true; }

return

false; }基于鄰接表的有向圖實現(xiàn)012341430122

public

booleanremoveEdge(int

u,int

v){ rangeCheck(u); rangeCheck(v);

if(edges[u].remove(Integer.valueOf(v))){ --e;

return

true; }

return

false; }ABECD基于鄰接表的有向圖實現(xiàn)012341430122

public

booleanremoveEdge2(int

u,int

v){//效率比較高，需要newiterator對象 rangeCheck(u); rangeCheck(v); Iterator<Integer>itr=edges[u].iterator();

while(itr.hasNext()){

int

w=itr.next();

if(w==v){

itr.remove();//利用迭代器的就地刪除 --e;

return

true; } }

return

false; }ABECD基于鄰接表的有向圖實現(xiàn)012341430122

//indexOf和remove各遍歷了一次LinkedList，效率低

public

booleanremoveEdge3(int

u,int

v){ rangeCheck(u); rangeCheck(v);

int

w=edges[u].indexOf(v);//O(n)

if(w!=-1){

edges[u].remove(w);//O(n) --e;

return

true; }

return

false; }ABECD基于鄰接表的有向圖實現(xiàn)

publicIterator<Integer>iterator(int

v){ rangeCheck(v);

return

edges[v].iterator();//使用List實現(xiàn)的迭代器 }012341430122ABECD總結1、使用鄰接矩陣，inDegree、outDegree、index是O(|V|)，addEdge和removeEdge是O(1)。2、使用鄰接表，inDegree是O(|E|)、outDegree、index是O(|V|)addEdge和removeEdge是O(|V|)。3、給出的代碼沒有實用價值，只用于體會如何實現(xiàn)復雜的數(shù)據(jù)結構。因為使用頂點在數(shù)組的下標作為頂點的編號，不利于增加和刪除頂點。帶權重有向圖-鄰接矩陣ABECD9876543ABCDEABCDE9876543如何表示2個頂點之間沒有邊？如果使用泛型，因為必須以某個引用類型參數(shù)化，所以可以使用null表示無邊如果使用基本類型，必須以某個特定值表示無邊。基于鄰接矩陣的帶權重有向圖實現(xiàn)public

classAjacencyMatrixWeightedDirectedGraph<T>implementsIGraph<T>{

public

final

staticGraphKindgraghKind=GraphKind.WeightedDirectedGraph;

public

final

static

double

noEdge=Double.POSITIVE_INFINITY;

privateObject[]vertices;

private

double[][]edges;//這里讓權重為double

private

int

e;

private

final

int

n;

publicAjacencyMatrixWeightedDirectedGraph(T[]data){

//也可以把noEdge的值作為1個參數(shù)

n=data.length;

vertices=newObject[n]; System.arraycopy(data,0,vertices,0,n);

edges=new

double[n][n];

for(int

i=0;i<n;++i) Arrays.fill(edges[i],noEdge); }基于鄰接矩陣的帶權重有向圖實現(xiàn)

public

booleanaddEdge(int

u,int

v){

throw

newUnsupportedOperationException(); }

public

booleanremoveEdge(int

u,int

v){ rangeCheck(u); rangeCheck(v);

if(edges[u][v]!=noEdge){

edges[u][v]=noEdge; --e;

return

true; }

return

false; }基于鄰接矩陣的帶權重有向圖實現(xiàn)

public

voidaddWeightedEdge(int

u,int

v,double

w){ rangeCheck(u); rangeCheck(v);

if(edges[u][v]==noEdge){

edges[u][v]=w; ++e;

return; }

edges[u][v]=w;//已經(jīng)有的邊，認為是修改權重 }

public

doublegetWeight(int

u,int

v){ rangeCheck(u); rangeCheck(v);

return

edges[u][v]; }基于鄰接表的帶權重有向圖實現(xiàn)01234ABCDEABECD9876543012341,94,83,60,51,42,32,7基于鄰接表的帶權重有向圖實現(xiàn)

private

static

classPair{

int

vertex;//鄰接點

double

weight;//權重 Pair(int

v,double

w){

vertex=v;

weight=w; } Pair(){ } PairsetNode(int

u){

vertex=u;

return

this; }

public

booleanequals(Objecto){//List的indexOf、remove要使用

if(o

instanceofPair)

return

this.vertex==((Pair)o).vertex;

return

false; } }public

classLinkedListWeightedDirectedGraph2<T>implementsIGraph<T>{

public

final

staticGraphKindgraghKind=GraphKind.WeightedDirectedGraph;

public

final

static

double

noEdge=Double.POSITIVE_INFINITY;

privateObject[]vertices;

privateLinkedList<Pair>[]edges;//使用數(shù)組

private

int

e;

private

final

int

n;

private

finalPairpair=newPair();//用于鏈表的indexOf和remove

publicLinkedListWeightedDirectedGraph2(T[]data){

n=data.length;

vertices=newObject[n]; System.arraycopy(data,0,vertices,0,n);

edges=(LinkedList<Pair>[])newLinkedList<?>[n];

for(int

i=0;i<n;i++)

edges[i]=newLinkedList<>(); }基于鄰接表的帶權重有向圖實現(xiàn)

public

voidaddWeightedEdge(int

u,int

v,double

w){ rangeCheck(u); rangeCheck(v); LinkedList<Pair>list=edges[u]; Iterator<Pair>it=list.iterator();

while(it.hasNext()){ Pairpair=it.next();

if(pair.vertex==v){//邊存在，認為修改

pair.weight=w;

return; } }

list.add(newPair(v,w)); ++e; }012341,94,83,60,51,42,32,7基于鄰接表的帶權重有向圖實現(xiàn)

public

doublegetWeight(int

u,int

v){ rangeCheck(u); rangeCheck(v); Iterator<Pair>it=edges[u].iterator();

while(it.hasNext()){ Pairpair=it.next();

if(pair.vertex==v)

return

pair.weight; }

return

noEdge;//無u->v的邊，用正無窮大表示 }012341,94,83,60,51,42,32,7基于鄰接表的帶權重有向圖實現(xiàn)012341,94,83,60,51,42,32,7

public

booleanremoveEdge(int

u,int

v){ rangeCheck(u); rangeCheck(v);

if(edges[u].remove(pair.setNode(v))){ --e;

return

true; }

return

false; }基于鄰接表的帶權重有向圖實現(xiàn)無向圖的實現(xiàn)01234514043525011253BACDFE1條邊存了2次，當然，也可以1條邊只存1次，怎么存？addEdge(1,0)、addEdge(0,1)addEdge(1,0)、removeEdge(0,1)ABCDEFABCDEF010010100011000101001001110000011100無向圖-鄰接矩陣BACDFE012345ABCDEF對稱矩陣，只存儲、使用下三角部分ABCDEFABCDEF010010100011000101001001110000011100基于鄰接矩陣的無向圖實現(xiàn)public

classAjacencyMatrixUnDirectedGraph<T>implementsIGraph<T>{

public

final

staticGraphKindgraghKind=GraphKind.UnDirectedGraph;

privateObject[]vertices;

private

int[][]edges;

private

int

e;

private

final

int

n;

publicAjacencyMatrixUnDirectedGraph(T[]data){

n=data.length;

vertices=newObject[n]; System.arraycopy(data,0,vertices,0,n);

edges=new

int[n][];//使用下三角形

for(int

i=0;i<n;i++)

edges[i]=new

int[i+1];//注意：數(shù)組的大小等于頂點編號+1 }

public

intdegree(int

v){ rangeCheck(v);

int

count=0;

int

i=0;

for(;i<=v;i++)

count+=edges[v][i];

for(;i<n;i++)

count+=edges[i][v];

return

count; }ABCDEFABCDEF010010100011000101001001110000011100基于鄰接矩陣的無向圖實現(xiàn)ABCDEFABCDEF010010100011000101001001110000011100

public

booleanaddEdge(int

u,int

v){ rangeCheck(u); rangeCheck(v);

if(v>u){//保證u>v

int

tmp=u;

u=v;

v=tmp; }

if(edges[u][v]==0){

edges[u][v]=1; ++e;

return

true; }

return

false; }基于鄰接矩陣的無向圖實現(xiàn)基于鄰接矩陣的無向圖實現(xiàn)ABCDEFABCDEF010010100011000101001001110000011100

public

booleanremoveEdge(int

u,int

v){ rangeCheck(u); rangeCheck(v);

if(v>u){//保證u>v,交換2個整數(shù)的另外的寫法

v=v^u;

u=v^u;

v=v^u; }

if(edges[u][v]!=0){

edges[u][v]=0; --e;

return

true; }

return

false; }基于鄰接矩陣的無向圖實現(xiàn)ABCDEFABCDEF010010100011000101001001110000011100

public

booleanhasNext(){

for(;curPos<=vertex;++curPos){

if(edges[vertex][curPos]!=0)

return

true; }

for(;curPos<n;++curPos){

if(edges[curPos][vertex]!=0)

break; }

return

curPos==n?false:true; }

publicIntegernext(){

return

curPos++; }討論1、很多書把圖作為一種數(shù)據(jù)結構介紹2、也有這樣的考題：邏輯數(shù)據(jù)結構有哪幾種？答：線性表、樹、圖、集合個人觀點：前面已經(jīng)學習了線性表、棧、隊列、二叉樹、樹，知道了如何表達數(shù)據(jù)之間的關系(結構)：數(shù)組、引用(即順序和鏈式)討論更一般的關系也是使用數(shù)組和引用描述因此，以圖為例，探討各種合適的數(shù)據(jù)結構：鄰接矩陣鄰接表多重鏈表十字鏈表...ABECDABCDEABCDE010010010000010110000010001234ABCDE0100101234ABCDE00100000101100000100有向圖-鄰接矩陣->Node//拆分鄰接矩陣，將頂點數(shù)組和鄰接數(shù)組合并到Node數(shù)組，使用數(shù)組表示鄰接關系public

classNodeDirectedGraph2<T>implementsIGraph<T>{

public

final

staticGraphKindgraghKind=GraphKind.DirectedGraph;

privateNode<?>[]graph;

private

int

e;//邊的條數(shù)

private

final

int

n;//頂點的個數(shù)

private

static

classNode<T>{ Tvertex;//頂點

int[]to;//鄰接點 Node(Tnode,int

count){

vertex=node;

to=new

int[count]; } }有向圖-鄰接矩陣->NodeABECD012341430122有向圖-鄰接表->Node01234ABCDE143012201234ABCDE//將頂點數(shù)組和鄰接表合并到Node數(shù)組，使用LinkedList表示鄰接關系public

classNodeDirectedGraph<T>implementsIGraph<T>{

public

final

staticGraphKindgraghKind=GraphKind.DirectedGraph;

privateNode<?>[]graph;

private

int

e;

private

final

int

n;

private

static

classNode<T>{ Tvertex;//頂點 List<Integer>to;//鄰接點 Node(Tnode){

vertex=node;

to=newLinkedList<>(); } }有向圖-鄰接表->Node泛型數(shù)組T[]=>Object[]Object[]a=newObject[10];//T[]a=(T[])Object[10];不再用這種形式Tb=(T)a[0];a[0]=new***();Node<T>[]=>Node<?>[]Node<?>[]a=newNode<?>[10];Tb=(T)a[0];a[0]=newNode<>(....);ABECD有向圖-鄰接表143012201234ABCDE1401234ABCDE23012適用的場合???樹的鏈式存儲a.頂點同構b.頂點異構樹的每個頂點的子樹個數(shù)不一樣，如何設計結構？樹的鏈式存儲public

classNode<T>{ Tdata; Node<?>[]subtrees=newNode<?>[5];

publicNode(Tdata){

this.data=data; }}樹的鏈式存儲public

classNode<T>{ Tdata; Node<?>[]subtrees;

publicNode(Tdata,int

n){

this.data=data;

subtrees=newNode<?>[n]; }}樹的鏈式存儲importjava.util.LinkedList;importjava.util.List;public

classNode<T>{ Tdata; List<Node<?>>subtrees;

publicNode(Tdata){

this.data=data;

subtrees=newLinkedList<>(); }}