Презентация на тему Bridges and Cut Vertices

Содержание

2. DefinitionsBridge – an edge of a graph
3. Example - Bridges
4. Example – Cut Vertices
5. Definitions for Depth-First-Search in undirected graphTree edge
6. Algorithm - Bridges
7. Implementation - Bridgesvoid dfs(int v, int p
8. Algorithm – Cut Vertices
9. Implementation – Cut Verticesvoid dfs(int v, int
10. Скачать презентацию
11. Похожие презентации

DefinitionsBridge – 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.

Bridges and Cut VerticesLyzhin Ivan, 2016

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

Implementation - Bridgesvoid dfs(int v, int p = -1) {used[v] = true;tin[v]

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

Additional links and home taskBridge searching http://e-maxx.ru/algo/bridge_searchingCut vertex searching http://e-maxx.ru/algo/cutpointsTasks http://codeforces.com/group/Hq4vrJcA4s/contest/100703/problem/E

Слайды презентации

Слайд 2 Definitions
Bridge – an edge of a graph whose

DefinitionsBridge – an edge of a graph whose deletion increases the

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 =

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

-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);
}