图算法第二版：深入浅出网络流与图论经典

需积分: 9 16 浏览量更新于2024-07-25 收藏 1.47MB PDF 举报

"《Graph Algorithms（Shimon Even，Guy Even）第二版》是1979年出版的经典算法书籍，由Shimon Even撰写，对图算法进行了深入浅出的介绍。该书在第二版中由Richard M. Karp作序，Andrew V. Goldberg提供注解，继续沿袭第一版的优秀讲解风格，用简洁直观的语言描述算法。内容包括图的基本概念、最短路径、树结构、深度优先搜索和广度优先搜索。主要部分专注于网络流算法及其应用，并在结尾探讨平面图和图的平面性测试。" 在图算法领域，这本书涵盖了以下几个关键知识点： 1. **图理论基础**：书中首先介绍了图的基本概念，包括有向图、无向图、加权图、连通图等，这些都是理解图算法的基础。此外，还涉及了图的各种性质，如度、环、路径和生成树。 2. **最短路径算法**：这部分讲解了寻找图中两点间最短路径的方法，如Dijkstra算法和Floyd-Warshall算法。这些算法在路由选择、交通规划等领域有广泛应用。 3. **树结构**：书中涵盖了树的基本操作，如遍历（深度优先搜索DFS和广度优先搜索BFS），以及树的构建和分解。树在数据结构中占有重要地位，如二叉树、平衡树（AVL树、红黑树）等。 4. **网络流与最大流问题**：这是本书的核心内容，网络流理论用于解决资源分配、调度和设施选址等问题。Max-Flow Min-Cut定理是网络流理论的基础，书中会详细介绍Ford-Fulkerson算法和Edmonds-Karp算法。 5. **应用网络流**：书中讨论了网络流在实际问题中的应用，如运输问题、电路设计和作业调度等，这些应用突显了网络流算法的实际价值。 6. **平面图与图的平面性**：最后，书中探讨了平面图的概念，即如何在不使边交叉的情况下在平面上绘制图。平面图测试算法用于判断一个图是否可以被表示为平面图，这对于图形布局和图的可视化很重要。 Shimon Even作为图算法和密码学的先驱研究者，他的著作对计算机科学教育产生了深远影响，不仅为学生提供了丰富的学习材料，也为研究者提供了宝贵的参考。此书适合计算机科学专业的学生和研究人员，以及任何对图算法感兴趣的读者。通过深入学习，读者将能够理解和掌握图算法的精髓，进一步提升在图论和网络优化问题上的分析和解决能力。

2 1 Paths in Graphs

Figure 1.1: Example of a graph.

The notation u

v means that the edge e is incident on vertices u and v.In

this case we also say that e connects vertices u and v, or that vertices u and v

are adjacent.

A path, P, is a sequence of vertices and edges, interweaved in the following

way: P starts with a vertex, say v

,followedbyanedgee

incident to v

followed by the other endpoint v

of e

, and so on. We write

P : v

···

If P is ﬁnite, it ends with a vertex, say v

. We call v

the start-vertex of P and

the end-vertex of P. The number of edge appearances in P, l, is called the

length of P.Ifl = 0, then P is said to be empty, but it has a start-vertex and

an end-vertex, which are identical. (We shall not use the term “path” unless a

start-vertex exists.)

In a path, edges and vertices may appear more than once, unless otherwise

stated. If no vertex appears more than once, and therefore no edge can appear

more than once, the path is called simple.

A circuit, C,isaﬁnite path in which the start and end vertices are identical.

However, an empty path is not considered a circuit. By deﬁnition, the start and

end verticesof a circuit are the same, and ifthere isno other repetition ofa vertex,

the circuit is called simple. However, a circuit of lengthtwo,a

a,where

the same edge, e, appears twice, is not considered simple. (For a longer circuit,

it is superﬂuous to state that if it is simple, then no edge appears more than

once.) A self-loop is a simple circuit of length one.

If for every two vertices u and v of a graph G,thereisa(ﬁnite) path that starts

in u and ends in v,thenG is said to be connected.

A digraph or directed graph G(V,E) is deﬁned similarly to a graph, except

that the pair of endpoints of every edge is now ordered. If the ordered pair of

1.2 Computer Representation of Graphs 3

endpoints of a (directed) edge e is (u,v), we write

−→ v.

The vertex u is called the start-vertex of e; and the vertex, v,theend-vertex of

e. The edge e is said to be directed from u to v. Edges with the same start-vertex

and the same end-vertex are called parallel.Ifu = v, u

−→ v and v

−→ u,then

and e

are antiparallel. An edge u −→ u is called a self-loop.

The out-degree d

out

(v) of vertex v is the number of (directed) edges having

v as their start-vertex; in-degree d

(v) is similarly deﬁned. Clearly, for every

ﬁnite digraph G(V,E),



v∈V

(v)=



v∈V

out

(v).

A directed path is similar to a path in an undirected graph; if the sequence of

edges is e

,··· then for every i  1, the end-vertex of e

is the start-vertex of

i+1

. The directed path is simple if no vertex appears on it more than once. A

ﬁnite directed path C is a directed circuit if the start-vertex and end-vertex of C

are the same. If C consists of one edge, it is a self-loop. As stated, the start and

end vertices of C are identical, but if there is no other repetition of a vertex, C

is simple. A digraph is said to be strongly connected if, for every ordered pair

of vertices (u,v) there is a directed path which starts at u and ends in v.

1.2 Computer Representation of Graphs

To understand the time and space complexities of graph algorithms one needs

to know how graphs are represented in the computers memory. In this section

two of the most common methods of graph representation are brieﬂy described.

Let us consider graphs and digraphs that have no parallel edges. For such

graphs, the speciﬁcation of the two endpoints is sufﬁcient to specify the edge;

for digraphs, the speciﬁcation of the start-vertex and the end-vertexis sufﬁcient.

Thus, we can represent such a graph or digraph of n vertices by an n× n matrix

M,whereM

= 1 if there is an edge connecting vertex v

to v

,andM

= 0, if

not. Clearly, in the case of (undirected) graphs, M

= 1 implies that M

= 1;

or in other words,M is symmetric. But in the case of digraphs, any n×n matrix

of zeros and ones is possible. This matrix is called the adjacency matrix.

Given the adjacency matrix M of a graph, one can compute d(v

) by counting

the number of ones in the i-th row, except that a one on the main diagonal

representsa self-loop and contributestwoto the count. For a digraph,the number

4 1 Paths in Graphs

of ones in the i-th row is equal to d

out

), and the number of ones in the j-th

column is equal to d

The adjacency matrix is not an efﬁcientrepresentationof the graph if thegraph

is sparse; namely, the number of edges is signiﬁcantly smaller than n

.Inthese

cases, it is more efﬁcient to use the incidence lists representation, described

later. We use this representation, which also allows parallel edges, in this book

unless stated otherwise.

A vertex array is used. For each vertex v, it lists v’s incident edges and a

pointer indicating the current edge. The incidence list maysimplybeanarray

or may be a linked list. Initially, the pointer points to the ﬁrst edge on the list.

Also, we use an edge array, which tells us for each edge its two endpoints (or

start-vertex and end-vertex, in the case of a digraph).

Assume we want an algorithm TRACE(s,P), such that given a ﬁnite graph

G(V,E) and a start-vertex s ∈ V traces a maximal path P that starts at s and does

not use any edge more than once. Note that by “maximal” we do not mean that

the resulting path, P, will be the longest possible; we only mean that P cannot

be extended, that is, there are no unused incident edges at the end-vertex.

We can trace a path starting at s by taking the ﬁrst edge e

on the incidence list

of s, marking e

as “used” in the edge array, and looking up its other endpoint

(which is s if e

is a self-loop). Next, use the vertex array to ﬁnd the pointer

to the current edge on the list of v

. Scan the incidence list of v

for the ﬁrst

unused edge, take it, and so on. If the scanning hits the last edge and it is used,

TRACE(s,P) halts. A PASCAL-like description of TRACE(s,P) is presented

in Algorithm 1.1. Here is a list of the data structures it uses:

(i) A vertex table such that, for every v ∈ V, it includes the following:

– A list of the edges incident on v, which ends with NIL

– A pointer N(v) to the current item in this list. Initially, N(v) points to

the ﬁrst edge on the list (or to NIL, if the list is empty).

(ii) An edge table such that every e ∈ E consists of the following:

– The two endpoints of e

– A ﬂag that indicates whether e is used or unused. Initially, all edges are

unused.

(iii) An array (or linked list) P of edges that is initially empty, and when

TRACE(s,P) halts, will contain the resulting path.

Notice that in each application of the “while” loop of TRACE (lines 2–10 in

Algorithm 1.1), either N(v) is moved to the next item on the incidence list of

v (line 4), or lines 6–10 are applied, but not both. The number of times line

剩余203页未读，继续阅读

tragedies

粉丝: 1
资源: 28

图算法第二版：深入浅出网络流与图论经典

Graph Algorithms：Practical Examples in Apache Spark and Neo4j+高清无码书签完整内容可编辑完美资源

Graph Algorithms

Distributed Graph Algorithms for Computer Networks

Dynamic Graph Algorithms

Neo4j Graph Algorithms

Graph Algorithms.zip

Graph Algorithms 2ed

neo4j graph algorithms docment

Advanced Topics in Graph Algorithms

Friendship Graph Algorithms.pdf

最新资源

Graph　Algorithms　2ed