Простая для понимания топологическая сортировка

задняя часть структура данных

вводить

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

Что касается определения, Википедия говорит следующее:

Топологическая сортировка ориентированного ациклического графа (DAG) G состоит в том, чтобы упорядочить все вершины в G в линейную последовательность, так что любая пара вершин u и v в графе, если ребро ∈ E(G), тогда u появляется перед v в линейной последовательности. Обычно такую ​​линейную последовательность называют последовательностью, удовлетворяющей топологическому порядку, или сокращенно топологической последовательностью. Проще говоря, полный порядок на множестве получается из частичного порядка на множестве, этотопологическая сортировка.

Почему существует топологическая сортировка? Что делает топологическая сортировка?

Например, изучение серии руководств по Java.

код предмет Освоить до школы
A1 javaSE
A2 html
A3 Jsp А1, А2
A4 servlet A1
A5 ssm A3,A4
A6 springboot A5

Например, изучение классов (частей) Java от java Foundation до jsp/servlet, до ssm, до springboot, springcloud и т. д.循序渐进И есть зависимые процессы. существуетjspсначала научись мастеритьjava基础иhtmlБаза. Структура обучения для освоения jsp/servlet и jdbc и т.п. Затем этот процесс обучения составляет топологическую последовательность. КонечноЭта последовательность не уникальна,Вы можете выбрать любой порядок для несвязанных дисциплин (например, html и java могут запускаться в зависимости от того, что наступит раньше).

Тогда вышеуказанная последовательность может быть просто выражена как:

在这里插入图片描述

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

Некоторые другие примечания:

DGA: ориентированный ациклический граф Сеть AOV: данные в вершине можно понимать как объектно-ориентированные. Сеть AOE: данные находятся на стороне, что можно понимать как процессно-ориентированное!

А мы скажем проще,按照某种规则Выньте вершины этого графа, эти вершиныможет указывать на что-то или иметь связь.

правило:

  • Каждая вершина графа появляется только一次.
  • Если A предшествует B, то нет пути, где B предшествует A. (不能成环！！！！)
  • Порядок вершинубедитесь, что все следующие узлы, указывающие на него, находятся перед указанным узлом! (Например, A->B->C, тогда A должен быть перед B, а B должен быть перед C). Следовательно, пока выполняется это основное правило,Таким образом, топологически отсортированные последовательности не обязательно уникальны.!

Анализ алгоритма топологической сортировки

在这里插入图片描述
Обычные шаги (методы не обязательно уникальны):

  • найти один из графика DGA没有前驱выход вершины. (Его можно пройти или поддерживать с помощью приоритетной очереди)
  • Удалить ребра, начиная с этой точки. (ребро, на которое оно указывает, удаляется, чтобы найти следующую вершину без предшествующей)
  • повторить вышесказанное, пока не будет выведена последняя вершина.Если остались еще не выведенные вершины, значит есть кольцо!

Для простой последовательности, показанной выше, шаги можно просто описать так:

  • 1: удалить 1 или 2 выхода
    在这里插入图片描述
  • 2: удалить 2 или 3 и соответствующее ребро
    在这里插入图片描述
  • 3: удалить 3 или 4 и соответствующее ребро
    在这里插入图片描述
  • 3: Повторите вышеуказанные шаги правила
    在这里插入图片描述

Таким образом, топологическая сортировка завершается, итопологическая последовательность, но эта последовательностьне единственный! Также видно из процесса有很多选择方案, конкретный результат зависит от конструкции вашего алгоритма. Но пока оно выполняется, это топологически отсортированная последовательность.

Также обратите внимание1 2 4 3 6 5 7 9Эта последовательность удовлетворяет тому, что мы называем реляционным узлом, указывающим вперед, и указывающим назад. Если это вообще не имеет значения, то не обязательно до и после (например, 1,2)

Реализация кода топологической сортировки

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

Рассмотрим сначала存储. Для узлов, в первую очередь, у него очень много атрибутов точек соединения. При работе с разреженными матрицами лучше использовать список смежности. Поскольку узел указывает на меньшее количество узлов, используйте邻接矩阵较浪费资源.

Кроме того, если это последовательность, такая как 1, 2, 3, 4, 5, 6 для топологической сортировки, мы можем рассмотреть возможность использования массива, но если вы встретите аналогичные данные 1, 2, 88, 9999, вы можете рассмотреть используя карту для передачи. Так,

мыконкретные идеи кодаза:

  • новыйкласс узла, содержащий значение узла и его указатель (здесь набор списков используется напрямую вместо связанного списка)
  • Массив содержит узлы (число по умолчанию здесь более концентрированное). инициализация,Добавьте степень входа узла, на который указывает в то же время, когда каждый узел указывает +1! (A->C) затем входящая степень C+1;
  • сканировать все узлы. Сложите все точки со степенью вхождения 0 к одной栈(队列).
  • Когда стек (очередь) не пуст,бросить любой из узлов(Стек — это хвост, команда — это голова, и порядок не имеет значения. Вышеприведенный анализ показывает, что до тех пор, пока входящая степень равна нулю, порядок можно выбирать по желанию). выходной узел иnode指向的所有元素入度减一.Если степень вхождения точки уменьшается до 0, то она добавляется в стек (очередь).
  • Повторяйте описанную выше операцию до тех пор, пока стек не станет пустым.

Здесь в основном используютСтепень входа в хранилище стека или очереди равна только 0Узлу нужно только просканировать таблицу в первый раз и поместить нулевой уровень в стек (очередь).

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

Что касается конкретной демонстрации:

package 图论;

import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.List;
import java.util.Queue;
import java.util.Stack;

public class tuopu {
	static class node
	{
		int value;
		List<Integer> next;
		public node(int value) {
			this.value=value;
			next=new ArrayList<Integer>();
		}
		public void setnext(List<Integer>list) {
			this.next=list;
		}
	}

	public static void main(String[] args) {
		// TODO Auto-generated method stub
		node []nodes=new node[9];//储存节点
		int a[]=new int[9];//储存入度
		List<Integer>list[]=new ArrayList[10];//临时空间，为了存储指向的集合
		for(int i=1;i<9;i++)
		{
			nodes[i]=new node(i);
			list[i]=new ArrayList<Integer>();
		}
		initmap(nodes,list,a);
		
		//主要流程
		//Queue<node>q1=new ArrayDeque<node>();
		Stack<node>s1=new Stack<node>();
		for(int i=1;i<9;i++)
		{
			//System.out.print(nodes[i].next.size()+" 55 ");
			//System.out.println(a[i]);
			if(a[i]==0) {s1.add(nodes[i]);}
			
		}
		while(!s1.isEmpty())
		{
			node n1=s1.pop();//抛出输出
		    
			System.out.print(n1.value+" ");
			
			List<Integer>next=n1.next;
			for(int i=0;i<next.size();i++)
			{
				a[next.get(i)]--;//入度减一
				if(a[next.get(i)]==0)//如果入度为0
				{
					s1.add(nodes[next.get(i)]);
				}
			}
		}
	}

	private static void initmap(node[] nodes, List<Integer>[] list, int[] a) {
		list[1].add(3);
		nodes[1].setnext(list[1]);
		a[3]++;
		list[2].add(4);list[2].add(6);
		nodes[2].setnext(list[2]);
		a[4]++;a[6]++;
		list[3].add(5);
		nodes[3].setnext(list[3]);
		a[5]++;
		list[4].add(5);list[4].add(6);
		nodes[4].setnext(list[4]);
		a[5]++;a[6]++;
		list[5].add(7);
		nodes[5].setnext(list[5]);
		a[7]++;
		list[6].add(8);
		nodes[6].setnext(list[6]);
		a[8]++;
		list[7].add(8);
		nodes[7].setnext(list[7]);
		a[8]++;
		
	}
}

выходной результат

2 4 6 1 3 5 7 8

在这里插入图片描述
Конечно, как упоминалось выше, можно использовать как стеки, так и очереди! Если вы используете очередь, вы получите1 2 3 4 5 6 7 8топологическая последовательность

Что касается структуры графика, так как нет условий, эффективность может быть невысокой, а алгоритм может быть не идеальным, если есть ошибки оптимизации, прошу меня поправить!

Кроме того, я также прошу вас двигать рукамиНравится, следите (бигсай)Волна! Спасибо 🙏

Категории