Câu hỏi 2
Ta sẽ tiếp tục thế nào khi đã tìm được một thành phần liên thông
mạnh?
Mệnh đề
Nếu C và D là các thành phần liên thông mạnh, và có một cạnh
từ một đỉnh trong C tới một đỉnh trong D, vậy thì số post lớn
nhất trong C phải lớn hơn số post lớn nhất trong D.
Khi ta tìm thấy một thành phần liên thông mạnh và xóa nó khỏi
đồ thị G, vậy thì đỉnh với số post lớn nhất trong các đỉnh còn lại
sẽ thuộc vào thành phần liên thông mạnh hút của đồ thị còn lại
của G.
Thuật toán tìm thành phần liên thông mạnh
1. Chạy DFS trên đồ thị ngược GR của G.
2. Chạy thuật toán tìm thành phần liên thông (tương tự như của
đồ thị vô hướng) trên đồ thị có hướng G;
và trong khi chạy DFS, xử lý các đỉnh theo thức tự giảm dần
theo số post của mỗi đỉnh (tìm được theo bước 1).
58 trang |
Chia sẻ: hachi492 | Ngày: 08/01/2022 | Lượt xem: 434 | Lượt tải: 0
Bạn đang xem trước 20 trang tài liệu Bài giảng Toán rời rạc - Bài 17, Phần 2: Tìm kiếm trên đồ thị - Trần Vĩnh Đức, để xem tài liệu hoàn chỉnh bạn click vào nút DOWNLOAD ở trên
Tìm kiếm trên đồ thị (Version 0.5)
Trần Vĩnh Đức
HUST
Ngày 16 tháng 9 năm 2019
1 / 58
Tài liệu tham khảo
▶ S. Dasgupta, C. H. Papadimitriou, and U. V. Vazirani,
Algorithms, July 18, 2016.
▶ Chú ý: Nhiều hình vẽ trong tài liệu được lấy tùy tiện mà chưa
xin phép.
2 / 58
Nội dung
Biểu diễn đồ thị
Tìm kiếm theo chiều sâu trên đồ thị vô hướng
Tìm kiếm theo chiều sâu trên đồ thị có hướng
Thành phần liên thông mạnh
Đồ thị
▶ Một đồ thị xác định bởi một tập đỉnh (còn gọi là nút) V và
bởi các cạnh E giữa các cặp đỉnh được chọn.
▶ Đồ thị có thể vô hướng: cạnh e = {u, v}
▶ hoặc có hướng e = (u, v).
4 / 58
Biểu diễn đồ thị dùng Ma trận kề
Nếu đồ thị có n = |V| đỉnh v1, v2, . . . , vn, thì ma trận kề là một
mảng n× n với phần tử (i, j) của nó là
aij =
{
1 nếu có cạnh từ vi tới vj
0 ngược lại.
Ví dụ
v1
v2
v3
A =
1 1 10 0 1
0 1 0
5 / 58
Dùng ma trận kề có hiệu quả?
▶ Có thể kiểm tra có cạnh nối giữa cặp đỉnh bất kỳ chỉ cần một
lần truy cập bộ nhớ.
▶ Tuy nhiên, không gian lưu trữ là O(n2)
6 / 58
Biểu diễn đồ thị dùng danh sách kề
▶ Dùng một mảng Adj gồm |V| danh sách.
▶ Với mỗi đỉnh u ∈ V, phần tử Adj[u] lưu trữ danh sách các
hàng xóm của u. Có nghĩa rằng:
Adj[u] = {v ∈ V | (u, v) ∈ E}.
Ví dụ
0
1
2
Adj[0] = {0, 1, 2}
Adj[1] = {2}
Adj[2] = {1}
7 / 58
Dùng danh sách kề có hiệu quả?
▶ Có thể liệt kê các đỉnh kề với một đỉnh cho trước một cách
hiệu quả.
▶ Nó cần không gian lưu trữ là O(|V|+ |E|). Ít hơn O(|V|2) rất
nhiều khi đồ thị ít cạnh.
8 / 58
Nội dung
Biểu diễn đồ thị
Tìm kiếm theo chiều sâu trên đồ thị vô hướng
Tìm kiếm theo chiều sâu trên đồ thị có hướng
Thành phần liên thông mạnh
ptg12441863
Adjacency-lists data structure. 4HE STANDARD GRAPH REPRESENTATION FOR GRAPHS THAT ARE
NOT DENSE IS CALLED THE adjacency-lists data structure WHERE WE KEEP TRACK OF ALL THE
VERTICES ADJACENT TO EACH VERTEX ON A LINKED LIST THAT IS ASSOCIATED WITH THAT VERTEX 7E
MAINTAIN AN ARRAY OF LISTS SO THAT GIVEN A VERTEX WE CAN IMMEDIATELY ACCESS ITS LIST 4O
IMPLEMENT LISTS WE USE OUR Bag !$4 FROM Section 1.3 WITH A LINKED
LIST IMPLEMENTA-
TION SO THAT WE CAN ADD NEW EDGES IN CONSTANT TIME AND ITERATE THROUGH ADJACENT VERTI-
CES IN CONSTANT TIME PER ADJACENT VERTEX 4HE Graph IMPLEMENTATION ON PAGE IS BASED
ON THIS APPROACH AND THE lGURE ON THE FACING PAGE DEPICTS THE DATA STRUCTURES BUILT BY
THIS CODE FOR tinyG.txt 4O ADD AN EDGE CONNECTING v and w, we add w to vS ADJACENCY
list and v to wS ADJACENCY LIST 4HUS EACH EDGE APPEARS twice IN THE DATA STRUCTURE 4HIS
Graph IMPLEMENTATION ACHIEVES THE FOLLOWING PERFORMANCE CHARACTERISTICS
n 3PACE USAGE PROPORTIONAL TO V + E
n #ONSTANT TIME TO ADD AN EDGE
n 4IME PROPORTIONAL TO THE DEGREE OF v TO ITERATE THROUGH VERTICES ADJACENT TO v
CONSTANT TIME PER ADJACENT VERTEX PROCESSED
4HESE CHARACTERISTICS ARE OPTIMAL FOR THIS SET OF OPERATIONS WHICH SUFlCE FOR THE GRAPH
PROCESSING APPLICATIONS THAT WE CONSIDER 0ARALLEL EDGES AND SELF
LOOPS ARE ALLOWED WE
DO NOT CHECK FOR THEM Note )T IS IMPORTANT TO REALIZE THAT THE ORDER IN WHICH EDGES
ARE ADDED TO THE GRAPH DETERMINES THE ORDER IN WHICH VERTICES APPEAR IN THE ARRAY OF
ADJACENCY LISTS BUILT BY Graph -ANY DIFFERENT AR-
RAYS OF ADJACENCY LISTS CAN REPRESENT THE SAME GRAPH
7HEN USING THE CONSTRUCTOR THAT READS EDGES FROM
AN INPUT STREAM THIS MEANS THAT THE INPUT FORMAT
AND THE ORDER IN WHICH EDGES ARE SPECIlED IN THE
lLE DETERMINE THE ORDER IN WHICH VERTICES APPEAR
IN THE ARRAY OF ADJACENCY LISTS BUILT BY Graph 3INCE
OUR ALGORITHMS USE adj() AND PROCESS ALL ADJACENT
VERTICES WITHOUT REGARD TO THE ORDER IN WHICH THEY
APPEAR IN THE LISTS THIS DIFFERENCE DOES NOT AFFECT
THEIR CORRECTNESS BUT IT IS IMPORTANT TO BEAR IT IN
MIND WHEN DEBUGGING OR FOLLOWING TRACES 4O FA-
CILITATE THESE ACTIVITIES WE ASSUME THAT Graph HAS A
TEST CLIENT THAT READS A GRAPH FROM THE INPUT STREAM
NAMED AS COMMAND
LINE ARGUMENT AND THEN PRINTS
IT RELYING ON THE toString() IMPLEMENTATION ON
PAGE TO SHOW THE ORDER IN WHICH VERTICES AP-
PEAR IN ADJACENCY LISTS WHICH IS THE ORDER IN WHICH
ALGORITHMS PROCESS THEM SEE Exercise 4.1.7
13
13
0 5
4 3
0 1
9 12
6 4
5 4
0 2
11 12
9 10
0 6
7 8
9 11
5 3
% java Graph tinyG.txt
13 vertices, 13 edges
0: 6 2 1 5
1: 0
2: 0
3: 5 4
4: 5 6 3
5: 3 4 0
6: 0 4
7: 8
8: 7
9: 11 10 12
10: 9
11: 9 12
12: 11 9
tinyG.txt
Output for list-of-edges input
V
E
first adjacent
vertex in input
is last on list
second
representation
of each edge
appears in red
5254.1 n Undirected Graphs
Câu hỏi
Từ một đỉnh của đồ thị ta có thể đi tới những đỉnh nào?
10 / 58
Tìm đường trong mê cung
P1: OSO/OVY P2: OSO/OVY QC: OSO/OVY T1: OSO
das23402 Ch03 GTBL020-Dasgupta-v10 August 10, 2006 19:18
Chapter 3 Algorithms 83
Figure 3.2 Exploring a graph is rather like navigating a maze.
A
C
B
F
D
H I J
K
E
G
L
H
G
DA
C
F
K
L
J
I
B
E
3.2 Depth-first search in undirected graphs
3.2.1 Exploring mazes
Depth-first search is a surprisingly versatile linear-time procedure that reveals a
wealth of information about a graph. The most basic question it addresses is,
What parts of the graph are reachable from a given vertex?
To understand this task, try putting yourself in the position of a computer that has
just been given a new graph, say in the form of an adjacency list. This representation
offers just one basic operation: finding the neighbors of a vertex. With only this
primitive, the reachability problem is rather like exploring a labyrinth (Figure 3.2).
You start walking from a fixed place andwhenever you arrive at any junction (vertex)
there are a variety of passages (edges) you can follow. A careless choice of passages
might lead you around in circles or might cause you to overlook some accessible
part of the maze. Clearly, you need to record some intermediate information during
exploration.
This classic challenge has amused people for centuries. Everybody knows that all
you need to explore a labyrinth is a ball of string and a piece of chalk. The chalk
prevents looping, by marking the junctions you have already visited. The string
always takes you back to the starting place, enabling you to return to passages that
you previously saw but did not yet investigate.
How can we simulate these two primitives, chalk and string, on a computer? The
chalk marks are easy: for each vertex, maintain a Boolean variable indicating
whether it has been visited already. As for the ball of string, the correct cyber-
analog is a stack. After all, the exact role of the string is to offer two primitive
operations—unwind to get to a new junction (the stack equivalent is to push the
new vertex) and rewind to return to the previous junction (pop the stack).
Instead of explicitly maintaining a stack, we will do so implicitly via recursion
(which is implemented using a stack of activation records). The resulting algorithm
Hình: Tìm kiếm trên đồ thị cũng giống tìm đường trong mê cung
11 / 58
procedure explore(G, v)
Input: đồ thị G = (V,E); v ∈ V
Output: visited(u)=true với mọi đỉnh u có thể đến
được từ v
visited(v) = true
previsit(v)
for each edge (v, u) ∈ E:
if not visited(u): explore(G, u)
postvisit(v)
12 / 58
Ví dụ: Kết quả chạy explore(G,A)
P1: OSO/OVY P2: OSO/OVY QC: OSO/OVY T1: OSO
das23402 Ch03 GTBL020-Dasgupta-v10 August 10, 2006 19:18
Chapter 3 Algorithms 83
Figure 3.2 Exploring a graph is rather like navigating a maze.
A
C
B
F
D
H I J
K
E
G
L
H
G
DA
C
F
K
L
J
I
B
E
3.2 Depth-first search in undirected graphs
3.2.1 Exploring mazes
Depth-first search is a surprisingly versatile linear-time procedure that reveals a
wealth of information about a graph. The most basic question it addresses is,
What parts of the graph are reachable from a given vertex?
To understand this task, try putting yourself in the position of a computer that has
just been given a new graph, say in the form of an adjacency list. This representation
offers just one basic operation: finding the neighbors of a vertex. With only this
primitive, the reachability problem is rather like exploring a labyrinth (Figure 3.2).
You start walking from a fixed place andwhenever you arrive at any junction (vertex)
there are a variety of passages (edges) you can follow. A careless choice of passages
might lead you around in circles or might cause you to overlook some accessible
part of the maze. Clearly, you need to record some intermediate information during
exploration.
This classic challenge has amused people for centuries. Everybody knows that all
you need to explore a labyrinth is a ball of string and a piece of chalk. The chalk
prevents looping, by marking the junctions you have already visited. The string
always takes you back to the starting place, enabling you to return to passages that
you previously saw but did not yet investigate.
How can we simulate these two primitives, chalk and string, on a computer? The
chalk marks are easy: for each vertex, maintain a Boolean variable indicating
whether it has been visited already. As for the ball of string, the correct cyber-
analog is a stack. After all, the exact role of the string is to offer two primitive
operations—unwind to get to a new junction (the stack equivalent is to push the
new vertex) and rewind to return to the previous junction (pop the stack).
Instead of explicitly maintaining a stack, we will do so implicitly via recursion
(which is implemented using a stack of activation records). The resulting algorithm
P1: OSO/OVY P2: OSO/OVY QC: OSO/OVY T1: OSO
das23402 Ch03 GTBL020-Dasgupta-v10 August 10, 2006 19:18
Chapter 3 Algorithms 85
Figure 3.4 The result of explore(A) on the graph of Figure 3.2.
I
E
J
C
F
B
A
D
G
H
For instance, while B was being visited, the edge B − E was noticed and, since E
was as yet unknown, was traversed via a call to explore(E ). These solid edges
form a tree (a connected graph with no cycles) and are therefore called tree edges.
The dotted edges were ignored because they led back to familiar terrain, to vertices
previously visited. They are c lled back edges.
3.2.2 Depth-first search
The explore procedure visits only the portion of the graph reachable from its
starting point. To examine the rest of the graph, we need to restart the procedure
elsewhere, at some vertex that has not yet been visited. The algorithm of Figure 3.5,
called depth-first search (DFS), does this repea edly until the entire graph h been
traversed.
Figure 3.5 Depth-first search.
procedure dfs(G)
for all v ∈ V:
visited(v) = false
for all v ∈ V:
if not visited(v): explore(v)
The first step in analyzing the running time of DFS is to observe that each vertex is
explore’d just once, thanks to the visited array (the chalk marks). During the
exploration of a vertex, there are the following steps:
1. Some fixed amount of work—marking the spot as visited, and the
pre/postvisit.
13 / 58
Tìm kiếm theo chiều sâu
procedure dfs(G)
for all v ∈ V:
visited(v) = false
for all v ∈ V :
if not visited(v): explore(G, v)
14 / 58
Ví dụ: Đồ thị và Rừng DFS
P1: OSO/OVY P2: OSO/OVY QC: OSO/OVY T1: OSO
das23402 Ch03 GTBL020-Dasgupta-v10 August 10, 2006 19:18
86 3.2 Depth-first search in undirected graphs
2. A loop in which adjacent edges are scanned, to see if they lead somewhere
new.
This loop takes a different amount of time for each vertex, so let’s consider all
vertices together. The total work done in step 1 is then O(|V |). In step 2, over
the course of the entire DFS, each edge {x, y} ∈ E is examined exactly twice, once
during explore(x) and once during explore(y). The overall time for step 2 is
therefore O(|E |) and so the depth-first search has a running time of O(|V | + |E |),
linear in the size of its input. This is as efficient as we could possibly hope for, since
it takes this long even just to read the adjacency list.
Figure 3.6 (a) A 12-node graph. (b) DFS search forest.
(a)
A B C D
E F G H
I J K L
(b) A
B E
I
J G
K
FC
D
H
L
1,10
2,3
4,9
5,8
6,7
11,22 23,24
12,21
13,20
14,17
15,16
18,19
Figure 3.6 shows the outcome of depth-first search on a 12-node graph, once again
breaking ties alphabetically (ignore the pairs of numbers for the time being). The
outer loop of DFS calls explore three times, on A, C , and finally F . As a result,
there are three trees, each rooted at one of these starting points. Together they
constitute a forest.
3.2.3 Connectivity in undirected graphs
An undirected graph is connected if there is a path between any pair of vertices. The
graph of Figure 3.6 is not connected because, for instance, there is no path from A
to K . However, it does have three disjoint connected regions, corresponding to the
following sets of vertices:
{A, B, E , I , J } {C , D,G , H, K , L} {F }.
These regions are called connected components: each of them is a subgraph that is
internally connected but has no edges to the remaining vertices. When explore
is started at a particular vertex, it identifies precisely the connected component
containing that vertex. And each time the DFS outer loop calls explore, a new
connected component is picked out.
15 / 58
Bài tập
Xây dựng rừng DFS cho đồ thị sau với các đỉnh lấy theo thứ tự từ
điển. Vẽ cả những cạnh nét đứt.
16 / 58
Rừng DFS và số thành phần liên thông
P1: OSO/OVY P2: OSO/OVY QC: OSO/OVY T1: OSO
das23402 Ch03 GTBL020-Dasgupta-v10 August 10, 2006 19:18
86 3.2 Depth-first search in undirected graphs
2. A loop in which adjacent edges are scanned, to see if they lead somewhere
new.
This loop takes a different amount of time for each vertex, so let’s consider all
vertices together. The total work done in step 1 is then O(|V |). In step 2, over
the course of the entire DFS, each edge {x, y} ∈ E is examined exactly twice, once
during explore(x) and once during explore(y). The overall time for step 2 is
therefore O(|E |) and so the depth-first search has a running time of O(|V | + |E |),
linear in the size of its input. This is as efficient as we could possibly hope for, since
it takes this long even just to read the adjacency list.
Figure 3.6 (a) A 12-node graph. (b) DFS search forest.
(a)
A B C D
E F G H
I J K L
(b) A
B E
I
J G
K
FC
D
H
L
1,10
2,3
4,9
5,8
6,7
11,22 23,24
12,21
13,20
14,17
15,16
18,19
Figure 3.6 shows the outcome of depth-first search on a 12-node graph, once again
breaking ties alphabetically (ignore the pairs of numbers for the time being). The
outer loop of DFS calls explore three times, on A, C , and finally F . As a result,
there are three trees, each rooted at one of these starting points. Together they
constitute a forest.
3.2.3 Connectivity in undirected graphs
An undirected graph is connected if there is a path between any pair of vertices. The
graph of Figure 3.6 is not connected because, for instance, there is no path from A
to K . However, it does have three disjoint connected regions, corresponding to the
following sets of vertices:
{A, B, E , I , J } {C , D,G , H, K , L} {F }.
These regions are called connected components: each of them is a subgraph that is
internally connected but has no edges to the remaining vertices. When explore
is started at a particular vertex, it identifies precisely the connected component
containing that vertex. And each time the DFS outer loop calls explore, a new
connected component is picked out.
v ccnum[v]
A 1
B 1
C 2
D 2
E 1
F 3
G 2
H 2
I 1
J 1
Biến ccnum[v] để xác định thành phần liên thông của đỉnh v.
17 / 58
Tính liên thông trong đồ thị vô hướng
procedure dfs(G)
cc = 0
for all v ∈ V: visited(v) = false
for all v ∈ V:
if not visited(v):
cc = cc + 1
explore(G, v)
procedure explore(G, v)
visited(v) = true
previsit(v)
for each edge (v, u) ∈ E:
if not visited(u): explore(G, u)
postvisit(v)
procedure previsit(v)
ccnum[v] = cc
18 / 58
Bài tập
Hãy cài đặt chương trình tìm số thành phần liên thông của một đồ
thị vô hướng.
19 / 58
previsit và postvisit
▶ Lưu thời gian lần đầu đến đỉnh trong mảng pre
▶ Lưu thời gian lần cuối rời khỏi đỉnh trong mảng post
▶ Để tính hai thông tin này ta dùng một bộ đếm clock, khởi
tạo bằng 1, và được cập nhật như sau:
procedure previsit(v)
pre[v] = clock
clock = clock + 1
procedure postvisit(v)
post[v] = clock
clock = clock + 1
20 / 58
Bài tập
Vẽ rừng DFS với cả số pre và post cho mỗi đỉnh cho đồ thị sau.
21 / 58
Tính chất của previsit và postvisit
Mệnh đề
Với mọi đỉnh u và v, hai khoảng
[ pre(u), post(u) ] và [ pre(v), post(v) ]
▶ hoặc là rời nhau,
▶ hoặc là có một khoảng chứa một khoảng khác.
Tại sao? vì [ pre(u), post(u) ] là khoảng thời gian đỉnh u nằm
trong ngăn xếp. Cấu trúc vào-sau, ra-trước đảm bảo tính chất này.
22 / 58
Nội dung
Biểu diễn đồ thị
Tìm kiếm theo chiều sâu trên đồ thị vô hướng
Tìm kiếm theo chiều sâu trên đồ thị có hướng
Thành phần liên thông mạnh
Bài tập
Hãy vẽ rừng DFS với số pre và post trên mỗi đỉnh cho đồ thị có
hướng sau.
P1: OSO/OVY P2: OSO/OVY QC: OSO/OVY T1: OSO
das23402 Ch03 GTBL020-Dasgupta-v10 August 10, 2006 19:18
88 3.3 Depth-first search in directed graphs
Figure 3.7 DFS on a directed graph.
AB C
F DE
G H
A
H
B C
E D
F
G
12,15
13,14
1,16
2,11
4,7
5,6
8,9
3,10
In further analyzing the directed case, it helps to have terminology for important
relationships between nodes of a tree. A is the root of the search tree; everything
else is its descendant. Similarly, E has descendants F , G , and H , and conversely,
is an ancestor of these three nodes. The family analogy is carried further: C is the
parent of D, which is its child.
For undirected graphs we distinguished between tree edges and nontree edges. In
the directed case, there is a slightly more elaborate taxonomy:
B
ac
k
Forw
ard
Cross
Tr
ee
A
B
C D
DFS tree
Tree edges are actually part of the DFS forest.
Forward edges lead from a node to a nonchild descendant in
the DFS tree.
Back edges lead to an ancestor in the DFS tree.
Cross edges lead to neither descendant nor ancestor; they
therefore lead to a node that has already been completely
explored (that is, already postvisited).
Figure 3.7 has two forward edges, two back edges, and two cross edges. Can you
spot them?
Ancestor and descendant relationships, as well as edge types, can be read off directly
from pre and post numbers. Because of the depth-first exploration strategy, vertex
u is an ancestor of vertex v exactly in those cases where u is discovered first and
24 / 58
Lời giải
P1: OSO/OVY P2: OSO/OVY QC: OSO/OVY T1: OSO
das23402 Ch03 GTBL020-Dasgupta-v10 August 10, 2006 19:18
88 3.3 Depth-first search in directed graphs
Figure 3.7 DFS on a directed graph.
AB C
F DE
G H
A
H
B C
E D
F
G
12,15
13,14
1,16
2,11
4,7
5,6
8,9
3,10
In further analyzing the directed case, it helps to have terminology for important
relationships between nodes of a tree. A is the root of the search tree; everything
else is its descendant. Similarly, E has descendants F , G , and H , and conversely,
is an ancestor of these three nodes. The family analogy is carried further: C is the
parent of D, which is its child.
For undirected graphs we distinguished between tree edges and nontree edges. In
the directed case, there is a slightly more elaborate taxonomy:
B
ac
k
Forw
ard
Cross
Tr
ee
A
B
C D
DFS tree
Tree edges are actually part of the DFS forest.
Forward edges lead from a node to a nonchild descendant in
the DFS tree.
Back edges lead to an ancestor in the DFS tree.
Cross edges lead to neither descendant nor ancestor; they
therefore lead to a node that has already been completely
explored (that is, already postvisited).
Figure 3.7 has two forward edges, two back edges, and two cross edges. Can you
spot them?
Ancestor and descendant relationships, as well as edge types, can be read off directly
from pre and post numbers. Because of the depth-first exploration strategy, vertex
u is an ancestor of vertex v exactly in those cases where u is discovered first and
25 / 58
Các kiểu cạnh
P1: OSO/OVY P2: OSO/OVY QC: OSO/OVY T1: OSO
das23402 Ch03 GTBL020-Dasgupta-v10 August 10, 2006 19:18
88 3.3 Depth-first search in directed graphs
Figure 3.7 DFS on a directed graph.
AB C
F DE
G H
A
H
B C
E D
F
G
12,15
13,14
1,16
2,11
4,7
5,6
8,9
3,10
In further analyzing the directed case, it helps to have terminology for important
relationships between nodes of a tree. A is the root of the search tree; everything
else is its descendant. Similarly, E has descendants F , G , and H , and conversely,
is an ancestor of these three nodes. The family analogy is carried further: C is the
parent of D, which is its child.
For undirected graphs we distinguished between tree edges and nontree edges. In
the directed case, there is a slightly more elaborate taxonomy:
B
ac
k
Forw
ard
Cross
Tr
ee
A
B
C D
DFS tree
Tree edges are actually part of the DFS forest.
Forward edges lead from a node to a nonchild descendant in
the DFS tree.
Back edges lead to an ancestor in the DFS tree.
Cross edges lead to neither descendant nor ancestor; they
therefore lead to a node that has already been completely
explored (that is, already postvisited).
Figure 3.7 has two forward edges, two back edges, and two cross edges. Can you
spot them?
Ancestor and descendant relationships, as well as edge types, can be read off directly
from pre and post numbers. Because of the depth-first exploration strategy, vertex
u is an ancestor of vertex v exactly in those cases where u is discovered first and
Tree Edges (Cạnh cây) là cạnh thuộc
rừng DFS.
Forward Edges (Cạnh tới) là cạnh dẫn
từ một nút tới một nút con cháu của nó
nhưng không thuộc rừng DFS.
Back Edges (Cạnh ngược) là cạnh dẫn
từ một nút tới một tổ tiên của nó.
Cross Edges (Cạnh ngang) là cạnh dẫn
từ một nút tới một nút không phải tổ
tiên cũng k ông phải con cháu của nó.
26 / 58
Bài tập
Thực hiện thuật toán DFS trên mỗi đồ thị sau; nếu phải thực hiện
lựa chọn đỉnh, chọn đỉnh theo thứ tự từ điển. Phân loại mỗi cạnh
(tree edge, forward edge, back edge, hay cross edge) và đưa ra số
pre và post cho mỗi đỉnh.
27 / 58
Các khả năng cho cạnh (u, v)
Thứ tự pre/post của (u, v) Kiểu cạnh[
u
[
v
]
v
]
u Tree/forward[
v
[
u
]
u
]
v Back[
v
]
v
[
u
]
u Cross
Câu hỏi
Tại sao các kiểu thứ tự khác không thể xảy ra?
28 / 58
Mệnh đề
Một đồ thị có hướng có chu trình nếu và chỉ nếu thuật toán tìm
kiếm theo chiều sâu tạo ra back edge.
Chứng minh.
P1: OSO/OVY P2: OSO/OVY QC: OSO/OVY T1: OSO
das23402 Ch03 GTBL020-Dasgupta-v10 August 10, 2006 19:18
88 3.3 Depth-first search in directed graphs
Figure 3.7 DFS on a directed graph.
AB C
F DE
G H
A
H
B C
E D
F
G
12,15
13,14
1,16
2,11
4,7
5,6
8,9
3,10
In further analyzing the directed case, it helps to have terminology for important
relationships between nodes of a tree. A is the root of the search tree; everything
else is its descendant. Similarly, E has descendants F , G , and H , and conversely,
is an ancestor of these three nodes. The family analogy is carried further: C is the
parent of D, which is its child.
For undirected graphs we distinguished between tree edges and nontree edges. In
the directed case, there is a slightly more elaborate taxonomy:
B
ac
k
Forw
ard
Cross
Tr
ee
A
B
C D
DFS tree
Tree edges are actually part of the DFS forest.
Forward edges lead from a node to a nonchild descendant in
the DFS tree.
Back edges lead to an ancestor in the DFS tree.
Cross edges lead to neither descendant nor ancestor; they
therefore lead to a node that has already been completely
explored (that is, already postvisited).
Figure 3.7 has two forward edges, two back edges, and two cross edges. Can you
spot them?
Ancestor and descendant relationships, as well as edge types, can be read off directly
from pre and post numbers. Because of the depth-first exploration strategy, vertex
u is an ancestor of vertex v exactly in those cases where u is discovered first and
▶ Nếu (u, v) là back edge, thì
u; v→ u là một chu trình.
▶ Ngược lại, giả sử đồ thị có chu
trình
C = v0 → v1 → · · · → vk → v0.
Xét vi là đỉnh đầu tiên trong C
được thăm theo DFS. Mọi đỉnh
khác trong chu trình sẽ đạt được từ
vi. Vậy thì vi−1 → vi là back edge.
29 / 58
Bài tập
1. Hãy mô tả một thuật toán kiểm tra liệu đồ thị có hướng cho
trước có chu trình hay không.
2. Hãy cài đặt thuật toán này.
30 / 58
Đồ thị phi chu trình và sắp xếp topo
▶ Đồ thị phi chu trình (DAG) cho phép sắp thứ tự các đỉnh sao
cho:
Có cạnh (u, v) nếu và chỉ nếu u đứng trước v.
▶ Cách sắp thứ tự các đỉnh này gọi là sắp xếp topo.
▶ DAG cho phép mô hình hiệu quả các bài toán liên quan đến
quan hệ nhân quả, phân cấp, phụ thuộc thời gian.
▶ Ví dụ: Mỗi môn học có môn tiên quyết (môn cần học trước).
Một cách lựa chọn thứ tự học các môn là một cách sắp topo.
31 / 58
Đồ thị phi chu trình (DAG)
P1: OSO/OVY P2: OSO/OVY QC: OSO/OVY T1: OSO
das23402 Ch03 GTBL020-Dasgupta-v10 August 10, 2006 19:18
90 3.3 Depth-first search in directed graphs
Figure 3.8 A directed acyclic graph with one source, two sinks, and four
possible linearizations.
A
B
C
D
E
F
out of bed; you have to be out of bed, but not yet dressed, to take a shower; and so
on). The question then is, what is a valid order in which to perform the tasks?
Such constraints are conveniently represented by a directed graph in which each
task is a node, and there is an edge from u to v if u is a precondition for v. In other
words, before performing a task, all the tasks pointing to it must be completed. If this
graph has a cycle, there is no hope: no ordering can possibly work. If on the other
hand the graph is a dag, we would like if possible to linearize (or topologically sort)
it, to order the vertices one after the other in such a way that each edge goes from
an earlier vertex to a later vertex, so that all precedence constraints are satisfied. In
Figure 3.8, for instance, one valid ordering is B, A, D,C , E , F . (Can you spot the
other three?)
What types of dags can be linearized? Simple: All of them. And once again depth-
first search tells us exactly how to do it: simply perform tasks in decreasing or-
der of their post numbers. After all, the only edges (u, v) in a graph for which
post(u) <post(v) are back edges (recall the table of edge types on page 88)—and
we have seen that a dag cannot have back edges. Therefore:
Property In a dag, every edge leads to a vertex with a lower post number.
This gives us a linear-time algorithm for ordering the nodes of a dag. And, to-
gether with our earlier observations, it tells us that three rather different-sounding
properties—acyclicity, linearizability, and the absence of back edges during a depth-
first search—are in fact one and the same thing.
Since a dag is linearized by decreasing post numbers, the vertex with the smallest
post number comes last in this linearization, and it must be a sink—no outgoing
edges. Symmetrically, the one with the highest post is a source, a node with no
incoming edges.
Property Every dag has at least one source and at least one sink.
The guaranteed existence of a source suggests an alternative approach to lineariza-
tion:
Phi chu trình⇐⇒ Không có Back Edge⇐⇒ Sắp topo
32 / 58
Bài tập
Hãy đưa ra mọi cách sắp topo cho đồ thị phi chu trình sau:
P1: OSO/OVY P2: OSO/OVY QC: OSO/OVY T1: OSO
das23402 Ch03 GTBL020-Dasgupta-v10 August 10, 2006 19:18
90 3.3 Depth-first search in directed graphs
Figure 3.8 A directed acyclic graph with one source, two sinks, and four
possible linearizations.
A
B
C
D
E
F
out of bed; you have to be out of bed, but not yet dressed, to take a shower; and so
on). The question then is, what is a valid order in which to perform the tasks?
Such constraints are conveniently represented by a directed graph in which each
task is a node, and there is an edge from u to v if u is a precondition for v. In other
words, before performing a task, all the tasks pointing to it must be completed. If this
graph has a cycle, there is no hope: no ordering can possibly work. If on the other
hand the graph is a dag, we would like if possible to linearize (or topologically sort)
it, to order the vertices one after the other in such a way that each edge goes from
an earlier vertex to a later vertex, so that all precedence constraints are satisfied. In
Figure 3.8, for instance, one valid ordering is B, A, D,C , E , F . (Can you spot the
other three?)
What types of dags can be linearized? Simple: All of them. And once again depth-
first search tells us exactly how to do it: simply perform tasks in decreasing or-
der of their post numbers. After all, the only edges (u, v) in a graph for which
post(u) <post(v) are back edges (recall the table of edge types on page 88)—and
we have seen that a dag cannot have back edges. Therefore:
Property In a dag, every edge leads to a vertex with a lower post number.
This gives us a linear-time algorithm for ordering the nodes of a dag. And, to-
gether with our earlier observations, it tells us that three rather different-sounding
properties—acyclicity, linearizability, and the absence of back edges during a depth-
first search—are in fact one and the same thing.
Since a dag is linearized by decreasing post numbers, the vertex with the smallest
post number comes last in this linearization, and it must be a sink—no outgoing
edges. Symmetrically, the one with the highest post is a source, a node with no
incoming edges.
Property Every dag has at least one source and at least one sink.
The guaranteed existence of a source suggests an alternative approach to lineariza-
tion:
33 / 58
Tính chất của DAG
Mệnh đề
Trong DAG, nếu (u, v) ∈ E thì post(u) > post(v).
Vậy thì các đỉnh của DAG có thể sắp topo theo thứ tự giảm dần
của post.
34 / 58
Bài tập
Xét một DAG có pre và post như dưới đây. Hãy đưa ra một thứ
tự topo cho các đỉnh.
10
3 2
54
0 : [1, 12]
1 : [2, 7]
2 : [8, 9]
3 : [3, 6]
4 : [4, 5]
5 : [10, 11]
35 / 58
Bài tập
1. Hãy mô tả một thuật toán sắp Topo cho một DAG.
2. Hãy cài đặt thuật toán này.
36 / 58
Đỉnh nguồn và đỉnh hút
P1: OSO/OVY P2: OSO/OVY QC: OSO/OVY T1: OSO
das23402 Ch03 GTBL020-Dasgupta-v10 August 10, 2006 19:18
90 3.3 Depth-first search in directed graphs
Figure 3.8 A directed acyclic graph with one source, two sinks, and four
possible linearizations.
A
B
C
D
E
F
out of bed; you have to be out of bed, but not yet dressed, to take a shower; and so
on). The question then is, what is a valid order in which to perform the tasks?
Such constraints are conveniently represented by a directed graph in which each
task is a node, and there is an edge from u to v if u is a precondition for v. In other
words, before performing a task, all the tasks pointing to it must be completed. If this
graph has a cycle, there is no hope: no ordering can possibly work. If on the other
hand the graph is a dag, we would like if possible to linearize (or topologically sort)
it, to order the vertices one after the other in such a way that each edge goes from
an earlier vertex to a later vertex, so that all precedence constraints are satisfied. In
Figure 3.8, for instance, one valid ordering is B, A, D,C , E , F . (Can you spot the
other three?)
What types of dags can be linearized? Simple: All of them. And once again depth-
first search tells us exactly how to do it: simply perform tasks in decreasing or-
der of their post numbers. After all, the only edges (u, v) in a graph for which
post(u) <post(v) are back edges (recall the table of edge types on page 88)—and
we have seen that a dag cannot have back edges. Therefore:
Property In a dag, every edge leads to a vertex with a lower post number.
This gives us a linear-time algorithm for ordering the nodes of a dag. And, to-
gether with our earlier observations, it tells us that three rather different-sounding
properties—acyclicity, linearizability, and the absence of back edges during a depth-
first search—are in fact one and the same thing.
Since a dag is linearized by decreasing post numbers, the vertex with the smallest
post number comes last in this linearization, and it must be a sink—no outgoing
edges. Symmetrically, the one with the highest post is a source, a node with no
incoming edges.
Property Every dag has at least one source and at least one sink.
The guaranteed existence of a source suggests an alternative approach to lineariza-
tion:
Trong đồ thị có hướng,
▶ Đỉnh nguồn (source) là đỉnh không có cạnh đi vào.
▶ Đỉnh hút (sink) là đỉnh không có cạnh đi ra.
37 / 58
Tính chất của DAG
Mệnh đề (Nhắc lại)
Trong DAG, nếu (u, v) ∈ E thì post(u) > post(v).
Vậy thì các đỉnh của DAG có thể sắp topo theo thứ tự giảm dần
của post.
Và khi đó, đỉnh có post nhỏ nhất sẽ nằm cuối danh sách, và vậy
thì nó phải là đỉnh hút.
Tương tự, đỉnh có post lớn nhất là đỉnh nguồn.
38 / 58
Mệnh đề
Mọi DAG đều có ít nhất một đỉnh nguồn và ít nhất một đỉnh hút.
Bài tập
Hãy chứng minh mệnh đề trên.
39 / 58
Thuật toán sắp topo (thứ 2)
▶ Tìm một đỉnh nguồn, ghi ra nó, và xóa nó khỏi đồ thị.
▶ Lặp lại cho đến khi đồ thị trở thành rỗng.
40 / 58
Thuật toán sắp topo (thứ 2)
▶ Tìm một đỉnh nguồn, ghi ra nó, và xóa nó khỏi đồ thị.
▶ Lặp lại cho đến khi đồ thị trở thành rỗng.
41 / 58
Thuật toán sắp topo (thứ 2)
▶ Tìm một đỉnh nguồn, ghi ra nó, và xóa nó khỏi đồ thị.
▶ Lặp lại cho đến khi đồ thị trở thành rỗng.
42 / 58
Thuật toán sắp topo (thứ 2)
▶ Tìm một đỉnh nguồn, ghi ra nó, và xóa nó khỏi đồ thị.
▶ Lặp lại cho đến khi đồ thị trở thành rỗng.
43 / 58
Bài tập
Chạy thuật toán sắp topo trên đồ thị sau:
1. Chỉ ra số pre và post của mỗi đỉnh.
2. Tìm các đỉnh nguồn và đỉnh hút của đồ thị.
3. Tìm thứ tự topo theo thuật toán.
4. Đồ thị này có bao nhiêu thứ tự topo?
44 / 58
Câu hỏi
▶ Tại sao thuật toán trước cho một thứ tự topo?
▶ Nếu đồ thị có chu trình thì thuật toán gặp vấn gì?
▶ Làm thế nào để cài đặt thuật toán này trong thời gian tuyến
tính?
45 / 58
Nội dung
Biểu diễn đồ thị
Tìm kiếm theo chiều sâu trên đồ thị vô hướng
Tìm kiếm theo chiều sâu trên đồ thị có hướng
Thành phần liên thông mạnh
Thành phần liên thông mạnh
Định nghĩa
Hai đỉnh u và v của một đồ thị có hướng là liên thông nếu có một
đường đi từ u tới v và một đường đi từ v tới u.
Quan hệ này phân hoạch tập đỉnh V thành các tập rời nhau và ta
gọi các tập rời nhau này là các thành phần liên thông mạnh.
47 / 58
Thành phần liên thông mạnh
P1: OSO/OVY P2: OSO/OVY QC: OSO/OVY T1: OSO
das23402 Ch03 GTBL020-Dasgupta-v10 August 10, 2006 19:18
Chapter 3 Algorithms 91
Find a source, output it, and delete it from the graph.
Repeat until the graph is empty.
Can you see why this generates a valid linearization for any dag? What happens if
the graph has cycles? And, how can this algorithm be implemented in linear time?
(Exercise 3.14.)
3.4 Strongly connected components
3.4.1 Defining connectivity for directed graphs
Connectivity in undirected graphs is pretty straightforward: a graph that is not con-
nected can be decomposed in a natural and obvious manner into several connected
components (Figure 3.6 is a case in point). As we saw in Section 3.2.3, depth-first
search does this handily, with each restart marking a new connected component.
In directed graphs, connectivity is more subtle. In some primitive sense, the directed
graph of Figure 3.9(a) is “connected”—it can’t be “pulled apart,” so to speak, with-
out breaking edges. But this notion is hardly interesting or informative. The graph
cannot be considered connected, because for instance there is no path from G
to B or from F to A. The right way to define connectivity for directed graphs is
this:
Two nodes u and v of a directed graph are connected if there is a path from u to
v and a path from v to u.
Figure 3.9 (a) A directed graph and its strongly connected components. (b) The
meta-graph.
(a)
A
D E
C
F
B
HG
K
L
JI
(b)
A B,E C,F
D
J,K,L
G,H,I
Hình: (a) Đồ thị có hướng và các thành phần liên thông mạnh. (b) Các
thành phần liên thông mạnh tạo thành một DAG
48 / 58
Các thành phần liên thông mạnh trong đồ thị
Mệnh đề
Mọi đồ thị có hướng đều là một DAG của các thành phần liên
thông mạnh.
Vì nếu có chu trình đi qua một số thành phần liên thông mạnh thì
các thành phần này phải được gộp chung lại thành một thành
phần liên thông mạnh.
49 / 58
Một số tính chất
Mệnh đề
Nếu thủ tục con explore bắt
đầu từ một đỉnh u, thì nó sẽ
kết thúc khi mọi đỉnh có thể
đến được từ u đã được thăm.
50 / 58
Một số tính chất
Nếu ta gọi explore từ một đỉnh
thuộc một thành phần liên thông
mạnh hút, vậy thì ta sẽ nhận
được đúng thành phần này.
51 / 58
Câu hỏi
1. Làm thế nào ta có thể tìm
được một đỉnh mà ta chắc
chắn nó thuộc vào thành phần
liên thông mạnh hút?
2. Ta sẽ tiếp tục thế nào khi
đã tìm được một thành phần
liên thông mạnh?
52 / 58
Câu hỏi 1
Làm thế nào ta có thể tìm được một đỉnh mà ta chắc chắn nó
thuộc vào thành phần liên thông mạnh hút?
Xét GR là đồ thị ngược của G, tức là đồ thị GR đạt được từ G
bằng cách đảo hướng các cạnh.
Thành phần liên thông mạnh của G cũng là của GR. Tại sao?
Và thành phần liên thông mạnh hút trong G sẽ là thành phần liên
thông mạnh nguồn trong GR.
Mệnh đề
Đỉnh có số post lớn nhất theo DFS phải thuộc một thành phần
liên thông mạnh nguồn.
53 / 58
Hình: Đồ thị G Hình: Đồ thị ngược GR của G
54 / 58
Câu hỏi 2
Ta sẽ tiếp tục thế nào khi đã tìm được một thành phần liên thông
mạnh?
Mệnh đề
Nếu C và D là các thành phần liên thông mạnh, và có một cạnh
từ một đỉnh trong C tới một đỉnh trong D, vậy thì số post lớn
nhất trong C phải lớn hơn số post lớn nhất trong D.
Khi ta tìm thấy một thành phần liên thông mạnh và xóa nó khỏi
đồ thị G, vậy thì đỉnh với số post lớn nhất trong các đỉnh còn lại
sẽ thuộc vào thành phần liên thông mạnh hút của đồ thị còn lại
của G.
55 / 58
Thuật toán tìm thành phần liên thông mạnh
1. Chạy DFS trên đồ thị ngược GR của G.
2. Chạy thuật toán tìm thành phần liên thông (tương tự như của
đồ thị vô hướng) trên đồ thị có hướng G;
và trong khi chạy DFS, xử lý các đỉnh theo thức tự giảm dần
theo số post của mỗi đỉnh (tìm được theo bước 1).
56 / 58
Bài tập
Chạy thuật toán tìm thành phần liên thông mạnh trên đồ thị sau.
57 / 58
Bài tập
Chạy thuật toán tìm thành phần liên thông mạnh trên đồ thị sau.
58 / 58
Các file đính kèm theo tài liệu này:
- bai_giang_toan_roi_rac_bai_17_phan_2_tim_kiem_tren_do_thi_tr.pdf