Иллюстрация: ориентированные кольца, топологическая сортировка и алгоритм Косараджу.

Алгоритмы графов. Часть 3 Диаграммы: направленные кольца, топологическая сортировка иKosarajuалгоритм

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

1. Понятие и представление ориентированных графов

концепция

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

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

На самом деле в определении ориентированного графа нам особо нечего объяснять, потому что каждому покажется, что это определение очень естественно, но мы всегда должны помнитьиметь направлениеэто дело!

представление данных

мы все еще используемсписок смежностиСохраняет ориентированный граф, гдеv-->wВыражается как顶点vСписок смежности содержит顶点w. Обратите внимание, что каждое ребро появляется здесь только один раз из-за направленности!

Давайте посмотрим, как реализована структура данных ориентированного графа.Digraph类(Directed Graph)

package Graph.Digraph;
import java.util.LinkedList;

public class Digraph{
    private final int V;//顶点数目
    private int E;//边的数目
    private LinkedList<Integer> adj[];//邻接表

    public Digraph(int V){
        //创建邻接表
        //将所有链表初始化为空
        this.V=V;this.E=0;
        adj=new LinkedList[V];
        for(int v=0;v<V;++v){
            adj[v]=new LinkedList<>();
        }
    }

    public int V(){ return V;}//获取顶点数目
    public int E(){ return E;}//获取边的数目

    //注意，只有这里与无向图不同
    public void addEdge(int v,int w){
        adj[v].add(w);//将w添加到v的链表中
        E++;
    }

    public Iterable<Integer> adj(int v){
        return adj[v];
    }

    //获取有向图的取反
    public Digraph reverse(){
        Digraph R=new Digraph(V);
        for(int v=0;v<V;v++){
            for(int w:adj(V))
                R.addEdge(w, v);//改变加入的顺序
        }
        return R;
    }
}

Если вы освоили представление данных неориентированными графами, вы обнаружите, что ориентированные графы только что изменили свое название.Есть только две вещи, на которые следует обратить внимание:addEdge(v,w)方法а такжеreverse()方法. При добавлении ребра нам нужно добавить его только один раз в список смежности из-за направления;reverse()方法Возможность возвращать инверсию графика (т. е. каждое направление перевернуто) пригодится в будущих приложениях, а пока у нас есть только представление.

2. Достижимость ориентированных графов

В неориентированном графе (предыдущий пост) мы используем поиск в глубину, чтобы найти путь, и поиск в ширину, чтобы найти кратчайший путь между двумя точками. Подумайте об этом, применимы ли они к ориентированным графам? Да,Тот же код может выполнить эту задачу, нам не нужно вносить никаких изменений (за исключением того, что Graph заменяется на Digraph).

Поскольку это содержание было подробно представлено в предыдущей статье, оно не будет расширяться.Если вам интересно, вы можете обратиться к предыдущей статье за подробными иллюстрациями.

3. Кольца и ориентированные ациклические графы.

В реальной жизни мы можем столкнуться с такой проблемой: проблемой планирования при ограничениях приоритета. Чтобы говорить человеческими словами, вам нужно сделать что-то вродеA,B,C, но существуют определенные ограничения по порядку выполнения этих трех действий, выполнитеBдолжны быть завершены доA,ДелатьCдолжны быть завершены доB…….Ваша задача состоит в том, чтобы придумать решение (как упорядочить различные вещи), чтобы ограничения не конфликтовали.

Как показано выше, с первым и вторым случаями справиться проще, а с третьим?Здесь что-то не так! ! !

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

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

1. Найдите направленные кольца

Наше решение состоит в том, чтобы использовать поиск в глубину. Потому что стек рекурсивных вызовов, поддерживаемый системой, представляет «текущий» направленный путь, по которому проходят. Как только мы найдем направленное реброv-->w,а такжеwуже существует в стеке, цикл найден. Поскольку стек представляет собойwнаправлениеvнаправленный путь иv-->wОн просто завершает кольцо. Между тем, если такое ребро не найдено, это означает, что направленное ребро ациклично.

Структура данных, которую мы использовали:

базовыйdfsалгоритм
добавить одинonStack[]Массивы используются для явной записи вершин в стеке (то есть, находится ли вершина в стеке).

Мы по-прежнему берем конкретный процесс в качестве примера, чтобы объяснить

Я не думаю, что конкретный код слишком сложен для вас, давайте посмотрим.

package Graph.Digraph;

import java.util.Stack;

public class DirectedCycle {
    private boolean [] marked;
    private int [] edgeTo;
    private Stack<Integer> cycle;//有向环中的所有顶点（如果存在）
    private boolean[] onStack; //递归调用的栈上的所有顶点

    public DirectedCycle(Digraph G){
        onStack=new boolean[G.V()];
        edgeTo=new int[G.V()];
        marked=new boolean[G.V()];
        
        for(int v=0;v<G.V();v++){
            if(!marked[v]) dfs(G,v);
        }
    }

    private void dfs(Digraph G,int v){
        onStack[v]=true;//进入dfs时，顶点v入栈
        marked[v]=true;
        for(int w:G.adj(v)){
            if(this.hasCycle()) return;
            else if(!marked[w]){
                edgeTo[w]=v;dfs(G,w);
            }
            else if(onStack[w]){
                //重点
                cycle=new Stack<Integer>();
                for(int x=v;x!=w;x=edgeTo[x])
                    cycle.push(x);

                cycle.push(w);
                cycle.push(v);
            }
        }
        //退出dfs时，将顶点v出栈
        onStack[v]=false;
    }

    public boolean hasCycle(){
        return cycle!=null;
    }

    public Iterable<Integer> cycle(){
        return cycle;
    }
}

Этот класс является стандартным рекурсивнымdfs()метод добавляет массив логического типаonStack[]для сохранения значений в стеке при рекурсивных вызовах все вершины. когда он находит крайv → wа такжеwНаходясь в стеке, он обнаружил направленный цикл. Все вершины кольца можно пройти черезedgeTo[]Ссылка в полученном.

в исполненииdfs(G,v), ищем направленный путь из начальной точки в v. Чтобы сохранить этот путь,DirectedCycleподдерживает массив, индексированный по вершинамonStack[], чтобы пометить все вершины в стеке рекурсивного вызова (после вызоваdfs(G,v)когдаonStack[v]установить какTrue, установите его наfalse).DirectedCycleМежду тем также использовалedgeTo[]массив, возвращающий все вершины кольца при обнаружении направленного кольца,

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

Как решить проблемы планирования при ограничениях приоритета? На самом деле это топологическая сортировка

Определение топологической сортировки: задан ориентированный граф, отсортируйте все вершины так, чтобы все направленные ребра указывали от элементов спереди к элементам сзади (или объясните, что это невозможно сделать).

Ниже приведен типичный пример (задача планирования занятий).

Он также имеет некоторые другие типичные приложения, такие как:

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

Теперь предположим, что у нас естьНаправленный ациклический граф, чтобы гарантировать, что мы можем выполнить топологическую сортировку; с помощью топологической сортировки мы, наконец, надеемся получить отношение последовательности набора вершин, элементы в передней части указывают на элементы в задней части, то есть для любого ребраv——>w, результат, который мы получаем, должен гарантировать顶点vсуществует顶点wПередний;

Мы используемdfsрешить эту проблему,вызовdfs(v)Время, должна быть одна из следующих трех ситуаций:

dfs(w)был вызван и вернулся (в этот моментwуже отмечено)
dfs(w)позвонили и не вернулись (думая об этой ситуации, это невозможно)
dfs(w)не звонил(wне был отмечен), ситуация на данный момент не сложная, и следующий вызов будетdfs(w), затем вернутьсяdfs(w), а затем позвонитеdfs(v)

Короче говоря, мы можем сделать очень важный вывод:dfs(w)всегда вdfs(v)сделано раньше. Другими словами, финишируй первым.dfsвершины

Убедитесь, что вы полностью поняли изложенную выше идею, остальное на самом деле относительно просто.Мы создаем стек всякий раз, когда вершинаdfsКогда закончите, поместите вершину в стек.Наконец, выталкивание - это порядок, который нам нужен

На самом деле топологическая сортировка в основном была решена нами здесь, но здесь мы расширяем ее и даем некоторые общие методы сортировки, которые, как мы только что упомянули, на самом деле называютсяобратный порядок. они основаны наdfs.

Предварительный порядок: ставить вершины в очередь перед рекурсивным вызовом
Postorder: поставить вершины в очередь после рекурсивного вызова
Обратный порядок: помещать вершины в стек после рекурсивного вызова

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

package Graph.Digraph;

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.Queue;
import java.util.Stack;

public class DepthFirstOrder {

    private boolean [] marked;
    private Queue<Integer> pre;//所有顶点的前序排列
    private Queue<Integer> post;//所有顶点的后序排列
    private Stack<Integer> reversePost;//所有顶点的逆后序排列

    public DepthFirstOrder(Digraph G){
        pre=new LinkedList<>();
        post=new LinkedList<>();
        reversePost = new Stack<>();

        marked=new boolean[G.V()];

        for(int v=0;v<G.V();v++){
            if(!marked[v]) dfs(G,v);
        }
    }

    private void dfs(Digraph G,int v){
        pre.offer(v);

        marked[v]=true;
        for(int w:G.adj(v))
            if(!marked[w])
                dfs(G, w);
        post.offer(v);
        reversePost.push(v);
    }

    //这里可以不用管
    public Iterable<Integer> pre()  
    {  return pre;  } 
   public Iterable<Integer> post() 
   {  return post;  } 
   public Iterable<Integer> reversePost() 
   {  return reversePost;  }
}

поздравляю, здесь мы смогли достичьтопологическая сортировка, последующийTopological类реализовал эту функцию. Когда заданный ориентированный граф содержит циклы,order()方法вернутьnull, в противном случае возвращает итератор, который выдает все вершины в топологическом порядке (конечно, вы также можете просто вывести отсортированные вершины). Конкретный код выглядит следующим образом:

package Graph.Digraph;

public class Topological {

    private Iterable<Integer> order;//顶点的拓扑顺序

    public Topological(Digraph G){
        //判断给定的图G是否有环
        DirectedCycle cyclefinder=new DirectedCycle(G);
        if(!cyclefinder.hasCycle()){
            DepthFirstOrder dfs=new DepthFirstOrder(G);
            order = dfs.reversePost();
        }
    }

    public Iterable<Integer> order(){
        return order;
    }

    //判断图G是不是有向无环图
    public boolean isDAG(){
        return order!=null;
    }
    
}

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

4. Сильно связанные компоненты

1. Определение сильной связи

Вспомним, что когда мы работали с неориентированными графами, мы решали проблему связности неориентированного графа с помощью поиска в глубину. Согласно глубокому поиску можно достичь всех связанных вершин, мы можем легко решить эту проблему. Однако когда задача становится ориентированным графом, все не так просто! Ниже приведены два примера неориентированного и ориентированного графов:

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

Вот еще несколько примеров сильной связи:

2. Компоненты сильной связи

В ориентированном графе сильная связность на самом деле является отношением эквивалентности между вершинами, поскольку она обладает следующими свойствами:

Рефлексивность: любая вершина v сильно связана сама с собой.
Симметрия: если v и w сильно связаны, то w и v также сильно связаны.
Транзитивность: если v и w сильно связаны, а w и x также сильно связаны, то тогда v и x также сильно связаны

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

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

3. Алгоритм Косараджу

Алгоритм Косараджу — это классический алгоритм решения проблем сильной связности, его реализация очень проста, но не проста для понимания.why, надеюсь вы взбодритесь, надеюсь смогу разъяснить (и просто надеюсь, попробую, если непонятно, то настоятельно рекомендуется совмещатьАлгоритм 4есть вместе)

Вспомните, как мы ранее решали проблему связности в части неориентированного графа.dfs может пройти ровно через один связный компонент, так что мы можем пройтиdfsдля подсчета, получить количество каждой вершиныid[]; Поэтому, когда мы решим проблему сильной связности ориентированных графов, мы также надеемся, что сможем использоватьdfs может пройти ровно через один связный компонентСвойства ; однако в ориентированных графах он не работает, взгляните на рисунок 1:

На рисунке 1dfs遍历Есть две ситуации:

Первый случай: еслиdfsотправная точка顶点A, то один разdfs遍历Он пройдет через всю область 1 и область 2, но область 1 и область 2 не сильно связаны, что является трудностью, которую доставляют нам ориентированные графы!

Второй случай:еслиdfsОтправная точка顶点D, то первыйdfsПройдёт второй участок во второй разdfsбудет пересекать область один, разве это не то, что мы хотим?

Итак, вторая ситуация дает нам направление для работы! то естьЕсли мы искусственно превратим все возможные случаи во второй случай, дело будет решено!

С направлением, затем далее, давайте посмотрим на случай реального ориентированного графа, как показано на рисунке 2, это ориентированный граф, и его различные сильно связанные компоненты отмечены на рисунке серым цветом; наша операция состоит в том, чтобы рассматривать каждый сильно связанный компонент какВершина (только большая), то какие последствия?Наш исходный ориентированный граф становится ориентированным ациклическим графом!

ps: подумай, почему не может быть колец? В силу посылки мы рассматриваем все компоненты сильной связности как вершины, если顶点Aа также顶点BЕсть кольцо междуAа такжеBОн будет представлять собой более крупный сильносвязный компонент! Они должны принадлежать вершине!

После получения ориентированного ациклического графа (DAG) все не так сложно. А теперь давайте еще раз вспомним нашу цель——На рисунке 1 мы хотим, чтобы область 2 выполнялась первой.dfs, то есть область, указанная стрелкой, идет первойdfs. После абстрагирования регионов в точки проблема сводится кВ ориентированном ациклическом графе мы хотим найти порядок, правило которого состоит в том, что вершины, на которые указывают стрелки, идут первыми.!

Вот, давайте немного подумаем, наша задача найти способ осуществитьdfsПорядок, этот порядок, не такой, как мы упоминали ранее.какая-тоОчень похожий? Я думаю, вам легко думать об этом, т.топологическая сортировка! ноЭто полная противоположность топологической сортировки.

Мы понимаем стрелку как приоритет.Для вершины A в вершину B, то A имеет более высокий приоритет, чем B. Тогда для топологической сортировкиболее высокий приоритет, для нашей задачисначала более низкий приоритет(В результате мы хотим, чтобы dfs не запускалась из места с низким приоритетом в место с высоким приоритетом)

Для рисунка 2: желаемый результат показан на рисунке 3:

если мы начнем с顶点1Началоdfs, повернуть направо, то ситуация, которой мы не хотим, никогда не произойдет! Потому что стрелки однонаправленные!

Я думаю, здесь вы должны почти понять, что я имею в виду. У нас есть последний маленький вопрос ---Как получить обратный порядок топологической сортировки?

На самом деле решение очень простое: для ориентированного графаG, мы сначала отрицаем (обратный метод), графикGПоменяйте порядок всех ребер , затем получите перевернутый графСортировка в обратном порядке (мы не можем назвать ее топологической сортировкой, потому что реальный случай циклический); Наконец, мы используем только что полученный порядок вершин дляGпровестиdfsВсё, тогда его принцип точно такой же, как у неориентированного графа в предыдущей статье!

Наконец, суммируйте этапы реализации алгоритма Косараджу:

1. В заданном ориентированном графе G используйте DepthFirstOrder для вычисления обратного обратного порядка его обратного графа GR.
2. Выполните стандартный поиск в глубину в G, но получите доступ к нему в порядке, который вы только что вычислили, а не в стандартном порядке. Все непомеченные вершины.

Конкретный код реализации реализован только в неориентированном графе.CC类Добавлены две строки кода (изменить порядок dfs)

package Graph.Digraph;

public class KosarajuSCC 
{ 
   private boolean[] marked;   // 已访问过的顶点 
   private int[] id;           // 强连通分量的标识符 
   private int count;          // 强连通分量的数量
   public KosarajuSCC(Digraph G) 
   { 
      marked = new boolean[G.V()]; 
      id = new int[G.V()]; 
      DepthFirstOrder order = new DepthFirstOrder(G.reverse()); //重点
      for (int s : order.reversePost()) //重点
         if (!marked[s]) 
         {  dfs(G, s); count++;  }
    }
   private void dfs(Digraph G, int v) 
   { 
      marked[v] = true; 
      id[v] = count; 
      for (int w : G.adj(v)) 
         if (!marked[w]) 
             dfs(G, w); 
   }
   public boolean stronglyConnected(int v, int w) 
   {  return id[v] == id[w];  }
   public int id(int v) 
   {  return id[v];  }
   public int count()
   { return count;}
}

Наконец, конкретный процесс работы прилагается:

имеютKosaraju算法, мы можем легко судить

Дана связность двух вершин (код вышеstronglyConnected)
Сколько компонентов сильной связи в этом графе (код вышеcount)

постскриптум

Что ж, это все, что касается ориентированных графов. Надеюсь, вы сможете полностью понять эти три алгоритма благодаря этой статье! , в следующей статье Сяочао с вами!

Наконец, я пришлю вам ментальную карту алгоритма графа

Фоновый ответ【Алгоритмы графов] Доступныйxmind формат, я просто хочу сказать: действительно много контента! 😥

Рисовать кодовые слова непросто, и если вы считаете, что эта статья полезна для вас, то внимание к автору — лучшая поддержка! Не стесняйтесь нажимать на нее, чтобы увидеть более благодарных!

Приглашаю всех обратить внимание на мой публичный номер:Сяочао сказал, и я продолжу писать об алгоритмах и структурах данных, а также о компьютерных основах. Вы также можете добавить меня в WeChatchao_hey(Примечание: Occupation-City), давайте общаться и добиваться прогресса вместе!

Ссылка на эту статью: "Алгоритмы" (четвертое издание)