文档介绍：图算法基础知识
第1页，共29页，编辑于2022年，星期五
图
图 G = (V, E)
V = 顶点的非空有限集
E = 边集 = V V的子集，V中顶点对，边的有限集。
|E| = O(|V|2)
简单图(Sample3
第13页，共29页，编辑于2022年，星期五
1
2
4
3
图:邻接表
1
2
3
nil
2
3
nil
3
nil
4
3
nil
第14页，共29页，编辑于2022年，星期五
邻接表的实现
Type
pointer=↑adjnode
adjnode=record
adjvex:integer; {该点在图中的位置}
next:pointer; {指向下一个顶点的指针}
infor: …; {与边有关的信息，如权值w}
Adjlist=array[1..maxlength] of pointer;
图:邻接表
第15页，共29页，编辑于2022年，星期五
无环有向图的拓扑排序 Directed acyclic graphs( DAG) topological sort
DAG:不含回路的有向图称为无环有向图。
检查有向图中是否存在回路的方法之一，是对有向图进行拓扑排序。
如果有向图G有一个拓扑排序,, 任一有向无环图必可进行拓扑排序。
第16页，共29页，编辑于2022年，星期五
何谓“拓扑排序”？
按照有向图给出的次序关系，将图中顶点排成一个线性序列，对于有向图中没有限定次序关系的顶点，则可以人为加上任意的次序关系。
由此所得顶点的线性序列称之为拓扑有序序列
第17页，共29页，编辑于2022年，星期五
例如：对于下列有向图
B
D
A
C
可求得拓扑有序序列：
A B C D 或 A C B D
第18页，共29页，编辑于2022年，星期五
B
D
A
C
反之，对于下列有向图
不能求得它的拓扑有序序列。
因为图中存在一个回路 {B, C, D}
第19页，共29页，编辑于2022年，星期五
如何进行拓扑排序？
一、从有向图中选取一个没有前驱
的顶点，并输出之;
重复上述两步，直至图空，或者图不空但找不到无前驱的顶点为止。
二、从有向图中删去此顶点以及所
有以它为尾的弧;
第20页，共29页，编辑于2022年，星期五
a
b
c
g
h
d
f
e
a
b
h
c
d
g
f
e
在算法中需要用定量的描述替代定性的概念
没有前驱的顶点 入度为零的顶点
删除顶点及以它为尾的弧 弧头顶点的入度减1
第21页，共29页，编辑于2022年，星期五
拓扑排序算法
Function topsort:boolean; P140
var i,count:integer;
wadj:Arr3;//用来表示图的邻接表表头数组
indeg:Arr1; //一维数组，存储每个顶点的入度
p:wpointer; //链表，邻接表
q:queue; //队列q保存入度为零且未被排序的顶点
begin //算法依次对q的出队元素进行编号
topsort:=true;
count:=0;
makenull(q); //清空队列q
fillchar(indeg,sizeof(indeg),0); //数组indeg存储每个顶点入度
第22页，共29页，编辑于2022年，星期五
//通过遍历邻接表，计算所有顶点的入度
For i:=1 to n do
begin
p:=wadj[i]; //顶点i的邻接表的第一个邻接点
while p<>nil do //依次为顶点i的所有邻接点入度加1
begin
inc(indeg[p^.v]);
p:=p^.next;
end;
End;
第23页，共29页，编辑于2022年，星期五
//入度为0的顶点加入队列q
For i:=1 to n do
if indeg[i]=0 then enqueue(i,q)