Step1：Basic Theoretical Knowledge

有向图

无向图

连通图

完全图

连通分量

一张图有三个连通分量

Step2：Demos Of Practice

C++ 稀疏图（临接表实现）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
//
// Created by 张旭辉 on 2021/7/27.
//

#ifndef TESTDEMO_SPARSEGRAPH_H
#define TESTDEMO_SPARSEGRAPH_H

#include <vector>

using namespace std;

class SparseGraph {
private:
    int n; // 顶点个数
    int m; // 边数
    bool directed;
    // 用 邻接表 存储, 应该用链表，这里为了方便表示
    vector<vector<int>> g; //
public:
    SparseGraph(int n, bool directed) {
        this->n = n;
        this->m = 0;
        this->directed = directed;
        // 将矩阵全部初始化为 0
        g = vector<vector<int>>(n, vector<int>());
    }

    ~SparseGraph() {}

    int V() { return n; }

    int E() { return m; }

    bool hasEdge(int v1, int v2) {
        assert(v1 >= 0 && v1 < n);
        assert(v2 >= 0 && v2 < n);
//        v1 ---->v3->v5->v2->v6->v7 ... ->vn
        for (int i = 0; i < g[v1].size(); i++) {
            if (g[v1][i] == v2) {
                return true;
            }
        }
        return false;
    }

    /**
     * 两节点之间添加边
     * @param v1 节点1
     * @param v2 节点2
     */
    void addEdge(int v1, int v2) {
        if (!hasEdge(v1, v2)) {
            g[v1].push_back(v2);
        }
        // v1 !=v2 避免是闭环
        if (v1 != v2 && !directed) {
            g[v2].push_back(v1);
        }
        m++;
    }

    /**
     * 打印 graph
     */
    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;
        }
    }

    /**
     *  没有什么吊用，单纯的了解一下哈
     */
    class adjIterator {
    private:
        SparseGraph &G;
        int v;
        int index;
    public:
        adjIterator(SparseGraph &graph, int v): G(graph){
            this->v = v;
            this->index = 0;
        }
        ~adjIterator(){}
        int begin(){
            index = 0; // 防止用户多次调用index；
            if(G.g[v].size()){
                return G.g[v][index];
            }
            return -1;
        }
        int next(){
            index ++;
            if(index < G.g[v].size()){
                return G.g[v][index];
            }
            return -1;
        }
        bool end(){
            return index >= G.g[v].size();

        }

    };

};


#endif //TESTDEMO_SPARSEGRAPH_H

测试稀疏图

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
#include <iostream>
#include "SparseGraph.h"
#include "DenseGraph.h"
#include "ReadGraph.h"
using namespace std;

int main() {

    int N = 20;
    int M = 100;
    srand(time(NULL));
    // Sparse Graph
    cout << "=======================================SparseGraph=============================================="<< endl;
    SparseGraph graph(N, false);
    for(int i = 0 ; i < M ; i++){
        int a = rand()%N;
        int b = rand()%N;
        graph.addEdge(a, b);
    }

    for(int v = 0; v < N ; v++){
        cout << v << " : ";
        SparseGraph::adjIterator adj(graph, v);
        // 我觉得用 迭代器挺傻逼的，学习这种设计思想，但甄别这么做哈
        for(int w = adj.begin() ; !adj.end(); w=adj.next()){
            cout << w << " ";
        }
        cout << endl;
    }
    cout << "=========================================End============================================"<< endl;
    return 0;
}

结果

image-20210803140531702

C++ 稠密图（邻接矩阵实现）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
//
// Created by 张旭辉 on 2021/7/27.
//

#ifndef TESTDEMO_DENSEGRAPH_H
#define TESTDEMO_DENSEGRAPH_H

#include <iostream>
#include <vector>
#include <cassert>

using namespace std;

class DenseGraph {
private:
    int n; // 顶点数
    int m; // 边数
    bool directed;// 是否为有向图
    // 用邻接矩阵存贮
    vector<vector<bool>> g;

public:
    // 构造函数
    DenseGraph(int n, bool directed) {
        this->n = n; // 初始化顶点数
        this->m = 0; // 初始化变数 都为0
        this->directed = directed; // 是否为有向图
//        初始化矩阵 方法一
//        for(int i = 0 ; i < n ; i++){
//            // 初始化graph 给每个顶点都 设置为 false NxN的矩阵
//            g.push_back(vector<bool>(n, false));
//        }
//        初始化矩阵 方法二
        g = vector<vector<bool>>(n, vector<bool>(n, false));
    }

    ~DenseGraph() {} // 析构函数

    /**
     *
     * @return 获得顶点个数
     */
    int V() { return n; }

    /**
     *
     * @return 获得边数
     */
    int E() { return m; }

    /**
     * 判断顶点v 到顶点w 之间是否存在一条边
     * @param i
     * @param m
     * @return
     */
    bool hasEdge(int v, int w) {
        assert(v >= 0 && v < n);
        assert(w >= 0 && w < n);
        return g[v][w];
    }

    /**
     * 向图中添加一条边
     * @param v
     * @param w
     */
    void addEdge(int v, int w) {
        // 这里不用再 assert 因为 hasEdge 会帮你 assert
        if (!hasEdge(v, w)) {
            g[v][w] = true;
        } else {
            return;
        }
        // 如果是有向图
        if (!directed) {
            g[w][v] = true;
        }
        // 增加边数
        m++;
    }
    /**
     * 打印邻接矩阵
     */
    void show(){
        for (int i = 0; i < n; ++i) {
            for (int j = 0; j < n; ++j) {
                cout<<g[i][j]<<"\t";
            }
            cout<<endl;
        }
    }

    class adjIterator{
    private:
        DenseGraph &graph;
        int v; // 当前节点
        int index;
    public:
        adjIterator(DenseGraph &denseGraph , int v):graph(denseGraph){
            this->v = v;
            this->index = -1;
        }
        ~adjIterator(){}
        int begin(){
            index = -1; // 多次调用的情况
            return next();
        }
        int next(){
           for(index += 1 ; index < graph.V(); index ++){
               if(graph.g[v][index]){
                   return index;
               }
           }
           return -1;
        }

        bool end(){
            return index >= graph.V();
        }
    };
};


#endif //TESTDEMO_DENSEGRAPH_H

测试稠密图

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
#include <iostream>
#include "SparseGraph.h"
#include "DenseGraph.h"
#include "ReadGraph.h"
using namespace std;

int main() {

    int N = 20;
    int M = 100;
    srand(time(NULL));

    cout << "=======================================DenseGraph=============================================="<< 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;
    }
    cout << "=========================================End============================================"<< endl;

    return 0;
}

结果

image-20210803140659737

统一读取数据的头文件 ReadGraph.h

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
//
// Created by 张旭辉 on 2021/8/2.
//

#ifndef TESTDEMO_READGRAPH_H
#define TESTDEMO_READGRAPH_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){
        ifstream  file(filename);
        string line;
        int V, E;

        // 判断文件是否能打开
        assert(file.is_open());
        //获取第一行
        assert(getline(file,line));
        // 将 line 读取到的data  转变成 string 流
        stringstream ss(line);
        // ss 的 data 复制给 V，E
        ss>>V>>E;
        // V 和 graph 中的 v 是否相同 （v 是顶点的个数，初始化图的时候会初始化v，所以要做判断）
        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);
        }
    }
};

#endif //TESTDEMO_READGRAPH_H

测试读取文件 testG1.txt

testG1.txt

1
2
3
4
5
6
7
8
9
10
11
12
13
14
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

Main.cpp

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
#include <iostream>
#include "SparseGraph.h"
#include "DenseGraph.h"
#include "ReadGraph.h"
using namespace std;

int main() {
    string filename = "/Users/zhangxuhui/CLionProjects/Graph/testG1.txt";
    SparseGraph sparseGraph(13 , false);
    ReadGraph<SparseGraph> readGraph1(sparseGraph, filename);
    sparseGraph.show();
    cout<<"=========================================================================================="<<endl;

    DenseGraph denseGraph(13, false);
    ReadGraph<DenseGraph> readGraph2(denseGraph,filename);
    denseGraph.show();
    cout<<endl;
    return 0;
}

结果

image-20210803141622007

Step3: Flexible Use