<НазадПростыми словами о графах
12/18/2022В этой статье мы начнем знакомство с графами, познакомимся с алгоритмом поиска в ширину и реализуем граф на языке программирования Rust.
Что такое граф?
Граф воспроизводит набор связей. Представим, что есть Иван, который много слышал о Еве и теперь хочет познакомиться с ней. У Ивана есть две подруги, Алиса и Татьяна. Алиса знакома с Евой через свою подругу Ангелину, а Татьяна знакома с Евой напрямую. Такие формулировки связей воспринимаются трудно, но можно легко отобразить эту связь с помощью графа. Стрелки показывают направление связей: Иван дружит с Алисой и с Татьяной, Алиса дружит с Ангелиной и т.д.
Каждый граф состоит из узлов и ребер.
Типы графов
Существует много типов графов, вот некоторые из них:
- неориентированные;
- ориентированные;
- мультиграф;
- псевдограф.
Давайте рассмотрим их графическое представление.
Программное представление графов
Существуют четыре основных метода представления графов. Выбор представления определяется условиями конкретной задачи. Они различаются объемом занимаемой памяти и скоростью выполнения операций над графами. Существуют разные комбинации составляющих графа:
- Матрица смежности графа (или матрица весов графа).
- Структуры (списки) смежных вершин графа.
- Матрица инцидентности графа: вершина–ребра.
- Список ребер графа.
Чаще всего используется матрица смежности и списки смежных вершин. Однако следует подчеркнуть, что при небольшом количестве узлов ~ 10 представления не имеет значения.
В последующих примерах я буду использовать матрицу смежности, но в работе используйте такое представление, которое максимально эффективно для вашей задачи.
Матрицей смежности графа с n узлами называется матрица Anxn, элементы которой:
- Если узел i смежен с узлом j, то значение = 1.
- Если узел i не смежен с узлом j, то значение = 0.
- Если из узла исходит k количество ребер, то значение = k.
- Если у узла есть v петель, то соответствующее значение на диагонали = v, если без петель = 0.
Вот так будут выглядеть матрица для графов из предыдущего раздела:
В ориентированном графе для обозначения вхождение узла можно использовать как 0, так и -1. Например для второго графа, на рисунке выше, ребро (3,1) можно обозначить в матрице либо -1, либо 0. В примерах я буду использовать 0.
Реализуем матрицу на языке программирования Rust.
Создадим структуру строки матрица. И добавим для нее возможность индексирования.
use std::fmt::{Display, Formatter, Result, Write};
use std::ops::{Index, IndexMut};
use std::vec;
#[derive(Clone)]
pub struct Row {
data: Vec<i32>,
}
impl Row {
pub fn new(size: usize, filler: i32) -> Self {
Self {
data: vec![filler; size],
}
}
}
impl Index<usize> for Row {
type Output = i32;
fn index(&self, index: usize) -> &Self::Output {
&self.data[index]
}
}
impl IndexMut<usize> for Row {
fn index_mut(&mut self, index: usize) -> &mut Self::Output {
&mut self.data[index]
}
}
impl Display for Row {
fn fmt(&self, f: &mut Formatter) -> Result {
let mut str_row = String::new();
self.data
.iter()
.for_each(|c| write!(&mut str_row, "{} ", c).unwrap());
write!(f, "{}", str_row.trim_end())
}
}
Ну и теперь опишем структуру матрицы и базовые функции для работы со смежными узлами.
pub struct Matrix {
/// Number of nodespub n: usize,
data: Vec<Row>,
}
impl Index<usize> for Matrix {
type Output = Row;
fn index(&self, index: usize) -> &Self::Output {
&self.data[index]
}
}
impl IndexMut<usize> for Matrix {
fn index_mut(&mut self, index: usize) -> &mut Self::Output {
&mut self.data[index]
}
}
impl Matrix {
/// Creates a new instance of Matrix
/// with n nodes
pub fn new(nodes: usize, filler: i32) -> Self {
Self {
n: nodes,
data: vec![Row::new(nodes, filler); nodes],
}
}
}
impl Matrix {
/// Adds a weighted edge
pub fn add_weighted_edge(&mut self, n: usize, m: usize, val: i32) {
self[n][m] = val;
}
/// Adds a directed edge without weight
pub fn add_directed_edge(&mut self, n: usize, m: usize) {
self.add_weighted_edge(n, m, 1);
self.add_weighted_edge(m, n, -1);
}
/// Adds a directed edge with weight
pub fn add_w_directed_edge(&mut self, n: usize, m: usize, w: i32) {
self.add_weighted_edge(n, m, w);
self.add_weighted_edge(m, n, -w);
}
/// Adds an undirected edge
pub fn add_undirected_edge(&mut self, n: usize, m: usize) {
self.add_weighted_edge(n, m, 1);
self.add_weighted_edge(m, n, 1);
}
}
impl Matrix {
/// Returns true if some node has adjacent nodes
pub fn has_adjs(&self, node: usize) -> bool {
!self.get_adjs(node).is_empty()
}
/// Returns adjacent nodes
pub fn get_adjs(&self, node: usize) -> Vec<usize> {
let mut adjs = vec![];
for j in 0..self.n {
if self[node][j] > 0 {
adjs.push(j);
}
}
adjs
}
/// Returns adjacent nodes count
pub fn adjs_count(&self, node: usize) -> usize {
self.get_adjs(node).len()
}
}
impl Display for Matrix {
fn fmt(&self, f: &mut Formatter) -> Result {
let mut matrix = String::new();
if !self.data.is_empty() {
for row in &self.data {
matrix.push_str(&row.to_string());
matrix.push('\n');
}
} else {
matrix = String::from("Matrix is empty!");
}
write!(f, "{}", matrix)
}
}
impl Matrix {
pub fn bfs(&self, starter_node: usize, target_node: usize) -> bool {
let mut queue = vec![];
queue.push(starter_node);
let mut searched = vec![];
while !queue.is_empty() {
let node = queue.remove(0);
if !searched.contains(&node) {
if node == target_node {
println!("The target node was found!");
println!("Searched: {:?}", searched);
return true;
} else {
queue.extend(self.get_adjs(node));
searched.push(node);
}
println!("Node: {:?}", node);
println!("Q: {:?}\n", queue);
}
}
return false;
}
}
Теперь самое время рассмотреть один из алгоритмов обхода графа - «Поиск в ширину».
Алгоритм поиска в ширину
Этот алгоритм позволяет нам ответить на два вопроса:
- Существует ли путь от одного узла до другого?
- Какой путь самый кратчайший?
Предположим, что наша задача - найти инфлюэнсера в сфере программирования, среди наших друзей и их друзей, которые образуют сеть контактов. Вот так вот выглядит наша сеть:
В нашей сети контактов есть два инфлюэнсера: Марат и Света, но еще предстоит до этого дойти.
Нам нужно ответить на два вопроса:
- Существует ли в нашей сети инфлюэнсер?
- Какой кратчайший путь до инфлюэнсера?
У нашего графа есть уровни, давайте отразим их.
Алгоритм начинается с уровня один и переходит на следующие уровни по мере необходимости.
Абстрактно, алгоритм будет выглядеть так:
- Спрашиваем Максима и Руслана, являются ли они инфлюэнсерами. Если кто-то из них инфлюэнсер, то останавливаем алгоритм на первом найденном инфлюэнсере. Если среди них нет инфлюэнсеров, то просим кинуть клич среди своих друзей. Максим и Руслан не инфлюэнсеры, идем к их друзьям на следующий уровень.
- Максим и Руслан спрашивают у Петра и Марата, являются ли они инфлюэнсерами. Если кто-то из них инфлюэнсер, то останавливаем алгоритм на первом найденном инфлюэнсере. Если среди них нет инфлюэнсеров, то просим повторить запрос среди их друзей. Марат - инфлюэнсер, поэтому останавливаем алгоритм.
Запрограммируем реализацию. Будем использовать очереди.
impl Matrix {
pub fn bfs(&self, starter_node: usize, target_node: usize) -> bool {
let mut queue = vec![];
queue.push(starter_node);
let mut searched = vec![];
while !queue.is_empty() {
let node = queue.remove(0);
if !searched.contains(&node) {
if node == target_node {
println!("The target node was found!");
println!("Searched: {:?}", searched);
return true;
} else {
queue.extend(self.get_adjs(node));
searched.push(node);
}
println!("Node: {:?}", node);
println!("Q: {:?}\n", queue);
}
}
return false;
}
}
Ну а теперь давайте создадим наш граф и пройдемся по нему поиском в ширину.
fn main() {
// Node 0 - Me
// Node 1 - Ruslan
// Node 2 - Maksim
// Node 4 - Marat
// Node 3 - Peter
// Node 5 - Sveta
let mut graph: Matrix = Matrix::new(6, 0);
graph.add_directed_edge(0, 1);
graph.add_directed_edge(0, 2);
graph.add_directed_edge(1, 4);
graph.add_directed_edge(2, 3);
graph.add_directed_edge(3, 5);
graph.bfs(0, 4);
}
И вот что мы получаем на выходе:
Node: 0
Q: [1, 2]
Node: 1
Q: [2, 4]
Node: 2
Q: [4, 3]
The target node was found!
Searched: [0, 1, 2]
После прохождения первого уровня, узлов 1 и 2, первым в очереди был искомый узел 4, о чем алгоритм сообщил и остановил свое выполнение.
Исходный код можно найти в моем репозитории: https://github.com/arg2u/graphula
Заключение
Граф - это одна из фундаментальных структур для программиста. Она используется для моделирования различных связей между объектами.
Различные алгоритмы с графами позволяются находить кратчайший путь от точки А до точки B в навигационных приложениях, находить наиболее эффективное решение задачи в экспертных системах и другие.
Самое свежее
В чем отличие аутсорсинга разработки от аутстаффинга ИТ-сотрудника для разработки?
10/17/2022В этой статье разберемся, что такое аутсорс- и аутстафф-разработка.
Знакомьтесь, Пентест
8/22/2022Начинаем рассматривать один из основных методов оценки безопасности компьютерных систем и сетей на предмет потенциальных уязвимостей - тестирование на проникновение
Сокращаем срок реализации MVP
12/8/2022Разберемся со сроками реализации MVP.
Тестирование концепции MVP
1/9/2023Разбираемся с тем, как не потратить бюджеты на разработку MVP впустую
Неверная оценка стоимости услуг ИТ подрядчика
9/10/2022Сегодня мы поговорим о неверной оценке стоимости разработки ИТ решений. Эта боль - одна из основных для предприятий и стартапов, включая самих ИТ подрядчиков.
Введение в паттерны проектирования в разработке программного обеспечения
10/3/2022В этой статье мы начнем погружаться в мир оптимизации архитектуры приложений с помощью шаблонов проектирования
Уровни модели OSI
9/6/2022В этой статье мы более подробно рассмотрим каждый из уровней модели OSI
Документирование кода в языке программирования Rust
8/24/2022В этой статье рассмотрим то, как происходит документирование в Rust и рассмотрим очень полезную возможность - написание тестов через документирование.
Знакомство с моделью OSI
8/19/2022В этой статье начинаем рассматривать фундаментальную модель сетевого взаимодействия - OSI
CSS анимация пульсации
8/31/2022Простой пример того, как реализовать анимацию пульсации, используя HTML и CSS
От концепции к MVP
11/18/2022В этой статье вы узнаете, на примере, о том, как перейти от концепции к MVP без лишних усложнений в функционале продукта
Введение в написание технического задания
1/31/2023Техническое задание - это важная часть процесса разработки. В этой статье начнем погружение в данный вопрос.
Введение в разработку
10/10/2022Сегодня большинство компаний сталкивается с ИТ-разработкой и часто не получают то, чего хотят. В этой статье мы начинаем погружение в процесс создания ИТ-решений.
От идеи к концепции
10/27/2022В этой публикации мы поговорим о том, чем идея отличается от концепции. Сделаем это на примере конкретной цели
Взвешенные графы
12/26/2022В этой статье мы познакомимся со взвешенными графами, алгоритмом Дейкстры и его реализацией на языке программирования Rust.
Зачем VPN бизнесу?
9/27/2022В этой статье мы рассмотрим то, как можно обезопасить доступ к облачным ресурсам предприятия с помощью VPN