Introducción a los Grafos y Algoritmos
Cargado por
Bryan Tony Cipriano TarazonaIntroducción a los Grafos y Algoritmos
Cargado por
Bryan Tony Cipriano TarazonaGrafos
Román Castellarin
1
Definiciones básicas
Representación
DFS/BFS
Aplicaciones
Disjoint Sets
MST
Dijkstra
Floyd-Warshall
2
¿Qué son?
Puntitos y rayitas.
Más formalmente, un grafo G = (V, E) consiste de un conjunto V de vértices,
y un conjunto E de aristas que conectan cada una dos vértices.
Generalmente llamamos N = |V| y M = |E|.
3
Grafos
Un grafo es dirigido si las aristas están orientadas.
(Generalmente las llamamos arcos).
Es no dirigido si no importa la dirección.
4
Grafos
Un grafo está ponderado si las aristas tienen pesos (etiquetas numéricas)
asociados. Algunas veces aparecen pesos en los vértices.
10
5
25
30
7
3
5
Grafos
En un grafo no dirigido, una componente (débilmente) conexa es un
conjunto conectado de vértices.
6
Grafos
Para los grafos dirigidos, además, una componente fuertemente conexa
es un conjunto maximal de vértices tales que para todo par u, v en dicha
componente, existe el camino u ↝ v.
7
Grafos
Un grafo es simple si no tiene bucles ni aristas paralelas.
Bucle
Aristas paralelas
8
Ejemplos
Podemos representar una red social como un grafo no dirigido.
Cada vértice es una persona, y hay una arista entre u y v si son amigos.
Cada clique es un grupo de amigos.
9
Ejemplos
Podemos representar una red social como un grafo no dirigido.
Cada vértice es una persona, y hay una arista entre u y v si son amigos.
Los vértices de alto grado son influencers
(el grado de un vértice es la cantidad
de aristas que inciden en él)
10
Representación 11
Lista de Incidencias
Es la forma más usual en la que aparecen los grafos en los archivos de
entrada. Consiste en una simple lista de aristas, usualmente precedida de
la cantidad de vértices y aristas. 2
56
4
01
03
40 0
3
34
1
23
24
12
Lista de Incidencias
struct edge{
int a, b;
};
int N, M; 2
vector<edge> E;
… 4
cin>>N>>M;
forn(i, M){
int a, b; 0
cin >> a >> b; 3
E.push_back({a,b}); 1
}
13
Matriz de Adyacencia
Consiste en una matriz A de NxN tal que A[i][j] = 1 sii hay una arista (i, j)
int A[MAXN][MAXN]; 2
4
0 1 0 1 0
0 0 0 0 0
0 0 0 1 1 0
3
0 0 0 0 1
1
1 0 0 0 0
14
Matriz de Adyacencia
int N, M;
int A[MAXN][MAXN];
… 2
cin>>N>>M; 4
forn(i, M){
int a, b;
cin >> a >> b;
A[a][b] = 1; 0
} 3
15
Lista de Adyacencias
Es la forma preferida por los algoritmos de grafos más comunes.
Para cada vértice, guardar una lista de sus vecinos.
2
vector<int> G[MAXN];
4
0: 1, 3
1: 0
3
2: 3, 4
1
3: 4
4: 0
16
Lista de Adyacencias
int N, M;
vector<int> G[MAXN];
… 2
cin>>N>>M; 4
forn(i, M){
int a, b;
cin >> a >> b;
G[a].push_back(b); 0
} 3
17
Representaciones
Memoria Iterar vecinos de v Verificar si existe la arista u-v
Lista de Incidencias O(M) O(M) O(M)
Matriz de Adyacencia O(N2) O(N) O(1)
Lista de Adyacencias O(N+M) O(𝛿v) O(min(𝛿u, 𝛿v))
𝛿v : grado de v (cantidad de vecinos)
18
DFS/BFS
gato luego de aprender
BFS
19
Caminos
Un camino u-w es una secuencia de vértices u = v0, v1, .., vn= w adyacentes.
Un ciclo es un camino que comienza y termina en el mismo vértice.
La longitud de un camino es la cantidad de aristas en él.
Por lo tanto, todo bucle es un camino de longitud 1.
La distancia entre u y w es la longitud del menor camino u-w.
¿Cómo detectamos ciclos?
¿Cómo calculamos distancias?
20
DFS
Un recorrido por profundidad (depth-first search) comienza en un vértice
inicial y visita recursivamente todos los vértices no visitados.
2
void dfs(int v){ 5
color[v] = GRIS; 4
for(auto &w: G[v])
if( color[w] == BLANCO ) 0
3
dfs(w);
1
color[v] = NEGRO;
}
21
DFS
Un recorrido por profundidad (depth-first search) comienza en un vértice
inicial y visita recursivamente todos los vértices no visitados.
2
void dfs(int v){ 5
color[v] = GRIS; 4
for(auto &w: G[v])
if( color[w] == BLANCO ) 0
3
dfs(w);
1
color[v] = NEGRO;
}
22
DFS
Un recorrido por profundidad (depth-first search) comienza en un vértice
inicial y visita recursivamente todos los vértices no visitados.
2
void dfs(int v){ 5
color[v] = GRIS; 4
for(auto &w: G[v])
if( color[w] == BLANCO ) 0
3
dfs(w);
1
color[v] = NEGRO;
}
23
DFS
Un recorrido por profundidad (depth-first search) comienza en un vértice
inicial y visita recursivamente todos los vértices no visitados.
2
void dfs(int v){ 5
color[v] = GRIS; 4
for(auto &w: G[v])
if( color[w] == BLANCO ) 0
3
dfs(w);
1
color[v] = NEGRO;
}
24
DFS
Un recorrido por profundidad (depth-first search) comienza en un vértice
inicial y visita recursivamente todos los vértices no visitados.
2
void dfs(int v){ 5
color[v] = GRIS; 4
for(auto &w: G[v])
if( color[w] == BLANCO ) 0
3
dfs(w);
1
color[v] = NEGRO;
}
25
DFS
Un recorrido por profundidad (depth-first search) comienza en un vértice
inicial y visita recursivamente todos los vértices no visitados.
2
void dfs(int v){ 5
color[v] = GRIS; 4
for(auto &w: G[v])
if( color[w] == BLANCO ) 0
3
dfs(w);
1
color[v] = NEGRO;
}
26
DFS
Un recorrido por profundidad (depth-first search) comienza en un vértice
inicial y visita recursivamente todos los vértices no visitados.
2
void dfs(int v){ 5
color[v] = GRIS; 4
for(auto &w: G[v])
if( color[w] == BLANCO ) 0
3
dfs(w);
1
color[v] = NEGRO;
}
27
DFS
Un recorrido por profundidad (depth-first search) comienza en un vértice
inicial y visita recursivamente todos los vértices no visitados.
2
void dfs(int v){ 5
color[v] = GRIS; 4
for(auto &w: G[v])
if( color[w] == BLANCO ) 0
3
dfs(w);
1
color[v] = NEGRO;
}
28
DFS
Un recorrido por profundidad (depth-first search) comienza en un vértice
inicial y visita recursivamente todos los vértices no visitados.
2
void dfs(int v){ 5
color[v] = GRIS; 4
for(auto &w: G[v])
if( color[w] == BLANCO ) 0
3
dfs(w);
1
color[v] = NEGRO;
}
29
DFS
Un recorrido por profundidad (depth-first search) comienza en un vértice
inicial y visita recursivamente todos los vértices no visitados.
2
void dfs(int v){ 5
color[v] = GRIS; 4
for(auto &w: G[v])
if( color[w] == BLANCO ) 0
3
dfs(w);
1
color[v] = NEGRO;
}
30
DFS
Un recorrido por profundidad (depth-first search) comienza en un vértice
inicial y visita recursivamente todos los vértices no visitados.
2
void dfs(int v){ 5
color[v] = GRIS; 4
for(auto &w: G[v])
if( color[w] == BLANCO ) 0
3
dfs(w);
1
color[v] = NEGRO;
}
31
DFS
Un recorrido por profundidad (depth-first search) comienza en un vértice
inicial y visita recursivamente todos los vértices no visitados.
2
void dfs(int v){ 5
color[v] = GRIS; 4
for(auto &w: G[v])
if( color[w] == BLANCO ) 0
3
dfs(w);
1
color[v] = NEGRO;
}
32
DFS
Un recorrido por profundidad (depth-first search) comienza en un vértice
inicial y visita recursivamente todos los vértices no visitados.
2
void dfs(int v){ 5
color[v] = GRIS; 4
for(auto &w: G[v])
if( color[w] == BLANCO ) 0
3
dfs(w);
1
color[v] = NEGRO;
}
33
DFS
Podemos detectar ciclos en un grafo no dirigido si encontramos un vecino
no visitado que no sea mi padre (es decir, aquél de donde vine).
bool hasCycle(int v, int p=-1){
visited[v] = true; // más fácil que guardar colores
bool cycle = false;
for(auto &w: G[v])
if( not visited[w] )
cycle |= hasCycle(w, v);
else if( w != p )
cycle = true;
return cycle;
}
34
DFS
Podemos detectar ciclos en un grafo dirigido si encontramos una
back-edge (arco a un vértice gris).
bool hasCycle(int v){
color[v] = GRIS;
bool cycle = false;
for(auto &w: G[v])
if( color[w] == BLANCO )
cycle |= hasCycle(w);
else if( color[w] == GRIS )
cycle = true;
return cycle;
}
35
BFS
Un recorrido por anchura (breadth-first search) comienza en un vértice
inicial y visita a los vértices por distancia
void bfs(int inicial){ Entendido como 2
queue<int> Q; cantidad de arcos 5
[Link](inicial);
color[inicial] = GRIS; 4
while(not [Link]()){
int v = [Link](); [Link]();
G[v] = NEGRO;
for(auto &w: G[v]) 0
if( color[w] == BLANCO ){ 3
[Link](w);
1
color[w] = GRIS;
}
}
} 36
BFS
Un recorrido por anchura (breadth-first search) comienza en un vértice
inicial y visita a los vértices por distancia
void bfs(int inicial){ 2
queue<int> Q; 5
[Link](inicial);
color[inicial] = GRIS; 4
while(not [Link]()){
int v = [Link](); [Link]();
G[v] = NEGRO;
for(auto &w: G[v]) 0
if( color[w] == BLANCO ){ 3
[Link](w);
1
color[w] = GRIS;
}
}
} 37
BFS
Un recorrido por anchura (breadth-first search) comienza en un vértice
inicial y visita a los vértices por distancia
void bfs(int inicial){ 2
queue<int> Q; 5
[Link](inicial);
color[inicial] = GRIS; 4
while(not [Link]()){
int v = [Link](); [Link]();
G[v] = NEGRO;
for(auto &w: G[v]) 0
if( color[w] == BLANCO ){ 3
[Link](w);
1
color[w] = GRIS;
}
}
} 38
BFS
Un recorrido por anchura (breadth-first search) comienza en un vértice
inicial y visita a los vértices por distancia
void bfs(int inicial){ 2
queue<int> Q; 5
[Link](inicial);
color[inicial] = GRIS; 4
while(not [Link]()){
int v = [Link](); [Link]();
G[v] = NEGRO;
for(auto &w: G[v]) 0
if( color[w] == BLANCO ){ 3
[Link](w);
1
color[w] = GRIS;
}
}
} 39
BFS
Un recorrido por anchura (breadth-first search) comienza en un vértice
inicial y visita a los vértices por distancia
void bfs(int inicial){ 2
queue<int> Q; 5
[Link](inicial);
color[inicial] = GRIS; 4
while(not [Link]()){
int v = [Link](); [Link]();
G[v] = NEGRO;
for(auto &w: G[v]) 0
if( color[w] == BLANCO ){ 3
[Link](w);
1
color[w] = GRIS;
}
}
} 40
BFS
Un recorrido por anchura (breadth-first search) comienza en un vértice
inicial y visita a los vértices por distancia
void bfs(int inicial){ 2
queue<int> Q; 5
[Link](inicial);
color[inicial] = GRIS; 4
while(not [Link]()){
int v = [Link](); [Link]();
G[v] = NEGRO;
for(auto &w: G[v]) 0
if( color[w] == BLANCO ){ 3
[Link](w);
1
color[w] = GRIS;
}
}
} 41
BFS
Un recorrido por anchura (breadth-first search) comienza en un vértice
inicial y visita a los vértices por distancia
void bfs(int inicial){ 2
queue<int> Q; 5
[Link](inicial);
color[inicial] = GRIS; 4
while(not [Link]()){
int v = [Link](); [Link]();
G[v] = NEGRO;
for(auto &w: G[v]) 0
if( color[w] == BLANCO ){ 3
[Link](w);
1
color[w] = GRIS;
}
}
} 42
BFS
Un recorrido por anchura (breadth-first search) comienza en un vértice
inicial y visita a los vértices por distancia
void bfs(int inicial){ 2
queue<int> Q; 5
[Link](inicial);
color[inicial] = GRIS; 4
while(not [Link]()){
int v = [Link](); [Link]();
G[v] = NEGRO;
for(auto &w: G[v]) 0
if( color[w] == BLANCO ){ 3
[Link](w);
1
color[w] = GRIS;
}
}
} 43
BFS
Un recorrido por anchura (breadth-first search) comienza en un vértice
inicial y visita a los vértices por distancia
void bfs(int inicial){ 2
queue<int> Q; 5
[Link](inicial);
color[inicial] = GRIS; 4
while(not [Link]()){
int v = [Link](); [Link]();
G[v] = NEGRO;
for(auto &w: G[v]) 0
if( color[w] == BLANCO ){ 3
[Link](w);
1
color[w] = GRIS;
}
}
} 44
BFS
Un recorrido por anchura (breadth-first search) comienza en un vértice
inicial y visita a los vértices por distancia
void bfs(int inicial){ 2
queue<int> Q; 5
[Link](inicial);
color[inicial] = GRIS; 4
while(not [Link]()){
int v = [Link](); [Link]();
G[v] = NEGRO;
for(auto &w: G[v]) 0
if( color[w] == BLANCO ){ 3
[Link](w);
1
color[w] = GRIS;
}
}
} 45
BFS
Podemos calcular dichas distancias en un vector D, y los padres en P.
void bfs(int inicial){
queue<int> Q; D[5] = -1
[Link](inicial); 2 D[4] = -1 P[5] = -1
D[2] = -1
D[inicial] = 0; P[2] = -1 P[4] = -1 5
while(not [Link]()){
int v = [Link](); [Link](); 4
for(auto &w: G[v])
if( D[w] == -1 ){
[Link](w); 0 D[0] = -1
D[w] = D[v] + 1; P[0] = -1
3
P[w] = v;
} D[3] = -1 1
} P[3] = -1
} D[1] = -1
P[1] = -1
46
BFS
Podemos calcular dichas distancias en un vector D, y los padres en P.
void bfs(int inicial){
queue<int> Q; D[5] = -1
[Link](inicial); 2 D[4] = -1 P[5] = -1
D[2] = -1
D[inicial] = 0; P[2] = -1 P[4] = -1 5
while(not [Link]()){
int v = [Link](); [Link](); 4
for(auto &w: G[v])
if( D[w] == -1 ){
[Link](w); 0 D[0] = -1
D[w] = D[v] + 1; P[0] = -1
3
P[w] = v;
} D[3] = 0 1
} P[3] = -1
} D[1] = -1
P[1] = -1
47
BFS
Podemos calcular dichas distancias en un vector D, y los padres en P.
void bfs(int inicial){
queue<int> Q; D[5] = -1
[Link](inicial); 2 D[4] = -1 P[5] = -1
D[2] = -1
D[inicial] = 0; P[2] = -1 P[4] = -1 5
while(not [Link]()){
int v = [Link](); [Link](); 4
for(auto &w: G[v])
if( D[w] == -1 ){
[Link](w); 0 D[0] = 1
D[w] = D[v] + 1; P[0] = 3
3
P[w] = v;
} D[3] = 0 1
} P[3] = -1
} D[1] = -1
P[1] = -1
48
BFS
Podemos calcular dichas distancias en un vector D, y los padres en P.
void bfs(int inicial){
queue<int> Q; D[5] = -1
[Link](inicial); 2 D[4] = 1 P[5] = -1
D[2] = -1
D[inicial] = 0; P[2] = -1 P[4] = 3 5
while(not [Link]()){
int v = [Link](); [Link](); 4
for(auto &w: G[v])
if( D[w] == -1 ){
[Link](w); 0 D[0] = 1
D[w] = D[v] + 1; P[0] = 3
3
P[w] = v;
} D[3] = 0 1
} P[3] = -1
} D[1] = -1
P[1] = -1
49
BFS
Podemos calcular dichas distancias en un vector D, y los padres en P.
void bfs(int inicial){
queue<int> Q; D[5] = -1
[Link](inicial); 2 D[4] = 1 P[5] = -1
D[2] = 1
D[inicial] = 0; P[2] = 3 P[4] = 3 5
while(not [Link]()){
int v = [Link](); [Link](); 4
for(auto &w: G[v])
if( D[w] == -1 ){
[Link](w); 0 D[0] = 1
D[w] = D[v] + 1; P[0] = 3
3
P[w] = v;
} D[3] = 0 1
} P[3] = -1
} D[1] = -1
P[1] = -1
50
BFS
Podemos calcular dichas distancias en un vector D, y los padres en P.
void bfs(int inicial){
queue<int> Q; D[5] = -1
[Link](inicial); 2 D[4] = 1 P[5] = -1
D[2] = 1
D[inicial] = 0; P[2] = 3 P[4] = 3 5
while(not [Link]()){
int v = [Link](); [Link](); 4
for(auto &w: G[v])
if( D[w] == -1 ){
[Link](w); 0 D[0] = 1
D[w] = D[v] + 1; P[0] = 3
3
P[w] = v;
} D[3] = 0 1
} P[3] = -1
} D[1] = 2
P[1] = 0
51
BFS
Podemos calcular dichas distancias en un vector D, y los padres en P.
void bfs(int inicial){
queue<int> Q; D[5] = 2
[Link](inicial); 2 D[4] = 1 P[5] = 4
D[2] = 1
D[inicial] = 0; P[2] = 3 P[4] = 3 5
while(not [Link]()){
int v = [Link](); [Link](); 4
for(auto &w: G[v])
if( D[w] == -1 ){
[Link](w); 0 D[0] = 1
D[w] = D[v] + 1; P[0] = 3
3
P[w] = v;
} D[3] = 0 1
} P[3] = -1
} D[1] = 2
P[1] = 0
52
Análisis
Bajo la representación de lista de adyacencias, ambos algoritmos iteran
cada arco exactamente una vez, y cada vértice es visitado una única vez.
De donde resulta que el tiempo es O(N + M).
Si el grafo es conexo, O(N+M) = O(M).
53
Aplicaciones 54
Orden topológico
Un grafo dirigido se denomina DAG si no tiene ciclos dirigidos.
Un ordenamiento topológico es un ordenamiento de los vértices de un
grafo dirigido tal que todos los arcos quedan dibujados hacia la derecha.
Ejemplo: 4
2 2 3 4 0 1
0
posible toposort
3
1
55
Orden topológico
Teorema:
Un grafo es un DAG sii tiene un orden topológico.
¡ Podemos calcular uno con dfs !
Mantenemos una lista en espacio global y antes de retornar de visitar un
vértice, lo anexamos al final de la lista.
Una vez visitados todos los vértices, revertimos la lista.
56
Orden topológico
vector<int> toposort;
void dfs(int v){
visitado[v] = true;
for(auto &w: G[v])
if( not visitado[w] )
dfs(w);
toposort.push_back(v);
}
…
forn(v, N)
if( not visitado[v] )
dfs(v);
reverse([Link](), [Link]());
57
Más aplicaciones DFS
● Hallar componentes conexas
● Hallar componentes biconexas
○ Hallar puntos de articulación y puentes
● Hallar componentes fuertemente conexas
○ 2-SAT
● Test bipartición
● Test de planaridad
● Hallar ciclo Eulerianos
58
Kosaraju's
Es un algoritmo para hallar las componentes fuertemente conexas de un
grafo dirigido.
¿Qué pasaría si intentáramos obtener un toposort de un grafo que no sea
un DAG?
Obtendríamos un ordenamiento que preserva el orden (topológico) de las
SCCs, aunque los vértices de una misma SCC estén desordenados.
59
4
Kosaraju's
1
Supongamos que obtenemos: 2
24103 0 3
Si tiramos un DFS en el grafo transpuesto
4
en este orden, obtenemos las SCCs
1
0 3
60
4
Kosaraju's
1
Supongamos que obtenemos: 2
24103 0 3
Si tiramos un DFS en el grafo transpuesto
4
en este orden, obtenemos las SCCs
1
0 3
61
4
Kosaraju's
1
Supongamos que obtenemos: 2
24103 0 3
Si tiramos un DFS en el grafo transpuesto
4
en este orden, obtenemos las SCCs
1
0 3
62
4
Kosaraju's
1
Supongamos que obtenemos: 2
24103 0 3
Si tiramos un DFS en el grafo transpuesto
4
en este orden, obtenemos las SCCs
1
0 3
63
2-SAT
Toda fórmula proposicional (PROP) puede obtenerse inductivamente:
● x es una variable ⇒ x ∈ PROP
● x ∈ PROP ⇒ (¬x) ∈ PROP
● x, y ∈ PROP ⇒ (x ★ y) ∈ PROP donde ★ ∈ { Λ, V, ➝ }
Una fórmula está en k-CNF si puede escribirse como una conjunción de
disjunciones de hasta k variables (negadas o no).
Queremos ver si una fórmula es satisfacible (es decir, es posible encontrar
una valuación de variables tales que la fórmula da verdadero)
64
2-SAT
Infortunadamente k-SAT es NP-Completo para k > 2.
1-SAT es trivial
2-SAT es interesante!
Podemos construir el grafo de implicancias de la fórmula:
Los vértices son las variables y sus negaciones.
Hay un arco de u a v si u implica v cuando vale la fórmula.
La fórmula es satisfacible sii una variable y su negación no están en la
misma SCC.
65
2-SAT
Ejemplo:
(a∨¬b) ∧ (¬a∨b) ∧ (¬a∨¬b) ∧ (a∨¬c)
Resulta en las siguientes implicancias:
¬a➝¬b
b➝a
a➝b
¬b➝¬a
a➝¬b
b➝¬a
¬a➝¬c
c➝a ejemplo extraído de [Link] 66
2-SAT
Ejemplo:
(a∨¬b) ∧ (¬a∨b) ∧ (¬a∨¬b) ∧ (a∨¬c)
Resulta en las siguientes implicancias:
¬a➝¬b
b➝a
a➝b
¬b➝¬a
a➝¬b
b➝¬a
¬a➝¬c
c➝a ejemplo extraído de [Link] 67
Puentes
Existe un algoritmo por el Dr. Robert Tarjan para encontrar componentes
biconexas, puntos de articulación (vértices de corte) y puentes de un grafo
en O(N) con un solo DFS.
Sin embargo, siguiendo la onda de SCC, podemos encontrar los puentes
mediante el siguiente algoritmo:
● Tirar un DFS, orientar las aristas en el sentido en las cual las recorremos
● Hallar las SCCs del grafo
● Una arista u-v es un puente sii u y v pertenecen a SCCs distintas
68
Árbol
Generador
Mínimo
(MST)
esto no es un
MST
69
MST
Un árbol (no dirigido) es un grafo tal que:
● es conexo
● es acíclico
Equivalentemente, podemos decir:
● existe un único camino entre cada par de vértices
70
MST
1 10 1 10 1 10 1 10
5 5 5 5
8 8 8 8
7 4 7 4 7 4 7 4
3 3 3 3
grafo original árbol generador árbol no MST
peso = 17 generador peso = 13
peso = 15
71
Kruskal 72
Kruskal
El algoritmo de Kruskal halla un MST de la siguiente manera:
- ordenamos las aristas por peso creciente
- MST = vacío
- por cada arista e:
si MST + e no forma un ciclo:
MST += e
La única cosa difícil de este algoritmo es verificar si formamos un ciclo o no.
Esto se resuelve con la estructura de conjuntos disjuntos (AKA union-find)
73
Union Find
La estructura de conjuntos disjuntos tiene 3 operaciones:
● init(n) crea n conjuntos disjuntos
● find(x) devuelve el ID del conjunto donde está x
● join(x, y) une los conjuntos donde están x e y
find y join se realizan muy eficientemente, O(1) a fines prácticos.
¡Y su implementación es muy simple!
74
Union Find
struct disjoint_sets{
void init(int n){
[Link]();
[Link](n, -1);
}
int find(int x){
return v[x] == -1 ? x : v[x] = find(v[x]);
}
int join(int x, int y){
x = find(x); y = find(y);
if( x != y )
v[x] = y;
}
vector<int> v;
}; 75
Kruskal
// Sea E la lista de aristas {u, v, peso} de un grafo conexo
// Sea S la estructura de conjuntos disjuntos
sort([Link](), [Link]());
for(auto &e: E) 1 7
if( [Link](e.u) != [Link](e.v) ) 5
Ans += [Link];
else [Link](e.u, e.v);
8
10 15
cout << "Peso del MST: " << Ans << endl;
76
Kruskal
// Sea E la lista de aristas {u, v, peso} de un grafo conexo
// Sea S la estructura de conjuntos disjuntos
sort([Link](), [Link]());
for(auto &e: E) 1 7
if( [Link](e.u) != [Link](e.v) ) 5
Ans += [Link];
else [Link](e.u, e.v);
8
10 15
cout << "Peso del MST: " << Ans << endl;
77
Kruskal
// Sea E la lista de aristas {u, v, peso} de un grafo conexo
// Sea S la estructura de conjuntos disjuntos
sort([Link](), [Link]());
for(auto &e: E) 1 7
if( [Link](e.u) != [Link](e.v) ) 5
Ans += [Link];
else [Link](e.u, e.v);
8
10 15
cout << "Peso del MST: " << Ans << endl;
78
Kruskal
// Sea E la lista de aristas {u, v, peso} de un grafo conexo
// Sea S la estructura de conjuntos disjuntos
sort([Link](), [Link]());
for(auto &e: E) 1 7
if( [Link](e.u) != [Link](e.v) ) 5
Ans += [Link];
else [Link](e.u, e.v);
8
10 15
cout << "Peso del MST: " << Ans << endl;
79
Kruskal
// Sea E la lista de aristas {u, v, peso} de un grafo conexo
// Sea S la estructura de conjuntos disjuntos
sort([Link](), [Link]());
for(auto &e: E) 1 7
if( [Link](e.u) != [Link](e.v) ) 5
Ans += [Link];
else [Link](e.u, e.v);
8
10 15
cout << "Peso del MST: " << Ans << endl;
80
Análisis
Ordenar las aristas por peso creciente es O(M log M).
Luego, por cada iteración hacemos a lo sumo dos finds y un join.
Ambas operaciones son prácticamente O(1).
Como son M iteraciones, en total quedaría O(M).
Por lo que el algoritmo completo es O(M log M) por el ordenamiento.
Sin embargo, si las aristas ya vienen ordenadas el algoritmo es O(M).
81
Distancias en
grafos
ponderados
82
Dijkstra 83
Dijkstra
Cuando tenemos grafos ponderados, el BFS ya no nos sirve para calcular la
distancia más corta desde un vértice a los demás.
Por suerte existe un algoritmo que resuelve el problema: Dijkstra.
El algoritmo es similar al BFS, iremos metiendo los caminos descubiertos
en una bolsa de prioridad, y en cada iteración extraeremos el de menor
longitud e intentaremos extenderlo.
84
Dijkstra
struct hedge{ La estructura hedge guarda "medio
int v, d; arco": la longitud y el vértice final.
bool operator<(const arco &otro) const {
return d > otro.d;
} Para insertar el arco u→v con peso d:
}; G[u].push_back({v, d});
vector<hedge> G[MAXN]; Reutilizaremos la misma estructura para
representar el camino de longitud d que
termina en v.
Diremos que un camino tiene menos
prioridad que otro si su longitud es
mayor.
85
D[3] = -1
Dijkstra P[3] = -1
D[4] = -1 3
30
void Dijkstra(int inicial){ P[4] = -1 3 D[5] = -1
priority_queue<hedge> Q; P[5] = -1
[Link]({inicial, 0}); 4
20
D[inicial] = 0; 50 5
while(not [Link]()){
20
auto c = [Link](); [Link]();
if( D[c.v] < c.d ) 2 D[2] = -1
continue; 3 P[2] = -1 10
for(auto &e: G[c.v]) 2
if( D[e.v] == -1 or D[e.v] > c.d + e.d ){ 10
D[e.v] = c.d + e.d;
P[e.v] = c.v;
1
[Link]({e.v, D[e.v]});
0 15
} D[1] = -1
} D[0] = -1 P[1] = -1
} P[0] = -1
86
D[3] = -1
Dijkstra P[3] = -1
D[4] = -1 3
30
void Dijkstra(int inicial){ P[4] = -1 3 D[5] = -1
priority_queue<hedge> Q; P[5] = -1
[Link]({inicial, 0}); 4
20
D[inicial] = 0; 50 5
while(not [Link]()){
20
auto c = [Link](); [Link]();
if( D[c.v] < c.d ) 2 D[2] = -1
continue; 3 P[2] = -1 10
for(auto &e: G[c.v]) 2
if( D[e.v] == -1 or D[e.v] > c.d + e.d ){ 10
D[e.v] = c.d + e.d;
P[e.v] = c.v;
1
[Link]({e.v, D[e.v]});
0 15
} D[1] = -1
} D[0] = 0 P[1] = -1
} P[0] = -1
87
D[3] = -1
Dijkstra P[3] = -1
D[4] = -1 3
30
void Dijkstra(int inicial){ P[4] = -1 3 D[5] = -1
priority_queue<hedge> Q; P[5] = -1
[Link]({inicial, 0}); 4
20
D[inicial] = 0; 50 5
while(not [Link]()){
20
auto c = [Link](); [Link]();
if( D[c.v] < c.d ) 2 D[2] = -1
continue; 3 P[2] = -1 10
for(auto &e: G[c.v]) 2
if( D[e.v] == -1 or D[e.v] > c.d + e.d ){ 10
D[e.v] = c.d + e.d;
P[e.v] = c.v;
1
[Link]({e.v, D[e.v]});
0 15
} D[1] = -1
} D[0] = 0 P[1] = -1
} P[0] = -1
88
D[3] = -1
Dijkstra P[3] = -1
D[4] = -1 3
30
void Dijkstra(int inicial){ P[4] = -1 3 D[5] = -1
priority_queue<hedge> Q; P[5] = -1
[Link]({inicial, 0}); 4
20
D[inicial] = 0; 50 5
while(not [Link]()){
20
auto c = [Link](); [Link]();
if( D[c.v] < c.d ) 2 D[2] = -1
continue; 3 P[2] = -1 10
for(auto &e: G[c.v]) 2
if( D[e.v] == -1 or D[e.v] > c.d + e.d ){ 10
D[e.v] = c.d + e.d;
P[e.v] = c.v;
1
[Link]({e.v, D[e.v]});
0 15
} D[1] = 15
} D[0] = 0 P[1] = 0
} P[0] = -1
89
D[3] = -1
Dijkstra P[3] = -1
D[4] = -1 3
30
void Dijkstra(int inicial){ P[4] = -1 3 D[5] = -1
priority_queue<hedge> Q; P[5] = -1
[Link]({inicial, 0}); 4
20
D[inicial] = 0; 50 5
while(not [Link]()){
20
auto c = [Link](); [Link]();
if( D[c.v] < c.d ) 2 D[2] = 10
continue; 3 P[2] = 0 10
for(auto &e: G[c.v]) 2
if( D[e.v] == -1 or D[e.v] > c.d + e.d ){ 10
D[e.v] = c.d + e.d;
P[e.v] = c.v;
1
[Link]({e.v, D[e.v]});
0 15
} D[1] = 15
} D[0] = 0 P[1] = 0
} P[0] = -1
90
D[3] = -1
Dijkstra P[3] = -1
D[4] = 3 3
30
void Dijkstra(int inicial){ P[4] = 0 3 D[5] = -1
priority_queue<hedge> Q; P[5] = -1
[Link]({inicial, 0}); 4
20
D[inicial] = 0; 50 5
while(not [Link]()){
20
auto c = [Link](); [Link]();
if( D[c.v] < c.d ) 2 D[2] = 10
continue; 3 P[2] = 0 10
for(auto &e: G[c.v]) 2
if( D[e.v] == -1 or D[e.v] > c.d + e.d ){ 10
D[e.v] = c.d + e.d;
P[e.v] = c.v;
1
[Link]({e.v, D[e.v]});
0 15
} D[1] = 15
} D[0] = 0 P[1] = 0
} P[0] = -1
91
D[3] = -1
Dijkstra P[3] = -1
D[4] = 3 3
30
void Dijkstra(int inicial){ P[4] = 0 3 D[5] = -1
priority_queue<hedge> Q; P[5] = -1
[Link]({inicial, 0}); 4
20
D[inicial] = 0; 50 5
while(not [Link]()){
20
auto c = [Link](); [Link]();
if( D[c.v] < c.d ) 2 D[2] = 10
continue; 3 P[2] = 0 10
for(auto &e: G[c.v]) 2
if( D[e.v] == -1 or D[e.v] > c.d + e.d ){ 10
D[e.v] = c.d + e.d;
P[e.v] = c.v;
1
[Link]({e.v, D[e.v]});
0 15
} D[1] = 15
} D[0] = 0 P[1] = 0
} P[0] = -1
92
D[3] = 33
Dijkstra P[3] = 4
D[4] = 3 3
30
void Dijkstra(int inicial){ P[4] = 0 3 D[5] = -1
priority_queue<hedge> Q; P[5] = -1
[Link]({inicial, 0}); 4
20
D[inicial] = 0; 50 5
while(not [Link]()){
20
auto c = [Link](); [Link]();
if( D[c.v] < c.d ) 2 D[2] = 10
continue; 3 P[2] = 0 10
for(auto &e: G[c.v]) 2
if( D[e.v] == -1 or D[e.v] > c.d + e.d ){ 10
D[e.v] = c.d + e.d;
P[e.v] = c.v;
1
[Link]({e.v, D[e.v]});
0 15
} D[1] = 15
} D[0] = 0 P[1] = 0
} P[0] = -1
93
D[3] = 33
Dijkstra P[3] = 4
D[4] = 3 3
30
void Dijkstra(int inicial){ P[4] = 0 3 D[5] = -1
priority_queue<hedge> Q; P[5] = -1
[Link]({inicial, 0}); 4
20
D[inicial] = 0; 50 5
while(not [Link]()){
20
auto c = [Link](); [Link]();
if( D[c.v] < c.d ) 2 D[2] = 10
continue; 3 P[2] = 0 10
for(auto &e: G[c.v]) 2
if( D[e.v] == -1 or D[e.v] > c.d + e.d ){ 10
D[e.v] = c.d + e.d;
P[e.v] = c.v;
1
[Link]({e.v, D[e.v]});
0 15
} D[1] = 15
} D[0] = 0 P[1] = 0
} P[0] = -1
94
D[3] = 33
Dijkstra P[3] = 4
D[4] = 3 3
30
void Dijkstra(int inicial){ P[4] = 0 3 D[5] = -1
priority_queue<hedge> Q; P[5] = -1
[Link]({inicial, 0}); 4
20
D[inicial] = 0; 50 5
while(not [Link]()){
20
auto c = [Link](); [Link]();
if( D[c.v] < c.d ) 2 D[2] = 10
continue; 3 P[2] = 0 10
for(auto &e: G[c.v]) 2
if( D[e.v] == -1 or D[e.v] > c.d + e.d ){ 10
D[e.v] = c.d + e.d;
P[e.v] = c.v;
1
[Link]({e.v, D[e.v]});
0 15
} D[1] = 12
} D[0] = 0 P[1] = 2
} P[0] = -1
95
D[3] = 33
Dijkstra P[3] = 4
D[4] = 3 3
30
void Dijkstra(int inicial){ P[4] = 0 3 D[5] = 30
priority_queue<hedge> Q; P[5] = 2
[Link]({inicial, 0}); 4
20
D[inicial] = 0; 50 5
while(not [Link]()){
20
auto c = [Link](); [Link]();
if( D[c.v] < c.d ) 2 D[2] = 10
continue; 3 P[2] = 0 10
for(auto &e: G[c.v]) 2
if( D[e.v] == -1 or D[e.v] > c.d + e.d ){ 10
D[e.v] = c.d + e.d;
P[e.v] = c.v;
1
[Link]({e.v, D[e.v]});
0 15
} D[1] = 12
} D[0] = 0 P[1] = 2
} P[0] = -1
96
D[3] = 30
Dijkstra P[3] = 2
D[4] = 3 3
30
void Dijkstra(int inicial){ P[4] = 0 3 D[5] = 30
priority_queue<hedge> Q; P[5] = 2
[Link]({inicial, 0}); 4
20
D[inicial] = 0; 50 5
while(not [Link]()){
20
auto c = [Link](); [Link]();
if( D[c.v] < c.d ) 2 D[2] = 10
continue; 3 P[2] = 0 10
for(auto &e: G[c.v]) 2
if( D[e.v] == -1 or D[e.v] > c.d + e.d ){ 10
D[e.v] = c.d + e.d;
P[e.v] = c.v;
1
[Link]({e.v, D[e.v]});
0 15
} D[1] = 12
} D[0] = 0 P[1] = 2
} P[0] = -1
97
D[3] = 30
Dijkstra P[3] = 2
D[4] = 3 3
30
void Dijkstra(int inicial){ P[4] = 0 3 D[5] = 30
priority_queue<hedge> Q; P[5] = 2
[Link]({inicial, 0}); 4
20
D[inicial] = 0; 50 5
while(not [Link]()){
20
auto c = [Link](); [Link]();
if( D[c.v] < c.d ) 2 D[2] = 10
continue; 3 P[2] = 0 10
for(auto &e: G[c.v]) 2
if( D[e.v] == -1 or D[e.v] > c.d + e.d ){ 10
D[e.v] = c.d + e.d;
P[e.v] = c.v;
1
[Link]({e.v, D[e.v]});
0 15
} D[1] = 12
} D[0] = 0 P[1] = 2
} P[0] = -1
98
D[3] = 30
Dijkstra P[3] = 2
D[4] = 3 3
30
void Dijkstra(int inicial){ P[4] = 0 3 D[5] = 22
priority_queue<hedge> Q; P[5] = 1
[Link]({inicial, 0}); 4
20
D[inicial] = 0; 50 5
while(not [Link]()){
20
auto c = [Link](); [Link]();
if( D[c.v] < c.d ) 2 D[2] = 10
continue; 3 P[2] = 0 10
for(auto &e: G[c.v]) 2
if( D[e.v] == -1 or D[e.v] > c.d + e.d ){ 10
D[e.v] = c.d + e.d;
P[e.v] = c.v;
1
[Link]({e.v, D[e.v]});
0 15
} D[1] = 12
} D[0] = 0 P[1] = 2
} P[0] = -1
99
D[3] = 30
Dijkstra P[3] = 2
D[4] = 3 3
30
void Dijkstra(int inicial){ P[4] = 0 3 D[5] = 22
priority_queue<hedge> Q; P[5] = 1
[Link]({inicial, 0}); 4
20
D[inicial] = 0; 50 5
while(not [Link]()){
20
auto c = [Link](); [Link]();
if( D[c.v] < c.d ) 2 D[2] = 10
continue; 3 P[2] = 0 10
for(auto &e: G[c.v]) 2
if( D[e.v] == -1 or D[e.v] > c.d + e.d ){ 10
D[e.v] = c.d + e.d;
P[e.v] = c.v;
1
[Link]({e.v, D[e.v]});
0 15
} D[1] = 12
} D[0] = 0 P[1] = 2
} P[0] = -1
100
D[3] = 25
Dijkstra P[3] = 5
D[4] = 3 3
30
void Dijkstra(int inicial){ P[4] = 0 3 D[5] = 22
priority_queue<hedge> Q; P[5] = 1
[Link]({inicial, 0}); 4
20
D[inicial] = 0; 50 5
while(not [Link]()){
20
auto c = [Link](); [Link]();
if( D[c.v] < c.d ) 2 D[2] = 10
continue; 3 P[2] = 0 10
for(auto &e: G[c.v]) 2
if( D[e.v] == -1 or D[e.v] > c.d + e.d ){ 10
D[e.v] = c.d + e.d;
P[e.v] = c.v;
1
[Link]({e.v, D[e.v]});
0 15
} D[1] = 12
} D[0] = 0 P[1] = 2
} P[0] = -1
101
D[3] = 25
Dijkstra P[3] = 5
D[4] = 3 3
30
void Dijkstra(int inicial){ P[4] = 0 3 D[5] = 22
priority_queue<hedge> Q; P[5] = 1
[Link]({inicial, 0}); 4
20
D[inicial] = 0; 50 5
while(not [Link]()){
20
auto c = [Link](); [Link]();
if( D[c.v] < c.d ) 2 D[2] = 10
continue; 3 P[2] = 0 10
for(auto &e: G[c.v]) 2
if( D[e.v] == -1 or D[e.v] > c.d + e.d ){ 10
D[e.v] = c.d + e.d;
P[e.v] = c.v;
1
[Link]({e.v, D[e.v]});
0 15
} D[1] = 12
} D[0] = 0 P[1] = 2
} P[0] = -1
102
Análisis
Bajo la representación de lista de adyacencias, y usando una binary heap
como priority queue, la complejidad temporal es O(M log N).
103
Floyd Warshall 104
Floyd-Warshall
Si quisiéramos calcular el camino más corto entre cualquier par de vértices,
podríamos…
Si el grafo no es ponderado, tirar un BFS desde cada vértice en tiempo
O(NM).
Si el grafo es ponderado, tirar un Dijkstra desde cada vértice en tiempo
O(NM log N).
105
Floyd-Warshall
Si el grafo es muy denso (M ∼ N2), muchos Dijkstras van a dar una
complejidad peor que N3.
Por suerte existe un algoritmo que:
- Corre en O(N3)
- Es trivial de programar
- No se rompe con arcos con pesos negativos
106
Floyd-Warshall
La idea es calcular mediante programación dinámica la siguiente tabla:
D[i][j][k] :=
longitud de un i-j camino mínimo cuyos vértices intermedios están en 1..k
Vemos que D[i][j][k] es el mínimo de:
D[i][j][k-1] ← el camino mínimo no pasa por k
D[i][k][k-1] + D[k][j][k-1] ← el camino mínimo pasa por k
107
Floyd-Warshall
Guardaremos en una matriz D de NxN la distancia más corta para todo par
de vértices.
INF representa un número muy grande.
forn(i, N) forn(j, N) D[i][j] = i == j ? 0 : INF;
for(auto &e: E) D[e.u][e.v] = min(D[e.u][e.v], e.d);
forn(k, N)
forn(i, N)
forn(j, N)
D[i][j] = min(D[i][j], D[i][k] + D[k][j]);
108
Floyd-Warshall
Podemos rápidamente reconstruir los caminos guardando el siguiente vértice:
for(auto &e: E){
D[e.u][e.v] = e.d;
Next[e.u][e.v] = e.v;
}
forn(k, N)
forn(i, N)
forn(j, N)
if( D[i][j] > D[i][k] + D[k][j] ){
D[i][j] = D[i][k] + D[k][j];
Next[i][j] = Next[i][k];
}
109
Gracias! 110
También podría gustarte
- Introducción a Grafos y AlgoritmosAún no hay calificacionesIntroducción a Grafos y Algoritmos10 páginas
- Introducción a Grafos y AplicacionesAún no hay calificacionesIntroducción a Grafos y Aplicaciones9 páginas
- Recorridos y Componentes en GrafosAún no hay calificacionesRecorridos y Componentes en Grafos20 páginas
- Introducción a Grafos en Estructuras de DatosAún no hay calificacionesIntroducción a Grafos en Estructuras de Datos6 páginas
- CAP5 Aplicaciones de Estructuras de Datos - GrafosAún no hay calificacionesCAP5 Aplicaciones de Estructuras de Datos - Grafos40 páginas
- Introducción a los Grafos y sus AplicacionesAún no hay calificacionesIntroducción a los Grafos y sus Aplicaciones15 páginas
- Introducción a los Grafos y sus AplicacionesAún no hay calificacionesIntroducción a los Grafos y sus Aplicaciones27 páginas
- Grafos Estructura y Recorridos en JAVA ExplicaciónAún no hay calificacionesGrafos Estructura y Recorridos en JAVA Explicación22 páginas
- Introducción a Grafos y Estructuras de DatosAún no hay calificacionesIntroducción a Grafos y Estructuras de Datos19 páginas
- Representación y Algoritmos de GrafosAún no hay calificacionesRepresentación y Algoritmos de Grafos56 páginas
- Introducción a Algoritmos de GrafosAún no hay calificacionesIntroducción a Algoritmos de Grafos7 páginas
- Introducción a la Teoría de GrafosAún no hay calificacionesIntroducción a la Teoría de Grafos40 páginas
- Actividades de Algoritmos: BFS y DFSAún no hay calificacionesActividades de Algoritmos: BFS y DFS5 páginas
- Algoritmos de Grafos y Ordenamiento EficienteAún no hay calificacionesAlgoritmos de Grafos y Ordenamiento Eficiente14 páginas
- Teoría de Grafos y Árboles en Matemáticas100% (1)Teoría de Grafos y Árboles en Matemáticas13 páginas
- Teoría de Grafos y Algoritmos en BUAPAún no hay calificacionesTeoría de Grafos y Algoritmos en BUAP17 páginas
- Profundidad Primera Búsqueda o DFS para Un GráficoAún no hay calificacionesProfundidad Primera Búsqueda o DFS para Un Gráfico5 páginas
- Introducción a TDA Grafos en JavaAún no hay calificacionesIntroducción a TDA Grafos en Java9 páginas
- Tipos de Grafos y Algoritmos ClaveAún no hay calificacionesTipos de Grafos y Algoritmos Clave85 páginas
- Introducción a Grafos y su Implementación en JavaAún no hay calificacionesIntroducción a Grafos y su Implementación en Java30 páginas
- Recorridos en Grafos: Algoritmos y AplicacionesAún no hay calificacionesRecorridos en Grafos: Algoritmos y Aplicaciones101 páginas
- Recorridos en Grafos: Búsqueda Profundidad y AnchuraAún no hay calificacionesRecorridos en Grafos: Búsqueda Profundidad y Anchura19 páginas
- Introducción a Grafos Dirigidos y AlgoritmosAún no hay calificacionesIntroducción a Grafos Dirigidos y Algoritmos4 páginas
- Estrategias para Competencias de ProgramaciónAún no hay calificacionesEstrategias para Competencias de Programación72 páginas
- Inversión y Producción de AlfajoresAún no hay calificacionesInversión y Producción de Alfajores20 páginas
- Diagnóstico de Compañía Minera BuenaventuraAún no hay calificacionesDiagnóstico de Compañía Minera Buenaventura21 páginas
- Geometria Descriptiva Aplicada A La Industria25% (4)Geometria Descriptiva Aplicada A La Industria35 páginas
- Evaluación Final: Fundamentos de AlgoritmosAún no hay calificacionesEvaluación Final: Fundamentos de Algoritmos2 páginas
- Definir Los Siguientes Conceptos:: 1. InterpretesAún no hay calificacionesDefinir Los Siguientes Conceptos:: 1. Interpretes5 páginas
- Programa de Programación I POO INF-120Aún no hay calificacionesPrograma de Programación I POO INF-1206 páginas
- Ejercicios Java para PrincipiantesAún no hay calificacionesEjercicios Java para Principiantes9 páginas
- Introducción Rápida A Matlab Y Simulink - Manuel Gil Rodríguez PDF100% (6)Introducción Rápida A Matlab Y Simulink - Manuel Gil Rodríguez PDF112 páginas
- Ejercicios sobre Algoritmos de Ordenamiento0% (1)Ejercicios sobre Algoritmos de Ordenamiento4 páginas
- Estructuras de Datos en C: Vectores EstáticosAún no hay calificacionesEstructuras de Datos en C: Vectores Estáticos80 páginas
- Arrays en LabVIEW: Creación y UsoAún no hay calificacionesArrays en LabVIEW: Creación y Uso6 páginas
- Introducción a Arreglos en ProgramaciónAún no hay calificacionesIntroducción a Arreglos en Programación20 páginas
- Estructuras de Datos en ProgramaciónAún no hay calificacionesEstructuras de Datos en Programación49 páginas
- Regresión Logística con R: Tutorial CompletoAún no hay calificacionesRegresión Logística con R: Tutorial Completo38 páginas
- Ejercicios de Algoritmos y ProgramaciónAún no hay calificacionesEjercicios de Algoritmos y Programación2 páginas
- Metodos de Ordenamiento en Arreglos en LPP100% (1)Metodos de Ordenamiento en Arreglos en LPP12 páginas
- Aplicaciones de Matrices en C++ y MatlabAún no hay calificacionesAplicaciones de Matrices en C++ y Matlab8 páginas
- Introducción a JavaScript y VariablesAún no hay calificacionesIntroducción a JavaScript y Variables102 páginas
- Introducción a Constructores en JavaAún no hay calificacionesIntroducción a Constructores en Java27 páginas
