《数据结构》 (java版) 课件 6-1图的基本概念与邻接表和矩阵实现的实现10-27

图(Graph)的数学定义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>)}图的数据结构课的定义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)图的规模两个参数：V、E有向图：|E|≤|V|*(|V|-1)=O(|V|2)无向图：|E|≤(|V|*(|V|-1))/2=O(|V|2)图的基本内容本章的主要内容：图的存储图的遍历及应用有向图的拓扑排序问题带权有向图的最短路径问题带权无向图的最小生成树问题图的存储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链表中的数字是顶点的编号。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|)无论是邻接矩阵还是邻接表，边都使用了顶点的下标(引用)：简单、易行改变了顶点的编号必须改变邻接矩阵和邻接表也可以考虑其它的数据结构：例如Map等图的类型public

enumGraphKind{

UnDirectedGraph,

DirectedGraph,

WeightedUnDirectedGraph,

WeightedDirectedGraph}图的接口public

interfaceIGraph<T>{

publicGraphKindgetGraphKind();//图的类型

public

intnumberOfVertices();//顶点的个数

public

intnumberOfEdges();//边数

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的邻接点}基于邻接矩阵的有向图实现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]; }基于邻接矩阵的有向图实现

publicGraphKindgetGraphKind(){

return

graghKind; }

private

voidrangeCheck(int

v){

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

throw

newIndexOutOfBoundsException(); }

public

intnumberOfVertices(){

return

n; }

public

intnumberOfEdges(){

return

e; }基于邻接矩阵的有向图实现

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]; }基于邻接矩阵的有向图实现

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基于邻接矩阵的有向图实现

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基于邻接矩阵的有向图实现

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基于邻接矩阵的有向图实现

public

voidaddWeightedEdge(int

u,int

v,double

w){

throw

newUnsupportedOperationException(); }

public

doublegetWeight(int

u,int

v){

throw

newUnsupportedOperationException(); }基于邻接矩阵的有向图实现

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基于邻接矩阵的有向图实现

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基于邻接矩阵的有向图实现

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基于邻接表的有向图实现012341430122public

classLinkedListDirectedGraph2<T>implementsIGraph<T>{

public

final

staticGraphKindgraghKind=GraphKind.DirectedGraph;

privateObject[]vertices;

privateList<Integer>[]edges;//线性表数组，比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);

//创建数组时必须使用具体类型。List<?>是具体类型，而List<Integer>不是

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

for(int

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

edges[i]=newLinkedList<>(); }ABECD基于邻接表的有向图实现

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基于邻接表的有向图实现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; }基于邻接表的有向图实现012341430122

public

booleanremoveEdge(int

u,int

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

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

return

true; }

return

false; }ABECD基于邻接表的有向图实现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基于邻接表的有向图实现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基于邻接表的有向图实现

publicIterator<Integer>iterator(int

v){ rangeCheck(v);

return

edges[v].iterator();//使用List实现的迭代器 }012341430122ABECD总结1、使用邻接矩阵，inDegree、outDegree、index是O(|V|)，addEdge和removeEdge是O(1)。2、使用邻接表，inDegree是O(|E|)、outDegree、index是O(|V|)addEdge和removeEdge是O(|V|)。3、给出的代码没有实用价值，只用于体会如何实现复杂的数据结构。因为使用顶点在数组的下标作为顶点的编号，不利于增加和删除顶点。带权重有向图-邻接矩阵ABECD9876543ABCDEABCDE9876543如何表示2个顶点之间没有边？如果使用泛型，因为必须以某个引用类型参数化，所以可以使用null表示无边如果使用基本类型，必须以某个特定值表示无边。基于邻接矩阵的带权重有向图实现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个参数

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); }基于邻接矩阵的带权重有向图实现

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; }基于邻接矩阵的带权重有向图实现

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;//已经有的边，认为是修改权重 }

public

doublegetWeight(int

u,int

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

return

edges[u][v]; }基于邻接表的带权重有向图实现01234ABCDEABECD9876543012341,94,83,60,51,42,32,7基于邻接表的带权重有向图实现

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;//使用数组

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<>(); }基于邻接表的带权重有向图实现

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基于邻接表的带权重有向图实现

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基于邻接表的带权重有向图实现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; }基于邻接表的带权重有向图实现无向图的实现01234514043525011253BACDFE1条边存了2次，当然，也可以1条边只存1次，怎么存？addEdge(1,0)、addEdge(0,1)addEdge(1,0)、removeEdge(0,1)ABCDEFABCDEF010010100011000101001001110000011100无向图-邻接矩阵BACDFE012345ABCDEF对称矩阵，只存储、使用下三角部分ABCDEFABCDEF010010100011000101001001110000011100基于邻接矩阵的无向图实现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];//注意：数组的大小等于顶点编号+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基于邻接矩阵的无向图实现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; }基于邻接矩阵的无向图实现基于邻接矩阵的无向图实现ABCDEFABCDEF010010100011000101001001110000011100

public

booleanremoveEdge(int

u,int

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

if(v>u){//保证u>v,交换2个整数的另外的写法

v=v^u;

u=v^u;

v=v^u; }

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

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

return

true; }

return

false; }基于邻接矩阵的无向图实现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、很多书把图作为一种数据结构介绍2、也有这样的考题：逻辑数据结构有哪几种？答：线性表、树、图、集合个人观点：前面已经学习了线性表、栈、队列、二叉树、树，知道了如何表达数据之间的关系(结构)：数组、引用(即顺序和链式)讨论更一般的关系也是使用数组和引用描述因此，以图为例，探讨各种合适的数据结构：邻接矩阵邻接表多重链表十字链表...ABECDABCDEABCDE010010010000010110000010001234ABCDE0100101234ABCDE00100000101100000100有向图-邻接矩阵->Node//拆分邻接矩阵，将顶点数组和邻接数组合并到Node数组，使用数组表示邻接关系public

classNodeDirectedGraph2<T>implementsIGraph<T>{

public

final

staticGraphKindgraghKind=GraphKind.DirectedGraph;

privateNode<?>[]graph;

private

int

e;//边的条数

private

final

int

n;//顶点的个数

private

static

classNode<T>{ Tvertex;//顶点

int[]to;//邻接点 Node(Tnode,int

count){

vertex=node;

to=new

int[count]; } }有向图-邻接矩阵->NodeABECD012341430122有向图-邻接表->Node01234ABCDE143012201234ABCDE//将顶点数组和邻接表合并到Node数组，使用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泛型数组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.顶点异构树的每个顶点的子树个数不一样，如何设计结构？树的链式存储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<>(); }}