Это седьмой день моего участия в августовском испытании обновлений. Узнайте подробности мероприятия: Испытание августовского обновления
Разработка и анализ алгоритмов Тема 1:
Поиск остовного дерева с минимальным радиусом в неориентированном связном графе
Цель:
Освойте использование графиков для разработки и реализации алгоритмов
Научитесь использовать списки смежности для построения и вывода ориентированных графов.
Освойте использование обхода в ширину (DFS) для вычисления глубины вершин.
Освойте использование алгоритмов динамического программирования, чтобы найти остовное дерево с наименьшим радиусом.
содержание:
1. Введите количество вершин и ребер ориентированного графа, а также начало и хвост каждого ребра.
2. Функция проектирования использует список смежности для представления создания и вывода неориентированного связного графа.
3. Функция проектирования использует обход в ширину для вычисления максимальной глубины поддерева с каждой вершиной в качестве корня дерева.
4. Функция проектирования использует алгоритм динамического программирования для вычисления максимальной глубины поддерева, образованного поддеревом, представленным вершиной и соседними с ней точками.
5. Вызовите функцию для вывода остовного дерева минимального радиуса неориентированного связного графа.
В соответствии со списком смежности графа представлен неориентированный связный граф, а алгоритм реализации поиска минимального радиуса посредством обхода в ширину и алгоритм динамического программирования выглядит следующим образом, основной код и комментарии:
void getDepth(int id)
{
//如果访问过就不再访问
if (v[id]) return;
//标记未访问结点为访问状态
v[id] = true;
head *curPtr = heads[id];
//孤立点的最大深度是0，所以maxD的初始值为0
int maxD = 0;
//遍历邻接表
while (curPtr)
{
//邻居结点的id
int toId = curPtr->toId;
//如果当前邻居点没有处理过，那么需要借助第一遍DFS时生成的countv数组计算以当前结点id以及它的邻居结点toId组成的子树的最大深度
if (!v[toId])
{
//记录
curPtr->maxDepth = countv[toId];
if (countv[toId] > maxD) maxD = countv[toId];
}
//如果当前邻居点处理过了，那需要利用当前邻居结点toId的结果来得到id的状态值
else
{
//遍历toId的所有邻居toIdd。toIdd构成的子树+toId+Id作为一棵新的子树
int maxDD = 1;
head *tempPtr = heads[toId];
while (tempPtr)
{
int toIdd = tempPtr->toId;
if (toIdd != id)
{
if (tempPtr->maxDepth + 1 > maxDD)
maxDD = tempPtr->maxDepth + 1;
}
tempPtr = tempPtr->next;
}
curPtr->maxDepth = maxDD;
if (maxDD > maxD) maxD = maxDD;
}
curPtr = curPtr->next;
}
//更新结果
if (maxD < minDepthVal)
{
minDepthVal = maxD;
num = 1;
res[0] = id;
}
else if (maxD == minDepthVal)
{
res[num++] = id;
}
//DFS
curPtr = heads[id];
while (curPtr)
{
int toId = curPtr->toId;
getDepth(toId);
curPtr = curPtr->next;
}
}
Этот алгоритм в основном использует список смежности для достижения построения графа и использует обход в ширину и динамическое программирование для достижения минимального радиуса поиска.Задача требует найти кратчайший путь от корня до листа, то есть минимальный радиус, который собственно и должен найти минимальную глубину остовного дерева.
Скриншот результатов эксперимента: