0.x 14.图论基础-表示和遍历（无权图）

dddd数据结构课本

• Author：李英民 | Henry
• E-mail: li_yingmin@outlookdotcom
• $Beijing~~U~of~Posts~and~Telecom$$(BUPT~)$
• Home: https://liyingmin.wixsite.com/henry

• 快速了解我: About Me

• 转载请保留上述引用内容，谢谢配合！

1.邻接表和邻接矩阵

邻接矩阵

#include <iostream>
#include <vector>
#include <cassert>
using namespace std;
// 稠密图 - 邻接矩阵
class DenseGraph{
private:
    int n, m;       // 节点数和边数
    bool directed;  // 是否为有向图
    vector<vector<bool>> g; // 图的具体数据
public:
    // 构造函数
    DenseGraph( int n , bool directed )
    : g(n, vector<bool>(n, false)),n(n),m(0),directed(directed){}
    ~DenseGraph(){}
    int V(){ return n;} // 返回节点个数
    int E(){ return m;} // 返回边的个数
    // 向图中添加一个边
    void addEdge( int v , int w ){
        assert( v >= 0 && v < n );
        assert( w >= 0 && w < n );
        if(v != w)//自环边避免
        {
            if( hasEdge( v , w ) )
                return; //去除平行边
            g[v][w] = true;
            if( !directed )
                g[w][v] = true;
            ++m;//无向图中有连接的边只算一条
        }
    }
    // 验证图中是否有从v到w的边
    bool hasEdge( int v , int w ){ //O(1)来判断是否有连接
        return g[v][w];
    }
};

邻接表

#include <iostream>
#include <vector>
#include <cassert>
using namespace std;
// 稀疏图 - 邻接表
class SparseGraph{
private:
    int n, m;       // 节点数和边数
    bool directed;  // 是否为有向图
    vector<vector<int>> g;  // 图的具体数据
public:
    // 构造函数
    SparseGraph( int n , bool directed )
    : n(n),m(0),directed(directed),g(n, 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 );
        if(v != w)
        {
            g[v].push_back(w);
            if(!directed )
                g[w].push_back(v);
            ++m;
        }
    }
    // 验证图中是否有从v到w的边
    bool hasEdge( int v , int w ){  //O(n)的复杂度，因此一般不判断平行边
        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;
    }
};

2.打印一张图

邻接表

#include <iostream>
#include <vector>
#include <cassert>
using namespace std;
// 稀疏图 - 邻接表
class SparseGraph{
private:
    int n, m;       // 节点数和边数
    bool directed;  // 是否为有向图
    vector<vector<int>> g;  // 图的具体数据
public:
    // 构造函数
    SparseGraph( int n , bool directed )
    : n(n),m(0),directed(directed),g(n, 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 );
        if(v != w)
        {
            g[v].push_back(w);
            if(!directed )
                g[w].push_back(v);
            ++m;
        }
    }
    // 验证图中是否有从v到w的边
    bool hasEdge( int v , int w ){  //O(n)的复杂度，因此一般不判断平行边
        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),v(v),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();
        }
    };
};

//main.cpp
#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;
}

邻接矩阵

// 邻边迭代器, 传入一个图和一个顶点,
    // 迭代在这个图中和这个顶点向连的所有顶点
    class adjIterator{
    private:
        DenseGraph &G;  // 图G的引用
        int v;
        int index;
    public:
        // 构造函数
        adjIterator(DenseGraph &graph, int v): G(graph),v(v),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();
        }
    };

//main.cpp
#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;
}

3.读取文件建立图，打印矩阵和邻接表

#include <iostream>
#include <string>
#include <fstream>
#include <sstream>
#include <cassert>
using namespace std;
// 读取图算法
template <typename Graph> //表示SparseGraph或者DenseGraph
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() ); //建立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 );
        }
    }
};

//打印DenseGraph
    void show(){
        for( int i = 0 ; i < n ; i ++ ){
            for( int j = 0 ; j < n ; j ++ )
                cout<<g[i][j]<<"\t";
            cout<<endl;
        }
    }

//打印SparseGraph
    // 显示图的信息
    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;
        }
    }

//main.cpp
#include <iostream>
#include "SparseGraph.h"
#include "DenseGraph.h"
#include "ReadGraph.h"
using namespace std;
// 测试通过文件读取图的信息
int main() {
    // 使用两种图的存储方式读取testG1.txt文件
    string filename = "testG1.txt";
    SparseGraph g1( 13 , false );
    ReadGraph<SparseGraph> readGraph1( g1 , filename );
    cout<<"test G1 in Sparse Graph:" << endl;
    g1.show();
    cout<<endl;
    DenseGraph g2( 13 , false );
    ReadGraph<DenseGraph> readGraph2( g2 , filename );
    cout<<"test G1 in Dense Graph:" << endl;
    g2.show();
    cout<<endl;
    // 使用两种图的存储方式读取testG2.txt文件
    filename = "testG2.txt";
    SparseGraph g3( 6 , false );
    ReadGraph<SparseGraph> readGraph3( g3 , filename );
    cout<<"test G2 in Sparse Graph:" << endl;
    g3.show();
    cout<<endl;
    DenseGraph g4( 6 , false );
    ReadGraph<DenseGraph> readGraph4( g4 , filename );
    cout<<"test G2 in Dense Graph:" << endl;
    g4.show();
    return 0;
}

4.图的深度优先遍历与连通分量个数+判断顶点的连通性

#include <iostream>
#include <cassert>
using namespace std;
// 求无权图的联通分量
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);//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];
    }
};
#include <iostream>
#include "SparseGraph.h"
#include "DenseGraph.h"
#include "ReadGraph.h"
#include "Components.h"
using namespace std;
// 测试图的联通分量算法
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;
}

5.深度优先遍历与寻路

#include <vector>
#include <stack>
#include <iostream>
#include <cassert>
using namespace std;
// 路径查询
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
#include <iostream>
#include "SparseGraph.h"
#include "DenseGraph.h"
#include "ReadGraph.h"
#include "Path.h"
using namespace std;
// 测试寻路算法
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;
}

6.广度优先遍历与最短路径

// 寻找无权图的最短路径
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
#include <iostream>
#include "SparseGraph.h"
#include "DenseGraph.h"
#include "ReadGraph.h"
#include "Path.h"
#include "ShortestPath.h"
using namespace std;
// 测试无权图最短路径算法
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;
}