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\to 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$