算法与数据结构之图的表示与遍历-白红宇

主要介绍图论的基础、图的两种表示、图的遍历（深度和广度）、一个点到另一点的路径和最短路径等。

原文访问我的技术博客

图论基础

图论并不是研究图画。而是研究由节点和边所构成的数学模型

图论抽象模型

万事开头难，虽然看上去很复杂，但是慢慢学习深入之后会体会到他的魅力

很多信息之间的联系都可以使用图来表示。数据可视化

图可以表示的关系

交通运输（每个节点是城市，边是道路。点是航站楼，边是航线）

社交网络（人 & 好友关系电影 & 电影相似程度）

互联网（域名域名跳转）

工作安排（先后程度）

脑区活动

程序状态执行（自动机）

图的分类：

无向图（Undirected Graph）人和人认识就是边，没有方向

有向图（Directed Graph）自动机转移有方向

无向图是一种特殊的有向图

无权图（边:认识不认识：好友度）

有权图（边带值：电影相似程度 & 路长）

图的连通性：

三图或者一图

可以看做是三张图。也可以视为一个。

图不是完全连通的。

简单图（simple Graph）：

考虑最小生成树，连通性，这两种边意义不大

简单图：不包含。

图的表示

对于边的表示采用什么样的数据结构：

邻接矩阵

n个节点就是一个n行n列的矩阵，无向图对角线对称：1表示连通。0表示没通

有向图的矩阵表示：

邻接表：

对于每个顶点只表达与这个顶点相连接的信息

每一行都是一个链表，存放了对这一行而言相连的节点。

也可以表示有向图

优点：存储空间小

具体问题具体分析

邻接表适合表示稀疏图 (Sparse Graph) 多少

邻接矩阵适合表示稠密图 (Dense Graph)边多
- 每个电影和其他所有电影之间的相似度。不管相似大小都是连接的边。所有的点之间都有边。

稠密：边的个数与能拥有的最大边的个数对比。

如下图就是一个稀疏图：

稠密图完全图

代码实现

邻接矩阵代码实现

// 稠密图 - 邻接矩阵class DenseGraph{private:    int n, m;       // 节点数和边数    bool directed;  // 是否为有向图    vector
    
     
      > 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
      
       
        >(n, vector
        
         (n, false));          for (int i = 0; i < n; ++i) {            g.push_back(vector
         
          (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的时候已经去除了平行边的概念。因为如果有边之间return

O(1)来判断是否有边

稀疏图代码实现

// 稀疏图 - 邻接表class SparseGraph{private:    int n, m;       // 节点数和边数    bool directed;  // 是否为有向图    vector
    
     
      > 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
      
       
        >(n, vector
        
         ());        for (int i = 0; i < n; ++i) {            g.push_back(vector
         
          ()); } } ~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 
    
     #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<
     
      <<" : ";        SparseGraph::adjIterator adj( g1 , v );        for( int w = adj.begin() ; !adj.end() ; w = adj.next() )            cout<
      
       <<" ";        cout<

运行结果：

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 
    
     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 
    
     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
    
      readGraph1(g1, filename1);    Component
     
       component1(g1);    cout<<"TestG1.txt, Component Count: "<
      
       <
       
         readGraph2(g2, filename2);    Component
        
          component2(g2);    cout<<"TestG2.txt, Component Count: "<
         
          <

结果

TestG1.txt, Component Count: 3TestG2.txt, Component Count: 1复制代码

** 注意**

求出连通分量，可以求出两个结点是否相连

添加id来记录。

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

并查集只能让我们知道两个结点是否相连。而路径需要图论来解决

寻路

深度优先获得一条路径。遍历的同时保存是从哪遍历过来的。

int * from;     // 记录路径, from[i]表示查找的路径上i的上一个节点// 路径查询template 
    
     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
     
       &vec){        assert( hasPath(w) );        stack
      
        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
       
         vec;        path( w , vec );        for( int i = 0 ; i < vec.size() ; i ++ ){            cout<
        
          ";        }    }};复制代码

main.cpp:

// 测试寻路算法int main() {    string filename = "testG.txt";    SparseGraph g = SparseGraph(7, false);    ReadGraph
    
      readGraph(g, filename);    g.show();    cout<
     
       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 
    
     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
     
       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
      
        &vec){        assert( w >= 0 && w < G.V() );        stack
       
         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
        
          vec;        path(w, vec);        for( int i = 0 ; i < vec.size() ; i ++ ){            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
    
      readGraph(g, filename);    g.show();    cout<
     
       dfs(g,0);    cout<<"DFS : ";    dfs.showPath(6);    ShortestPath
      
        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 -> 6BFS : 0 -> 6复制代码

注意：

广度优先一定可以找到最短无权路径

广度优先一定可以找到最短无权路径并可能找到多条，深度也有可能找到。

多条最短路径。跟遍历顺序有关。

-------------------------华丽的分割线--------------------

看完的朋友可以点个喜欢/关注，您的支持是对我最大的鼓励。

个人博客和

想了解更多，欢迎关注我的微信公众号：番茄技术小栈