предисловие
в структурах данных и алгоритмахТеория графовСреди них (генерирующий) алгоритм минимального связующего дерева является широко используемым и реалистичным алгоритмом. Но, возможно, многие люди не очень хорошо понимают эту концепцию. Давайте заглянем в энциклопедию Baidu дляОпределение минимального связующего дерева:
Остовное дерево связного графа с n узлами — это минимальный связный подграф исходного графа, содержащий все n узлов исходного графа и имеющий наименьшее количество ребер, поддерживающих связность графа. Минимальное остовное дерево можно рассчитать с помощью алгоритма Краскала или алгоритма простого числа.
С точки зрения непрофессионала, это минимальное остовное дерево.Содержит все узлы исходного графаи только用最少的边и最小的权值距离. так какnТребуется минимум узловn-1Каждое ребро связано, и расстояние требует определенной стратегии для выбора подходящего ребра.
По определению минимальное остовное дерево на самом деле представляет собой структуру, которую можно рассматривать как дерево. в то время как минимальная остовная древовидная структураисходное изображение(особенно в случае с кольцами). С помощью этого графа мы используем алгоритм для формирования алгоритма минимального связующего дерева, который можно назвать алгоритмом минимального связующего дерева. Существует два конкретных метода и стратегии реализации:kruskalалгоритм иprimалгоритм.
Прежде чем изучать алгоритм реализации минимального остовного дерева, мы должны сначала определить структуру и значение минимального остовного дерева. Прежде всего, я желаю вам лучшего понимания на основе некоторых фотографий.
рассказ
В планировании городских дорог в Китае это очень научное исследование (просто предположим, что к обучению не нужно относиться серьезно). Мощение городских дорог может проходить следующие этапы.
- Первоначально в различных городах не было автомобильных дорог (железных дорог). В городе его нет!
- Правительство планирует проложить дороги (железные дороги) в различных городах, и каждый город хочет стать транспортным узлом, чтобы быстро добраться до других городов! Однако в этом случае национальные коллективные ресурсы не выдерживают, а стоимость строительства слишком высока. И привести к огромным потерям!
- В конце концов, страна выбирает несколько крупных городов для подключения, а некоторые города могут совершать лишь небольшой объезд, а страны со слишком дальними объездами и большим количеством людей рассматривают возможность строительства новых дорог (железных дорог). Соответствующим образом повысить эффективность.
Таким образом, мы должны выбрать стоимость и наименьший маршрут из циклического графа с одной стороны.минимальная стоимость(Общее расстояние наименьшее, и сохраняется больше всего золота) С другой стороныПодключить все города.
Однако согласно приведенному выше рисунку мы можем получить следующее минимальное остовное дерево:
- сомнительный
主要矛盾решающую роль в проблеме. Первичные противоречия и вторичные противоречия влияют друг на друга, проникают друг в друга и могут до известной степени переходить друг в друга. Поэтому смотрим на проблемуВозьмите ключ, найдите ядро. - существуетвозраст дорогиОсновное противоречие городской связности состоит в том, что время идет медленно, а стоимость строительства является второстепенным противоречием по сравнению со временем транспортировки. Поэтому в эпоху автомагистралей мы делаем все возможное, чтобы города были связаны напрямую и сокращали время соединения между городами. И немного учета затрат на строительство дорог!С развитием науки и техники, Передача информации быстрее, чем автомобильный транспорт, поэтому основное противоречие события изменилось со времени транспортировки на стоимость. Поэтому мы сосредоточимся на расстоянии (кратчайшем), соединяющем все точки. При этом используется алгоритм минимального связующего дерева.
Точно так же есть мосты, связанные с островами в местных районах, и более или менее будут использоваться дорогостоящие подводные каналы.
Алгоритм Крускала
Выше описано, что такое минимальное остовное дерево, но нам нужно понять, как формируется минимальное остовное дерево. Дайте вам график и сгенерируйте минимальное остовное дерево, конечно, требуются определенные правила. С точки зрения реализации минимального остовного дерева существуют алгоритмы prim и kruskal.Стратегии этих двух алгоритмов различны, но временная сложность одинакова.
Основная идея энциклопедии Baidu:
Сначала постройте подграф с n вершинами и пустым набором ребер, считайте каждую вершину в подграфе корневым узлом каждого дерева, а затем выберите вершину с наименьшим весом из набора ребер E сети. ребра принадлежат разным деревьям, добавить его в подграф, то есть объединить два дерева в одно дерево, иначе, если две вершины ребра уже попадают на одно и то же дерево, нецелесообразно, а ребро с следует взять наименьший вес и повторить попытку. И так до тех пор, пока в лесу не останется только одно дерево, то есть подграф содержит n-1 ребер.
короче,KruskalЕдиницей планирования алгоритма является ребро, и его убеждение:все стороны могут быть как можно меньше, аспекты реализации алгоритма иНаборы поиска объединения (непересекающиеся наборы) очень похожи, вам нужно использовать набор проверок объединения, чтобы определить, принадлежат ли две точки одному и тому же набору.
Конкретные шаги алгоритма:
- Добавлять объекты ребра (и 2 вершины) в коллекцию (приоритетную очередь) по очереди
q1середина.Изначально все точки независимы друг от друга. - снять ток
q1Наименьшее ребро, чтобы определить, связаны ли две точки ребра. -
Если Китай Юником,перепрыгни,Если не подключен, затем используйте
union(Union Finder Merge) Объединяет две вершины. Это ребро используется (может хранить или вычислять значения). - Повторяйте операции 2, 3 до установки (приоритетная очередь)
q1Пусто. Выбранные ребра в это время составляют минимальное остовное дерево.
Алгоритм Прима
КромеKruskalВнешний алгоритм, алгоритм Prim (PrimАлгоритм) также обычно используется минимальный алгоритм охваченного дерева. Хотя эффективность примерно одинаково. Но жадный путь иKruskalполностью отличается. Основные убеждения алгоритма prim таковы:Найдите наименьший из известных спредов. как это реализовано иDijkstraАлгоритм похож, но немного отличается, Дейкстра находит кратчайший путь из одного источника. И каждый раз, когда вычисляется точка, необходимо повторно обновлять расстояние для этой точки. А приму даже не нужно обновлять расстояние.Непосредственно найти соседнее ребро известной точки, чтобы присоединиться к минимумуВот и все!
Конкретные шаги конкретного алгоритма примерно следующие:
- найти на рисункелюбая точка, взяв его за отправную точку, егоВсе ребра V присоединяются к набору (приоритетная очередь)
q1, установитьboolean数组bool[]Отметьте, что позиция определена. - найдено из набора q1Минимальное расстояниета сторона
v1иОпределить, отмечена ли (посещена) другая точка p стороны,еслиpОн отмечен, чтобы указать, что он был определен, а затем пропущен.Если он не отмечен (посещен), то отметьте точкуp,иРебра, образованные неизвестными точками (не помеченными), соединенными с pприсоединиться к коллекцииq1,Ребро v1 (вы можете рассчитать расстояние и т.п., это ребро представляет собой минимальное остовное дерево) . - Повторяйте 1, 2, пока q1 не станет пустым, образуя минимальное остовное дерево!
Общий шаг:
Поскольку prim распространяется как единое целое от начала до конца, нет необходимости рассматривать задачу слияния двух деревьев, что несколько удобнее в реализации.
Конечно, следует отметить, что минимальное остовное дерево не уникально, и даже минимальное остовное дерево, сгенерированное одним и тем же алгоритмом, может быть другим, но одно и то же независимо от того, какое минимальное остовное дерево сгенерировано:
- Может гарантировать, что все узлы подключены (может соответствовать требованиям и условиям)
- Может гарантировать, что сумма всех путей будет наименьшей (результат совпадает с целью)
- Минимальное остовное дерево не уникально и может быть разнообразным
Код
Логическая реализация проанализирована выше. Ниже мы просто реализуем описанный выше алгоритм с помощью кода.
prim
package 图论;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Comparator;
import java.util.List;
import java.util.PriorityQueue;
import java.util.Queue;
public class prim {
public static void main(String[] args) {
int minlength=0;//最小生成树的最短路径长度
int max=66666;
String cityname[]= {"北京","武汉","南京","上海","杭州","广州","深圳"};
int city[][]= {
{ max, 8, 7, max, max, max, max }, //北京和武汉南京联通
{ 8, max,6, max,9, 8,max }, //武汉——北京、南京、杭州、广州
{ 7, 6, max, 3,4, max,max }, //南京——北京、武汉、上海、杭州
{ max, max,3, max,2, max,max }, //上海——南京、杭州
{ max, 9,4, 2,max, max,10 }, //杭州——武汉、南京、上海、深圳
{ max, 8,max, max,max, max,2 }, //广州——武汉、深圳
{ max, max,max, max,10,2,max }//深圳——杭州、广州
};// 地图
boolean istrue[]=new boolean[7];
//南京
Queue<side>q1=new PriorityQueue<side>(new Comparator<side>() {
public int compare(side o1, side o2) {
// TODO Auto-generated method stub
return o1.lenth-o2.lenth;
}
});
for(int i=0;i<7;i++)
{
if(city[2][i]!=max)
{
istrue[2]=true;
q1.add(new side(city[2][i], 2, i));
}
}
while(!q1.isEmpty())
{
side newside=q1.poll();//抛出
if(istrue[newside.point1]&&istrue[newside.point2])
{
continue;
}
else {
if(!istrue[newside.point1])
{
istrue[newside.point1]=true;
minlength+=city[newside.point1][newside.point2];
System.out.println(cityname[newside.point1]+" "+cityname[newside.point2]+" 联通");
for(int i=0;i<7;i++)
{
if(!istrue[i])
{
q1.add(new side(city[newside.point1][i],newside.point1,i));
}
}
}
else {
istrue[newside.point2]=true;
minlength+=city[newside.point1][newside.point2];
System.out.println(cityname[newside.point2]+" "+cityname[newside.point1]+" 联通");
for(int i=0;i<7;i++)
{
if(!istrue[i])
{
q1.add(new side(city[newside.point2][i],newside.point2,i));
}
}
}
}
}
System.out.println(minlength);
}
static class side//边
{
int lenth;
int point1;
int point2;
public side(int lenth,int p1,int p2) {
this.lenth=lenth;
this.point1=p1;
this.point2=p2;
}
}
}
Осознайте эффект:
Kruskal:
package 图论;
import java.util.Comparator;
import java.util.PriorityQueue;
import java.util.Queue;
import 图论.prim.side;
/*
* 作者：bigsai(公众号)
*/
public class kruskal {
static int tree[]=new int[10];//bing查集
public static void init() {
for(int i=0;i<10;i++)//初始
{
tree[i]=-1;
}
}
public static int search(int a)//返回头节点的数值
{
if(tree[a]>0)//说明是子节点
{
return tree[a]=search(tree[a]);//路径压缩
}
else
return a;
}
public static void union(int a,int b)//表示 a，b所在的树合并小树合并大树(不重要)
{
int a1=search(a);//a根
int b1=search(b);//b根
if(a1==b1) {//System.out.println(a+"和"+b+"已经在一棵树上");
}
else {
if(tree[a1]<tree[b1])//这个是负数，为了简单减少计算，不在调用value函数
{
tree[a1]+=tree[b1];//个数相加 注意是负数相加
tree[b1]=a1; //b树成为a的子树，直接指向a；
}
else
{
tree[b1]+=tree[a1];//个数相加 注意是负数相加
tree[a1]=b1; //b树成为a的子树，直接指向a；
}
}
}
public static void main(String[] args) {
// TODO Auto-generated method stub
init();
int minlength=0;//最小生成树的最短路径长度
int max=66666;
String cityname[]= {"北京","武汉","南京","上海","杭州","广州","深圳"};
boolean jud[][]=new boolean[7][7];//加入边需要防止重复 比如 ba和ab等价的
int city[][]= {
{ max, 8, 7, max, max, max, max },
{ 8, max,6, max,9, 8,max },
{ 7, 6, max, 3,4, max,max },
{ max, max,3, max,2, max,max },
{ max, 9,4, 2,max, max,10 },
{ max, 8,max, max,max, max,2 },
{ max, max,max, max,10,2,max }
};// 地图
boolean istrue[]=new boolean[7];
//南京
Queue<side>q1=new PriorityQueue<side>(new Comparator<side>() {//优先队列存边+
public int compare(side o1, side o2) {
// TODO Auto-generated method stub
return o1.lenth-o2.lenth;
}
});
for(int i=0;i<7;i++)
{
for(int j=0;j<7;j++)
{
if(!jud[i][j]&&city[i][j]!=max)//是否加入队列
{
jud[i][j]=true;jud[j][i]=true;
q1.add(new side(city[i][j], i, j));
}
}
}
while(!q1.isEmpty())//执行算法
{
side newside=q1.poll();
int p1=newside.point1;
int p2=newside.point2;
if(search(p1)!=search(p2))
{
union(p1, p2);
System.out.println(cityname[p1]+" "+cityname[p2]+" 联通");
minlength+=newside.lenth;
}
}
System.out.println(minlength);
}
static class side//边
{
int lenth;
int point1;
int point2;
public side(int lenth,int p1,int p2) {
this.lenth=lenth;
this.point1=p1;
this.point2=p2;
}
}
}
kruskal
Суммировать
Алгоритм минимального связующего дерева относительно прост для понимания и не сложен в реализации.Kruskal和PrimЕсть в основном два аспекта жадного алгоритма. Один начинает с целого, чтобы найти наименьшее ребро, сталкивается с ассоциацией и непрерывно объединяется, а другой начинает распространяться от локального, чтобы найти наименьшее окружение, и продолжает распространяться, пока не будет сгенерировано минимальное остовное дерево. Лучше изучить, прежде чем изучать минимальное остовное деревоdijkstraАлгоритм и объединение поиска, чтобы его можно было реализовать быстрее и понятнее.
Наконец, если вы действительно получите много денег в этот день, чтобы построить такой дорогой золотой маршрут, вы можете принять этот метод соответствующим образом, а оставшееся большое количество,Гоу богат, не забывай. .
Если вы чувствуете себя хорошо, пожалуйста, поставьте лайк, обратите внимание и обратите внимание на публичный аккаунт автора:bigsaiОтветьте на структуру данных, чтобы получить копию учебных материалов и видео структуры данных!