我的算法之路 -- Graph 图论


我的算法之路 – Graph 图论

Created by miccall (转载请注明出处)
  • 按理说这类文章首先应该讲一些鸡汤啊 鼓励学习什么的话       但是没有

  • 按理说这类文章应该有一些推荐路径或者学习方法       但是没有

  • 按理说这个文章应该和其他的类似 讲些算法之坑       但是没有

  • 那这篇文章出现的意义是什么 没什么 就是我的学习之路      你爱看就看看

一.互联问题

  • 构成 : 节点(Vertex) 边(Edge)

  • 解决问题 : 交通运输 社交网络 互联网 工作安排 程序执行状态

  • 分类 : 无向图(Undirected Graph) 有向图(Directed Graph) 无权图(Unweighted Graph) 有权图(Weighted Graph)

  • 联通性 自环边 平行边

  • 图的表示方式 :

  • 邻接矩阵 (Adjacency Matrix) 适合表示稠密图(Dense) 近似于完全图 所有的点和所有的点都有一个边

  • 邻接表 (Adjacency Lists) 适合表示稀疏图(Sparse) 一个节点边的个数 远小于整个图所能有的最大边的个数

二.代码架构

1.邻接矩阵 表示 稠密图


        #include <iostream>
        #include <vector>
        #include <cassert>
        using namespace std ;
  • vector 我们引入vector 二维数组来存取 具体用法另行参考

        // 稠密图 邻接矩阵 
        class DenseGraph
        {
        private:
            int m,n;  //点数和边数
            bool directed;  //是否为 有向图
            vector< vector<bool> > g; // 一个二维的矩阵

        public:

            //构造一个稠密图 
            DenseGraph(int n ,bool directed){

            }
            //析构
            ~DenseGraph(){

            }

            //返回点数
            int V()
            { 
                return n ;
            }

            //返回边数
            int E(){ 
                return m ;
            }

            //给两个点添加一条边
            void  addEdge(int v ,int w )
            {

            }

            //判断两个点是否有边
            bool hasEdge(int v ,int w)
            {

            }

            //打印这个矩阵
            void show()
            {

            }

            //迭代器 来遍历整个图
            class adjIterator{

            };

        };
  • 构造函数

        //我们传入一个图的大小 和 是否为有向图 
        DenseGraph(int n , bool directed){

            this->n = n ;
            //初始化为 0 条边
            this->m = 0 ;

            this->directed = directed ;

            //初始化这个矩阵 
            for (int i = 0; i < n; i++)
            {
                g.push_back( vector<bool> (n,false) ); 

                /*
                    初始化形成一个 n*n 的 bool 矩阵

                    函数用法 : push_back( const T &n) ;

                    参数 vector<bool>(n,false);

                    创建一个含有n个 false 拷贝的 vector

                */
            }

        }
  • 析构函数为空 因为我们没有开辟新的空间

  • 给两个点添加一条边


        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++ ;
        }
  • 判断两个点是否有边

        bool hasEdge(int v ,int w)
        {
            assert( v>=0 && v < n);
            assert( w>=0 && w < n);

            //直接返回v和w标识是否为true
            return g[v][w];
        }
  • 打印这个矩阵

        void show()
        {
            for (int i = 0; i < n; i++) 
            {
                for (int j = 0; j < n; j++) 
                {
                    cout<<g[i][j]<<"\t";
                }
                cout<<endl;
            }
        }
  • 迭代器我们暂时先放一放

  • 先来看稀疏图

2.邻接表 表示 稀疏图

  • 头文件是一样的

        // 稀疏图 邻接表 
        class SparseGraph
        {
        private:
            int n ; //图的节点数 
            int m ;  //图的边数 
            bool directed ; //是否为 有向图
            vector< vector<int> > g;  // 邻接表

        public:
            //构造一个节点的图 
            SparseGraph(int n , bool directed){

            }
            ~SparseGraph(){

            }

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

            //返回边的个数 

            int E(){ return m ;}

            //给两个点  添加一个边  
            void  addEdge(int v ,int w ) {

            }

            //判断两个点是否有 边 
            bool hasEdge(int v ,int w )
            {

            }

            void show()
            {

            }

            //迭代器 来遍历整个图
            class adjIterator{

            };
        };
  • 构造函数

        //我们传入一个图的大小 和是否为有向图 
        SparseGraph(int n , bool directed){

            //初始化
            this->n = n ;
            this->m = 0 ;

            this->directed = directed ;

            for (int i = 0; i < n; i++)
            {
                g.push_back( vector<int>() ); 
                //动态建立的邻接表
            }
        }
  • 析构函数为空 因为我们没有开辟新的空间

  • 给两个点添加一条边


        void  addEdge(int v ,int w ) {

            //判断不越界 
            assert(v >= 0 && v < n);
            assert(w >= 0 && w < n);

            g[v].push_back(w) ; //给第v个点 动态建立的邻接表 

            //如果是无向图的话 反过来也得建立一个边 
            if(v != w && ! directed )  //自环边 如果v==w的话 只要运行一次 push_back就可以了
                g[w].push_back(v); 

            m++ ;
        }
  • 判断两个点是否有边

        bool hasEdge(int v ,int w )
        {
            assert( v >= 0 && v < n);
            assert(w >= 0 && w < n);

            //遍历动态的表  循环他的长度 看看里面是有一个是我们要找的边   最坏的话 O(n)
            for (int i = 0 ; i < g[v].size() ; i ++) {
                if( g[v][i] == w )
                    return true ;
            }

            return false ;
        }
  • 打印这个矩阵

        void show()
        {
            for (int i = 0; i < n; i++) 
            {
                cout<<"vertex "<<i<<":\t" ;
                for (int j = 0; j < g[i].size(); j++) 
                {
                    cout<<g[i][j]<<"\t";
                }
                cout<<endl;
            }
        }

3.迭代器

  • 图的算法 ,首先想到的就是遍历某一点的所有领边
  • 最简单的方式 当然是把图g直接交给用户 直接就能对g进行操作
  • 但是这样的不好就是 用户有权限对g修改 造成数据的错误

  • 我们使用迭代器 可以隐藏迭代的过程 来遍历我们需要的某一行

  • 稀疏图的迭代器


    class adjIterator{
        private:
            SparseGraph &G; //图的引用 
            int v;          //点 
            int index;      //索引
        public:

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

            //开始条件 
            int begin(){

                index = 0;
                // g应该是private 这里是内部类 所以可以访问
                if( G.g[v].size() )
                    return G.g[v][index];
                return -1;
                //在大小大于零 的情况下 我们就获取到了 v相邻的第一条边所连的点   
            }

            int next(){

                index ++;
                //如果 index 没有越界 那么我们就可以获取到这个索引所指向的的那个边连接的点
                if( index < G.g[v].size() )
                    return G.g[v][index];
                return -1;

                //这样 用户每调用一次next 就获取到了下一条边指向的点 
            }

            bool end(){

                //判断迭代是否结束 我们只要判断 index是否超过了 图一行的大小

                return index >= G.g[v].size();
            }
    };
  • 测试使用

    int main()
    {
        int N = 20 ; //定点个数 
        int M = 100 ;  // 边的个数 

        //先在main函数中 构造一个图 
        srand(time(NULL));
        SparseGraph g1(N ,false );
        for(int i = 0 ; i<M ; i++)
        {
            int a = rand() % N ;
            int b = rand() % N ;
            g1.addRdge( a, b) ;
        }

        //对每一个节点 都进行一次迭代 
        for(int v = 0 ;v < N ; v++)
        {
            cout << v << " : " ;
            //声明一个关于在g1图中 v的迭代器 
            SparseGraph :: adjItrator adj (g1 ,v );
            //不断的访问他的next() 直到迭代结束 
            for(int w  = adj.begin() ; ! adj.end() ; w= adj.next() )
            {
                cout<< w << "  " ;
            }
            cout << endl;
        }
        cout << endl;

    }
  • 稠密图的迭代器

    class adjIterator{
        private:
            DenseGraph &G;
            int v;
            int index;
        public:
            adjIterator(DenseGraph &graph, int v): G(graph){
                this->v = v;
                this->index = -1;
            }

            int begin(){

                index = -1;
                return next();
            }

            //从当前index 去找第一个为true的元素节点 
            int next(){
                for( index += 1 ; index < G.V() ; index ++ )
                    if( G.g[v][index] )
                        return index;
                return -1;
            }

            bool end(){
                //不越界 
                return index >= G.V();
            }
    };
  • 测试方法与上面类似

三.图的相关算法

1.读取文件测试用例

  • testG1.txt

    13 13
    0 5
    4 3
    0 1
    9 12
    6 4
    5 4
    0 2
    11 12
    9 10
    0 6
    7 8
    9 11
    5 3
  • 第一行是n个点 n个边
  • 剩下的都是 两个点直接有一条边
  • 我们将使用这个文件里面的数据 来进行图的构造

  • 新建一个 .h 文件


    #include <iostream>
    #include <string>
    #include <fstream>
    #include <sstream>
    #include <cassert>

    using namespace std;
  • 然后是我们写的读取类

        template <typename Graph>
        class ReadGraph{

        public:
            //构造函数 我们传入一个图 可以是稠密图 或者是稀疏图 
            //第二个参数是文件名
            ReadGraph(Graph &graph, const string &filename){

                // 用文件输入流读入文件名为filename这个文件
                ifstream file(filename.c_str());

                string line;

                int V, E;
                assert( file.is_open() );
                //读取一行 并保证读取成功 
                assert( getline(file, line) );
                //把读到的一行 放入stringstream里面 这里起个名字叫 ss
                stringstream ss(line);
                //把ss包含的值依次放入V和E中
                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 );
                }
            }
        };
  • 使用方法

    int main() {

        //载入读取文件 
        string filename = "testG1.txt";
        SparseGraph<int> g1 = SparseGraph<int>(V, false);
        //读入文件到g图中 
        ReadGraph<SparseGraph<int>, int> readGraph(g1, filename);
        g1.show();

        return 0;
    }

2.图的遍历方法

  • 广度遍历 和 深度搜索