Способы представления графов

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

Примеры кода в статье будут на Rust. Полные исходники лежат на github.

Введение

С точки зрения математики, граф - это совокупность непустого множества вершин и множества пар вершин (связей между вершинами). Если же говорить простым языком, то граф - это набор вершин и связей между ними.

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

Есть много способов хранения графа в памяти. Выбор конкретной реализации зависит от конкретного графа и задач, которые необходимо решить. Наиболее распространены три способа:

  • Список смежности
  • Матрица смежности
  • Список ребер

Для начала мы объявим типаж графа, а затем добавим реализации для каждого конкретного способа представления.

pub type Key = usize;
pub type Weight = usize;

pub trait Graph<N> {
    fn new() -> Self;
    fn add_node(&mut self, node: N) -> Key;
    fn add_edge(&mut self, begin: Key, end: Key, weight: Weight, bidirected: bool);
}

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

Привер графа

Для того, чтобы создать граф, представленный на изображении выше, мы будем использовать функцию create_sample_graph(), которая принимает пустой граф и заполняет его.

fn create_sample_graph<T: Graph<&'static str>>(graph: &mut T) {
    let key0 = graph.add_node("node0");
    let key1 = graph.add_node("node1");
    let key2 = graph.add_node("node2");
    let key3 = graph.add_node("node3");
    let key4 = graph.add_node("node4");
    let key5 = graph.add_node("node5");
    let key6 = graph.add_node("node6");
    let key7 = graph.add_node("node7");
    let key8 = graph.add_node("node8");
    let key9 = graph.add_node("node9");
    graph.add_edge(key0, key1, 5, false);
    graph.add_edge(key1, key4, 1, false);
    graph.add_edge(key2, key8, 5, true); // Ребро, а не дуга
    graph.add_edge(key3, key0, 3, false);
    graph.add_edge(key3, key7, 4, false);
    graph.add_edge(key3, key9, 4, false);
    graph.add_edge(key4, key3, 5, false);
    graph.add_edge(key6, key0, 1, false);
    graph.add_edge(key7, key2, 2, false);
    graph.add_edge(key7, key4, 2, false);
    graph.add_edge(key8, key5, 1, false);
    graph.add_edge(key9, key6, 2, false);
    graph.add_edge(key9, key8, 2, false);
}

Список смежности

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

Обратите внимание, что данный способ позволяет хранить только одну петлю для каждой вершины.

Создадим структуру AdjacencyList и реализуем для нее типаж Graph.

use std::collections::HashMap;

#[derive(Debug)]
pub struct AdjacencyList<N> {
    map: HashMap<Key, HashMap<Key, Weight>>,
    list: HashMap<Key, N>,
    next_value: Key,
}

impl<N> AdjacencyList<N> {
    fn get_next_key(&mut self) -> Key {
        let key = self.next_value;
        self.next_value += 1;
        key
    }
}

impl<N> Graph<N> for AdjacencyList<N> {
    fn new() -> Self {
        AdjacencyList {
            map: HashMap::new(),
            list: HashMap::new(),
            next_value: 0,
        }
    }

    fn add_node(&mut self, node: N) -> Key {
        let key = self.get_next_key();
        self.list.insert(key, node);
        self.map.insert(key, HashMap::new());
        key
    }

    fn add_edge(&mut self, begin: Key, end: Key, weight: Weight, bidirected: bool) {
        if let Some(map) = self.map.get_mut(&begin) {
            map.insert(end, weight);
        } else {
            return;
        }

        if bidirected {
            if let Some(map) = self.map.get_mut(&end) {
                map.insert(begin, weight);
            }
        }
    }
}

Здесь мы отдельно храним список вершин в поле list. При добавлении вершины, ей присваивается ключ Key и дальше он используется в самом списке смежности map. Список смежности здесь реализован при помощи HashMap. Код достаточно прост и понятен.

Единственное на что, стоит обратить внимание - метод add_edge(). Если аргумент bidirected равен true, то он создает дугу (ненаправленное ребро). Для этого просто создается еще одна дуга, обратная основной. Пример можно увидеть на связи 2 и 8 вершин.

Вот как будет выглядеть наш граф, если представить его в виде списка смежности:

let mut adjacency_list = AdjacencyList::<&str>::new();
create_sample_graph(&mut adjacency_list);
println!("{:?}", adjacency_list);
// AdjacencyList {
//     map: {
//         0: {1: 5}, <-- С вершиной 0, связана вершина 1 и вес этой дуги равен 5.
//         1: {4: 1},
//         2: {8: 2},
//         3: {0: 3, 7: 4, 9: 4},
//         4: {3: 5},
//         5: {}
//         6: {0: 1},
//         7: {2: 2, 4: 2},
//         8: {2: 5, 5: 1},
//         9: {6: 2, 8: 2},
//     },
//     ...
// }

Матрица смежности

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

Реализация может быть различной. Это может быть список bool значений. Если ребро существует, то записываем true, иначе - false. Если мы работаем со взвешенным графом, то вместо этого мы можем записывать в ячейку вес ребра и смотреть: если вес указан - то ребро существует. В таком случае для указания отсутствия ребра необходимо использовать недопустимое значение. Rust предоставляется для этого удобный инструмент - опциональные типы. Там, где нет ребра будем записывать None.

Как и список смежности, этот способ не позволяет указать больше одной петли для вершины.

Создадим структуру AdjacencyMatrix и точно так же реализуем для нее типаж Graph.

use std::collections::HashMap;

#[derive(Debug)]
pub struct AdjacencyMatrix<N> {
    map: HashMap<Key, HashMap<Key, Option<Weight>>>,
    list: HashMap<Key, N>,
    next_value: Key,
}

impl<N> AdjacencyMatrix<N> {
    fn get_next_key(&mut self) -> Key {
        let key = self.next_value;
        self.next_value += 1;
        key
    }
}

impl<N> Graph<N> for AdjacencyMatrix<N> {
    fn new() -> Self {
        AdjacencyMatrix {
            map: HashMap::new(),
            list: HashMap::new(),
            next_value: 0,
        }
    }

    fn add_node(&mut self, node: N) -> Key {
        let key = self.get_next_key();
        self.list.insert(key, node);
        self.map.insert(key, HashMap::new());

        let mut exist_keys: Vec<usize> = vec![];
        for (item_key, item_map) in &mut self.map {
            item_map.insert(key, None);
            if *item_key != key {
                exist_keys.push(*item_key);
            }
        }

        let mut inserted_map = self.map.get_mut(&key).unwrap();
        for item_key in exist_keys {
            inserted_map.insert(item_key, None);
        }

        key
    }

    fn add_edge(&mut self, begin: Key, end: Key, weight: Weight, bidirected: bool) {
        if let Some(map) = self.map.get_mut(&begin) {
            map.insert(end, Some(weight));
        } else {
            return;
        }

        if bidirected {
            if let Some(map) = self.map.get_mut(&end) {
                map.insert(begin, Some(weight));
            }
        }
    }
}

Главное отличие от AdjacencyList состоит в том, что при добавлении вершины ей сразу присваивается полный список всех остальных вершин графа и для каждой из них проставляется значение None.

Вот как хранится матрица смежности:

let mut adjacency_matrix = AdjacencyMatrix::<&str>::new();
create_sample_graph(&mut adjacency_matrix);
println!("{:?}", adjacency_matrix);
// AdjacencyMatrix {
//     map: {
//         0: {0: None,    1: Some(5), 2: None,    3: None,    4: None,    5: None,    6: None,    7: None,    8: None,    9: None   },
//         1: {0: None,    1: None,    2: None,    3: None,    4: Some(1), 5: None,    6: None,    7: None,    8: None,    9: None   },
//         2: {0: None,    1: None,    2: None,    3: None,    4: None,    5: None,    6: None,    7: None,    8: Some(5), 9: None   },
//         3: {0: Some(3), 1: None,    2: None,    3: None,    4: None,    5: None,    6: None,    7: Some(4), 8: None,    9: Some(4)},
//         4: {0: None,    1: None,    2: None,    3: Some(5), 4: None,    5: None,    6: None,    7: None,    8: None,    9: None   },
//         5: {0: None,    1: None,    2: None,    3: None,    4: None,    5: None,    6: None,    7: None,    8: None,    9: None   },
//         6: {0: Some(1), 1: None,    2: None,    3: None,    4: None,    5: None,    6: None,    7: None,    8: None,    9: None   },
//         7: {0: None,    1: None,    2: Some(2), 3: None,    4: Some(2), 5: None,    6: None,    7: None,    8: None,    9: None   },
//         8: {0: None,    1: None,    2: Some(5), 3: None,    4: None,    5: Some(1), 6: None,    7: None,    8: None,    9: None   },
//         9: {0: None,    1: None,    2: None,    3: None,    4: None,    5: None,    6: Some(2), 7: None,    8: Some(2), 9: None   },
//     },
//     ...
// }

Список ребер

Список ребер использует совершенно иной подход. Он просто хранит ребра в виде списка, где каждый элемент содержит описание одного ребра: смежные вершины и вер. Естественно, он проще в реализации.

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

#[derive(Debug)]
pub struct ListOfEdges<N> {
    map: Vec<(Key, Key, Weight)>,
    list: Vec<N>,
}
impl<N> Graph<N> for ListOfEdges<N> {
    fn new() -> Self {
        ListOfEdges {
            map: vec![],
            list: vec![],
        }
    }

    fn add_node(&mut self, node: N) -> Key {
        self.list.push(node);
        self.list.len() - 1
    }

    fn add_edge(&mut self, begin: Key, end: Key, weight: Weight, bidirected: bool) {
        self.map.push((begin, end, weight));
        if bidirected {
            self.map.push((end, end, weight));
        }
    }
}

Здесь мы храним список ребер в обычном векторе и каждое ребро представляем как кортеж из трех элементов (begin, end, weight).

Вот как он выглядит в памяти:

let mut list_of_edges = ListOfEdges::<&str>::new();
create_sample_graph(&mut list_of_edges);
// ListOfEdges {
//     map: [
//         (0, 0, 5),
//         (1, 4, 1),
//         (2, 8, 5),
//         (3, 0, 3),
//         (3, 7, 4),
//         (3, 9, 4),
//         (4, 3, 5),
//         (6, 0, 1),
//         (7, 2, 2),
//         (7, 4, 2),
//         (8, 2, 5),
//         (8, 5, 1),
//         (9, 6, 2),
//         (9, 8, 2),
//     ],
//     ...
// }

Заключение

На самом дела выбрать способ представления графа не так-то просто. Нужно ясно понимать какие задачи будут решаться и какой граф будет обрабатываться. Естественно, что для графа размером в 10 вершин разницы не будет. Но на больших графах она заметна.

Правильный выбор не всегда очевиден. Существует распространенное заблуждение, что матрица смежности требует намного больше памяти, чем список смежности т.к. хранит множество пустых значений. Но это справедливо только для слабосвязанных графов. Если же вы работаете с сильно связанным графом, то разница в потребляемой памяти будет не так велика, зато матрица смежности обеспечит более быстрый поиск ребер.

Существует много способов представления графов. Но самые распространенные - это матрица смежности и список смежности. Если вы не знаете точно, что вам надо - используйте один из них.

Материалы по теме:

Коментарии

Используйте Markdown

Thank you for comment!
Ваше сообщение будет доступно после проверки.