Предположим, что есть следующий сценарий, есть доска, к доске прибиты несколько гвоздей, и эти гвозди можно соединить какими-то нитями. Предполагая, что каждый гвоздь можно соединить одной или несколькими нитями, должен быть случай, когда для соединения всех гвоздей используется наименьшее количество нити.
Более реалистичным сценарием была бы ситуация, когда где-то распределеныNдеревни, теперь нужно быть вNДороги построены между деревнями, а расстояния до каждой деревни разные. Спросите, как построить самую короткую дорогу, чтобы соединить каждую деревню.
Все вышеперечисленные проблемы могут быть обобщены как минимальная проблема охватавания дерева, которая может быть формально описана как: с учетом неисправленного взвешенного графикаG=(V, E), минимальное остовное дерево — это множествоT, Tподключить с минимальными затратамиVРебра, используемые всеми вершинами вEсамый маленький набор. собиратьTРебра могут образовывать дерево, потому что каждый узел (кроме корневого узла) может найти один из своих родительских узлов вверху.
Решение проблемы минимального остовного дерева было впервые предложено предшественниками,Primeалгоритм иKruskalАлгоритм решает задачу с точки и с ребра соответственно.
Алгоритм Прима
PrimАлгоритм — это алгоритм, который создает минимальное остовное дерево. Алгоритм основан на1930Чешский математик Войтек ЯрникVojtěch Jarník) найдено; и в1957американского ученого-компьютерщика Роберта ПриммаRobert C. Prim) обнаружены самостоятельно;1959В 2008 году Эзге Диркшер снова открыл алгоритм.
PrimАлгоритм начинается с любой вершины, выбирает вершину, ближайшую к текущему набору вершин, и добавляет к дереву ребро между двумя вершинами.PrimАлгоритм использует жадный алгоритм для поиска текущей ближайшей вершины.
Графический алгоритм:
1. В взвешенной соболезнении коллекция вершинV, множество реберE
2. Произвольно выберите точку в качестве начальной вершины, отмеченную какvisit, Вычислите расстояние всех точек, связанных с ним, выберите кратчайшее расстояние, отметьтеvisit.
3. Повторяйте следующие действия, пока все точки не будут отмечены какvisit:
В оставшиеся часы расчет и отмеченныйvisitТочка с наименьшим межточечным расстоянием, отмеченнаяvisitДокажите, что минимальное охваченное дерево добавлено.
Давайте посмотрим на процесс создания минимального остовного дерева:
1 Первоначально из вершиныaНачать создание минимального остовного дерева
aЗатем вершина устанавливается вvisit(зачернено), рассчитайте расстояние вокруг точки, с которой он соединяется:7,6,4,выберитеCКратчайшее расстояние точки, затемненноеC, при добавлении этого ребра к минимальному остовному дереву:a,cРасстояние между соединенными точками (уже затемненные точки не учитываются), так какaподключено уже рассчитано, нужно только рассчитать иcсоединенные точки, если точкаa,cсвязаны, то этоaРасстояние было рассчитано ранее. Если оно ближе к c, значение расстояния обновляется. Здесь рассчитывается ближайшее расстояние между незачерненной точкой и зачерненной точкой. Очевидно,bа такжеaдля7,bа такжеcРасстояние6,продлитьbРасстояние от набора посещаемых точек равно6,а такжеf,eа такжеcРасстояния8,9, так что он все еще черныйb, выделить крайbc:dрасстояниеbсамый короткий, будетdзатемнены,bdВыделять:fрасстояниеdдля7,расстояниеbдля4, кратчайшее значение расстояния для его обновления4, так затемненоf, выделеноbf:eсейчас:Код:
#include<iostream>
#define INF 10000
using namespace std;
const int N = 6;
bool visit[N];
int dist[N] = { 0, };
int graph[N][N] = { {INF,7,4,INF,INF,INF}, //INF代表两点之间不可达
{7,INF,6,2,INF,4},
{4,6,INF,INF,9,8},
{INF,2,INF,INF,INF,7},
{INF,INF,9,INF,INF,1},
{INF,4,8,7,1,INF}
};
int prim(int cur)
{
int index = cur;
int sum = 0;
int i = 0;
int j = 0;
cout << index << " ";
memset(visit, false, sizeof(visit));
visit[cur] = true;
for (i = 0; i < N; i++)
dist[i] = graph[cur][i];//初始化，每个与a邻接的点的距离存入dist
for (i = 1; i < N; i++)
{
int minor = INF;
for (j = 0; j < N; j++)
{
if (!visit[j] && dist[j] < minor) //找到未访问的点中，距离当前最小生成树距离最小的点
{
minor = dist[j];
index = j;
}
}
visit[index] = true;
cout << index << " ";
sum += minor;
for (j = 0; j < N; j++)
{
if (!visit[j] && dist[j]>graph[index][j]) //执行更新，如果点距离当前点的距离更近，就更新dist
{
dist[j] = graph[index][j];
}
}
}
cout << endl;
return sum; //返回最小生成树的总路径值
}
int main()
{
cout << prim(0) << endl;//从顶点a开始
return 0;
}
Алгоритм Крускала
Крускал — это еще один алгоритм вычисления минимального остовного дерева, и принцип его алгоритма следующий. Во-первых, поместите каждую вершину в свой собственный набор данных. Затем ребра выбираются в порядке возрастания веса. При выборе каждого ребра определяется, находятся ли вершины, определяющие ребро, в разных наборах данных. Если да, то вставляем это ребро в набор минимального остовного дерева, и при этом вынимаем объединение, содержащее каждую вершину набора, если нет, переходим к следующему ребру. Повторяйте этот процесс, пока не будут прощупаны все края.
Графический алгоритм:
1 Исходная ситуация, связный граф, определяет структуру данных для ребра, включая начальную точку, конечную точку и длину ребра:
typedef struct _node{
int val; //长度
int start; //边的起点
int end; //边的终点
}Node;
a,eПомещенные в тот же набор, в реализации мы используем концепцию поиска по объединению:c, dСнова поместите его в ту же коллекцию:ab,потому чтоa,eуже в наборе, а потомbПрисоединяйся:b,e,потому чтоb,eОни уже принадлежат одному множеству, и если они соединены, то образуют кольцо, поэтому реброbeБез присоединения к минимальному остовному дереву:bc,потому чтоc,dэто набор,a,b,eявляется набором, поэтому объедините два набора:Код:
#include<iostream>
#define N 7
using namespace std;
typedef struct _node{
int val;
int start;
int end;
}Node;
Node V[N];
int cmp(const void *a, const void *b)
{
return (*(Node *)a).val - (*(Node*)b).val;
}
int edge[N][3] = { { 0, 1, 3 },
{ 0, 4, 1 },
{ 1, 2, 5 },
{ 1, 4, 4 },
{ 2, 3, 2 },
{ 2, 4, 6 },
{ 3, 4, 7}
};
int father[N] = { 0, };
int cap[N] = {0,};
void make_set() //初始化集合，让所有的点都各成一个集合，每个集合都只包含自己
{
for (int i = 0; i < N; i++)
{
father[i] = i;
cap[i] = 1;
}
}
int find_set(int x) //判断一个点属于哪个集合，点如果都有着共同的祖先结点，就可以说他们属于一个集合
{
if (x != father[x])
{
father[x] = find_set(father[x]);
}
return father[x];
}
void Union(int x, int y) //将x,y合并到同一个集合
{
x = find_set(x);
y = find_set(y);
if (x == y)
return;
if (cap[x] < cap[y])
father[x] = find_set(y);
else
{
if (cap[x] == cap[y])
cap[x]++;
father[y] = find_set(x);
}
}
int Kruskal(int n)
{
int sum = 0;
make_set();
for (int i = 0; i < N; i++)//将边的顺序按从小到大取出来
{
if (find_set(V[i].start) != find_set(V[i].end)) //如果改变的两个顶点还不在一个集合中，就并到一个集合里，生成树的长度加上这条边的长度
{
Union(V[i].start, V[i].end); //合并两个顶点到一个集合
sum += V[i].val;
}
}
return sum;
}
int main()
{
for (int i = 0; i < N; i++) //初始化边的数据，在实际应用中可根据具体情况转换并且读取数据,这边只是测试用例
{
V[i].start = edge[i][0];
V[i].end = edge[i][1];
V[i].val = edge[i][2];
}
qsort(V, N, sizeof(V[0]), cmp);
cout << Kruskal(0)<<endl;
return 0;
}