¿Qué es un grafo y cómo se puede representar?

Un grafo es una estructura de datos avanzada, que se usa muy frecuentemente en algunos esquemas algorítmicos.

Podemos definir grafo como una colección de nodos o vértices unidos por líneas o aristas. Los nodos o vértices representarían los objetos y las aristas las relaciones entre ellos.

Los grafos pueden ser dirigidos o no, son dirigidos cuando las líneas o arístas están orientadas en alguna dirección, sino estamos ante un grafo no dirigido.

El grado de un vértice en un grafo no dirigido es el número de aristas que salen o entran de él. En cambio si el grafo es dirigido se puede hablar de grado de entrada de un vértice (las líneas que entran a él) o grado de salida (las líneas que salen de él).

Un camino en un grafo dirigido es una secuencia finita de arcos entre dos vértices. Un ciclo o circuito es un camino que empieza y termina en el mismo vértice.

Existen varios tipos de grafos entre los que destacan el grafo nulo que es un grafo sin vértices, grafos acíclicos que son los que no contienen ciclos, grafos simples si entre cada par de vértices existe a lo sumo una arista que los una, grafo conexo si para cualquier par de vértices distintos existe un camino que los contiene, etc.

A la hora de representar los grafos tenemos muchas posibilidades entre las que destacan dibujarlo directamente con sus nodos y aristas, las matrices de adyacencia que son matrices cuadradas que solo pueden contener valores 1 o 0 (true o false) en las que el número 1 indica que hay arista entre los dos nodos de esa casilla de la matriz y si hay un 0 indica que no hay arista entre los dos nodos de esa casilla. Las listas de adyacencia también son otro método que se usa bastante para representar nodos, en realidad estás listas son un array de listas, siendo la cantidad de listas igual a la cantidad de nodos del grafo.

Ponemos un ejemplo gráfico de un grafo no dirigido y su correspondiente matriz de adyacencia que cómo vemos, al no estar dirigido nos sale una matriz simétrica:

Grafo no dirigido:

Grafo

Matriz de adyacencia:

Matriz de adyacencia