<Назад

Простыми словами о графах

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

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

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

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

Типы графов

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

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

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

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

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

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

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

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

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

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