《算法设计与分析》课件第7章

第7章图算法7.1图的表示7.2广度优先搜索7.3

Dijkstra算法7.4

Bellman-Ford算法7.5

Floyd-Warshall算法

习题许多应用问题可以归结为图模型上的问题。因而，我们可以用图作为表示和求解问题的工具。例如，在航线图中，图中的顶点可以表示机场，边可以表示飞行航线，边上的权值则可能表示距离或费用。在电路图中，图中的顶点表示逻辑门、寄存器、引脚或处理器，边表示接线，边上的权值可能表示接线长度或传输延迟。在作业调度问题中，图中的顶点表示作业，边表示优先关系，边上的权值可能表示优先级。在金融问题中，图中的顶点表示股票或流通货币，边表示交易或事务处理，边上的权值可能表示费用。表7-1列举了不同应用领域在图模型中的意义。表7-1应用领域与图模型

7.1图的表示

可以使用邻接矩阵来表示一个图。对于有n(=|V|)个顶点的图，其邻接矩阵的第(i，j)个元素为

其中，vi(i=1,…,n)为图中顶点。对于一个无向图，因为其中的每条边{u，v}可从两个方向看待，因而该邻接矩阵是对称的。这种表示的好处是可在常量时间内检查图中是否存在某条边，只需要访问一次内存。而矩阵需要O(n2)的空间。如果图中的边数不是很多，这种表示方式浪费空间。图的另一种表示方法是邻接表表示法。这种方法只需要与边数成正比的空间，由|V|个链表组成，每个顶点都有一个链表。顶点u的链表存放由u出发所指向的顶点，也就是说，存放(u，v)∈E的那些顶点v。因此，如果图为有向图，则每条边只在一个链表中出现；如果图为无向图，则每条边在两个链表中出现。无论是哪种情况，数据结构的总规模为O(|E|)。在这种情况下，检查某条边(u，v)不再为常量时间，因为这个过程需要查找u的邻接表。但通过一个顶点的所有近邻还是可以比较容易地完成这个过程。我们很快就可知，这个过程证明是图算法中的一个很有用的操作。对于无向图，这种表示是对称的，当且仅当u在v的邻接表中，v在u的邻接表中。使用哪一种表示法，取决于顶点集|V|中顶点之间的关系、图中的顶点数以及边数|E|。|E|的规模可与|V|相当或与|V|2相当(所有边可能相连)。如果是前者，则称该图是稀疏的，否则称该图是稠密的。我们将在后续的章节中看到，|E|与|V|之间的这个关系将会成为我们选择合适图算法的主要因素。

7.2广度优先搜索

广度优先搜索(BreadthFirstSearch，BFS)是图搜索中最简单的算法之一，也是很多重要图算法的基础算法。Dijkstra单源点最短路径算法就使用了与BFS类似的思想。

给定一个图G=(V，E)以及一个称为源点的特殊顶点s，BFS系统地探索图G中的边，找出由s可达的那些顶点。BFS计算出从s到每个可达顶点的距离(最少边数)。同时，还形成一棵根为s的广度优先树，这棵树中包括了由s可达的所有顶点。对于由s可达的任一顶点v，在这棵广度优先树中从s到v的路径对应于图G中从s到v的一条最短路径，也就是说，包含了边数最少的一条路径。BFS算法对于有向图和无向图均适用。对于图7-1，以结点a作为源点s，将该图划分为若干层：s自身，与s距离为1的那些顶点作为一层，与s距离为2的那些结点作为另一层，以此类推。一种简便的计算从s到其他顶点的距离的方法是逐层进行计算。一旦计算出距离为0，1，2，…，d的那些顶点，就很容易确定出距离为d+1的顶点。这些顶点就是那些与距离为d的那层顶点相邻的尚未被访问的顶点。这就给出一个在任一给定时刻只有两层是活跃的迭代算法：在某层d，其中的顶点完全被访问过；在d+1层，要通过扫描第d层顶点的近邻，来找出该层的顶点。图7-1有向图示例广度优先搜索直接实现了我们上述的过程。初始时，队列Q中只含顶点s，即距离为0的顶点。对于后续距离d=1，2，3，…，在某时刻，队列Q中只包含距离为d的所有顶点。随着这些顶点被处理(执行出队操作)，其尚未被访问的近邻被插入到队尾。图7-2给出了访问图7-1中顶点时的当前队列，其中a为起始点，顶点按照字母顺序排列。队列Q中字母上方的数字表示起始点到该顶点的距离。而且图7-2右边的广度优先搜索树包含了每个顶点最先被访问时所通过的那些边。由此可得，从a开始的每条路径都是最短路径。因此，这棵树称为最短路径树(shortestpathtree)。图7-2图7-1的广度优先队列Q及其广度优先搜索树广度优先搜索算法如下所示。

BFS(G,s)

1 foreachvertexv

V[G]//初始化到顶点v的最短路径及前驱

2

do

d[v]

3

[v]

NIL

4 d[s]

0

5 Q

//初始化队列Q

6 ENQUEUE(Q,s)

7 while

Q

//队列中存在顶点

8

dou

DEQUEUE(Q)//摘取队列中最小元素

9

foreachvertexv

Adj[u]//更新顶点v的最短路径长度

10 do

if

d[v]=

11

then

d[v]

d[u]+1

12

ENQUEUE(Q,v)以下分析算法的运行时间。初始化后，第10行的测试保证每个顶点至多入队一次，且至多出队一次。入队和出队操作所需时间为常量时间O(1)，因而，队列操作的总时间为O(V)。由于仅在顶点出队时才扫描该顶点的邻接表，因此，每个邻接表至多被扫描一次。由于所有邻接表的长度之和为Θ(E)，因此扫描邻接表所花费的总时间为O(E)。初始化的开销为O(V)。因此，BFS的总运行时间为O(V+E)。由此可得，广度优先搜索算法的运行时间为G的邻接表表示规模的线性时间。

BFS算法的执行过程如图7-3所示。图7-3

BFS算法的执行过程

7.3

Dijkstra算法

给定加权有向图G=(V，E)，定义权函数w为边到其上实值的映射w：E→R。路径p=〈v0，v1，…，vk〉上的权定义为这条路径边上的权值之和，即

定义从u到v的最短路径权值为

因此，从u到v的最短路径定义为u到v且满足w(p)=δ(u,v)的路径p。

1.最短路径问题的最优子结构

最短路径算法具有这样一个性质：两个顶点之间的最短路径包括这条路径上其他顶点之间的最短路径。这个最优子结构性质应用了动态规划和贪心算法的特点。Dijkstra算法是一个贪心算法。引理7.1更准确地阐述了最短路径问题的最优子结构性质。

引理7.1最短路径的子路径是最短路径。

证明给定权函数为w：E→R的加权有向图G=(V,E)，设p=〈v1,v2,…,vk〉是从顶点v1到顶点vk的最短路径，对于任意满足1≤i≤j≤k的顶点i和j，设pij=〈vi,vi+1,…,vj〉为p的从顶点vi到顶点vj的子路径，那么，pij是从顶点vi到顶点vj的最短路径。

2.权值为负的边与回路

在单源点最短路径问题的例子中，可能存在权值为负的边。如果图G=(V,E)不含从源点s可达的负权值回路，那么对于所有v∈V，即使最短路径权值为负，最短路径权值d(s,v)的定义依然成立。然而，如果图G中存在从源点s可达的负权值回路，那么对于所有v∈V，最短路径权值d(s,v)的定义就不能成立。在这种情况下，不存在从源点s到这个回路

上顶点的最短路径。如果G中存在从源点s到v的负权值回路，则定义d(s,v)=－∞，如图7-4所示。每个顶点上的数字表示从源点s到该点的最短路径权值，顶点e和f形成由s可达的负权值回路，因此，它们的最短路径权值为－∞。而顶点g可由最短路径权值为－∞的顶点到达，因此，它的最短路径权值也为－∞。顶点h、i和j由s不可达，因此即使它们位于负权值的回路上，它们的最短路径权值也为∞。图7-4有向图中的负权值边

3.最短路径表示与松弛操作

常常需要计算最短路径的权值，而且还要找出组成最短路径上的那些顶点。给定图G=(V,E)，用π［v］表示顶点v∈V的前驱(predecessor)，它是一个顶点或为NIL。在最短路径算法的执行过程中，无需通过π值表明最短路径，主要关注π值所导出的前驱子图Gπ=(Vπ,Eπ)即可。定义顶点集合Vπ如下：

Vπ={v∈V：π［v］≠NIL}∪{s}

有向边集Eπ定义为由Vπ中顶点的π值所导出的边集，即

Eπ={(π［v］,v)∈E：v∈Vπ－{s}}算法所产生的π值具有如下性质：在算法终止时，Gπ就是最短路径树。这棵树以源点s为根，包含了由s可达的每个顶点的一条最短路径。因此，以s为根的最短路径树是有向子图G′=(V′,E′)，其中V′

V，E′

E，满足：

(1)V′是G中由s可达的顶点集合。

(2)G′形成以s为根的有根树。

(3)对于所有v∈V′，G′中从s到v的最短路径就是G中从s到v的最短路径。最短路径不必惟一，最短路径树也不必惟一。算法的主要思想是反复应用松弛(relaxation)操作。对于每个顶点v∈V，维持d［v］，这是从源点s到顶点v的最短路径权值的上界。称d［v］为最短路径估值。算法的初始化过程如下：

INITIALIZE-SINGLE-SOURCE(G,s)

1 foreachvertexv

V[G]//初始化到顶点v的最短路径及前驱

2

do

d[v]

3

[v]

NIL

4 d[s]

0

初始化之后，对于所有v∈V，有π［v］=NIL；对于v∈Vπ－{s}，有d［s］=0和d［v］←∞。一条边(u,v)是否需要松弛，取决于对这条边的测试结果。如果能够通过顶点u改进目前源点到顶点v的最短路径，则对d［v］和π［v］进行更新。因此，松弛操作会使最短路径估值d［v］下降，并对顶点v的前驱π［v］进行更新。过程RELAX实现对边(u,v)的松弛：

RELAX(u,v,w)//对更小权值顶点的最短路径长度进行更新

1 ifd[v]>d[u]+w(u,v)

2 thend[v]

d[u]+w(u,v)

3

[v]

u

4.Dijkstra算法

在Dijkstra算法中，假定有加权有向图G，且对于每条边(u,v)∈E，w(u,v)≥0，即所有边上的权值非负。算法维持顶点集合S，从源点到该集合中顶点的最短路径已被确定。算法不断从集合V－S中选出具有最短路径估值的顶点u∈V－S，并将u添加到S中，松弛所有离开u的边。在算法实现中，利用顶点的最小优先队列Q作为数据结构，以d值为优先级。

第1、2行分别初始化d、π、集合S(为空)。第3行对最小优先队列Q进行初始化，使其包含所有顶点。在第4～8行的while循环每次迭代的开始，算法维持不变式Q=V－S。由于初始化S=，执行第3行之后，循环不变式为真。在每次执行4～8行的while循环体时，从Q=V－S中摘取一个顶点u，并添加到集合S中，因而保持循环不变式。第一次执行while循环时，u=s。因而，顶点u是V－S中最短路径估值最小的顶点。如果到v的最短路径可以通过顶点u得到改进，则在第7和第8行中，将离开u的边(u,v)松弛，即对d［v］的估值和π［v］进行更新。在第3行之后，Q中不再插入顶点，每个顶点只从Q中被摘取一次，只向S中添加一次，因此，第4～8行的while循环恰好迭代|V|次。DIJKSTRA(G,w,s)

1 INITIALIZE-SINGLE-SOURCE(G,s)//初始化到顶点v的最短路径及前驱

2 S

3 Q

V[G]

//初始化队列Q

4 while

Q

//队列中存在顶点

5

dou

EXTRACT-MIN(Q)//摘取队列中最小元素

6 S

S

{u}

7

foreachvertexv

Adj[u]//更新顶点v的最短路径长度

8

doRELAX(u,v,w)Dijkstra算法的执行过程如图7-5所示。图7-5

Dijkstra算法的执行过程

5.Dijkstra算法的贪心策略

由于Dijkstra算法总是选择V－S中最轻或者最近顶点添加到集合S中，因此称该算法利用了贪心策略。尽管贪心策略并不一定会产生最优解，但是正如在定理4.7及推论4.8中所表明的那样，Dijkstra算法可以计算顶点的最短路径。证明的关键是每次向集合S中添加顶点u时，d［u］=δ(s,u)。我们在证明Dijkstra算法的正确性时，使用图7-6进行说明。图7-6

Dijkstra算法的证明图示

定理7.2

Dijkstra算法的正确性。

给定加权有向图G=(V,E)，以及非负权函数w和源点s。如果对该图运行Dijkstra算法，则在算法终止时，对于所有顶点u∈V，有d［u］=δ(s,u)。

证明：利用循环不变式：对于每一顶点v∈S，执行第6～10行的while循环的每次迭代时，有d［v］=δ(s,v)。

只要证明，对于每一顶点u∈S，当u添加到集合S时，d［u］=δ(s,u)即可。一旦证明d［u］=δ(s,u)，就可以根据上界性质证明此后的所有时刻，这个等式都成立。初始时：S=，因而，循环不变式平凡成立。

维持时：希望证明，在每次迭代过程中，添加到集合S中的顶点满足d［u］=δ(s,u)。用反证法证明。设u是添加到S中满足d［u］≠δ(s,u)的第一个顶点。要证明while循

环迭代的开始，u被添加到S中，通过检查此时从s到u的最短路径，导出d［u］=δ(s,u)的矛盾。因为s是添加到S中的第一个顶点，且d［s］=δ(s,s)=0，因而必有u≠s。由于u≠s,可以得出就在u被添加到S中之前，S≠。因而，一定存在从s到u的路径，否则，如果路径不存在，则有d［u］=δ(s,u)=∞，这与假设d［u］≠δ(s,u)矛盾。因为从s到u至少存在一条路径，设这条路径为p。在将顶点u添加到集合S中之前，路径p将S中的顶点s与V－S中的某个顶点相连。考虑路径p上满足y∈V－S的第一个顶点y，设x∈S是y的前驱，参考图7-6，路径p可以分解为 。

首先证明断言，当u添加到S中时，d［y］=δ(s,y)。观察可见x∈S。由于u是插入集合S且满足d［u］≠δ(s,u)的第一个顶点，当x被添加到S中时，则有d［x］=δ(s,x)。此时，边(x,y)被松弛。由收敛性质(如果s～>u→v是G中的一条最短路径，u,v∈V，且在松弛边(u,v)之前的任何时刻，d［u］=δ(s,u)，那么，此后的任意时刻，d［v］=δ(s,v))，声明成立。现在证明d［u］=δ(s,u)，导出矛盾。因为在从s到u的最短路径上，y出现在u之前，且所有边的权值非负(注意p2上的那些权值)，则有δ(s,y)≤δ(s,u)。因此有

d［y］=δ(s,y)≤δ(s,u)≤d［u］//由上界性质 (7.1)

推论7.3给定加权有向图G=(V,E)，以及非负权函数w和源点s。如果对该图运行Dijkstra算法，则在算法终止时，前驱子图Gπ是一棵根为s的最短路径树。

证明：由定理7.2和前驱子图的性质直接得到。证毕。

6.Dijkstra算法的运行时间

Dijkstra算法通过调用3个优先队列的操作,来维持最小优先队列Q。这3个操作是INSERT(第3行中隐含)、EXTRACT-MIN(第5行)和DECREASE-KEY(隐含在第8行的RELAX中)。每个顶点调用一次INSERT，同样EXTRACT-MIN也被每个顶点调用一次。因为每个顶点v∈V只向集合S中添加一次，所以在算法运行过程中，第7、8行的for循环只对邻接表Adj［v］中的每条边检查一次。邻接表中边的总数为|E|，因此，这个for循环总共迭代|E|次，总共进行至多|E|次的DECREASE-KEY操作。

Dijkstra算法的运行时间取决于最小优先队列如何实现。考虑这样一种情况，利用从1到|V|的顶点编号维持优先队列Q。将d［v］存储在数组的第v个元素中。每个INSERT和

DECREASE-KEY操作需要O(1)的时间。每个EXTRACT-MIN操作需要O(V)的时间，因为需要查找整个数组。因此算法的运行时间为O(V2+E)=O(V2)。

如果G是稀疏图，可用二叉堆实现优先队列。每个EXTRACT-MIN操作需要O(lbV)的时间，共有|V|个这样的操作。建立二叉堆的时间为O(V)，每个DECREASE-KEY操作需要O(lbV)的时间,至多有|V|个这样的操作,因此算法的运行时间为O((V+E)lbV)，如果所有顶点均从源点s可达，则算法的运行时间为O(ElbV)。如果用斐波那契堆实现优先队列，则可得算法的运行时间为O(VlbV+E)。这是因为|V|个EXTRACT-MIN操作的平摊开销为O(lbV)。每个DECREASE-KEY操作的调用只需O(1)的平摊开销，这样的操作至多有|E|个。

由以上分析可得，Dijkstra算法的运行时间T=Θ(V)TEXTRACT-MIN+Θ(E)TDECREASE-KEY主要取决于所使用的优先队列Q的实现。表7-2给出了基于上述三种实现时的Dijkstra算法的运行时间。表7-2不同实现时的Dijkstra算法的运行时间 7.4

Bellman-Ford算法

在Dijkstra算法中，从起始点s到任何顶点v的最短路径必定只通过那些比到顶点v更近的顶点。当边上的权值为负时，这一结论不再成立。在图7-7中，从s到v的最短路径通

过u，而顶点u距离s的最短路径要长。图7-7带有负权值边的图松弛操作具有如下性质：

(1)这个松弛操作给出了如下情况下到v的正确距离，此时u是到v的这条最短路径上倒数第2个顶点且d［u］也是正确距离。

(2)松弛操作将不再使d［v］更小，从这个意义上讲，它是安全的。例如，其他松弛操作也不会对已有结果产生影响。这个操作非常有用。如果仔细斟酌，就可以设置出正确距离。实际上，也可将Dijkstra算法简单地看做一系列的松弛过程。如上所述，这个松弛序列并不适合于带有负权值边的图，那么是否存在适合于负权值边的其他序列呢？为了得到这个序列所具备的属性，我们选取顶点t，并观察从s到顶点t的最短路径：这条路径上至多包含|V|－1条边。如果执行的松弛序列包含(s，u1)，(u1，u2)，(u2，u3)，…，(uk，t)，那么由第一个性质可正确计算出到t的距离。这些边上出现的其他松弛操作是不重要的，因为这些松弛是安全的。

然而，如果预先并不知道最短路径，怎样才能确信以正确的顺序松弛了正确的边呢？这里给出一种简单的解决方案：简单地对所有边松弛|V|－1次。以下给出的算法具有O(VE)

的运行时间，称为Bellman-Ford算法。BELLMAN-FORD(G,w,s)

1 INITIALIZE-SINGLE-SOURCE(G,s)

2 fori

1to|V[G]|－1

3 doforeachedge

(u,v)

E[G]

4

doRELAX(u,v,w)

5 foreachedge

(u,v)

E[G]

6 doif

d[v]>d[u]+w(u,v)

7thenreturnFALSE

8returnTRUE实际中，很多图的最短路径中的最大边数远远小于|V|－1，这使得所需的松弛操作轮数大为减少。因此，增加一个对最短路径算法的检查具有实际意义，它可以将没有松弛出现的那些轮很快地终止。

Bellman-Ford算法的执行过程(i=1)如图7-8所示。图7-8

Bellman-Ford算法的执行过程(i=1) 7.5

Floyd-Warshall算法

如果k是路径p上具有最大编号的中间顶点，那么将路径p分为如图7-9所示的两条路径p1和p2。由最优子结构性质，p1是所有中间顶点均在{1，2，…，k－1}中的从顶点i到k的一条最短路径。类似地，p2是所有中间顶点均在{1,2，

…，k－1}中的从顶点k到j的一条最短路径。图7-9从顶点i到j的最短路径p从以上分析可得，我们可以定义最短路径估值的递归公式。令d(i，j，k)表示其所有中间顶点均在{1，2，…，k}中的从顶点i到j的最短路径的长度。初始时，如果顶点i和j之间有边相连，则d(i，j，0)=wij；否则d(i,j,0)=∞。它表示在不含编号k大于0的中间顶点的从顶点i到j的最短路径上，不包含任何中间顶点。此时这样的路径至多包含一条边。以上讨论可得最短路径估值的递归定义对于任何路径，由于其所有中间顶点均在集合{1，2，…，k}中，因而d(i，j，n)给出每一对顶点i，j之间的最短路径，即d(i，j，n)=δ(i，j)，其中i，j∈V。

FLOYD-WARSHALL(W)

1 fori

1to|V[G]|

2

doforj

1to|V[G]|

3

do

d(i,j,0)

4 forall(i,j)

E[G]

5

do

d(i,j,0)

wij

6 fork

1to|V[G]| 7

dofori

1to|V[G]|

8

do

forj

1to|V[G]|

9 do

d(i,j,k)

min(d(i,j,k－1),d(i,k,k－1)+d(k,j,k－1))

10 return

d(i,j,n)

算法的执行过程如图7-10所示。图7-10

Floyd-Warshall算法的执行过程

习题

7-1假设在图7-11上运行Dijkstra算法，源点为a。

(1)在有向图7-11上，运行Dijkstra算法，以a作为源点。要求显示while循环的每次迭代后d和π的值，以及集合S中的顶点。

(2)给出最终的最短路径树。

7-2在有向图7-12上运行Dijkstra算法，首先以s作为源点，然后以z作为源点。要求显示while循环的每次迭代后d和π的值，以及集合S中的顶点。图7-12习题7-2图

7-3假定将Dijkstra算法中的第(4)行变为

4

while|Q|>1[HT5K]

所做的改变会使while循环执行|V|－1，而不是|V|次。试问这个算法是否正确。

7-4假设在图7-13上运行Bellman-Ford算法，源点为z。在每一遍松弛边的过程中，顺序为(t，x)，(t，y)，(t，z)，(x，t)，(y，x)，(y，z)，(z，x)，(z，s)，(s，t)，(s，y)。

(1)在图7-13上运行Bellman-Ford算法，给出类似图7-8执行该算法第一遍后的过程，并给出d值和π值。

(2)将边(z，x)上的权值变为4，以s为源点，重做(1)。图7-13习题7-3图

7-5给出一个含有负权值边的有向图的简单实例，该图使Dijkstra算法的运行产生错误的结果。当允许图中存在负权值边时，为什么定理7.2的证明不能成立？

7-6给定有向图G=(V，E)，对于每条边(u，v)∈E，关联一个值r(u，v)，且0≤r(u，v)≤1。该值表示从顶点u到顶点v的信道的可靠性。可以将r(u，v)的意义解释为u到v的信道不发生故障的概率，并假设这些概率是独立的。试设计一有效算法，找出两个给定顶点之间最可靠的路径。

7-7设G=(V，E)为加权有向图，权函数为w：E→{0，1，…，W}，其中W是一非负整数。修改Dijkstra算法，使得对于给定的源点s，计算最短路径的运行时间为O(WV+E)。

7-8单源点最短路径问题的Gabow定标算法。定标算法按照以下步骤求解问题。初始时，只考虑每个相关输入值(如边的权值)的最高位，然后通过检查两个最高位对初始解进行求精，像这样逐步检查更多的最高位，同时每次都对前次的解进行求精，直到检查完所有位且计算出正确解为止。

在这个问题中，考察一种通过定标边权值计算单源点最短路径的算法。给定有向图G=(V，E)，其中边上权值w为非负整数。设W=max(u,v)∈E{w(u,v)}。目标是研制一种运行时间为O(ElgW)的算法。假设所有顶点由源点可达。算法用二进制表示边的权值。并从最高位到最低位每次检查一位。设k=［lg(W+1)］为W的以二进制表示的位数，对于i=1，2，…，k，令wi(u，v)=［w(u，v)/2k－i］，即wi(u，v)是取w(u，v)的二进制表示的i个高位而得。因此，对于所有(u，v)∈E，wk(u，v)=w(u，v)。例如，如果k=5，w(u，v)=25，它的二进制表示为〈11001〉，那么w3(u，v)=〈110〉=6；如果对于k=5，w(u，v)=4，它的二进制表示为〈00100〉，那么w3(u，v)=〈001〉=1。定义δi(u，v)为从u到v且使用权函数wi的最短路径权值。因此，对于所有u，v∈V，δk(u，v)=δ(u，v)。对于给定的源点s，定标算法首先对于所有v∈V计算出最短路径的权值δ1(s，v)，然后对于所有v∈V计算出最短路径的权值δ2(s，v)，继续这一过程，直到对于所有v∈V计算出最短路径的权值δk(s，v)。假设|E|≥|V|－1，则由δi－1计算出δi所需的运行时间为O(E)。因此，整个算法的运行时间为O(kE)=(ElgW)。

(1)假设对于所有v∈V的顶点，有δ(s，v)≤|E|。证明可以用O(E)时间计算出