图算法基础知识

图算法基础知识第一页，共二十九页，编辑于2023年，星期二图图

G=(V,E)V=顶点的非空有限集E=边集

=VV的子集，V中顶点对，边的有限集。|E|=O(|V|2)简单图(SampleGraph)

任意两个顶点最多只有一条边，且每个点都没有连接到自身的边。完全图(CompleteGrapth)

若有n个顶点的无向图n(n-1)/2条边，则此图为完全图。第二页，共二十九页，编辑于2023年，星期二图的扩展扩展:连通图（

connectedgraph）

从图中每一顶点都有到其它顶点的路径。无向图（

undirectedgraph）:边(u,v)=边

(v,u)有向图（directed

graph）:(u,v)表示从顶点u到顶点v的一条有向边,记为uv一个不含有环的有向图称为无环有向图(Directedacyclicgraphs

,DAG）。加权图（

weightedgraph）

图中不是边就是顶点与权关联，例如：公路交通图，边以距离w为权。第三页，共二十九页，编辑于2023年，星期二图通常用边数|E|和顶点数|V|描述运行时间。无向图中

0≤|E|≤|V|(|V|-1)/2有向图中

0≤|E|≤|V|(|V|-1)若|E||V|2

，图是稠密的

dense若

|E||V|，图是稀疏的

sparse对稠密图和稀疏图使用不同的数据结构第四页，共二十九页，编辑于2023年，星期二图的表示假设V={1,2,…,n}邻接矩阵（adjacencymatrix）

将图表示成一个

nxn

矩阵

A:A[i,j] =1若边

(i,j)E(或边的权wij)

=0若边

(i,j)E第五页，共二十九页，编辑于2023年，星期二图:邻接矩阵Example:1243A123410110200103000040010有向图非对称矩阵第六页，共二十九页，编辑于2023年，星期二图:邻接矩阵Example:1243adbcA1234123??4第七页，共二十九页，编辑于2023年，星期二图:邻接矩阵Example:1243adbcA123410ad0200b030000400c0第八页，共二十九页，编辑于2023年，星期二图:邻接矩阵Example:12435143A123410350200103000040040第九页，共二十九页，编辑于2023年，星期二图:邻接矩阵Example:1243adbcA123410ad02a0b03db0c400c0无向图对称矩阵第十页，共二十九页，编辑于2023年，星期二图:邻接矩阵邻接矩阵的实现

constmaxlength=100{最大顶点数}typegraph=array[1..maxlength,1..maxlength]ofinteger;

二维数组第十一页，共二十九页，编辑于2023年，星期二输入和查看一遍邻接矩阵需要多少时间？答:O(|V|2)存储一个邻接矩阵需要多少存储空间？答:O(|V|2)稀疏图（|E||V|或|E|<<|V|),邻接矩阵是稀疏矩阵，浪费空间，因此采用邻接表更有效。图:邻接矩阵第十二页，共二十九页，编辑于2023年，星期二图:邻接表邻接表:对每个顶点

vV,将v的所有邻接点存放在一个列表中。Example:Adj[1]={2,3}Adj[2]={3}Adj[3]={}Adj[4]={3}1243第十三页，共二十九页，编辑于2023年，星期二1243图:邻接表123nil23nil3nil43nil第十四页，共二十九页，编辑于2023年，星期二邻接表的实现Typepointer=↑adjnodeadjnode=record

adjvex:integer;{该点在图中的位置}

next:pointer;{指向下一个顶点的指针}

infor:…;{与边有关的信息，如权值w}Adjlist=array[1..maxlength]ofpointer;图:邻接表第十五页，共二十九页，编辑于2023年，星期二

无环有向图的拓扑排序

Directedacyclicgraphs(DAG)topologicalsort

DAG:不含回路的有向图称为无环有向图。

检查有向图中是否存在回路的方法之一，是对有向图进行拓扑排序。

如果有向图G有一个拓扑排序,则G是一个有向无环图.反之,任一有向无环图必可进行拓扑排序。第十六页，共二十九页，编辑于2023年，星期二何谓“拓扑排序”？

按照有向图给出的次序关系，将图中顶点排成一个线性序列，对于有向图中没有限定次序关系的顶点，则可以人为加上任意的次序关系。

由此所得顶点的线性序列称之为拓扑有序序列第十七页，共二十九页，编辑于2023年，星期二例如：对于下列有向图BDAC可求得拓扑有序序列：

ABCD

或

ACBD第十八页，共二十九页，编辑于2023年，星期二BDAC反之，对于下列有向图不能求得它的拓扑有序序列。因为图中存在一个回路

{B,C,D}第十九页，共二十九页，编辑于2023年，星期二如何进行拓扑排序？一、从有向图中选取一个没有前驱的顶点，并输出之;

重复上述两步，直至图空，或者图不空但找不到无前驱的顶点为止。二、从有向图中删去此顶点以及所有以它为尾的弧;第二十页，共二十九页，编辑于2023年，星期二abcghdfeabhcdgfe在算法中需要用定量的描述替代定性的概念

没有前驱的顶点入度为零的顶点删除顶点及以它为尾的弧弧头顶点的入度减1第二十一页，共二十九页，编辑于2023年，星期二拓扑排序算法Functiontopsort:boolean;P140vari,count:integer;wadj:Arr3;//用来表示图的邻接表表头数组

indeg:Arr1;//一维数组，存储每个顶点的入度

p:wpointer;//链表，邻接表

q:queue;//队列q保存入度为零且未被排序的顶点

begin//算法依次对q的出队元素进行编号

topsort:=true;count:=0;makenull(q);//清空队列qfillchar(indeg,sizeof(indeg),0);

//数组indeg存储每个顶点入度第二十二页，共二十九页，编辑于2023年，星期二//通过遍历邻接表，计算所有顶点的入度Fori:=1tondobeginp:=wadj[i];//顶点i的邻接表的第一个邻接点

whilep<>nildo//依次为顶点i的所有邻接点入度加1begininc(indeg[p^.v]);p:=p^.next;end;End;第二十三页，共二十九页，编辑于2023年，星期二//入度为0的顶点加入队列qFori:=1tondoifindeg[i]=0thenenqueue(i,q);//入队//队列q的队首顶点出队，与该顶点邻接的顶点的出度减1Whilenotempty(q)dobegini:=dequeue(q);inc(count);//计数器加1ord[i]:=count;//ord数组存储顶点i的排序后的序号

p:=wadj[i];

whilep<>nildo//该循环将顶点i的所有邻接点入度减1begindec(indeg[p^.v]);ifindeg[p^.v]=0thenenqueue(p^.v,q);p:=p^.next;endEnd第二十四页，共二十九页，编辑于2023年，星期二//入度为0的顶点数小于n时，存在环；

否则图不存在环，且可进行拓扑排序，ord数组存储的就是排序后的序号Ifcount<nthenbeginwriteln(‘graphiscyclic’);topsort:=false;end;End;第二十五页，共二十九页，编辑于2023年，星期二拓扑排序应用字母排序给定的一组字母，并在该组字母上定义偏序关系<，确定该组字母能否按此偏序关系升序排序。例如，有序序列A,B,C,D表示A<B,B<CandC<D.在该问题中，给出一形如A<B的关系集，并要求确定该序列是否有序。如果有序，输出这个序列，并输出是通过前多少关系得出的（即使之后的关系引出矛盾也不必理会）。如果存在矛盾，则输出前多少项出现的矛盾的。第二十六页，共二十九页，编辑于2023年，星期二具体思路：

每输入一组偏序关系进行一次拓扑排序。如果存在回路，输出矛盾。在不存在回路的基础上，判断每次入度为0的点是否唯一，只有保证每次只有一个点入度为0，才能保证最终的序列唯一。第二十七页，共二十九页，编辑于2023年，星期二Input46//n=4表示字母数,2≤n≤26,m=6表示形如A<B的偏序关系数A<B//第1个偏序关系A<CB<CC<DB<DA<B//第6个