2012版《图算法》详解：奠基之作，深入浅出

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

身份认证购VIP最低享 7 折!

领优惠券(最高得80元）

资源详情

资源推荐

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页未读，继续阅读

zou_mono

粉丝: 0
资源: 40

2012版《图算法》详解：奠基之作，深入浅出

Algorithms.in.C++.Part.5.Graph.Algorithms

Handbook.of.Graph.Theory.Combinatorial.Optimization.and.Algorithms.158

Data.Structures.and.Algorithms.Made.Easy.epub

module 'networkx.algorithms.approximation' has no attribute 'hamiltonian_path'

betweeness java

NameError: name 'dijkstra' is not defined ModuleNotFoundError: No module named 'graph_algorithms'怎么解决

基于图的图像分割算法python

spanning tree

对Email数据集，用Katz算法进行链路预测，设置训练集比例为90%，并比较AUC值和Precision(L=100,200)

x = x.detach()

Genetic Algorithms in Search, Optimization and Machine Learning

bfd and dfs introduction pdf

编写一般图最大加权匹配算法

最短路径dijkstra算法参考文献

K. Dynamic Reachability

graph 和 communities 分别是 NetworkX 图和使用 fast_greedy_modularity 函数计算得到的社群列表 其中 fast_greedy_modularity 函数的代码实现

加权模块度的计算 python

最新资源

graph 和 communities 分别是 NetworkX 图和使用 fast_greedy_modularity 函数计算得到的社群列表其中 fast_greedy_modularity 函数的代码实现