Определение диаграммы
График состоит из конечного непустого набора вершин и набора краев между вершинами. Обычно он представлен как: g (v, e), где G представляет график, V - набор вершин на графике G, а E - набор краев на графике G.
Направленный график
Направленный край: если край от вершины VI к VJ имеет направление, этот край называется направленным краем, который также становится дугой (дугой). Это представлено упорядоченным <Vi, Vj>. VI называется дуговым хвостом, а VJ называется головой дуги.
Беспорядочная диаграмма
Недопроизведенный край: если край между вершинами VI к VJ не имеет направления, этот край называется неправомерным краем (краем) и представлен неупорядоченной парой (VI, VJ).
Простая картина
Простая диаграмма: в структуре графика, если нет вершины до его собственного края, и тот же край не появляется неоднократно, эта картина называется простой диаграммой.
Картинка класс
Указывает вершину
Первым шагом в создании класса графика является создание класса Vertex для сохранения вершин и краев. Этот класс функционирует так же, как у узла связанных списков и двоичных поисковых деревьев. В классе Vertex есть два члена данных: один для идентификации вершины, а другой, чтобы указать, была ли она доступна. Они названы этикеткой и были посещены соответственно.
Кода -копия выглядит следующим образом:
функция Vertex (метка) {
this.label = label;
}
Мы сохраняем все вершины в массиве, и в классе графика мы можем ссылаться на них по своей позиции в массиве
Указывает на край
Фактическая информация графика хранится на «краю», потому что они описывают структуру графика. Родительский узел двоичного дерева может иметь только два дочерних узла, но структура графика гораздо более гибкая. В вершине может быть подключен один край или несколько краев.
Мы будем использовать метод представления краев графика, чтобы стать таблицей смежности или массива смежности. В нем хранится массив, состоящий из списка соседних вершин вершин
Создайте график
Определите следующий класс графика:
Кода -копия выглядит следующим образом:
График функции (v) {
this.vertices = v; // вершины в высокую точку
this.edges = 0;
this.adj = [];
for (var i = 0; i <this.vertices; ++ i) {
this.adj [i] = [];
this.adj [i] .push ('');
}
this.addedge = addedge;
this.toString = toString;
}
Этот класс записывает, сколько ребра представляет график и использует длину и количество вершин графика для записи количества вершин.
Кода -копия выглядит следующим образом:
функция addedge () {
this.adj [v] .push (w);
this.adj [w] .push (v);
this.edges ++;
}
Здесь мы используем цикл для добавления Subarray для каждого элемента в массиве для хранения всех соседних вершин и инициализации всех элементов в пустые строки.
Прохождение картины
Глубинный приоритет
DexiFirstSearch, также известный как DexitFirstSearch, называется DFS для коротких.
Например, в поисках ключа в комнате, независимо от того, какую комнату вы начинаете, вы можете искать углы комнаты, тумбочки, кровати, под кровати, шкафы, телевизионные шкафы и т. Д. Один за другим, чтобы не пропустить никаких слепых пятен. После поиска всех ящиков и шкафов для хранения, затем поиска в следующей комнате.
Поиск приоритета глубины:
Поиск по глубине-означает доступ к вершине, которая не была посещена, отмечает ее как доступ, а затем рекурсивно доступа к другим вершинам, которые не посещались в таблице смежности начальной вершины.
Добавьте массив в класс графика:
Кода -копия выглядит следующим образом:
this.marked = []; // Сохранить посещаемые вершины
for (var i = 0; i <this.vertices; ++ i) {
this.marked [i] = false; // Инициализируется до false
}
Функция поиска в глубине:
Кода -копия выглядит следующим образом:
функция dfs (v) {
this.marked [v] = true;
// Если оператор здесь не требуется
if (this.adj [v]! = не определен) {
print ("Посещение Vertex:" + V);
для каждого (var w в этом.adj [v]) {
if (! this.marked [w]) {
this.dfs (w);
}
}
}
}
Поиск по ширине
Поиск по ширине (BFS)-это метод слепого поиска с целью систематического расширения и изучения всех узлов на графике, чтобы найти результаты. Другими словами, он не учитывает возможное местоположение результата и тщательно ищет всю картину, пока результат не будет найден.
Поиск по ширине начинается с первой вершины и попытайтесь получить доступ к вершине как можно ближе к нему, как показано на следующем рисунке:
Его принцип работы:
1. Сначала найдите недоступные вершины, прилегающие к текущей вершине и добавьте их в список и очередь посещенных вершин;
2. Затем выньте следующую вершину V с графика и добавьте его в список Vertice Cisted Vertice
3. Наконец -то добавьте все неопубликованные вершины, прилегающие к V в очередь
Ниже приведено определение функции поиска в ширину:
Кода -копия выглядит следующим образом:
Функция BFS (S) {
var queue = [];
this.marked = true;
queue.push (ы); // добавить к концу очереди
while (queue.length> 0) {
var v = queue.shift (); // Удалить из лидера команды
if (v == неопределенное) {
print ("Посещение Vertex:" + V);
}
для каждого (var w в этом.adj [v]) {
if (! this.marked [w]) {
this.edgeto [w] = v;
this.marked [w] = true;
queue.push (w);
}
}
}
}
Кратчайший путь
При выполнении поиска в ширину, самый короткий путь от одной вершины к другой подключенной вершине автоматически найден
Определить путь
Чтобы найти самый короткий путь, нам нужно изменить алгоритм поиска в ширину, чтобы записать путь от одной вершины к другой. Нам нужен массив, чтобы сохранить все края следующей вершины от одной вершины. Мы называем этот массив Edgeto
Кода -копия выглядит следующим образом:
this.edgeto = []; // добавить эту строку в класс графика
// функция BFS
Функция BFS (S) {
var queue = [];
this.marked = true;
queue.push (ы); // добавить к концу очереди
while (queue.length> 0) {
var v = queue.shift (); // Удалить из лидера команды
if (v == неопределенное) {
print ("Посещение Vertex:" + V);
}
для каждого (var w в этом.adj [v]) {
if (! this.marked [w]) {
this.edgeto [w] = v;
this.marked [w] = true;
queue.push (w);
}
}
}
}
Топологический алгоритм сортировки
Топологическая сортировка сортирует все вершины направленного графика, так что направленные края точка от передней вершины к задней вершине.
Топологический алгоритм сортировки похож на BFS. Разница состоит в том, что топологический алгоритм сортировки не сразу же выводит доступные вершины, а вместо этого обращается к всем смежным вершинам в текущей вершине смежной таблицы. До тех пор, пока этот список не будет исчерпан, текущая вершина не будет втянута в стек.
Топологический алгоритм сортировки разделен на две функции. Первая функция - TopSort (), которая используется для установления процесса сортировки и вызов вспомогательной функции TopSorthelper (), а затем отобразить сортированный список вершин.
Основная работа алгоритма сортировки топологии выполняется в рекурсивной функции Topsorthelper (), которая отмечает текущую вершину как доступ, а затем рекурсивно обращается к каждой вершине в текущей таблице смежности вершины, отмечая эти вершины как доступ. Наконец, вставьте текущую вершину в стек.
Кода -копия выглядит следующим образом:
// функция topsort ()
функция topsort () {
var stack = [];
var посетил = [];
for (var i = 0; i <this.vertices; i ++) {
посетил [i] = false;
}
for (var i = 0; i <this.vertices; i ++) {
if (посещение [i] == false) {
this.topsorthelper (i, посетил, стек);
}
}
for (var i = 0; i <stack.length; i ++) {
if (stack [i]! = undefined && стек [i]! = false) {
print (this.vertexlist [stack [i]]);
}
}
}
// функция TopSorthelper ()
Функция Topsorthelper (v, посещение, стек) {
посетил [v] = true;
для каждого (var w в этом.adj [v]) {
if (! Посещение [w]) {
this.topsorthelper (посетил [w], посетил, стек);
}
}
stack.push (v);
}