图相关

###1. 图的表示

  • 邻接矩阵：这种表示方式存储了每一个顶点，因此大小为$o(n^2)$,对于那些稀疏矩阵来说很浪费空间。
  • 邻接表：存储每一个顶点和其他顶点的关系时将其顶点按升序排列，可以快速定位至某一顶点。
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
#include <vector>
#include <list>
#include <utility>
#include <iostream>


typedef std::pair<int, int> int_int_pair; //first是顶点号，second是权，默认为1。
typedef std::list<int_int_pair> vertex_list; //存储的是某个顶点的所有关系

class graph
{
public:
    graph();
    graph(int n);
    graph(int n, bool d);
    ~graph();
    void load(const char *file);
    bool is_directed() const ;
    int num_of_vertices() const ;
    std::pair<bool, int> is_edge(int u, int v) const;
    int edge_weight(int u, int v) const; //若u，v不构成边则返回0
    void add_edge(int u, int v);
    void add_edge(int u, int v, int weight);
    bool remove_edge(int u, int v);

    std::vector<int> dfs(int beg) const;

    vertex_list::const_iterator cbegin(int u) const;
    vertex_list::const_iterator cend(int u) const;
private:
    std::vector<vertex_list> vertices;
    bool directed;
    int current_size;

    void dfs(int beg, std::vector<int>& pre, std::vector<int>& state) const;
};


graph::graph() : vertices(1), directed(false), current_size(1)
{ }
graph::graph(int n) : vertices(n), directed(false), current_size(n)
{ }
graph::graph(int n, bool d) : vertices(n), directed(d), current_size(n)
{ }
graph::~graph()
{ }
void graph::load(const char *file)
{

}
bool graph::is_directed() const
{
    return directed;
}
int graph::num_of_vertices() const
{
    return current_size;
}
std::pair<bool, int> graph::is_edge(int u, int v) const
{
    for (const auto& x : vertices[u] )
    {
        if (x.first == v)
            return std::make_pair(true, x.second);
    }
    return std::make_pair(false, 0);
}
int graph::edge_weight(int u, int v) const
{
    return is_edge(u,v).second;
}
void graph::add_edge(int u, int v)
{
    if (is_edge(u, v).first)
    {
        std::cerr << "u,v已经存在边！";
        return;
    }
    vertices[u].push_back(std::make_pair(v, 1));
    if (!directed)
        vertices[v].push_back(std::make_pair(u, 1));
}
void graph::add_edge(int u, int v, int weight)
{
    if (is_edge(u, v).first)
    {
        std::cerr << "u,v已经存在边！";
        return;
    }
    vertices[u].push_back(std::make_pair(v, weight));
    if (!directed)
        vertices[v].push_back(std::make_pair(u, weight));
}
bool graph::remove_edge(int u, int v)
{
    if (!is_edge(u, v).first)
    {
        std::cerr << "u,v不构成边！";
        return false;
    }
    vertices[u].remove_if([v](int_int_pair& res){return res.first==v;});
    if (!directed)
        vertices[v].remove_if([u](int_int_pair& res){return res.first==u;});
    return true;
}
vertex_list::const_iterator graph::cbegin(int u) const
{
    return vertices[u].cbegin();
}
vertex_list::const_iterator graph::cend(int u) const
{
    return vertices[u].cend();
}

###2. 图的遍历

  • 深度优先遍历（DFS）

    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
    std::vector<int> graph::dfs(int beg) const
    {
        std::vector<int> pre(current_size, -1);
        std::vector<int> state(current_size, -1); //-1代表未被访问，0代表正在访问，1代表访问完成
        dfs(beg, pre, state);
        for (int i = 0; i < current_size; ++i)
        {
            if(state[i] == -1)
                dfs(i, pre, state);
        }
        return pre;
    }
    void graph::dfs(int beg, std::vector<int> &pre, std::vector<int>& state) const
    {
        state[beg] = 0;
        for (auto _beg = cbegin(beg);_beg != cend(beg);++_beg)
        {
            int i = _beg->first;
            if (state[i] == -1)
            {
                pre[i] = beg;
                dfs(i, pre, state);
            }
        }
        state[beg] = 1;
    }

  • 广度优先遍历（BFS）

    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
    std::vector<int> graph::bfs(int beg) const
    {
        std::vector<int> pre(current_size, -1);
        std::vector<int> state(current_size, -1); //-1代表未被访问，0代表正在访问，1代表访问完成
        bfs(beg, pre, state);
        for (int i = 0; i < current_size; ++i)
        {
            if(state[i] == -1)
                bfs(i, pre, state);
        }
        return pre;
    }

    void graph::bfs(int beg, std::vector<int> &pre, std::vector<int> &state) const
    {
        std::queue<int> q;
        q.push(beg);
        while(!q.empty())
        {
            int u = q.front();
            state[u] = 0;
            for (auto _beg = cbegin(u);_beg != cend(u);++_beg)
            {
                int i = _beg->first;
                if (state[i] == -1)
                {
                    pre[i] = u;
                    q.push(i);
                }
            }
            q.pop();
            state[u] = 1;
        }
    }