Алгоритмы обхода графов на Python и C#
Если вы во время учебы в институте пренебрегали теорией графов, то зря. Ибо граф – это замечательная абстракция, к которой можно свести много различных задач и решить их через алгоритмы на графах. К графам сводятся не только задачи транспортной логистики. В виде графа можно представить, например, компьютерную сеть, сеть социальных контактов, да и вообще различные взаимоотношения между людьми, а так же многие другие задачи, которые можно решить программированием на языках C# и Python. В частности, задачу паросочетаний можно представить в виде двудольного графа:
А теперь рассмотрим практический пример. Допустим, у нас есть вот такой вот граф:
Вершины графа могут быть закодированы как буквами, так и цифрами. Цифрами – удобнее, так как они могут быть индексами, по которыми мы можем обраться к определённой вершине. Давайте это проверим. В нашем примере мы назначим буквам соответствующую цифру и построим такой граф (пример на Python):
a, b, c, d, e, f, g, h = range(8)
N = [
{b, c, d, e, f}, # a
{c, e}, # b
{d}, # c
{e}, # d
{f}, # e
{c, g, h}, # f
{f, h}, # g
{f, g} # h
]
print(b in N[a])
print(len(N[f]))
В данном примере мы просто присвоили букве, как переменной, соответствующее числовое значение, а потом задали граф как массив вершин. Каждая вершина – это множество исходящих из него ребер. Каждое ребро идет в другую вершину, элементы множества – это вершины, в которые ведут эти ребра.
Как обратиться к конкретной вершине? По номеру, вот так, например, проверить, ведет ли ребро из одной вершины (a) к другой вершине (b)
print(b in N[a])
Степень вершины мы можем узнать, просто посмотрев размер множества исходящих из нее рёбер, вот так:
print(len(N[f]))
Теперь попробуем реализовать алгоритм обхода графа в ширину. Вот шаги этого алгоритма:
- Поместить узел, с которого начинается поиск, в изначально пустую очередь.
- Извлечь из начала очереди узел u {\displaystyle u} u и пометить его как развёрнутый.
- Если узел u {\displaystyle u} u является целевым узлом, то завершить поиск с результатом «успех».
- В противном случае, в конец очереди добавляются все преемники узла u {\displaystyle u}u, которые ещё не развёрнуты и не находятся в очереди.
- Если очередь пуста, то все узлы связного графа были просмотрены, следовательно, целевой узел недостижим из начального; завершить поиск с результатом «неудача».
- Вернуться к п. 2.
Вот пример реализации данного алгоритма на Python
a, b, c, d, e, f, g, h = range(8)
N = [
{b, c, d, e, f}, # a
{c, e}, # b
{d}, # c
{e}, # d
{f}, # e
{c, g, h}, # f
{f, h}, # g
{f, g} # h
]
#импортируем класс очереди
from queue import Queue
#соответсвие цифры букве
letters="abcdefgh"
visited_nodes={}
#Начальные переменные
queue=Queue()
beg_node=a
target_node=h
#шаг 1. Поместить узел, с которого начинается поиск, в изначально пустую очередь.
queue.put(beg_node)
visited_nodes={beg_node}
# это у нас цикл с постусловием
while True:
#шаг 2. Извлечь из начала очереди узел "u" и пометить его как развёрнутый.
u=queue.get()
print("Обходим узел",letters[u])
#Если узел "u" является целевым узлом, то завершить поиск с результатом «успех».
if u==target_node:
print("Поиск успешно завершен")
break
else:
#В противном случае, в конец очереди добавляются все преемники узла "u", которые ещё не развёрнуты и не находятся в очереди.
for node in N[u]:
print(" -- Смотрим ребро", letters[node])
if not(node in visited_nodes):
print(" ---- Узел", letters[node],"добавили в очередь")
visited_nodes.add(node)
queue.put(node)
#шаг 3. Если очередь пуста, то все узлы связного графа были просмотрены, следовательно, целевой узел
# недостижим из начального; завершить поиск с результатом «неудача».
if queue.empty():
print("Вершина ",letters[u]," не найдена")
#шаг 4. Вернуться к п. 2.
Алгоритм обхода графа в ширину (не обязательно это поиск) мы можем использовать, когда надо раскрыть все вершины графа последовательно, уровень за уровнем. То есть, сначала мы раскрываем вершины первого уровня, затем второго и так далее. Вот как это выгляди на практике:
Если очередь заменить стеком, то у нас получиться алгоритм поиска в глубину. В этом случае не раскрываются вершины каждого уровня, а программа идет сразу до конца. И, только в том случае, если не нашлось нужной вершины, идет возврат назад, чтобы исследовать другие пути. Именно поэтому алгоритм и называется алгоритм поиска в глубину. Вот как это выглядит:
А теперь для разнообразия попробуем реализовать этот алгоритм на языке C#. Для начала объявим класс узла (вершины):
/// <summary>
/// Вершина графа
/// </summary>
public class Node
{
/// <summary>
/// Номер вершины
/// </summary>
public int vertex_number;
/// <summary>
/// Список вершин, в которые ведут ребра из этой вершины
/// </summary>
public List<Node> vertex_edges;
/// <summary>
/// Дополнительная информация
/// </summary>
public object tag;
/// <summary>
/// Конструктор
/// </summary>
/// <param name="a_vertex_number">Номер вершины</param>
public Node(int a_vertex_number)
{
vertex_edges = new List<Node>();
vertex_number = a_vertex_number;
}
}
Для удобства программирования создадим еще и класс Graph, который инкапсулирует в себя описание графа.
/// <summary>
/// Граф
/// </summary>
public class Graph
{
/// <summary>
/// Узлы графа
/// </summary>
public List<Node> nodes;
/// <summary>
/// Конструктор
/// </summary>
public Graph()
{
nodes = new List<Node>();
}
/// <summary>
/// Инициализация вершин
/// </summary>
/// <param name="count">Кол-во вершин</param>
public void init(int count)
{
for (int i = 1; i <= count; i++) nodes.Add(new Node(i));
}
/// <summary>
/// Добавить ребро
/// </summary>
/// <param name="a_vertex_number_form">Из какой вершины исходит</param>
/// <param name="a_vertex_number_to">В какую вершину ведет</param>
public void add(int a_vertex_number_from, int a_vertex_number_to)
{
nodes[a_vertex_number_from - 1].vertex_edges.Add(nodes[a_vertex_number_to - 1]);
}
/// <summary>
/// Сбросить метки узлов
/// </summary>
public void reset_tags()
{
foreach(Node node in nodes) node.tag = null;
}
}
В качестве примера вот такой граф:
Закодируем его:
graph = new Graph();
graph.init(8);
graph.add(1, 2);
graph.add(2, 3);
graph.add(2, 4);
graph.add(2, 5);
graph.add(3, 1);
graph.add(4, 1);
graph.add(4, 6);
graph.add(4, 8);
graph.add(5, 6);
graph.add(6, 7);
graph.add(7, 5);
graph.add(8, 6);
Теперь реализуем алгоритм обхода в графа в глубину, который формирует дерево обхода, по сути, удаляет из графа все замкнутые циклы:
/// Построить дерево обхода в глубину
/// </summary>
/// <param name="a_vertex_number">Начальный номер вершины</param>
/// <param name="start">Это стартовая точка</param>
/// <returns>Результатирующее дерево</returns>
public List<Node> dfs_tree(int a_vertex_number, bool start)
{
List<Node> res = new List<Node>();
Node node = nodes[a_vertex_number - 1];
if (node.tag != null) return new List<Node>();
node.tag = true;
List<Node> additig_list = null;
if (start)
{
Node root_item = new Node(a_vertex_number);
res.Add(root_item);
additig_list = root_item.vertex_edges;
}
else
{
additig_list = res;
}
foreach (Node item in node.vertex_edges)
{
if(item.tag==null)
{
Node adding_item = new Node(item.vertex_number);
adding_item.vertex_edges = dfs_tree(item.vertex_number,false);
additig_list.Add(adding_item);
}
}
return res;
}
Выведем полученное дерево в TreeVeiw:
private void btnDfs_Click(object sender, EventArgs e)
{
graph.reset_tags();
List<Node> tree = graph.dfs_tree(1,true);
tvDfs.Nodes.Clear();
draw_tree(tree, tvDfs.Nodes);
}
/// <summary>
/// Вывести дерево
/// </summary>
/// <param name="tree">Дерево</param>
/// <param name="tree_nodes">Узлы визуального дерева</param>
private void draw_tree(List<Node> tree, TreeNodeCollection tree_nodes)
{
foreach(Node node in tree)
{
TreeNode tree_node = new TreeNode(node.vertex_number.ToString());
tree_nodes.Add(tree_node);
if (node.vertex_edges.Count > 0) draw_tree(node.vertex_edges, tree_node.Nodes);
}
}
И вот что в итоге у нас получается:
Теперь поговорим о том, в каком случае какой алгоритм использовать. Если мы предполагаем, что искомая вершина может находиться достаточно далеко от той, с которой мы начинаем поиск (предполагается, что будет много уровней), то лучше использовать алгоритм поиска в глубину. Если мы знаем, что вершина будет где-то близко, на верхних уровнях дерева раскрытия вершин, то лучше использовать алгоритм поиска в ширину. Но, ни в коем случае не используйте алгоритм поиска в ширину, если у вас потенциально может быть очень много уровней – алгоритм может «повеситься».
Comments
So empty here ... leave a comment!