algorithm
график

Вступление

замечания

Топологическая сортировка

Топологическое упорядочение или топологическая сортировка упорядочивает вершины в ориентированном ациклическом графе на линии, т. Е. В списке, так что все направленные ребра идут слева направо. Такое упорядочение не может существовать, если граф содержит направленный цикл, потому что нет способа, которым вы можете продолжать идти прямо по линии и все еще возвращаться туда, откуда вы начали.

Формально в графе G = (V, E) линейное упорядочение всех его вершин таково, что если G содержит ребро (u, v) ∈ E от вершины u до вершины v то u предшествует v в упорядочении.

Важно отметить, что каждая группа DAG имеет по крайней мере одну топологическую сортировку.

Известны алгоритмы построения топологического упорядочения любой DAG в линейном времени, например:

1. Вызовите depth_first_search(G) чтобы вычислить время окончания vf для каждой вершины v
2. Когда каждая вершина закончена, вставьте ее в переднюю часть связанного списка
3. связанный список вершин, так как теперь он отсортирован.

Топологическая сортировка может быть выполнена в ϴ(V + E) время, поскольку алгоритм поиска , глубина-сначала берет ϴ(V + E) время и он принимает Ω(1) (постоянное время) для вставки каждого из |V| вершины в списке связанного списка.

Во многих приложениях используются ориентированные ациклические графики, указывающие приоритеты среди событий. Мы используем топологическую сортировку, чтобы получить упорядочение для обработки каждой вершины перед любым ее преемником.

Вершины в графе могут представлять задачи, которые должны выполняться, и ребра могут представлять собой ограничения, которые одна задача должна выполнять перед другой; топологическое упорядочение является допустимой последовательностью для выполнения задач, заданных задачами, описанными в V

Экземпляр проблемы и ее решение

Пусть вершина v описывает Task(hours_to_complete: int) , то есть Task(4) описывает Task которая занимает 4 часа, а ребро e описывает время Cooldown(hours: int) , так что время Cooldown(3) описывает продолжительность чтобы остыть после выполнения заданной задачи.

Пусть наш граф называется dag (так как он является ациклическим графом) и пусть он содержит 5 вершин:

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));

где мы соединяем вершины с направленными ребрами, так что граф ацикличен,

// 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));

то существует три возможных топологических порядка между A и E ,

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

Алгоритм Торапа

Алгоритм Торапа для кратчайшего пути одного источника для неориентированного графа имеет временную сложность O (m), ниже Dijkstra.

Основные идеи заключаются в следующем. (Извините, я еще не пытался его реализовать, поэтому я мог бы пропустить некоторые мелкие детали. И исходная бумага была оплачена, поэтому я попытался восстановить ее из других источников, ссылающихся на нее. Удалите этот комментарий, если сможете проверить.)

• Есть способы найти остовное дерево в O (m) (не описано здесь). Вам нужно «развить» остовное дерево от самого короткого края до самого длинного, и это будет лес с несколькими компонентами, которые будут соединены до полного роста.
• Выберите целое число b (b> = 2) и рассмотрите только покрывающие леса с ограничением длины b ^ k. Объедините компоненты, которые являются точно такими же, но с разными k, и назовите минимум k уровнем компонента. Затем логически вставляйте компоненты в дерево. u является родительским элементом v, если u - наименьший компонент, отличный от v, который полностью содержит v. Корень - это весь граф, а листья - единственные вершины в исходном графе (с уровнем отрицательной бесконечности). Дерево все еще имеет только O (n) узлы.
• Поддерживайте расстояние каждого компонента до источника (как в алгоритме Дейкстры). Расстояние компонента с более чем одной вершиной - это минимальное расстояние его нерасширенных детей. Установите расстояние от исходной вершины до 0 и соответствующим образом обновите предков.
• Рассмотрим расстояния в базе b. При первом посещении узла на уровне k поместите его детей в ведра, разделяемые всеми узлами уровня k (как в сортировке ведра, заменяя кучу в алгоритме Дейкстры) цифрой k и выше ее расстояния. Каждый раз, посещая узел, учитывайте только его первые b ведра, посещайте и удаляйте каждый из них, обновляйте расстояние текущего узла и переставляйте текущий узел на свой собственный родитель с использованием нового расстояния и дожидайтесь следующего посещения для следующего ковши.
• Когда лист посещается, текущее расстояние является конечным расстоянием от вершины. Разверните все ребра из него в исходном графике и соответствующим образом обновите расстояния.
• Несколько раз перейдите на корневой узел (целый график) до достижения цели.

Он основан на том факте, что не существует края длиной менее l между двумя компонентами связующего леса с ограничением длины l, поэтому, начиная с расстояния x, вы можете сосредоточиться только на одном подключенном компоненте, пока не достигнете расстояние х + 1. Вы увидите некоторые вершины до того, как все вершины с более коротким расстоянием будут посещены, но это не имеет значения, поскольку известно, что здесь не будет более короткого пути от этих вершин. Другие части работают как сортировка ковша / MSD radix, и, конечно же, для этого требуется O (m) spanning tree.

Обнаружение цикла в ориентированном графе с использованием метода «Глубина первого обхода»

Цикл в ориентированном графе существует, если во время DFS есть задний край. Задний край - это край от узла к себе или к одному из предков в дереве DFS. Для несвязанного графа мы получаем лес DFS, поэтому вам нужно перебирать все вершины графа, чтобы найти непересекающиеся деревья DFS.

Реализация 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;
    }

Результат: Как показано ниже, на графике есть три задних края. Один между вершинами 0 и 2; между вершинами 0, 1 и 2; и вершина 3. Сложность времени поиска - O (V + E), где V - число вершин, E - число ребер.

Введение в теорию графов

Теория графов - это исследование графов, которые являются математическими структурами, используемыми для моделирования парных отношений между объектами.

Знаете ли вы, что почти все проблемы планеты Земля могут быть преобразованы в проблемы дорог и городов и решены? Теория графа была изобретена много лет назад, еще до изобретения компьютера. Леонард Эйлер написал статью о семи мостах Кенигсберга, которая рассматривается как первая статья теории графов. С тех пор люди поняли, что если мы сможем преобразовать любую проблему в эту проблему City-Road, мы сможем легко ее решить с помощью теории графов.

Теория диаграмм имеет много приложений. Одним из наиболее распространенных приложений является поиск кратчайшего расстояния между одним городом в другой. Мы все знаем, что для доступа к вашему компьютеру на этой веб-странице нужно было перемещать много маршрутизаторов с сервера. Теория графов помогает ему узнать маршрутизаторы, которые необходимо пересечь. Во время войны, на какую улицу нужно бомбардировать, чтобы отключить столицу от других, это также можно обнаружить с помощью теории графов.

Давайте сначала изучим некоторые базовые определения теории графов.

График:

Скажем, у нас 6 городов. Мы отмечаем их как 1, 2, 3, 4, 5, 6. Теперь мы соединяем города, которые имеют дороги между собой.

Это простой график, где показаны некоторые города с дорогими, которые соединяют их. В теории графов мы называем каждый из этих городов узлами или вершинами, а дороги называются Edge. График - это просто соединение этих узлов и ребер.

Узел может представлять много вещей. На некоторых графиках узлы представляют города, некоторые представляют аэропорты, а некоторые представляют собой квадрат в шахматной доске. Edge представляет собой отношение между каждым узлом. Это отношение может быть временем перехода из одного аэропорта в другой, движения рыцаря с одного квадрата на все остальные квадраты и т. Д.

Путь рыцаря в шахматной доске

Простыми словами, узел представляет любой объект, а Edge представляет связь между двумя объектами.

Прилегающий узел:

Если узел A разделяет ребро с узлом B , то B считается смежным с A. Другими словами, если два узла напрямую связаны, они называются соседними узлами. Один узел может иметь несколько соседних узлов.

График Directed и Undirected:

В ориентированных графах ребра имеют знаки направления с одной стороны, что означает, что ребра являются однонаправленными . С другой стороны, края неориентированных графов имеют знаки направления с обеих сторон, что означает, что они двунаправленные . Обычно неориентированные графы представлены без знаков по обе стороны от ребер.

Предположим, что вечеринка продолжается. Люди в партии представлены узлами, и между двумя людьми есть край, если они пожимают друг другу руки. Тогда этот граф неориентированный , потому что любой человек А пожать друг другу руки с человеком B тогда и только тогда , когда B также рукопожатием с. Напротив, если ребра от человека A другому человеку B соответствуют A , любующему B , тогда этот график направлен, потому что восхищение не обязательно взаимно. Первый тип графа называется неориентированным графом, а ребра называются неориентированными ребрами, а последний тип графа называется ориентированным графом, а ребра называются направленными ребрами.

Взвешенный и невзвешенный график:

Весовой график представляет собой график, в котором каждому ребру присваивается число (вес). Такие веса могут представлять собой, например, затраты, длины или мощности, в зависимости от проблемы.

Невзвешенный график просто противоположный. Предположим, что вес всех ребер одинаковый (предположительно 1).

Дорожка:

Путь представляет собой способ перехода от одного узла к другому. Он состоит из последовательности ребер. Между двумя узлами может быть несколько путей.

В приведенном выше примере есть два пути от A до D. A-> B, B-> C, C-> D - один путь. Стоимость этого пути равна 3 + 4 + 2 = 9 . Опять же, есть еще один путь A-> D. Стоимость этого пути равна 10 . Путь, который стоит наименьший, называется кратчайшим путем .

Степень:

Степень вершины - это число ребер, связанных с ней. Если есть какое-либо ребро, которое соединяется с вершиной на обоих концах (цикл), подсчитывается дважды.

В ориентированных графах узлы имеют два типа степеней:

• In-degree: количество ребер, указывающих на узел.
• Out-degree: количество ребер, которые указывают от узла к другим узлам.

Для неориентированных графов их просто называют степенью.

Некоторые алгоритмы, связанные с теорией графов

• Алгоритм Беллмана-Форда
• Алгоритм Дейкстры
• Алгоритм Форда-Фулкерсона
• Алгоритм Крускаля
• Алгоритм ближайшего соседа
• Алгоритм Прима
• Поиск по глубине
• Поиск по ширине

Сохранение графиков (матрица смежности)

Для хранения графика используются два метода:

• Матрица смежности
• Список прилавков

Матрица смежности представляет собой квадратную матрицу, используемую для представления конечного графа. Элементы матрицы указывают, смежны ли пары вершин или нет в графе.

Смежные средства «рядом или примыкают к чему-то другому» или быть рядом с чем-то. Например, ваши соседи находятся рядом с вами. В теории графов, если мы можем перейти к узлу B из узла A , можно сказать, что узел B смежна с узлом A. Теперь мы узнаем о том, как хранить, какие узлы примыкают к одному из них через матрицу Adjacency. Это означает, что мы будем представлять, какие узлы разделяют границу между ними. Здесь матрица означает 2D-массив.

Здесь вы можете увидеть таблицу рядом с графиком, это наша матрица смежности. Здесь Matrix [i] [j] = 1 представляет собой ребро между i и j . Если нет ребра, мы просто ставим Матрицу [i] [j] = 0 .

Эти края могут быть взвешены, так как они могут представлять расстояние между двумя городами. Затем мы помещаем значение в Матрицу [i] [j] вместо того, чтобы положить 1.

График, описанный выше, является двунаправленным или ненаправленным , что означает, что если мы сможем перейти к узлу 1 из узла 2 , мы также перейдем к узлу 2 из узла 1 . Если график был направлен , тогда на одной стороне графика был бы указатель стрелки. Даже тогда мы могли бы представлять его с помощью матрицы смежности.

Мы представляем узлы, которые не разделяют ребро на бесконечность . Следует заметить, что если граф неориентирован, матрица становится симметричной .

Псевдокод для создания матрицы:

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

Мы также можем заполнить матрицу следующим образом:

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

Для ориентированных графов мы можем удалить строку Matrix [n2] [n1] = cost .

Недостатки использования матрицы смещения:

Память - огромная проблема. Независимо от того, сколько ребер существует, нам всегда понадобится матрица размера N * N, где N - количество узлов. Если есть 10000 узлов, размер матрицы будет 4 * 10000 * 10000 около 381 мегабайт. Это огромная потеря памяти, если мы рассмотрим графики с несколькими ребрами.

Предположим, мы хотим выяснить, к какому узлу мы можем перейти от узла u . Нам нужно будет проверить всю строку u , которая стоит много времени.

Единственное преимущество в том, что мы можем легко найти связь между uv- узлами и их стоимостью с помощью Adjacency Matrix.

Java-код, реализованный с использованием вышеуказанного псевдокода:

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();
    }
}

Запуск кода: Сохраните файл и скомпилируйте его с помощью javac Represent_Graph_Adjacency_Matrix.java

Пример:

$ 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

Сохранение графиков (список адресов)

Список смежности представляет собой набор неупорядоченных списков, используемых для представления конечного графа. Каждый список описывает множество соседей вершины в графе. Для хранения графиков требуется меньше памяти.

Посмотрим на график и его матрицу смежности:

Теперь мы создаем список, используя эти значения.

Это называется списком смежности. Он показывает, какие узлы связаны с узлами. Мы можем хранить эту информацию с помощью 2D-массива. Но это будет стоить нам той же памяти, что и матрица смежности. Вместо этого мы будем использовать динамически выделенную память для ее хранения.

Многие языки поддерживают Vector или List, которые мы можем использовать для хранения списка смежности. Для этого нам не нужно указывать размер списка . Нам нужно только указать максимальное количество узлов.

Псевдокод будет:

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

Так как это - неориентированный граф, то есть ребро от x до y , также существует ребро от y до x . Если бы это был ориентированный граф, мы бы опустили второй. Для взвешенных графиков нам нужно также сохранить стоимость. Мы создадим другой вектор или список с именем cost [], чтобы сохранить их. Псевдокод:

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

Из этого можно легко узнать общее количество узлов, подключенных к любому узлу, и каковы эти узлы. Это занимает меньше времени, чем матрица смежности. Но если нам нужно выяснить, есть ли граница между u и v , было бы проще, если бы мы сохранили матрицу смежности.