Algoritmo de búsqueda-Profundidad DFS

Esta búsqueda sobre el grafo ,visita los nodos del grafo recursivamente , por lo que se puede realizar mediante un algoritmo recursivo o con ayuda de una pila.Lo más usual es realizarlo de manera recursiva.

Tiene útil aplicación para el estudio de la conectividad de los grafos.

Haremos un breve pseudocódigo:

algoritmo DFS (nodo origen){
 marcamos origen como visitado
para todos los adyacentes de origen y que no hayan sido visitados 
DFS(uno de los nodos que cumple la premisa dispuesta)
}

Recordemos que podemos obtener la adyacencia mediante la matriz de adyacencia...implementada sobre una matriz o sobre una lista de adyacencia

Matriz de Adyacencia- Definición

La Matriz de Adyacencia representa relaciones binarias,en este caso entre dos nodos de un grafo.

Esta matriz es cuadrada puesto que las columnas y filas representan los nodos o vértices del grafo.

Cada A[i][j] representa si existe una arista que una i,j nodo

0 si i y j no tiene arista que los relacione
1 si i y j si tiene arista que los relacione
2 si i=j y existe arista,bucle

Ejemplo De grafo no dirigido y su respectiva Matriz adyacencia ,podemos observar que la matriz es simétrica por ser no dirigido. 

En un grafo dirigido ocurre que:

La suma de los valores de la columna nos da el grado de entrada del nodo que la "proyecta".
La suma de los valores de la fila  nos da el grado de salida del nodo que la "proyecta".

Matriz de Incidencia - Definición

Una matriz de incidencia representa las relaciones binarias entre dos elementos,en nuestro caso entre un vértice y una arista del grafo.

Para construir la matriz de incidencia a partir de un grafo debemos realizar una matriz de n x a donde n es el nº de nodos o vértices y a es el nº de aristas.

En esta matriz las columnas representan las aristas y las filas los vértices.

Para cada A[i][j] ,nótese que A es la matriz de Incidencia, puede valer:

0 si vértice i no es incidente con arista j
1 si vértice i es incidente con arista j

Fotografía de un ejemplo de grafo no dirigido y su respectiva matriz de incidencia

Podemos que el nº de unos en una fila nos indican el nº de aristas que inciden en un vértice.