8.
Grafos
22.08 Algoritmos y estructuras de datos
Marc S. Ressl
sculpture by aranda/lasch
Grafos
En el ámbito informático, un grafo es un conjunto de
nodos conectados por arcos.
Los grafos son muy similares a los árboles, pero
pueden tener ciclos.
Todo árbol es un grafo, pero no todo grafo es un
árbol.
Grafos
Un grafo se de ne a partir de una lista de nodos V y
una lista de arcos E.
El número de arcos |E| es un valor entre 0 y |V|2.
Submarine Cable Map
©2018 Telegeography
fi
Grafos
Un grafo es disperso cuando |E| es del orden de |V|.
Un grafo es denso cuando |E| es del orden de |V|2.
TABLE I
I NTERACTION TABLE FOR BE
1)
Grafos 2)
3)
Los grafos pueden ser dirigidos o no-dirigidos.
Un grafo es cíclico cuando contiene ciclos. 4)
5)
Fig. 4. Putting together single interaction state machines into a complete
agent-level graph that describes all interactions of an agent. The black nodes
were the initial start and end nodes of the two graphs. They are basically the
Grafos 31.08 93.17 93.18 94.24 22.06
93.16 93.41 93.02 94.21 22.07
93.42 93.03 22.08 12.01
Cuando un grafo es dirigido y acíclico, el grafo es un
DAG (directed acyclic graph).
22.53 93.43 93.04 93.24
Los DAG son muy útiles para representar
dependencias de tareas y de software.
22.02 93.44 93.57 93.54 11.15
22.13 22.42 22.11 22.01 94.51
Grafos
Un grafo es conexo cuando existe un camino entre
dos nodos cualquiera.
Cuando un grafo no es conexo, posee múltiples
componentes conexas, o sea, sub-grafos conexos.
Grafos
Un grafo es pesado cuando sus arcos tienen pesos
asociados.
A
Grafos
B C
Podemos representar los grafos con listas de nodos,
en las que cada nodo enumera sus vecinos.
J D E F
K G H I
Grafos
template <class T>
class GraphNode
{
public:
T value;
bool mark;
En un grafo con lista de adyacencia, cada nodo
forward_list<int> neighbors; // Node indices
};
enumera sus vecinos directamente.
Solemos incluir una marca en los nodos, cuya template <class T>
función explicaremos en breve. class Graph
{
public:
vector<GraphNode<T>> nodes;
};
Grafos Ejemplo de un grafo con lista de adyacencia.
Grafos
template <class T>
class GraphNode2
{
public:
T value;
bool mark;
En un grafo con matriz de adyacencia,
vector<bool> neighbors; // Node connections
};
representamos los nodos y sus vecinos con una
matriz de |V|×|V| elementos.
template <class T>
La entrada i,j-ésima de la matriz indica si hay un class Graph2
camino desde el nodo i-ésimo al nodo j-ésimo. {
public:
Podemos representar la matriz de adyacencia con vector<GraphNode2<T>> nodes;
una lista de listas o con un arreglo de |V|2 elementos. };
Grafos Ejemplo de un grafo con matriz de adyacencia.
template <class T>
class GraphNode3
{
public:
Grafos };
T node;
bool mark;
class GraphArc
{
También podemos representar los grafos con un public:
conjunto de arcos. int src;
int dest;
Esta representación es fácil de comprender y de
};
implementar, pero no suele ser e ciente en cálculo.
template <class T>
class Graph3
{
public:
vector<GraphNode3<T>> nodes;
vector<GraphArc> arcs;
};
fi
Grafos
Las listas de adyacencia requieren O(|V| + |E|) de
memoria.
Las matrices de adyacencia requieren O(|V|2) de
memoria.
Los conjuntos de arcos requieren O(|V| + |E|) de
memoria.
Grafos
Si necesitamos recorrer un grafo y el grafo es
disperso, solemos preferir las listas de adyacencia
porque enumeran sólo los vecinos existentes.
El recorrido será por tanto más e ciente que con las
matrices de adyacencia, que enumeran todos los
vecinos.
fi
Grafos
Si, por el contrario, el grafo es denso, solemos preferir
las matrices de adyacencia, que, al ser denso el grafo,
suelen ocupar menos memoria que las listas de
adyacencia.
Recorrido de A
grafos
B C
Un recorrido de un grafo involucra visitar cada uno
de sus nodos en forma sistemática.
Los recorridos de grafos son similares a los recorridos
de árboles, con dos novedades: J D E F
- Puede haber ciclos.
- Puede haber múltiples componentes conexas.
K G H I
Recorrido de A
grafos
B C
Para resolver estos problemas usamos las marcas de
nodos que introdujimos antes.
El recorrido involucra dos pasos:
1. Borramos las marcas de todos los nodos.
J D E F
2. Buscamos iterativamente un nodo que no
hayamos visitado, y desde allí recorremos una
componente conexa con DFS o BFS.
K G H I
Recorrido de void traverseGraph(Graph &graph)
grafos {
// Clear marks
for (auto &node : [Link])
[Link] = false;
// Start traversal
El ejemplo a la derecha implementa estos pasos. for (auto &node : [Link])
{
if (![Link])
{
traverseDFS(graph, &node);
// Or:
// traverseBFS(graph, &node);
}
}
}
Recorrido DFS void traverseDFS(Graph &graph, GraphNode *node)
{
node->mark = true;
visitPreorder(node);
El recorrido DFS de grafos es similar al recorrido DFS
for (int i : node->neighbors)
de árboles, salvo por el código que maneja las
{
marcas.
if (![Link])
traverseDFS(graph, [Link] + i);
}
visitPostorder(node);
}
Recorrido DFS Ejemplo de un recorrido DFS.
void traverseBFS(Graph &graph, GraphNode *node)
{
queue<GraphNode *> q;
Recorrido BFS [Link](node);
while (![Link]())
{
GraphNode *node = [Link]();
El recorrido BFS de grafos también guarda un node->mark = true;
parecido muy grande con el recorrido BFS de
árboles. visit(node);
for (int i : node->neighbors)
{
if (![Link])
[Link]([Link] + i);
}
}
}
Recorrido BFS Ejemplo de un recorrido BFS.
El algoritmo
ood ll
El recorrido de grafos es la base del algoritmo
ood ll para rellenar bitmaps.
fl
fl
fi
fi
El problema del
camino más corto
Cuando un grafo no es pesado, podemos usar el
recorrido BFS para determinar el camino más corto
a otro nodo.
El problema del
camino más corto 9
B D
4 2
Cuando un grafo es pesado, podemos usar el 7
algoritmo de Dijkstra para determinar el camino A 11 13 F
más corto a otro nodo.
5 6
3
C E
Shakey the robot
El problema del
camino más corto
También podemos usar los siguientes algoritmos:
- A* (mejora la e ciencia con una heurística)
- Bellman-Ford (para pesos negativos)
- Floyd–Warshall (calcula todos los caminos)
- Johnson's (mejora a Floyd-Warshall)
- Viterbi (para pesos probabilísticos)
fi
Ordenamiento
topológico
El problema del ordenamiento topológico consiste
en determinar una secuencia de tareas que respete
las dependencias entre ellas.
El problema se puede resolver con un recorrido DFS
pos-orden.
PageRank
El algoritmo PageRank modela el grafo de enlaces
entre páginas web, y de esta manera asigna un
puntaje a cada cual para optimizar las búsquedas en
Internet.
Navmesh
Un navmesh es una estructura de datos basada en
grafos que permite la navegación de robots
autónomos o agentes de software en entornos
complejos.
Tareas
- Leer el capítulo 18 “Grafos” (opcional:
sección 18.7 “Algorithms for searching
the web”).
