TAD GRAFOS

Plantilla de clase que permite usar cualquier tipo de datos para los vértices ( V ) y los costos o pesos de las aristas
( C ).

C++

template <class V, class C>

class Grafo {

private:
int numVertices;
vector<V> vertices;
vector<list<pair<V, C>>> listaAdyacencia;
vector<vector<C>> matrizAdyacencia;
map<V, map<V, C>> conjuntoAdyacencia;

public:
Grafo() : numVertices(0) {}
Grafo(int n) : numVertices(n);

void agregarArista(V u, V v, C costo);

void eliminarArista(V u, V v);
bool findArista(V u, V v) const;

void agregarVertice(V v);

void eliminarVertice(V v);
bool findVertice(V v) const;

void imprimirGrafo() const;

int obtenerNumVertices() const;
const vector<list<pair<V, C>>>& obtenerListaAdyacencia() const;
const vector<vector<C>>& obtenerMatrizAdyacencia() const;
const map<V, map<V, C>>& obtenerConjuntoAdyacencia() const;
};

ALGORITMOS EN GRAFOS
PARA GAFOS NO DIRIGIDOS
Algoritmo de Prim
El algoritmo de Prim y el algoritmo de Kruskal son utilizados para encontrar árboles de expansión mínima en un
grafo ponderado.

Implementación con colas de prioridad

Complejidad temporal y espacial
Aplicaciones en problemas de árboles de expansión mínima
 Algoritmo de Kruskal
Implementación con estructuras de datos de conjuntos disjuntos
Complejidad temporal y espacial
Comparación con el algoritmo de Prim

ALGORTIMO DE FLEURY'S
El Algoritmo de Fleury es un método utilizado en teoría de grafos para encontrar un ciclo euleriano en un grafo
Euleriano o un camino euleriano en un grafo Semi Euleriano. Este algoritmo se aplica a grafos no dirigidos y
proporciona una forma sistemática de recorrer todas las aristas del grafo exactamente una vez.

Algoritmo

1. Revisar que el grafo tiene 0 o 2 vértices impares.

2. Si hay 0 vértices impares, empezar en cualquier vértice. Si hay 2 vértices impares,
empezar por uno de ellos.
3. Seguir las aristas de una en una. Si se puede elegir entre un puente y un no puente,
elegir siempre el no puente.
4. Detenerse cuando no haya más aristas.

Algoritmo de Borůvka
Otro enfoque para el problema del árbol de expansión mínima, se puede ejecutar en paralelo.

Algoritmo de Hierholzer
También encuentra un circuito euleriano, pero es más eficiente que el algoritmo de Fleury.

PARA GRAFOS DIRIGIDOS

ALGORITMO DE DIJKSTRA
El algoritmo de Dijkstra encuentra el camino más corto entre dos vértices en un grafo ponderado no dirigido o
dirigido.
 Implementación con colas de prioridad
Complejidad temporal y espacial
Variantes para grafos con pesos negativos

Uso de Dijkstra

Costos: A : 0, B : 3, C : 2, D : 5, E : 6

Algoritmo de Bellman-Ford**
Encuentra las rutas más cortas desde un nodo inicial a todos los otros nodos, puede manejar pesos negativos.

Algoritmo de Floyd-Warshall
El algoritmo de Floyd-Warshall encuentra todos los caminos más cortos entre todos los pares de vértices en
un grafo dirigido ponderado.
Implementación con matrices
Complejidad temporal y espacial
Variantes para grafos con pesos negativos

RECORRIDOS EN GRAFOS
RECORRIDOS DE BÚSQUEDA
Los dos recorridos más comunes son la búsqueda en anchura (BFS) y la búsqueda en profundidad (DFS).
Son algoritmos que visitan todos los vértices a aristas de un grafo de manera sistemática.
 DFS (DEPTH FIRST SEARCH)
Método Recurrentemente

Método usando una Stack

BFS (BREADTH FIRST SEARCH)

Este método realiza un recorrido en amplitud BFS de un grafo, empezando desde un vértice especificado como
semilla.

C++

list<V> Graph<V, C>::Levels(int seed){

list<V> res;
vector<bool> marks(this->m_Vertices.size(), false);
queue<int> q;
q.push(seed);

while(!q.empty()){
int n = q.front();
q.pop();

if(marks[n])
continue;
marks[n] = true;
res.push_back(this->m_Vertices[n]);

for(int i = 0; i < this->m_Vertices.size(); ++i){

if(this->m_Matrix.ElementExists(n, i))
q.push(i);
}
}
return (res);
}

BÚSQUEDA A* (A-STAR)

GRAFOS EULERIANOS
Un grafo Euleriano es un tipo de grafo que contiene un ciclo euleriano, es decir, un ciclo que recorre cada arista
exactamente una vez y regresa al punto de partida.
Un grafo Semi Euleriano es aquel que posee un camino euleriano, el cual recorre cada arista exactamente una
vez pero no necesariamente regresa al punto de partida.
 CAMINO Y CICLO EULERIANO

Camino Euleriano es un camino en un grafo que visita

cada arista exactamente una vez.

• Un grafo no dirigido tiene un camino de Euler si y

sólo si por mucho dos vértices tienen grado impar.
• Un grafo dirigido tiene un camino de Euler si
exactamente dos vértices tienen una diferencia de ±1
entre su grado de entrada y salida, y todos los demás
vértices tienen el mismo grado de entrada y salida.

Ciclo o Circuito Euleriano es un camino Euleriano que

empieza y finaliza en el mismo vértice.

• Un grafo no dirigido tiene un circuito de Euler si y

sólo si cada vértice tiene grado par.
• Un grafo dirigido tiene un circuito de Euler si y sólo si
cada vértice tiene el mismo grado de salida como de
entrada.

GRAFOS DE HAMILTON
Un grafo de Hamilton es un tipo de grafo que contiene un ciclo de Hamilton, es decir, un ciclo que recorre cada
arista exactamente una vez y regresa al punto de partida.
Un grafo Semi Hamiltoniano es aquel que posee un camino de Hamilton, el cual recorre cada vértice
exactamente una vez pero no necesariamente regresa al vértice de partida.

CAMINO Y CICLO DE HAMILTON

Camino Hamiltoniano es un camino que visita cada

vértice del grafo exactamente una vez, pero no
necesariamente regresa al vértice inicial.

• Un grafo no dirigido tiene un camino de Hamilton si y

sólo si la suma de los grados de cada par de vértices
no adyacentes es al menos igual al número de
vértices en el grafo.

Circuito o Ciclo Hamiltoniano es un camino que visita

cada vértice del grafo exactamente una vez y regresa al
vértice inicial.

• Un grafo no dirigido tiene un ciclo de Hamilton si y

sólo si cada vértice tiene un grado de al menos la
mitad del número total de vértices.

CONDICIONES DE EXISTENCIA
Para que un grafo tenga un circuito de Hamilton, asumiendo un grafo G = (V , E) con más de 2 vértices. Es
necesario cumplir con ciertas condiciones:

Los vértices con grado 1 no pueden formar parte de un circuito de Hamilton.

Si un vértice tiene grado 2, entonces ambas aristas incidentes deben pertenecer al circuito.
 No deben existir circuitos más pequeños (internos) dentro de cualquier circuito de Hamilton.

Existencia de Subgrafo Especial.

Debe existir un subgrafo H con las siguientes propiedades:

Contiene todos los vértices de G.

H está conectado.
Tiene el mismo número de aristas que de vértices.
Cada vértice en H tiene grado 2. Este subgrafo es el circuito de Hamilton de G.

ENCONTRAR CIRCUITOS DE HAMILTON

Dado que verificar las tres primeras condiciones es relativamente sencillo, encontrar un circuito de Hamilton se
vuelve desafiante debido a la última condición, que no puede verificarse en tiempo polinomial, lo que lo convierte
en un problema NP-difícil.

1. Fuerza Bruta: Probar todas las combinaciones posibles de conexiones entre vértices, lo que es
computacionalmente costoso.
2. Backtracking: Comenzar desde un vértice y seleccionar conexiones hasta que no se pueda
avanzar. Si quedan vértices sin visitar, retroceder y probar otras opciones.
3. Algoritmos Aproximados: Utilizar algoritmos basados en el problema del vendedor viajero, como
Cheapest Link Algorithm (CLA), Nearest Neighbor Algorithm (NNA), y Repetitive Nearest Neighbor
Algorithm (RNNA), que ofrecen soluciones cercanas al óptimo.

IMPLEMENTACIÓN DE GRAFOS
Hay varias formas de implementar grafos, incluyendo matrices de adyacencia, lista de adyacencia y matrices de
incidencia.

MATRIZ DE ADYACENCIA
Para un Grafo una matriz de adyacencia es una forma de representar un grafo como una matriz booleana (0 y 1).

Para un grafo no dirigido, Supongamos que hay n Para un grafo dirigido, la matriz de adyacencia es
vértices en el grafo. Entonces, crea una matriz 2D una matriz simétrica: a = a
i,j j,i

adyM at[n][n] de dimensión N xN . ○

• Para un grafo dirigido, inicialmente la matriz se
• Sí hay una arista desde el vértice i a j, llena de 0's.
adjM at[n][n] será 1. • Sí hay una arista desde el vértice de la fuente al
• Sí no hay una arista desde el vértice i a j, destino, adyM at[destino] será 1.
adyM at[n][n] será 0.

Ejemplo de Matriz de Adyacencia

 1 si hay una arista entre (i, j)
Aij = {
0 en otro caso

LISTA DE ADYACENCIA

No dirigido Dirigido

Ejemplo de Lista de Adyacencia

V = {A, B, C, D, E}
 CONJUNTO DE ADYACENCIA O ARISTAS

V = {A, B, C, D, E}

E = {(A, B)(A, C)(B, A)(B, D)(C, A)(C, D)(D, E)(E, D}

Diferencias entre Lista, Matriz y Conjunto de Adyacencia

Lista de Adyacencia

Uso: Eficiente en términos de espacio para grafos dispersos. Útil para iterar sobre los vecinos de un
vértice.
Estructura: Vector de listas, donde cada lista contiene pares (vértice adyacente, costo).

Matriz de Adyacencia

Uso: Eficiente para grafos densos donde se necesita acceso rápido para verificar la existencia de aristas.
Estructura: Vector de vectores, formando una matriz N x N, donde cada celda [i][j] representa el
costo de la arista desde i hasta j .

Conjunto de Adyacencia

Uso: Combina ventajas de listas y matrices, eficiente tanto en tiempo como en espacio para ciertos tipos
de operaciones. útil para acceso rápido a los vecinos y costos de aristas.
Estructura: Mapa de mapas, donde el primer mapa asocia vertices de origen a otros mapas que asocia
vértices de destino con costos.