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

圖(Graph)的數(shù)學(xué)定義G=(V,E,)V：頂點(diǎn)(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ù)結(jié)構(gòu)課的定義G=(V,E)V：頂點(diǎn)的集合例如，V={A,B,C,D}E：邊的集合例如，E={<A,B>,<B,C>,<C,D>,<D,B>}有向圖、無(wú)向圖EACBDBCAFEDdirectedgraphundirectedgraphACDFEB鄰接點(diǎn)(adjacentvertex)、度(degree)EACBDin-degreeout-degree子圖(subgraph)EACBDCBD沒(méi)有嚴(yán)格的定義，一般指：稠密圖：|E|=Θ(|V|2)稀疏圖：非稠密圖，或者|E|<<|V|2(遠(yuǎn)遠(yuǎn)小于)稀疏圖(sparsegraph)、稠密圖(densegraph)路徑(path)和路徑長(zhǎng)度(pathlength)A->B->C->DA->E->C->DEACBD簡(jiǎn)單路徑(simplepath)A->B->C->D√A->E->C->D->B->C->DEACBDBACDFE連通圖(connectedgraph)a、連通圖BACDFEb、非連通圖強(qiáng)連通圖(stronglyconnectedgraph)a、強(qiáng)連通圖b、非強(qiáng)連通圖ABECDABECDBACDFEBACDFE生成樹(shù)(spanningtree)圖的規(guī)模兩個(gè)參數(shù)：V、E有向圖：|E|≤|V|*(|V|-1)=O(|V|2)無(wú)向圖：|E|≤(|V|*(|V|-1))/2=O(|V|2)圖的基本內(nèi)容本章的主要內(nèi)容：圖的存儲(chǔ)圖的遍歷及應(yīng)用有向圖的拓?fù)渑判騿?wèn)題帶權(quán)有向圖的最短路徑問(wèn)題帶權(quán)無(wú)向圖的最小生成樹(shù)問(wèn)題圖的存儲(chǔ)G=(V,E)V：頂點(diǎn)的集合。例如，V={A,B,C,D}E：邊的集合。例如，E={<A,B>,<B,C>,<C,D>,<D,B>,<D,A>}兩種觀點(diǎn)：把E視為頂點(diǎn)之間的關(guān)系，則存儲(chǔ)V和V上的關(guān)系(即E)把V和E視為2個(gè)集合，則分別存儲(chǔ)V和E，再存儲(chǔ)V和E之間的鄰接關(guān)系無(wú)向圖-鄰接矩陣(adjacencymatrix)BACDFEABCDEFABCDEF010010100011000101001001110000011100012345012345010010100011000101001001110000011100012345ABCDEF無(wú)向圖-鄰接表(adjacencylist)鄰接表：使用線性表存儲(chǔ)鄰接點(diǎn)01234514043525011253BACDFE鏈表中的數(shù)字是頂點(diǎn)的編號(hào)。1條邊存了2次012345ABCDEFlist:鏈表無(wú)向圖-鄰接多重表(adjacencymultilist)例aecbd^^^^^1234acdb5e121434323552課堂練習(xí)V1V2V3V4V51、鄰接矩陣2、鄰接表3、鄰接多重表ABECD有向圖-鄰接矩陣ABCDEABCDE010010010000010110000010001234ABCDEABECD012341430122有向圖-鄰接表01234ABCDEABECD320030123414有向圖-逆鄰接表(inverseadjacencylist)01234ABCDE有向圖-十字鏈表ABCABC∧0121∧02∧

∧20∧

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

enumGraphKind{

UnDirectedGraph,

DirectedGraph,

WeightedUnDirectedGraph,

WeightedDirectedGraph}圖的接口public

interfaceIGraph<T>{

publicGraphKindgetGraphKind();//圖的類型

public

intnumberOfVertices();//頂點(diǎn)的個(gè)數(shù)

public

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

public

intindex(Tx);//值等于x的頂點(diǎn)編號(hào)，-1，表示沒(méi)找到

publicTvalue(int

v);//編號(hào)為v的頂點(diǎn)的值

public

intinDegree(int

v);//有向圖的編號(hào)為v的頂點(diǎn)的入度

public

intoutDegree(int

v);//有向圖的編號(hào)為v的頂點(diǎn)的出度

public

intdegree(int

v);//無(wú)向圖的編號(hào)為v的頂點(diǎn)的度

public

booleanaddEdge(int

u,int

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

public

booleanremoveEdge(int

u,int

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

public

voidaddWeightedEdge(int

u,int

v,double

w);//設(shè)置邊<u,v>的權(quán)重

public

doublegetWeight(int

u,int

v);//獲取邊<u,v>的權(quán)重

publicIterator<Integer>iterator(int

v);//用于迭代訪問(wèn)頂點(diǎn)v的鄰接點(diǎn)}基于鄰接矩陣的有向圖實(shí)現(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]; }基于鄰接矩陣的有向圖實(shí)現(xiàn)

publicGraphKindgetGraphKind(){

return

graghKind; }

private

voidrangeCheck(int

v){

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

throw

newIndexOutOfBoundsException(); }

public

intnumberOfVertices(){

return

n; }

public

intnumberOfEdges(){

return

e; }基于鄰接矩陣的有向圖實(shí)現(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]; }基于鄰接矩陣的有向圖實(shí)現(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基于鄰接矩陣的有向圖實(shí)現(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基于鄰接矩陣的有向圖實(shí)現(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基于鄰接矩陣的有向圖實(shí)現(xiàn)

public

voidaddWeightedEdge(int

u,int

v,double

w){

throw

newUnsupportedOperationException(); }

public

doublegetWeight(int

u,int

v){

throw

newUnsupportedOperationException(); }基于鄰接矩陣的有向圖實(shí)現(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基于鄰接矩陣的有向圖實(shí)現(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基于鄰接矩陣的有向圖實(shí)現(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基于鄰接表的有向圖實(shí)現(xiàn)012341430122public

classLinkedListDirectedGraph<T>implementsIGraph<T>{

public

final

staticGraphKindgraghKind=GraphKind.DirectedGraph;

privateObject[]vertices;

privateObject[]edges;//數(shù)組+鏈表

private

int

e;

private

final

int

n;

publicLinkedListDirectedGraph(T[]data){

n=data.length;

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

edges=newObject[n];

for(int

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

edges[i]=new

LinkedList<Integer>(); }ABECD基于鄰接表的有向圖實(shí)現(xiàn)

public

intinDegree(int

v){ rangeCheck(v);

int

count=0;

for(int

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

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

return

count; }

public

intoutDegree(int

v){ rangeCheck(v);

int

count=((List<?>)edges[v]).size();

return

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

public

booleanaddEdge(int

u,int

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

@SuppressWarnings("unchecked") List<Integer>list=(List<Integer>)edges[u];

if(list.indexOf(v)==-1){

list.add(v); ++e;

return

true; }

return

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

public

booleanremoveEdge(int

u,int

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

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

return

true; }

return

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

public

booleanremoveEdge2(int

u,int

v){//效率高，代碼行數(shù)多 rangeCheck(u); rangeCheck(v);

@SuppressWarnings("unchecked") Iterator<Integer>itr=((List<Integer>)edges[u]).iterator();

while(itr.hasNext()){

int

w=itr.next();

if(w==v){

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

return

true; } }

return

false; }ABECD基于鄰接表的有向圖實(shí)現(xiàn)012341430122//indexOf和remove各遍歷了一次LinkedList，效率低

public

booleanremoveEdge3(int

u,int

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

@SuppressWarnings("unchecked") List<Integer>list=(List<Integer>)edges[u];

int

w=list.indexOf(v);//O(n)

if(w!=-1){

list.remove(w);//O(n) --e;

return

true; }

return

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

@SuppressWarnings("unchecked")

publicIterator<Integer>iterator(int

v){ rangeCheck(v);

return((List<Integer>)edges[v]).iterator();//使用List實(shí)現(xiàn)的迭代器 }012341430122ABECD總結(jié)1、使用鄰接矩陣，inDegree、outDegree、index是O(|V|)，addEdge和removeEdge是O(1)。2、使用鄰接表，inDegree是O(|E|)、outDegree、index是O(|V|)addEdge和removeEdge是O(|V|)。3、給出的代碼沒(méi)有實(shí)用價(jià)值，只用于體會(huì)如何實(shí)現(xiàn)復(fù)雜的數(shù)據(jù)結(jié)構(gòu)。因?yàn)槭褂庙旤c(diǎn)在數(shù)組的下標(biāo)作為頂點(diǎn)的編號(hào)，不利于增加和刪除頂點(diǎn)。帶權(quán)重有向圖-鄰接矩陣ABECD9876543ABCDEABCDE9876543如何表示2個(gè)頂點(diǎn)之間沒(méi)有邊？如果使用泛型，因?yàn)楸仨氁阅硞€(gè)引用類型參數(shù)化，所以可以使用null表示無(wú)邊如果使用基本類型，必須以某個(gè)特定值表示無(wú)邊。基于鄰接矩陣的帶權(quán)重有向圖實(shí)現(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;//這里讓標(biāo)簽(權(quán)重)為double

private

int

e;

private

final

int

n;

publicAjacencyMatrixWeightedDirectedGraph(T[]data){

//也可以把noEdge的值作為1個(gè)參數(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); }基于鄰接矩陣的帶權(quán)重有向圖實(shí)現(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; }基于鄰接矩陣的帶權(quán)重有向圖實(shí)現(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)有的邊，認(rèn)為是修改權(quán)重 }

public

doublegetWeight(int

u,int

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

return

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

private

static

classPair{

int

vertex;

double

weight;

Pair(int

u,double

w){

vertex=u;

weight=w; }

public

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

if(o

instanceofPair){

return

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

return

false; } }public

classLinkedListWeightedDirectedGraph<T>implementsIGraph<T>{

public

final

staticGraphKindgraghKind=GraphKind.WeightedDirectedGraph;

public

final

static

double

noEdge=Double.POSITIVE_INFINITY;

privateObject[]vertices;

privateArrayList<LinkedList<Pair>>edges;//表套表

private

int

e;

private

final

int

n;

publicLinkedListWeightedDirectedGraph(T[]data){

n=data.length;

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

edges=newArrayList<>(n);

for(int

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

edges.add(newLinkedList<>()); }012341,94,83,60,51,42,32,7基于鄰接表的帶權(quán)重有向圖實(shí)現(xiàn)

public

voidaddWeightedEdge(int

u,int

v,double

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

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

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

pair.weight=w;

return; } }

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

public

doublegetWeight(int

u,int

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

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

if(pair.vertex==v)

return

pair.weight; }

returnnoEdge;

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

public

booleanremoveEdge(int

u,int

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

if(edges.get(u).remove(newPair(v,0))){ --e;

return

true; }

return

false; }基于鄰接表的帶權(quán)重有向圖實(shí)現(xiàn)無(wú)向圖的實(shí)現(xiàn)01234514043525011253BACDFE1條邊存了2次，當(dāng)然，也可以1條邊只存1次，怎么存？addEdge(1,0)、addEdge(0,1)removeEdge(1,0)、removeEdge(0,1)ABCDEFABCDEF010010100011000101001001110000011100無(wú)向圖-鄰接矩陣BACDFE012345ABCDEF對(duì)稱矩陣，只存儲(chǔ)、使用下三角部分ABCDEFABCDEF010010100011000101001001110000011100基于鄰接矩陣的無(wú)向圖實(shí)現(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ù)組的大小等于頂點(diǎn)編號(hào)+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基于鄰接矩陣的無(wú)向圖實(shí)現(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; }基于鄰接矩陣的無(wú)向圖實(shí)現(xiàn)基于鄰接矩陣的無(wú)向圖實(shí)現(xiàn)ABCDEFABCDEF010010100011000101001001110000011100

public

booleanremoveEdge(int

u,int

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

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

v=v^u;

u=v^u;

v=v^u; }

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

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

return

true; }

return

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

public

booleanhasNext(){

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

if(edges[vertex