Bridges and Cut Vertices

Август 8, 2022

Главная
Информатика
Bridges and Cut Vertices

Содержание

2. Definitions Bridge – an edge of a graph whose deletion increases the number of connected components.
3. Example - Bridges
4. Example – Cut Vertices
5. Definitions for Depth-First-Search in undirected graph Tree edge – edge to unvisited vertex. Back edge –
6. Algorithm - Bridges
7. Implementation - Bridges void dfs(int v, int p = -1) { used[v] = true; tin[v] =
8. Algorithm – Cut Vertices
9. Implementation – Cut Vertices void dfs(int v, int p = -1) { used[v] = true; tin[v]
11. Скачать презентацию

Слайд 2

Definitions
Bridge – an edge of a graph whose deletion increases the

number of connected components.
Cut vertex – a vertex whose deletion increases the number of connected components.

Слайд 3

Example - Bridges

Слайд 4

Example – Cut Vertices

Слайд 5

Definitions for Depth-First-Search in undirected graph
Tree edge – edge to unvisited

vertex.
Back edge – edge to visited vertex.
Parent edge – edge to parent vertex.

Слайд 6

Algorithm - Bridges

Слайд 7

Implementation - Bridges
void dfs(int v, int p = -1) {
used[v] =

true;
tin[v] = fup[v] = timer++;
for (size_t i = 0; iint to = g[v][i];
if (to == p) continue; // Parent edge
if (used[to]) // Back edge
fup[v] = min(fup[v], tin[to]);
else { // Tree edge
dfs(to, v);
fup[v] = min(fup[v], fup[to]);
if (fup[to] > tin[v])
IS_BRIDGE(v, to);
}
}
}

Слайд 8

Algorithm – Cut Vertices

Слайд 9

Implementation – Cut Vertices
void dfs(int v, int p = -1) {
used[v]

= true;
tin[v] = fup[v] = timer++;
int children = 0; // Number of children
for (size_t i = 0; iint to = g[v][i];
if (to == p) continue; // Parent edge
if (used[to]) // Back edge
fup[v] = min(fup[v], tin[to]);
else { // Tree edge
dfs(to, v);
fup[v] = min(fup[v], fup[to]);
if (fup[to] >= tin[v] && p != -1)
IS_CUTPOINT(v);
++children;
}
}
if (p == -1 && children > 1) // If root
IS_CUTPOINT(v);
}