<Назад
Простыми словами о графах

В этой статье мы начнем знакомство с графами, познакомимся с алгоритмом поиска в ширину и реализуем граф на языке программирования Rust.


Что такое граф?


Граф воспроизводит набор связей. Представим, что есть Иван, который много слышал о Еве и теперь хочет познакомиться с ней. У Ивана есть две подруги, Алиса и Татьяна. Алиса знакома с Евой через свою подругу Ангелину, а Татьяна знакома с Евой напрямую. Такие формулировки связей воспринимаются трудно, но можно легко отобразить эту связь с помощью графа. Стрелки показывают направление связей: Иван дружит с Алисой и с Татьяной, Алиса дружит с Ангелиной и т.д.



Каждый граф состоит из узлов и ребер.




Типы графов


Существует много типов графов, вот некоторые из них:

  • неориентированные;
  • ориентированные;
  • мультиграф;
  • псевдограф.


Давайте рассмотрим их графическое представление.



Программное представление графов


Существуют четыре основных метода представления графов. Выбор представления определяется условиями конкретной задачи. Они различаются объемом занимаемой памяти и скоростью выполнения операций над графами. Существуют разные комбинации составляющих графа:

  1. Матрица смежности графа (или матрица весов графа).
  2. Структуры (списки) смежных вершин графа.
  3. Матрица инцидентности графа: вершина–ребра.
  4. Список ребер графа.

Чаще всего используется матрица смежности и списки смежных вершин. Однако следует подчеркнуть, что при небольшом количестве узлов ~ 10 представления не имеет значения.


В последующих примерах я буду использовать матрицу смежности, но в работе используйте такое представление, которое максимально эффективно для вашей задачи.


Матрицей смежности графа с n узлами называется матрица Anxn, элементы которой:

  1. Если узел i смежен с узлом j, то значение = 1.
  2. Если узел i не смежен с узлом j, то значение = 0.
  3. Если из узла исходит k количество ребер, то значение = k.
  4. Если у узла есть 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;
    }
}


Теперь самое время рассмотреть один из алгоритмов обхода графа - «Поиск в ширину».


Алгоритм поиска в ширину


Этот алгоритм позволяет нам ответить на два вопроса:

  1. Существует ли путь от одного узла до другого?
  2. Какой путь самый кратчайший?


Предположим, что наша задача - найти инфлюэнсера в сфере программирования, среди наших друзей и их друзей, которые образуют сеть контактов. Вот так вот выглядит наша сеть:




В нашей сети контактов есть два инфлюэнсера: Марат и Света, но еще предстоит до этого дойти.


Нам нужно ответить на два вопроса:

  1. Существует ли в нашей сети инфлюэнсер?
  2. Какой кратчайший путь до инфлюэнсера?


У нашего графа есть уровни, давайте отразим их.




Алгоритм начинается с уровня один и переходит на следующие уровни по мере необходимости.


Абстрактно, алгоритм будет выглядеть так:

  1. Спрашиваем Максима и Руслана, являются ли они инфлюэнсерами. Если кто-то из них инфлюэнсер, то останавливаем алгоритм на первом найденном инфлюэнсере. Если среди них нет инфлюэнсеров, то просим кинуть клич среди своих друзей. Максим и Руслан не инфлюэнсеры, идем к их друзьям на следующий уровень.
  2. Максим и Руслан спрашивают у Петра и Марата, являются ли они инфлюэнсерами. Если кто-то из них инфлюэнсер, то останавливаем алгоритм на первом найденном инфлюэнсере. Если среди них нет инфлюэнсеров, то просим повторить запрос среди их друзей. Марат - инфлюэнсер, поэтому останавливаем алгоритм.


Запрограммируем реализацию. Будем использовать очереди.


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 в навигационных приложениях, находить наиболее эффективное решение задачи в экспертных системах и другие.

Хэштеги:
#графы
#rust
#алгоритмы
Поделиться:

Самое свежее

В чем отличие аутсорсинга разработки от аутстаффинга ИТ-сотрудника для разработки?

В этой статье разберемся, что такое аутсорс- и аутстафф-разработка.

#процессразработки

Знакомьтесь, Пентест

Начинаем рассматривать один из основных методов оценки безопасности компьютерных систем и сетей на предмет потенциальных уязвимостей - тестирование на проникновение

#пентест

Сокращаем срок реализации MVP

Разберемся со сроками реализации MVP.

#процессразработки

Тестирование концепции MVP

Разбираемся с тем, как не потратить бюджеты на разработку MVP впустую

#процессразработки

Неверная оценка стоимости услуг ИТ подрядчика

Сегодня мы поговорим о неверной оценке стоимости разработки ИТ решений. Эта боль - одна из основных для предприятий и стартапов, включая самих ИТ подрядчиков.

#консалтинг

Введение в паттерны проектирования в разработке программного обеспечения

В этой статье мы начнем погружаться в мир оптимизации архитектуры приложений с помощью шаблонов проектирования

#шаблоныпроектирования

Уровни модели OSI

В этой статье мы более подробно рассмотрим каждый из уровней модели OSI

#сети
#osi

Документирование кода в языке программирования Rust

В этой статье рассмотрим то, как происходит документирование в Rust и рассмотрим очень полезную возможность - написание тестов через документирование.

#rust

Знакомство с моделью OSI

В этой статье начинаем рассматривать фундаментальную модель сетевого взаимодействия - OSI

#сети

CSS анимация пульсации

Простой пример того, как реализовать анимацию пульсации, используя HTML и CSS

#css

От концепции к MVP

В этой статье вы узнаете, на примере, о том, как перейти от концепции к MVP без лишних усложнений в функционале продукта

#процессразработки

Введение в написание технического задания

Техническое задание - это важная часть процесса разработки. В этой статье начнем погружение в данный вопрос.

#процессразработки

Введение в разработку

Сегодня большинство компаний сталкивается с ИТ-разработкой и часто не получают то, чего хотят. В этой статье мы начинаем погружение в процесс создания ИТ-решений.

#процессразработки

От идеи к концепции

В этой публикации мы поговорим о том, чем идея отличается от концепции. Сделаем это на примере конкретной цели

#процессразработки

Взвешенные графы

В этой статье мы познакомимся со взвешенными графами, алгоритмом Дейкстры и его реализацией на языке программирования Rust.

#алгоритмы
#графы

Зачем VPN бизнесу?

В этой статье мы рассмотрим то, как можно обезопасить доступ к облачным ресурсам предприятия с помощью VPN

#сети
#впн