图的表达

前言

图的表达有两种方式实现，一种是利用邻接矩阵，一种是利用邻接表。
1. 利用邻接矩阵：利用一个二维数组来储存图结点的数据，数组的下标对应结点的编号，值代表结点之间的权值；
2. 利用邻接表：实际上是利用一维数组和链表来实现的，链表用来存储某个结点到其他结点的路径，链表的第一个元素为到本结点的路径，数组用来储存各个链表；

比较

我们将图的结点个数设为V，图的路径个数设为E。
用第一种方式实现，它的空间复杂度为O(V2)；
用第二种方式实现，它的空间复杂度为O(V*E)。
所以当图里面的路径比较稀疏用第二种方式实现，如果比较密集，则两种都可以。

代码实现

利用邻接矩阵实现

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

#include <iostream>
#include <stdio.h>
#include <vector>
using namespace std;

class Graphic {
private:
    std::vector<std::vector<int>> g;

public:
    Graphic(std::vector<std::vector<int>> &g):g(g){

    }
};

int main(int argc, const char * argv[]) {
    vector<vector<int>> g ={
      {0,0,1,1},
      {0,0,1,1},
      {0,1,0,0},
      {0,1,1,0}
    };

    Graphic gr(g);
    return 0;
}

利用邻接表实现

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

#include <stdio.h>
#include <vector>
#include <list>
#include <iostream>

/**
 * 图路径
 * dest_id 目的结点的ID
 * weight 路径权值
 **/
struct edge_node {
    int dest_id;
    int weight;

    edge_node(int id,int weight)
    :dest_id(id),weight(weight){

    }

};

class Graph {

    std::vector<std::list<edge_node>> ad_vector;

public:
    Graph(int n)
    :ad_vector(n){

    }

    /**
     * 添加图路径
     **/
    void add_edge(int source,int dist,int weight){
        edge_node new_eage(dist,weight);
        ad_vector[source].push_back(new_eage);
    }

    /**
    * 打印所有路径
    **/
    void dump(){
        for (int i=0; i<ad_vector.size(); i++) {
            for (auto pos = ad_vector[i].begin(); pos!=ad_vector[i].end(); pos++) {
                std::cout<<"edge from "<<i<<" to "<<pos->dest_id;
                std::cout<<" weight: "<<pos->weight<<std::endl;
            }
        }
    }
};

int main(int argc, const char * argv[]) {
    Graph g(4);
    g.add_edge(0, 1, 1);
    g.add_edge(0, 3, 1);
    g.add_edge(1, 2, 1);
    g.add_edge(1, 3, 1);
    g.add_edge(3, 2, 1);
    g.dump();
    return 0;
}

Comments