APPLIED ALGORITHMS
CONTENTS
• The longest path on a tree (Đường đi dài nhất trên cây)
• Total path length on the tree (Tổng đường đi trên cây)
APPLIED ALGORITHMS
DEPTH FIRST SEARCH (DFS) AND APPLICATIONS
3 4
THE LONGEST PATH ON THE TREE THE LONGEST PATH ON THE TREE
• Given a tree T = (V, E), each edge (u,v) has weight w(u,v). Find the path with the Init(V, A) { LongestPathOnTree(V, A){
longest length on T (the length of the path is the sum of weight on all edges of the for v in V do d[v] = -1; Init(V, A);
path). } s = select a node in V;
DFS(u) { DFS(s);
• Denote A[v] is the set of vertices adjacent to vertex v on T for x in A[u] do { x = select u in V such that d[u] is maximal;
• The algorithm is based on depth-first-search (DFS) if d[x] < 0 then { Init(V, A);
d[x] = d[u] + w(u,x); DFS(x);
• Choose an arbitrary vertex s on T DFS(x); y = select u in V such that d[u] is maximal;
• Perform DFS(s) to find vertex x farthest from s } P = unique path between x and y in T;
• Perform DFS(x) to find the vertex y that is farthest from x } return P;
• The path from x to y found will be the longest path on T } }
5 6
THE LONGEST PATH ON THE TREE TOTAL PATH LENGTH ON THE TREE
• The complexity: O(|V| + |E|) • Given a tree T = (V, E), each edge (u,v) has weight w(u,v). Vertex set V includes n vertices.
• Denote:
• A[v]: is the set of vertices adjacent to vertex v on T
• c(u,v) is the length of the unique path between two vertices u and v on T
• f(u): total path length from other vertices to u on T: f(u) = ∑ 𝑐(𝑣, 𝑢)
• Find f(u) for every u V
7 8
TOTAL PATH LENGTH ON THE TREE TOTAL PATH LENGTH ON THE TREE
• Choose an arbitrary vertex s on T as the root, perform DFS on T starting from s: • DFS1(u): depth-first search in the first phase
• p(u): parent vertex of u (the vertex from which the algorithm visits u) • Purpose: calculate d(x) and N(x) for all vertices x that are descendants of u
• When DFS1(u) is completed, d(u) is calculated and it will be used to calculate d(p(u))
• d(u): total path length from descendant vertices of u to u
• Do: for each vertex v A[u]:
• N(u): number of descendant vertices of u (including vertex u) • Call DFS1(v)
• Update: d(u) = d(u) + N(v)*d(v)
• N(u) = N(u) + N(v)
9 10
TOTAL PATH LENGTH ON THE TREE TOTAL PATH LENGTH ON THE TREE
• DFS1(u): depth-first search in the first phase DFS1(u){ DFS2(u){
for v in A[u] do { for v in A[u] do {
• Purpose: calculate d(x) and N(x) for all vertices x that are descendants of u
if p(v) = 0 then { if p(v) = 0 then {
• When DFS1(u) is completed, d(u) is calculated and it will be used to calculate d(p(u))
p(v) = u; F = f(u) – (d(v) + N(v)*w(u,v));
• Do: for each vertex v A[u]:
DFS1(v); f(v) = F + d(v) + w(u,v)*(n – N(v));
• Call DFS1(v)
d(u) = d(u) + d(v) + N(v)*w(u,v); p(v) = u; DFS2(v);
• Update: d(u) = d(u) + N(v)*d(v)
N(u) = N(u) + N(v); }
• N(u) = N(u) + N(v)
} }
• DFS2(u): depth-first search in the second phase } }
• Purpose: When DFS2(u) is called, f(u) has been already calculated and we will calculate f(v) for } Phase2(){
each vertex v being a child of u Phase1(){ for v in V do { p(v) = 0; }
• Do: for each vertex v A[u] not has been visited for v in V do { f(1) = d(1); p(1) = 1; DFS2(1);
• F = f(u) – (d(v) + w(u,v)*N(v)) p(v) = 0; d(v) = 0; N(v) = 1; f(v) = 0; }
• f(v) = F + d(v) + w(u,v)*(n – N(v)) } Main(){
• Call DFS2(v) p(1) = 1; DFS1(1); Phase1(); Phase2();
} }
11 12
TOTAL PATH LENGTH ON THE TREE
• The complexity: O(|V| + |E|)
THANK YOU !
13 14
