[영어 원서 독해] algorithms and programming - Paths in graphs 1

Chapter 4
Paths in graphs
4.1 Distances
Depth-rst search readily identies all the vertices of a graph that can be reached from a
designated starting point. It also nds explicit paths to these vertices, summarized in its
search tree (Figure 4.1). However, these paths might not be the most economical ones possible.
In the gure, vertex C is reachable from S by traversing just one edge, while the DFS tree
shows a path of length 3. This chapter is about algorithms for nding shortest paths in graphs.
Path lengths allow us to talk quantitatively about the extent to which different vertices of
a graph are separated from each other:
The distance between two nodes is the length of the shortest path between them.
To get a concrete feel for this notion, consider a physical realization of a graph that has a ball
for each vertex and a piece of string for each edge. If you lift the ball for vertex s high enough,
the other balls that get pulled up along with it are precisely the vertices reachable from s.
And to nd their distances from s, you need only measure how far below s they hang.
In Figure 4.2 for example, vertex B is at distance 2 from S, and there are two shortest
paths to it. When S is held up, the strings along each of these paths become taut. On the
other hand, edge (D;E) plays no role in any shortest path and therefore remains slack.

Figure 4.1 (a) A simple graph and (b) its depth-rst search tree.
(a)
E S A
D C B
(b) S
A
B
D
E
C
109
Figure 4.2 A physical model of a graph.
B
E S
D C
A
S
C D E
B
A
Figure 4.3 Breadth-rst search.
procedure bfs(G; s)
Input: Graph G = (V;E), directed or undirected; vertex s 2 V
Output: For all vertices u reachable from s, dist(u) is set
to the distance from s to u.
for all u 2 V :
dist(u) = 1
dist(s) = 0
Q = [s] (queue containing just s)
while Q is not empty:
u = eject(Q)
for all edges (u; v) 2 E:
if dist(v) = 1:
inject(Q; v)
dist(v) = dist(u) + 1

-----------------------------------------------------------------
번역번역중....

4단원

그래프의 경로

4.1 거리

깊이 우선 탐색은 지정된 시작점으로부터 도착할 수 있는 모든 그래프의 모서리를 쉽게 찾을 수 있고, 그것들의 트리 검색으로 요약된 정점들로부터 확실한 경로도 찾을 수 있다. 하지만 이 경로들은 가장 경제적인 유일한 방법이지 않을 수도 있다.

계산문제에서 DFS 트리가 길이 3의 경로를 보여주고 있는 동안 정점 C가 S로부터 오직 하나의 모서리를 지나서 도달 가능하다.

이 장은 그래프의 가장 짧은 경로를 찾는 알고리즘에 관해 쓰여져 있다. 경로 길이는 우리에게 그래프의 다른 정점이 각각의 정점으로부터 떨어져 있는 길이에 관해 말할 수 있도록 해준다.

두 노드 사이의 거리는 그들 사이에서 가장 짧은 경로의 길이 이다. 이 생각에 대해 구체적인 느낌을 얻기 위해서는, 각각의 모서리의 줄과 각각의 정점의 공을 갖고 있는 그래프의 자연적인 사실 이라고 여겨라.

만약 당신이 충분히 높이 정점의 공을 올린다면 멈춘 다른 공들은 정확하게 s로부터 도달한 정점일 것이다.

그리고 s로부터 연결된 그들의 거리를 찾고 싶다면 당신은 그들이 연결해놓은 그래프의 거리를 일정한 점까지 측정해야 한다. 예시 4.2에서 정점 B와 S의 거리는 2이고 가장 짧은 경로가 2 개 있다. S를 예로 들면 이 경로의 각각의 줄은 완전히 정비되었다. 한편, 모서리DE는 어떤 짧은 경로도 없고, 그러므로 slack으로 남았다.

계산 4.1 (a) 단순한 그래프와 (b) 그것의 깊이 우선 탐색 트리

(a)

E S A

D C B

(b) S

A

B

D

E

C

109

계산 4.2 그래프의 자연적인 모델

B

E S

D C

A

S

C D E

B

A

계산 4.3 너비 우선 탐색

procedure bfs(G; s)

Input: Graph G = (V;E), directed or undirected; vertex s 2 V

Output: For all vertices u reachable from s, dist(u) is set

to the distance from s to u.

for all u 2 V :

dist(u) = 1

dist(s) = 0

Q = [s] (queue containing just s)

while Q is not empty:

u = eject(Q)

for all edges (u; v) 2 E:

if dist(v) = 1:

inject(Q; v)

dist(v) = dist(u) + 1