# Gráfos: BFS y DFS

**Fecha:** 06.julio.2020

## Grafo
Un grafo $G$ es conjunto de vertices $V$ y aristas $E$, es decir:
$$
G = {V,E}
$$

### Grafo Direccional
Regularmente el grafo direccional es conocido como un ***digrafo***
Dada un arista $(U,V)$, solo podemos transitar dese $U$ hacia $V$, $U -> V$

### Grafo Bidireccional
Regularmente el grafo bidireccional es conocido como un ***grafo***
La representación de un grafo bidireccional, se da con una doble arísta. $(U,V)$, $(V,U)$
u,v = hay arista bidireccional

### Grafo *Multigrafo*
Nos encontrar con aristas del tipo $(U,U)$, o también $(U,V)_{1}$ $(U,V)_{2}$

### Grafo Conexo
De cualquier nodo $U \rightarrow V$.
Es decir, el grafo es una sola componente.

#### Componente
Un conjunto (*subgrafo*) en existe un camino entre cada par de nodos.

##### Una componente cíclica
$(U,V), (V,W), (W,U)$, en otras palabras, existe un camino que parte de $U$ y llega a $U$

### Arbol
- Es un grafo **conexo**
- Tiene **n-1** aristas
- No tiene **ciclos**

## BFS (Breath-First Search)
Es un algoritmo de recorrido y búsqueda de grafos.
Trabaja en grafos dirigidos y no dirigidos.

El algoritmo se llama así, ya que se expande entre la frontera de los vertices descubiertos o no descubiertos.

Una bfs necesita un nodo de inicio $U_{i}$

## DFS (Deep-First Search)
Es un algoritmo de recorrido y búsqueda de grafos.
Trabaja en grafos dirigidos y no dirigidos.

El algoritmo se llama así, porque de un nodo $U$ trataremos de llegar lo más profundo que se pueda, y despues iremos visitando los nodos no visitados más profundos a los menos profundos.

Una bfs necesita un nodo de inicio $U_{i}$