algorithm
Grafico

Introducción

Observaciones

Clasificación topológica

Un ordenamiento topológico, o una ordenación topológica, ordena los vértices en un gráfico acíclico dirigido en una línea, es decir, en una lista, de manera que todos los bordes dirigidos van de izquierda a derecha. Tal ordenamiento no puede existir si la gráfica contiene un ciclo dirigido porque no hay manera de que pueda continuar en una línea y aún regresar a donde comenzó.

Formalmente, en una gráfica G = (V, E) , entonces un ordenamiento lineal de todos sus vértices es tal que si G contiene un borde (u, v) ∈ E desde el vértice u al vértice v entonces u precede a v en el ordenamiento.

Es importante tener en cuenta que cada DAG tiene al menos un ordenamiento topológico.

Hay algoritmos conocidos para construir un ordenamiento topológico de cualquier DAG en tiempo lineal, un ejemplo es:

1. Llame a depth_first_search(G) para calcular los tiempos de finalización vf para cada vértice v
2. Cuando haya terminado cada vértice, insértelo en el frente de una lista vinculada
3. La lista enlazada de vértices, ya que ahora está ordenada.

Se puede realizar una ordenación topológica en el tiempo ϴ(V + E) , ya que el algoritmo de búsqueda primero en profundidad toma el tiempo ϴ(V + E) y toma Ω(1) (tiempo constante) para insertar cada uno de |V| vértices en el frente de una lista vinculada.

Muchas aplicaciones utilizan gráficos acíclicos dirigidos para indicar las precedencias entre los eventos. Utilizamos la ordenación topológica para obtener un orden para procesar cada vértice antes de cualquiera de sus sucesores.

Los vértices en una gráfica pueden representar tareas a realizar y los bordes pueden representar restricciones que una tarea debe realizar antes que otra; un ordenamiento topológico es una secuencia válida para realizar el conjunto de tareas de las tareas descritas en V

Ejemplo de problema y su solución

Deje que un vértice v describa una Task(hours_to_complete: int) , es decir, la Task(4) describe una Task que toma 4 horas para completar, y un borde e describe un Cooldown(hours: int) tal que Cooldown(3) describe una duración de tiempo para enfriarse después de una tarea completada.

Que nuestro gráfico se llame dag (ya que es un gráfico acíclico dirigido), y que contenga 5 vértices:

A <- dag.add_vertex(Task(4)); 
B <- dag.add_vertex(Task(5));
C <- dag.add_vertex(Task(3)); 
D <- dag.add_vertex(Task(2));
E <- dag.add_vertex(Task(7));

donde conectamos los vértices con bordes dirigidos de modo que el gráfico sea acíclico,

// A ---> C ----+
// |      |     |
// v      v     v
// B ---> D --> E
dag.add_edge(A, B, Cooldown(2));
dag.add_edge(A, C, Cooldown(2));
dag.add_edge(B, D, Cooldown(1));
dag.add_edge(C, D, Cooldown(1));
dag.add_edge(C, E, Cooldown(1));
dag.add_edge(D, E, Cooldown(3));

entonces hay tres posibles ordenamientos topológicos entre A y E ,

1. A -> B -> D -> E
2. A -> C -> D -> E
3. A -> C -> E

Algoritmo de Thorup

El algoritmo de Thorup para la ruta más corta de una sola fuente para el gráfico no dirigido tiene la complejidad de tiempo O (m), más baja que Dijkstra.

Las ideas básicas son las siguientes. (Lo siento, no intenté implementarlo todavía, así que podría faltar algunos detalles menores. Y el papel original está bloqueado, así que intenté reconstruirlo a partir de otras fuentes que lo mencionan. Por favor, elimine este comentario si lo pudo verificar).

• Hay formas de encontrar el árbol de expansión en O (m) (no se describe aquí). Debe "hacer crecer" el árbol de expansión desde el borde más corto hasta el más largo, y sería un bosque con varios componentes conectados antes de que crezca completamente.
• Seleccione un número entero b (b> = 2) y solo considere los bosques extensivos con el límite de longitud b ^ k. Combine los componentes que son exactamente iguales pero con k diferente, y llame al mínimo k el nivel del componente. Luego lógicamente hacer componentes en un árbol. u es el padre de v iff u es el componente más pequeño distinto de v que contiene completamente v. La raíz es la gráfica completa y las hojas son vértices simples en la gráfica original (con el nivel de infinito negativo). El árbol todavía tiene solo nodos O (n).
• Mantenga la distancia de cada componente a la fuente (como en el algoritmo de Dijkstra). La distancia de un componente con más de un vértice es la distancia mínima de sus hijos no expandidos. Establezca la distancia del vértice de origen a 0 y actualice los ancestros en consecuencia.
• Considera las distancias en base b. Cuando visite un nodo en el nivel k la primera vez, coloque a sus hijos en cubos compartidos por todos los nodos del nivel k (como en la clasificación de cubos, reemplazando el montón en el algoritmo de Dijkstra) por el dígito k y mayor de su distancia. Cada vez que visite un nodo, considere solo sus primeros b cubos, visite y elimine cada uno de ellos, actualice la distancia del nodo actual y vuelva a vincular el nodo actual a su propio padre utilizando la nueva distancia y espere la próxima visita para la siguiente visita cubos
• Cuando se visita una hoja, la distancia actual es la distancia final del vértice. Expanda todos los bordes en el gráfico original y actualice las distancias según corresponda.
• Visite el nodo raíz (gráfico completo) varias veces hasta llegar al destino.

Se basa en el hecho de que no hay un borde con una longitud menor que l entre dos componentes conectados del bosque de expansión con una limitación de longitud l, por lo que, a partir de la distancia x, puede enfocarse solo en un componente conectado hasta llegar a la distancia x + l. Visitará algunos vértices antes de que se vean todos los vértices con distancias más cortas, pero eso no importa porque se sabe que no habrá un camino más corto hasta aquí desde esos vértices. Otras partes funcionan como la clasificación de cubo / MSD radix, y por supuesto, requiere el árbol de expansión O (m).

Detectando un ciclo en un gráfico dirigido usando Depth First Traversal

Existe un ciclo en un gráfico dirigido si se descubre un borde posterior durante un DFS. Un borde posterior es un borde de un nodo a sí mismo o uno de los ancestros en un árbol DFS. Para un gráfico desconectado, obtenemos un bosque DFS, por lo que debe recorrer todos los vértices en el gráfico para encontrar árboles DFS separados.

Implementación de C ++:

    #include <iostream>
     #include <list>
        
    using namespace std; 
    
    #define NUM_V   4

    bool helper(list<int> *graph, int u, bool* visited, bool* recStack)
    {
        visited[u]=true;
        recStack[u]=true;
        list<int>::iterator i;
        for(i = graph[u].begin();i!=graph[u].end();++i)
        {  
            if(recStack[*i]) //if vertice v is found in recursion stack of this DFS traversal
                return true;
            else if(*i==u) //if there's an edge from the vertex to itself
                return true;
            else if(!visited[*i])
            {   if(helper(graph, *i, visited, recStack))
                   return true;
            }
        }
        recStack[u]=false;
        return false;
    }
    /*
    /The wrapper function calls helper function on each vertices which have not been visited. Helper function returns true if it detects a back edge in the subgraph(tree) or false.
*/
    bool isCyclic(list<int> *graph, int V)
    {
      bool visited[V];  //array to track vertices already visited
      bool recStack[V]; //array to track vertices in recursion stack of the traversal.

      for(int i = 0;i<V;i++)
       visited[i]=false, recStack[i]=false;  //initialize all vertices as not visited and not recursed

      for(int u = 0; u < V; u++) //Iteratively checks if every vertices have been visited
      {   if(visited[u]==false)
          {  if(helper(graph, u, visited, recStack)) //checks if the DFS tree from the vertex contains a cycle
               return true;
          }
      }
       return false;
    }
    /*
    Driver function
    */
    int main()
    {
        list<int>* graph = new list<int>[NUM_V];
        graph[0].push_back(1);
        graph[0].push_back(2);
        graph[1].push_back(2);
        graph[2].push_back(0);
        graph[2].push_back(3);
        graph[3].push_back(3);
        bool res = isCyclic(graph, NUM_V);
        cout<<res<<endl;
    }

Resultado: Como se muestra a continuación, hay tres bordes posteriores en el gráfico. Uno entre vértice 0 y 2; entre el vértice 0, 1 y 2; y vértice 3. La complejidad del tiempo de búsqueda es O (V + E) donde V es el número de vértices y E es el número de bordes.

Introducción a la teoría de grafos

La Teoría de los Gráficos es el estudio de los gráficos, que son estructuras matemáticas utilizadas para modelar relaciones de pares entre objetos.

¿Sabías que casi todos los problemas del planeta Tierra se pueden convertir en problemas de Caminos y Ciudades, y se pueden resolver? La teoría de los gráficos se inventó hace muchos años, incluso antes de la invención de la computadora. Leonhard Euler escribió un artículo sobre los Siete Puentes de Königsberg, que se considera el primer artículo de Graph Theory. Desde entonces, las personas se han dado cuenta de que si podemos convertir cualquier problema en este problema de la ciudad-carretera, podemos resolverlo fácilmente mediante la Teoría de grafos.

La teoría de los gráficos tiene muchas aplicaciones. Una de las aplicaciones más comunes es encontrar la distancia más corta entre una ciudad y otra. Todos sabemos que para llegar a su PC, esta página web tenía que viajar muchos enrutadores desde el servidor. La Teoría de Gráficos le ayuda a descubrir los enrutadores que necesitaban ser cruzados. Durante la guerra, qué calle necesita ser bombardeada para desconectar la ciudad capital de otras, eso también se puede descubrir usando la Teoría de Gráficos.

Primero aprendamos algunas definiciones básicas sobre la teoría de grafos.

Grafico:

Digamos que tenemos 6 ciudades. Los marcamos como 1, 2, 3, 4, 5, 6. Ahora conectamos las ciudades que tienen caminos entre sí.

Este es un gráfico simple donde se muestran algunas ciudades con las carreteras que las conectan. En Graph Theory, llamamos a cada una de estas ciudades Node o Vertex y las carreteras se llaman Edge. El gráfico es simplemente una conexión de estos nodos y bordes.

Un nodo puede representar muchas cosas. En algunos gráficos, los nodos representan ciudades, algunos representan aeropuertos, algunos representan un cuadrado en un tablero de ajedrez. Edge representa la relación entre cada uno de los nodos. Esa relación puede ser el momento de ir de un aeropuerto a otro, los movimientos de un caballero de una casilla a todas las demás plazas, etc.

Camino del caballero en un tablero de ajedrez

En palabras simples, un nodo representa cualquier objeto y Edge representa la relación entre dos objetos.

Nodo adyacente:

Si un nodo A comparte un borde con el nodo B , entonces se considera que B es adyacente a A. En otras palabras, si dos nodos están conectados directamente, se llaman nodos adyacentes. Un nodo puede tener múltiples nodos adyacentes.

Gráfico dirigido y no dirigido:

En los gráficos dirigidos, los bordes tienen signos de dirección en un lado, lo que significa que los bordes son unidireccionales . Por otro lado, los bordes de los gráficos no dirigidos tienen señales de dirección en ambos lados, lo que significa que son bidireccionales . Por lo general, los gráficos no dirigidos se representan sin signos en ninguno de los lados de los bordes.

Supongamos que hay una fiesta en marcha. Las personas en el grupo están representadas por nodos y hay una ventaja entre dos personas si se dan la mano. Entonces, esta gráfica no está dirigida porque cualquier persona A le da la mano a la persona B si y solo si B también le da la mano a A. Por el contrario, si los bordes de una persona de A a otra persona B corresponde a A 's admirando B, entonces este gráfico se dirige, debido a la admiración no es necesariamente un movimiento alternativo. El primer tipo de gráfico se denomina gráfico no dirigido y los bordes se denominan bordes no dirigidos, mientras que el último tipo de gráfico se denomina gráfico dirigido y los bordes se denominan bordes directos

Gráfico ponderado y no ponderado:

Un gráfico ponderado es un gráfico en el que se asigna un número (el peso) a cada borde. Dichos pesos podrían representar, por ejemplo, costos, longitudes o capacidades, dependiendo del problema en cuestión.

Un gráfico no ponderado es simplemente lo contrario. Asumimos que, el peso de todos los bordes es el mismo (presumiblemente 1).

Camino:

Una ruta representa una forma de ir de un nodo a otro. Se compone de secuencia de aristas. Puede haber múltiples rutas entre dos nodos.

En el ejemplo anterior, hay dos caminos de A a D. A-> B, B-> C, C-> D es una ruta. El costo de este camino es 3 + 4 + 2 = 9 . Una vez más, hay otro camino A-> D. El costo de este camino es 10 . La ruta que cuesta lo más bajo se llama ruta más corta .

La licenciatura:

El grado de un vértice es el número de bordes que están conectados a él. Si hay algún borde que se conecta al vértice en ambos extremos (un bucle) se cuenta dos veces.

En los gráficos dirigidos, los nodos tienen dos tipos de grados:

• En grado: el número de bordes que apuntan al nodo.
• Out-degree: el número de bordes que apuntan desde el nodo a otros nodos.

Para las gráficas no dirigidas, simplemente se llaman grados.

Algunos algoritmos relacionados con la teoría de grafos

• Algoritmo de Bellman-Ford
• Algoritmo de Dijkstra
• Algoritmo Ford – Fulkerson
• Algoritmo de Kruskal
• Algoritmo vecino más cercano
• Algoritmo de prim
• Búsqueda en profundidad primero
• Búsqueda de amplitud

Almacenando Gráficos (Matriz de Adyacencia)

Para almacenar una gráfica, dos métodos son comunes:

• Matriz de adyacencia
• Lista de adyacencia

Una matriz de adyacencia es una matriz cuadrada que se utiliza para representar un gráfico finito. Los elementos de la matriz indican si los pares de vértices son adyacentes o no en el gráfico.

Adyacente significa 'al lado o contiguo a otra cosa' o estar al lado de algo. Por ejemplo, tus vecinos están adyacentes a ti. En la teoría de gráficos, si podemos ir al nodo B desde el nodo A , podemos decir que el nodo B es adyacente al nodo A. Ahora aprenderemos cómo almacenar qué nodos son adyacentes a cada uno a través de la Matriz de Adyacencia. Esto significa que vamos a representar qué nodos comparten el borde entre ellos. Aquí matriz significa matriz 2D.

Aquí puede ver una tabla al lado del gráfico, esta es nuestra matriz de adyacencia. Aquí la matriz [i] [j] = 1 representa que hay un borde entre i y j . Si no hay ventaja, simplemente ponemos Matrix [i] [j] = 0 .

Estos bordes pueden ser pesados, al igual que puede representar la distancia entre dos ciudades. Luego pondremos el valor en Matriz [i] [j] en lugar de poner 1.

El gráfico descrito anteriormente es bidireccional o no dirigido , lo que significa que si podemos ir al nodo 1 desde el nodo 2 , también podemos ir al nodo 2 desde el nodo 1 . Si la gráfica fuera dirigida , entonces habría un signo de flecha en un lado de la gráfica. Incluso entonces, podríamos representarlo usando una matriz de adyacencia.

Representamos los nodos que no comparten borde por infinito . Una cosa a tener en cuenta es que, si la gráfica no está dirigida, la matriz se vuelve simétrica .

El pseudocódigo para crear la matriz:

Procedure AdjacencyMatrix(N):    //N represents the number of nodes
Matrix[N][N]
for i from 1 to N
    for j from 1 to N
        Take input -> Matrix[i][j]
    endfor
endfor

También podemos rellenar la matriz utilizando esta forma común:

Procedure AdjacencyMatrix(N, E):    // N -> number of nodes
Matrix[N][E]                        // E -> number of edges
for i from 1 to E
    input -> n1, n2, cost
    Matrix[n1][n2] = cost
    Matrix[n2][n1] = cost
endfor

Para gráficos dirigidos, podemos eliminar Matrix [n2] [n1] = línea de costo .

Los inconvenientes de usar la matriz de adyacencia:

La memoria es un gran problema. No importa cuántos bordes haya, siempre necesitaremos una matriz de tamaño N * N donde N es el número de nodos. Si hay 10000 nodos, el tamaño de la matriz será 4 * 10000 * 10000 alrededor de 381 megabytes. Esto es un gran desperdicio de memoria si consideramos gráficos que tienen algunos bordes.

Supongamos que queremos averiguar a qué nodo podemos ir desde un nodo u . Tendremos que revisar toda la fila de u , lo que cuesta mucho tiempo.

El único beneficio es que podemos encontrar fácilmente la conexión entre los nodos UV y su costo utilizando la Matriz de Adyacencia.

Código Java implementado utilizando el pseudo-código anterior:

import java.util.Scanner;
 
public class Represent_Graph_Adjacency_Matrix 
{
    private final int vertices;
    private int[][] adjacency_matrix;
 
    public Represent_Graph_Adjacency_Matrix(int v) 
    {
        vertices = v;
        adjacency_matrix = new int[vertices + 1][vertices + 1];
    }
 
    public void makeEdge(int to, int from, int edge) 
    {
        try 
        {
            adjacency_matrix[to][from] = edge;
        }
        catch (ArrayIndexOutOfBoundsException index) 
        {
            System.out.println("The vertices does not exists");
        }
    }
 
    public int getEdge(int to, int from) 
    {
        try 
        {
            return adjacency_matrix[to][from];
        }
        catch (ArrayIndexOutOfBoundsException index) 
        {
            System.out.println("The vertices does not exists");
        }
        return -1;
    }
 
    public static void main(String args[]) 
    {
        int v, e, count = 1, to = 0, from = 0;
        Scanner sc = new Scanner(System.in);
        Represent_Graph_Adjacency_Matrix graph;
        try 
        {
            System.out.println("Enter the number of vertices: ");
            v = sc.nextInt();
            System.out.println("Enter the number of edges: ");
            e = sc.nextInt();
 
            graph = new Represent_Graph_Adjacency_Matrix(v);
 
            System.out.println("Enter the edges: <to> <from>");
            while (count <= e) 
            {
                to = sc.nextInt();
                from = sc.nextInt();
 
                graph.makeEdge(to, from, 1);
                count++;
            }
 
            System.out.println("The adjacency matrix for the given graph is: ");
            System.out.print("  ");
            for (int i = 1; i <= v; i++)
                System.out.print(i + " ");
            System.out.println();
 
            for (int i = 1; i <= v; i++) 
            {
                System.out.print(i + " ");
                for (int j = 1; j <= v; j++) 
                    System.out.print(graph.getEdge(i, j) + " ");
                System.out.println();
            }
 
        }
        catch (Exception E) 
        {
            System.out.println("Somthing went wrong");
        }
 
        sc.close();
    }
}

Ejecutando el código: Guarde el archivo y compile usando javac Represent_Graph_Adjacency_Matrix.java

Ejemplo:

$ java Represent_Graph_Adjacency_Matrix
Enter the number of vertices:
4
Enter the number of edges:
6
Enter the edges: <to> <from>
1 1
3 4
2 3
1 4
2 4
1 2
The adjacency matrix for the given graph is:
  1 2 3 4
1 1 1 0 1
2 0 0 1 1
3 0 0 0 1
4 0 0 0 0

Almacenamiento de gráficos (lista de adyacencia)

La lista de adyacencia es una colección de listas desordenadas que se utilizan para representar un gráfico finito. Cada lista describe el conjunto de vecinos de un vértice en un gráfico. Se necesita menos memoria para almacenar gráficos.

Veamos un gráfico, y su matriz de adyacencia:

Ahora creamos una lista usando estos valores.

Esto se llama lista de adyacencia. Muestra qué nodos están conectados a qué nodos. Podemos almacenar esta información utilizando una matriz 2D. Pero nos costará la misma memoria que la Matriz de Adyacencia. En su lugar, vamos a utilizar memoria asignada dinámicamente para almacenar esta.

Muchos idiomas admiten Vector o Lista que podemos usar para almacenar la lista de adyacencia. Para estos, no necesitamos especificar el tamaño de la Lista . Solo necesitamos especificar el número máximo de nodos.

El pseudocódigo será:

Procedure Adjacency-List(maxN, E):       // maxN denotes the maximum number of nodes
edge[maxN] = Vector()                    // E denotes the number of edges
for i from 1 to E
    input -> x, y                        // Here x, y denotes there is an edge between x, y
    edge[x].push(y)
    edge[y].push(x)
end for
Return edge

Dado que este es un gráfico no dirigido, hay un borde de x a y , también hay un borde de y a x . Si fuera un gráfico dirigido, omitiríamos el segundo. Para los gráficos ponderados, necesitamos almacenar el costo también. Crearemos otro vector o lista llamado costo [] para almacenar estos. El pseudocódigo:

Procedure Adjacency-List(maxN, E):
edge[maxN] = Vector()
cost[maxN] = Vector()
for i from 1 to E
    input -> x, y, w
    edge[x].push(y)
    cost[x].push(w)
end for
Return edge, cost

A partir de este, podemos averiguar fácilmente el número total de nodos conectados a cualquier nodo y qué son estos nodos. Lleva menos tiempo que la Matriz de Adyacencia. Pero si tuviéramos que averiguar si hay una ventaja entre u y v , habría sido más fácil si hubiéramos mantenido una matriz de adyacencia.