17. Примеры задач на графы. Связность. Компоненты связности.
1. Примеры задач на графы. Связность. Компоненты связности.
Давайте рассмотрим несколько задач, которые можно решить, изменяя рассмотренные нами поиск в ширину или глубину на графах.
2. Компоненты связности.
На предприятии достаточно сложная компьютерная сеть. В каждом подразделении стоит сетевой коммуникатор - свич и все компьютеры подразделения связаны между собой через него. Некоторые из свичей связаны кабелем и тогда компьютеры этих подразделений могут «общаться между собой». Вам предложили непыльную работу сетевого администратора, но для начала поручили соединить все компьютеры предприятия между собой. Какое минимальное количество сетевых кабелей между свичами вам надо проложить, чтобы все компьютеры «видели» друг друга?
int count = 0;
//Console.Write("Введите N=");
//int n = Convert.ToInt32(Console.ReadLine());
int n = 10;
int[,] graf = new int[n, n];
//Console.Write("Введите M=");
//int m = Convert.ToInt32(Console.ReadLine());
int m = 8;
/*
for (int i = 0; i < m; i++)
{
Console.Write("Номер города, из которого идет дорога: ");
start = Convert.ToInt32(Console.ReadLine());
Console.Write("Номер города, в который идет дорога: ");
end = Convert.ToInt32(Console.ReadLine());
Console.Write("Номер города, в который идет дорога: ");
int size = Convert.ToInt32(Console.ReadLine());
graf[start, end] = size;
graf[end, start] = size;
}
*/
graf[0, 3] = 1;
graf[3, 0] = 1;
graf[0, 6] = 1;
graf[6, 0] = 1;
graf[3, 6] = 1;
graf[6, 3] = 1;
graf[1, 5] = 1;
graf[5, 1] = 1;
graf[5, 4] = 1;
graf[4, 5] = 1;
graf[7, 8] = 1;
graf[8, 7] = 1;
graf[7, 9] = 1;
graf[9, 7] = 1;
graf[8, 9] = 1;
graf[9, 8] = 1;
int[] path = new int[n];
for (int i = 0; i < n; i++)
{
path[i] = Int32.MaxValue;
}
for (int start = 0; start < n; start++)
{
if (path[start] == Int32.MaxValue)
{
Queue<int> list = new Queue<int>();
path[start] = 0;
list.Enqueue(start);
while (list.Count > 0)
{
int u = list.Dequeue();
for (int i = 0; i < n; i++)
{
if (graf[u, i] > 0)
{
if (path[u] + graf[u, i] < path[i])
{
path[i] = path[u] + graf[u, i];
list.Enqueue(i);
}
}
}
}
for (int i = 0; i < n; i++)
{
Console.WriteLine(i + " - " + path[i]);
}
Console.WriteLine();
count++;
}
}
for (int i = 0; i < n; i++)
{
Console.WriteLine(i + " - " + path[i]);
}
Console.WriteLine();
Console.WriteLine(count);3. Связи решают все.
Вам очень надо для решения важного вопроса «выйти» на конкретного человека – Ивана Ивановича через солидных знакомых. У вас есть информация, кто с кем из определенного круга лиц поддерживает достаточно близкие отношения (в том числе и вы). Есть ли у вас шанс получить нужную рекомендацию?
Так как нам нужен любой путь, а не кратчайший, будем использовать поиск в глубину.
private static bool[] _uses;
private static int[,] _graf;
private static int _n;
private static int _start = 0;
private static int _end = 0;
public static void Main(string[] args)
{
//Console.Write("Введите N=");
//_n = Convert.ToInt32(Console.ReadLine());
_n = 10;
_graf = new int[_n, _n];
//Console.Write("Введите M=");
//int m = Convert.ToInt32(Console.ReadLine());
int m = 9;
/*
for (int i = 0; i < m; i++)
{
Console.Write("Номер города, из которого идет дорога: ");
_start = Convert.ToInt32(Console.ReadLine());
Console.Write("Номер города, в который идет дорога: ");
_end = Convert.ToInt32(Console.ReadLine());
Console.Write("Номер города, в который идет дорога: ");
int size = Convert.ToInt32(Console.ReadLine());
_graf[_start, _end] = size;
_graf[_end, _start] = size;
}
*/
_graf[0, 3] = 1;
_graf[3, 0] = 1;
_graf[0, 6] = 1;
_graf[6, 0] = 1;
_graf[3, 6] = 1;
_graf[6, 3] = 1;
_graf[3, 7] = 1;
_graf[7, 3] = 1;
_graf[7, 8] = 1;
_graf[8, 7] = 1;
_graf[9, 7] = 1;
_graf[7, 9] = 1;
_graf[9, 8] = 1;
_graf[8, 9] = 1;
_graf[1, 5] = 1;
_graf[5, 1] = 1;
_graf[4, 5] = 1;
_graf[5, 4] = 1;
//Console.Write("Введите X=");
//_start = Convert.ToInt32(Console.ReadLine());
_start = 0;
//Console.Write("Введите Y=");
//_end = Convert.ToInt32(Console.ReadLine());
_end = 9;
_uses = new bool[_n];
Dfs(_start);
if (!_uses[_end])
{
Console.WriteLine("Путь не найден!");
}
}
static void Dfs(int v)
{
if (_uses[v]) // Если мы здесь уже были, то тут больше делать нечего
{
return;
}
_uses[v] = true; // Помечаем, что мы здесь были
if (v == _end) // Проверяем, конец ли
{
Console.WriteLine("Путь найден!");
return;
}
for (int i = 0; i < _n; i++) // Для каждого ребра
{
if (_graf[v, i] > 0)
{
Dfs(i); // Запускаемся из соседа
}
}
}4. Путь
Пусть надо найти и вывести кратчайший путь из вершины Start в вершину End.
Так как нам нужен не любой путь, а именно кратчайший, будем использовать поиск в ширину.
int start = 0;
int end = 0;
int current = 0;
//Console.Write("Введите N=");
//int n = Convert.ToInt32(Console.ReadLine());
int n = 7;
int[,] graf = new int[n, n];
//Console.Write("Введите M=");
//int m = Convert.ToInt32(Console.ReadLine());
int m = 10;
/*
for (int i = 0; i < m; i++)
{
Console.Write("Номер города, из которого идет дорога: ");
start = Convert.ToInt32(Console.ReadLine());
Console.Write("Номер города, в который идет дорога: ");
end = Convert.ToInt32(Console.ReadLine());
Console.Write("Номер города, в который идет дорога: ");
int size = Convert.ToInt32(Console.ReadLine());
graf[start, end] = size;
graf[end, start] = size;
}
*/
graf[0, 3] = 25;
graf[3, 0] = 25;
graf[0, 5] = 23;
graf[5, 0] = 23;
graf[0, 6] = 27;
graf[6, 0] = 27;
graf[1, 3] = 22;
graf[3, 1] = 22;
graf[1, 4] = 29;
graf[4, 1] = 29;
graf[2, 4] = 24;
graf[4, 2] = 24;
graf[2, 6] = 23;
graf[6, 2] = 23;
graf[3, 4] = 54;
graf[4, 3] = 54;
graf[4, 5] = 59;
graf[5, 4] = 59;
graf[4, 6] = 49;
graf[6, 4] = 49;
//Console.Write("Введите X=");
//start = Convert.ToInt32(Console.ReadLine());
start = 0;
//Console.Write("Введите Y=");
//end = Convert.ToInt32(Console.ReadLine());
end = 4;
int[] path = new int[n];
for (int i = 0; i < n; i++)
{
path[i] = Int32.MaxValue;
}
Boolean[] uses = new Boolean[n];
int[] previous = new int[n];
path[start] = 0;
previous[start] = -1;
int usesCount = 0;
while (usesCount < n)
{
int min = Int32.MaxValue;
current = 0;
for (int i = 0; i < n; i++)
{
if (!uses[i] && path[i] < min)
{
min = path[i];
current = i;
}
}
for (int i = 0; i < n; i++)
{
if (graf[current, i] > 0 && !uses[i])
{
if (path[current] + graf[current, i] < path[i])
{
path[i] = path[current] + graf[current, i];
previous[i] = current;
}
}
}
uses[current] = true;
usesCount++;
}
for (int i = 0; i < n; i++)
{
Console.WriteLine(i + " - " + path[i] + " " + previous[i]);
}
if (path[end] != Int32.MaxValue)
{
current = end;
LinkedList<int> move = new LinkedList<int>();
while (current != -1)
{
move.AddFirst(current);
current = previous[current];
}
LinkedListNode<int> node;
node = move.First;
while (node != null)
{
Console.Write(node.Value + " ");
node = node.Next;
}
Console.WriteLine("Длина пути: " + path[end]);
}
else
{
Console.WriteLine("Нет пути:!");
}Итоги занятия.
Мы рассмотрели несколько примеров, которые можно решать стандартными алгоритмами поиска в ширину и глубину на графах с небольшими изменениями. На самом деле таких задач огромное количество.
А на следующем занятии по завету для настоящих мужчин будем строить дом, сажать дерево и растить сына… Ой нет, все сразу не успеем. Поэтому как настоящие мужчины (и леди, кстати, тоже) будем сажать деревья! А так как здесь собрались будущие программисты, то деревья будут в первую очередь двоичные…