Представление и обход графов алгоритмов и структур данных

В основном он знакомит с основами теории графов, двумя представлениями графов, обходом графов (в глубину и в ширину), путями из одной точки в другую и кратчайшими путями.

Посетите мой технический блог для получения исходного текстаСтек технологий томатов — теория графов

Основы теории графов

Теория графов — это не изучение изображений. Вместо этого изучайте математические модели, состоящие из узлов и ребер.

Абстрактная модель теории графов

• В начале все сложно, хоть и выглядит очень сложно, но постепенно изучая и углубляясь, вы осознаете его прелесть

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

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

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

Классификация графиков:

• Неориентированный граф (неориентированный граф) люди знают, что люди являются ребрами, нет направления
• Направление передачи автоматов Directed Graph

• Неориентированный граф — это особый вид ориентированного графа.

• Несанкционированный граф (сторона: знать или нет: степень друга)

• Авторизованный график (значение боковой полосы: сходство фильма и длина дороги)

Графическая связность:

Три картинки или одна картинка

• Его можно увидеть в виде трех картинок. также можно рассматривать как единое целое.
• Граф не является полностью связным.

Простой график:

• Учитывая минимальное остовное дерево, связность, эти два вида ребер не имеют большого значения.
• Простая схема: не входит.

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

• Какая структура данных используется для представления ребер:

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

n узлов — это матрица с n строками и n столбцами, а неориентированный граф диагонально-симметричен: 1 означает связность. 0 означает отсутствие связи

Матричное представление ориентированного графа:

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

Для каждой вершины выражается только информация, связанная с этой вершиной

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

Плюсы: мало места для хранения

Анализ конкретных проблем

• Насколько список смежности подходит для представления разреженного графа (Sparse Graph)

• Матрица смежности подходит для представления плотного графа (Dense Graph) с множеством ребер

  • Сходство между каждым фильмом и любым другим фильмом. Ребра соединены независимо от одинакового размера. Между всеми точками есть ребра.

• Плотный: количество ребер сравнивается с максимальным количеством ребер, которые он может иметь.

• Следующий рисунок представляет собой разреженный граф:

• Полный граф плотного графа

  

Код

Реализация кода матрицы смежности

// 稠密图 - 邻接矩阵
class DenseGraph{

private:
    int n, m;       // 节点数和边数
    bool directed;  // 是否为有向图
    vector<vector<bool>> g; // 图的具体数据

public:
    // 构造函数
    DenseGraph( int n , bool directed ){
        assert( n >= 0 );
        this->n = n;
        this->m = 0;    // 初始化没有任何边
        this->directed = directed;
        // g初始化为n*n的布尔矩阵, 每一个g[i][j]均为false, 表示没有任和边
        //g = vector<vector<bool>>(n, vector<bool>(n, false));
          for (int i = 0; i < n; ++i) {
            g.push_back(vector<bool>(n, false));
        }
    }

    ~DenseGraph(){ }

    int V(){ return n;} // 返回节点个数
    int E(){ return m;} // 返回边的个数

    // 向图中添加一个边，v和w表示一个顶点
    void addEdge( int v , int w ){

        assert( v >= 0 && v < n );
        assert( w >= 0 && w < n );

        if( hasEdge( v , w ) )
            return;

        g[v][w] = true;
        if( !directed )
            g[w][v] = true;

        m ++;
    }

    // 验证图中是否有从v到w的边
    bool hasEdge( int v , int w ){
        assert( v >= 0 && v < n );
        assert( w >= 0 && w < n );
        return g[v][w];
    }
};

Уведомление:

• Addedge удалил концепцию параллельных ребер. потому что если есть возврат между ребрами
• O(1), чтобы определить, есть ли ребро

Реализация кода разреженного графа

// 稀疏图 - 邻接表
class SparseGraph{

private:
    int n, m;       // 节点数和边数
    bool directed;  // 是否为有向图
    vector<vector<int>> g;  // 图的具体数据

public:
    // 构造函数
    SparseGraph( int n , bool directed ){
        assert( n >= 0 );
        this->n = n;
        this->m = 0;    // 初始化没有任何边
        this->directed = directed;
        // g初始化为n个空的vector, 表示每一个g[i]都为空, 即没有任和边
        //g = vector<vector<int>>(n, vector<int>());
        for (int i = 0; i < n; ++i) {
            g.push_back(vector<int>());
        }
    }

    ~SparseGraph(){ }

    int V(){ return n;} // 返回节点个数
    int E(){ return m;} // 返回边的个数

    // 向图中添加一个边
    void addEdge( int v, int w ){

        assert( v >= 0 && v < n );
        assert( w >= 0 && w < n );

        g[v].push_back(w);
        //处理自环边
        if( v != w && !directed )
            g[w].push_back(v);

        m ++;
    }

    // 验证图中是否有从v到w的边
    bool hasEdge( int v , int w ){

        assert( v >= 0 && v < n );
        assert( w >= 0 && w < n );

        //使用邻接表在判断解决平行边复杂度高
        for( int i = 0 ; i < g[v].size() ; i ++ )
            if( g[v][i] == w )
                return true;
        return false;
    }
};

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

Преимущества списков смежности

• Обход смежных ребер - наиболее распространенная операция в алгоритмах графов.
• Пересекая соседние ребра, список смежности имеет преимущества

соседний итератор

Реализация кода итератора разреженного графа

  // 邻边迭代器, 传入一个图和一个顶点,
    // 迭代在这个图中和这个顶点向连的所有顶点
    class adjIterator{
    private:
        SparseGraph &G; // 图G的引用
        int v;
        int index;

    public:
        // 构造函数
        adjIterator(SparseGraph &graph, int v): G(graph){
            this->v = v;
            this->index = 0;
        }

        ~adjIterator(){}

        // 返回图G中与顶点v相连接的第一个顶点
        int begin(){
            index = 0;
            if( G.g[v].size() )
                return G.g[v][index];
            // 若没有顶点和v相连接, 则返回-1
            return -1;
        }

        // 返回图G中与顶点v相连接的下一个顶点
        int next(){
            index ++;
            if( index < G.g[v].size() )
                return G.g[v][index];
            // 若没有顶点和v相连接, 则返回-1
            return -1;
        }

        // 查看是否已经迭代完了图G中与顶点v相连接的所有顶点
        bool end(){
            return index >= G.g[v].size();
        }
    };

Кодовая реализация плотного графа

     // 邻边迭代器, 传入一个图和一个顶点,
    // 迭代在这个图中和这个顶点向连的所有顶点
    class adjIterator{
    private:
        DenseGraph &G;  // 图G的引用
        int v;
        int index;

    public:
        // 构造函数
        adjIterator(DenseGraph &graph, int v): G(graph){
            assert( v >= 0 && v < G.n );
            this->v = v;
            this->index = -1;   // 索引从-1开始, 因为每次遍历都需要调用一次next()
        }

        ~adjIterator(){}

        // 返回图G中与顶点v相连接的第一个顶点
        int begin(){

            // 索引从-1开始, 因为每次遍历都需要调用一次next()
            index = -1;
            return next();
        }

        // 返回图G中与顶点v相连接的下一个顶点
        int next(){

            // 从当前index开始向后搜索, 直到找到一个g[v][index]为true
            for( index += 1 ; index < G.V() ; index ++ )
                if( G.g[v][index] )
                    return index;
            // 若没有顶点和v相连接, 则返回-1
            return -1;
        }

        // 查看是否已经迭代完了图G中与顶点v相连接的所有顶点
        bool end(){
            return index >= G.V();
        }
    };

контрольная работа

#include <iostream>
#include "SparseGraph.h"
#include "DenseGraph.h"

using namespace std;


int main() {

    int N = 20;
    int M = 100;

    srand( time(NULL) );


    // Sparse Graph
    SparseGraph g1(N , false);
    for( int i = 0 ; i < M ; i ++ ){
        int a = rand()%N;
        int b = rand()%N;
        g1.addEdge( a , b );
    }

    // O(E)
    for( int v = 0 ; v < N ; v ++ ){
        cout<<v<<" : ";
        SparseGraph::adjIterator adj( g1 , v );
        for( int w = adj.begin() ; !adj.end() ; w = adj.next() )
            cout<<w<<" ";
        cout<<endl;
    }

    cout<<endl;


    // Dense Graph
    DenseGraph g2(N , false);
    for( int i = 0 ; i < M ; i ++ ){
        int a = rand()%N;
        int b = rand()%N;
        g2.addEdge( a , b );
    }

    // O(V^2)
    for( int v = 0 ; v < N ; v ++ ){
        cout<<v<<" : ";
        DenseGraph::adjIterator adj( g2 , v );
        for( int w = adj.begin() ; !adj.end() ; w = adj.next() )
            cout<<w<<" ";
        cout<<endl;
    }

    return 0;
}

результат операции:

0 : 0 7 17 18 4 2 17 17 7 9 8 
1 : 15 12 19 8 5 11 3 4 16 4 
2 : 19 6 2 17 3 9 6 19 4 6 17 7 6 0 
3 : 2 4 19 16 8 10 19 11 1 7 5 16 17 
4 : 10 15 3 2 14 0 17 1 16 1 
5 : 11 14 7 1 14 15 6 3 15 
6 : 8 2 16 8 11 19 10 2 6 2 11 14 5 9 2 12 17 
7 : 9 9 17 19 5 0 14 2 3 0 10 
8 : 9 6 6 9 14 14 1 16 3 17 0 
9 : 7 15 8 19 7 8 12 2 13 6 0 
10 : 4 10 6 3 19 18 7 
11 : 6 5 6 1 3 
12 : 1 9 6 
13 : 16 9 18 
14 : 18 5 8 8 4 7 16 5 6 17 
15 : 9 1 15 4 5 15 18 5 
16 : 6 13 8 3 14 4 3 18 1 
17 : 19 7 2 0 2 4 8 0 0 14 3 6 
18 : 14 13 0 15 10 16 19 18 
19 : 2 17 9 1 6 7 3 2 10 3 18 

0 : 2 3 7 8 13 14 19 
1 : 5 10 12 16 19 
2 : 0 3 5 6 7 9 10 11 12 18 
3 : 0 2 6 8 10 14 15 17 18 19 
4 : 4 6 7 8 14 17 18 19 
5 : 1 2 7 10 14 15 17 19 
6 : 2 3 4 8 9 11 12 14 
7 : 0 2 4 5 7 8 9 13 15 16 19 
8 : 0 3 4 6 7 17 18 19 
9 : 2 6 7 15 16 
10 : 1 2 3 5 13 18 
11 : 2 6 11 13 15 16 18 19 
12 : 1 2 6 
13 : 0 7 10 11 15 17 19 
14 : 0 3 4 5 6 
15 : 3 5 7 9 11 13 16 
16 : 1 7 9 11 15 16 17 
17 : 3 4 5 8 13 16 17 
18 : 2 3 4 8 10 11 19 
19 : 0 1 3 4 5 7 8 11 13 18 

Создание плотных и разреженных оболочек класса графа

template <typename Graph>
class ReadGraph{

public:
    // 从文件filename中读取图的信息, 存储进图graph中
    ReadGraph(Graph &graph, const string &filename){

        ifstream file(filename);
        string line;
        int V, E;

        assert( file.is_open() );

        // 第一行读取图中的节点个数和边的个数
        assert( getline(file, line) );
        stringstream ss(line);
        ss>>V>>E;

        assert( V == graph.V() );

        // 读取每一条边的信息
        for( int i = 0 ; i < E ; i ++ ){

            assert( getline(file, line) );
            stringstream ss(line);

            int a,b;
            ss>>a>>b;
            assert( a >= 0 && a < V );
            assert( b >= 0 && b < V );
            graph.addEdge( a , b );
        }
    }
};

Обход в глубину и связанные компоненты

• обход в глубину
• обход в ширину

Идея: попробовать точку и записать, пройдена ли она (потому что есть кольцо).

0-1-2-5-3-4-6

На рисунке показаны 3 соединенных компонента

Реализация кода обхода в глубину

После завершения обхода посмотрите точки, которые не были пройдены

// 求无权图的联通分量
template <typename Graph>
class Component{

private:
    Graph &G;       // 图的引用
    bool *visited;  // 记录dfs的过程中节点是否被访问
    int ccount;     // 记录联通分量个数
    int *id;        // 每个节点所对应的联通分量标记

    // 图的深度优先遍历(递归方式)
    void dfs( int v ){

        visited[v] = true;
        id[v] = ccount;
        typename Graph::adjIterator adj(G, v);
        for( int i = adj.begin() ; !adj.end() ; i = adj.next() ){
            if( !visited[i] )
                dfs(i);
        }
    }

public:
    // 构造函数, 求出无权图的联通分量
    Component(Graph &graph): G(graph){

        // 算法初始化
        visited = new bool[G.V()];
        id = new int[G.V()];
        ccount = 0;
        for( int i = 0 ; i < G.V() ; i ++ ){
            visited[i] = false;
            id[i] = -1;
        }

        // 求图的联通分量
        for( int i = 0 ; i < G.V() ; i ++ )
            if( !visited[i] ){
                dfs(i);
                ccount ++;
            }
    }

    // 析构函数
    ~Component(){
        delete[] visited;
        delete[] id;
    }

    // 返回图的联通分量个数
    int count(){
        return ccount;
    }

    // 查询点v和点w是否联通
    bool isConnected( int v , int w ){
        assert( v >= 0 && v < G.V() );
        assert( w >= 0 && w < G.V() );
        return id[v] == id[w];
    }
};

main.cpp

// 测试图的联通分量算法
int main() {

    // TestG1.txt
    string filename1 = "testG1.txt";
    SparseGraph g1 = SparseGraph(13, false);
    ReadGraph<SparseGraph> readGraph1(g1, filename1);
    Component<SparseGraph> component1(g1);
    cout<<"TestG1.txt, Component Count: "<<component1.count()<<endl;

    cout<<endl;

    // TestG2.txt
    string filename2 = "testG2.txt";
    SparseGraph g2 = SparseGraph(7, false);
    ReadGraph<SparseGraph> readGraph2(g2, filename2);
    Component<SparseGraph> component2(g2);
    cout<<"TestG2.txt, Component Count: "<<component2.count()<<endl;

    return 0;
}

результат

TestG1.txt, Component Count: 3

TestG2.txt, Component Count: 1

** Уведомление**

• Найдите связанные компоненты, вы можете узнать, связаны ли два узла
• Добавьте идентификатор в запись.

int *id;        // 每个节点所对应的联通分量标记

• Поиск объединения позволяет нам узнать только, связаны ли два узла. И путь нуждается в теории графов, чтобы решить

ориентироваться

Глубина сначала получает путь. Откуда взялся обход при сохранении.

 int * from;     // 记录路径, from[i]表示查找的路径上i的上一个节点


// 路径查询
template <typename Graph>
class Path{

private:
    Graph &G;   // 图的引用
    int s;      // 起始点
    bool* visited;  // 记录dfs的过程中节点是否被访问
    int * from;     // 记录路径, from[i]表示查找的路径上i的上一个节点

    // 图的深度优先遍历
    void dfs( int v ){

        visited[v] = true;

        typename Graph::adjIterator adj(G, v);
        for( int i = adj.begin() ; !adj.end() ; i = adj.next() ){
            if( !visited[i] ){
                from[i] = v;
                dfs(i);
            }
        }
    }

public:
    // 构造函数, 寻路算法, 寻找图graph从s点到其他点的路径
    Path(Graph &graph, int s):G(graph){

        // 算法初始化
        assert( s >= 0 && s < G.V() );

        visited = new bool[G.V()];
        from = new int[G.V()];
        for( int i = 0 ; i < G.V() ; i ++ ){
            visited[i] = false;
            from[i] = -1;
        }
        this->s = s;

        // 寻路算法
        dfs(s);
    }

    // 析构函数
    ~Path(){

        delete [] visited;
        delete [] from;
    }

    // 查询从s点到w点是否有路径
    bool hasPath(int w){
        assert( w >= 0 && w < G.V() );
        return visited[w];
    }

    // 查询从s点到w点的路径, 存放在vec中
    void path(int w, vector<int> &vec){

        assert( hasPath(w) );

        stack<int> s;
        // 通过from数组逆向查找到从s到w的路径, 存放到栈中
        int p = w;
        while( p != -1 ){
            s.push(p);
            p = from[p];
        }

        // 从栈中依次取出元素, 获得顺序的从s到w的路径
        vec.clear();
        while( !s.empty() ){
            vec.push_back( s.top() );
            s.pop();
        }
    }

    // 打印出从s点到w点的路径
    void showPath(int w){

        assert( hasPath(w) );

        vector<int> vec;
        path( w , vec );
        for( int i = 0 ; i < vec.size() ; i ++ ){
            cout<<vec[i];
            if( i == vec.size() - 1 )
                cout<<endl;
            else
                cout<<" -> ";
        }
    }
};

main.cpp:

// 测试寻路算法
int main() {

    string filename = "testG.txt";
    SparseGraph g = SparseGraph(7, false);
    ReadGraph<SparseGraph> readGraph(g, filename);
    g.show();
    cout<<endl;

    Path<SparseGraph> path(g,0);
    cout<<"Path from 0 to 6 : " << endl;
    path.showPath(6);

    return 0;
}

результат операции:

vertex 0:	1	2	5	6	
vertex 1:	0	
vertex 2:	0	
vertex 3:	4	5	
vertex 4:	3	5	6	
vertex 5:	0	3	4	
vertex 6:	0	4	

DFS : 0 -> 5 -> 3 -> 4 -> 6
[Finished in 1.2s]

сложность:

• Разреженный граф (список смежности): O(V + E), когда мы хотим получить все соседние узлы узла, мы должны просмотреть все узлы в графе
• Плотный граф (матрица смежности): O(V^2)

Уведомление:

• Алгоритм обхода в глубину по-прежнему действителен для ориентированных графов.
• Обход в глубину также можно использовать для определения наличия циклов в графе.

Обход графов в ширину

Обычно необходимо использовать очередь с помощью очереди.

• Очередь пуста, чтобы указать, что обход завершен
• Расстояние от узла 0 сортируется, расстояние узла, пройденного первым
• Записав расстояние и используя массив from для записи исходного узла, можно найти кратчайший путь.
• Обход в ширину: Найдите кратчайший путь невзвешенного графа.

Код:

// 寻找无权图的最短路径
template <typename Graph>
class ShortestPath{

private:
    Graph &G;       // 图的引用
    int s;          // 起始点
    bool *visited;  // 记录dfs的过程中节点是否被访问
    int *from;      // 记录路径, from[i]表示查找的路径上i的上一个节点
    int *ord;       // 记录路径中节点的次序。ord[i]表示i节点在路径中的次序；记录最短路径

public:
    // 构造函数, 寻找无权图graph从s点到其他点的最短路径
    ShortestPath(Graph &graph, int s):G(graph){

        // 算法初始化
        assert( s >= 0 && s < graph.V() );

        visited = new bool[graph.V()];
        from = new int[graph.V()];
        ord = new int[graph.V()];
        for( int i = 0 ; i < graph.V() ; i ++ ){
            visited[i] = false;
            from[i] = -1;
            ord[i] = -1;
        }
        this->s = s;

        // 无向图最短路径算法, 从s开始广度优先遍历整张图
        queue<int> q;

        q.push( s );
        visited[s] = true;
        ord[s] = 0;
        while( !q.empty() ){

            int v = q.front();
            q.pop();

            typename Graph::adjIterator adj(G, v);
            for( int i = adj.begin() ; !adj.end() ; i = adj.next() )
                if( !visited[i] ){
                    q.push(i);
                    visited[i] = true;
                    from[i] = v;
                    ord[i] = ord[v] + 1;
                }
        }

    }

    // 析构函数
    ~ShortestPath(){

        delete [] visited;
        delete [] from;
        delete [] ord;
    }

    // 查询从s点到w点是否有路径
    bool hasPath(int w){
        assert( w >= 0 && w < G.V() );
        return visited[w];
    }

    // 查询从s点到w点的路径, 存放在vec中
    void path(int w, vector<int> &vec){

        assert( w >= 0 && w < G.V() );

        stack<int> s;
        // 通过from数组逆向查找到从s到w的路径, 存放到栈中
        int p = w;
        while( p != -1 ){
            s.push(p);
            p = from[p];
        }

        // 从栈中依次取出元素, 获得顺序的从s到w的路径
        vec.clear();
        while( !s.empty() ){
            vec.push_back( s.top() );
            s.pop();
        }
    }

    // 打印出从s点到w点的路径
    void showPath(int w){

        assert( w >= 0 && w < G.V() );

        vector<int> vec;
        path(w, vec);
        for( int i = 0 ; i < vec.size() ; i ++ ){
            cout<<vec[i];
            if( i == vec.size()-1 )
                cout<<endl;
            else
                cout<<" -> ";
        }
    }

    // 查看从s点到w点的最短路径长度
    int length(int w){
        assert( w >= 0 && w < G.V() );
        return ord[w];
    }
};

main.cpp:

// 测试无权图最短路径算法
int main() {

    string filename = "testG.txt";
    SparseGraph g = SparseGraph(7, false);
    ReadGraph<SparseGraph> readGraph(g, filename);
    g.show();
    cout<<endl;

    // 比较使用深度优先遍历和广度优先遍历获得路径的不同
    // 广度优先遍历获得的是无权图的最短路径
    Path<SparseGraph> dfs(g,0);
    cout<<"DFS : ";
    dfs.showPath(6);

    ShortestPath<SparseGraph> bfs(g,0);
    cout<<"BFS : ";
    bfs.showPath(6);

    return 0;
}

результат операции:

vertex 0:	1	2	5	6	
vertex 1:	0	
vertex 2:	0	
vertex 3:	4	5	
vertex 4:	3	5	6	
vertex 5:	0	3	4	
vertex 6:	0	4	

DFS : 0 -> 5 -> 3 -> 4 -> 6
BFS : 0 -> 6

Уведомление:

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

---

------------------------- Великолепная разделительная линия --------------------

Друзья, которые прочитали это, могут нажать «Нравится» / «Подписаться», ваша поддержка — самая большая поддержка для меня.

личный блогСтек томатной технологиииДомашняя страница Наггетс

Если вы хотите узнать больше, обратите внимание на мой публичный аккаунт WeChat: Tomato Technology Stack.