algorithmgraph
algorithm, c, graph
Source
Edit
History

稀疏图-邻接表

Catalogue

无向图,邻接表的空间结构:

  1. 邻接表主要由数组 + 链表的方式实现
  2. 如图表的第一列为数组的索引，代表所有的顶点,0,1,2,3,4
  3. 如图表的每一行都对应了第列的所有相连接的点
  4. 行的关系是采用链表或者队列的方式实现

总的结构就是一个非常简单的数组+链表方式组成,当前demo是vector<vector<*>>方式实现，方便理解

实现解析:

  1. 用Edge来表示每条边，a代表左顶点,b代表右顶点,v代表边的权值（比如边的长度）

  2. SparseGraph的主要数据结构

    1
    2
    3
    4
    bool directed;//表示是否是有方向，如果为fasle表示无向，在添加边的时候需要两端都条件一条
    vector<vector<Edge*>> g;//存储所有的顶点关系，一维数组表示所有顶点，二维数组表示所有和顶点关联的其他顶点
    int points//顶点个数
    int edges;//边的个数

  3. 添加一条边

    1
    2
    3
    4
    5
    6
    7
    8
    9
    非常简单，直接push到 g[v]队列里就可以了，表示w是属于g[v]所有可以连接的边的其中一个
    void addEdge(int v,int w,int weight){
        assert(v < points);
        g[v].push_back(new Edge(v,w,weight));
        //无向图需要 反向自动添加另外一条边
        if(!directed)
            g[w].push_back(new Edge(w,v,weight));
        edges ++;
    }

  4. 查询某条边是否存在O(E)E为边数

    1
    2
    3
    4
    5
    6
    7
    8
    9
    因为该图的边对应关系是一个链表或者队列来存储的，所有需要有个遍历的步骤
    bool isEdge(int v,int w){
        for(auto i : g[v]){
            if(i->b == w){
                return true;
            }
        }
        return false;
    }

  5. 打印图

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    void print(){
        //双向遍历即可
        for(int i  = 0; i < points ; i ++ ){
            cout << i << ": ";
            for(auto i : g[i]){
                cout << i->b << " ";
            }
            cout << endl;
        }
    }

完整代码

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
struct Edge{
public:
    int a;
    int b;
    int v;
    Edge(int a,int b,int v):a(a),b(b),v(v){}
    ~Edge(){}
};

class SparseGraph{
public:
    //是否是有向图
    bool directed;
    //设置二维矩阵 表示图关系
    vector<vector<Edge*>> g;
    //设置顶点个数
    int points;
    //边的个数
    int edges;
    SparseGraph(int points,bool directed):points(points),directed(directed){
        //初始化一个邻接表
        g = vector<vector<Edge*>>(points,vector<Edge*>());
    }
    void addEdge(int v,int w,int weight){
        assert(v < points);
        g[v].push_back(new Edge(v,w,weight));
        //无向图需要 反向自动添加另外一条边
        if(!directed)
            g[w].push_back(new Edge(w,v,weight));
        edges ++;
    }
    void print(){
        //双向遍历即可
        for(int i  = 0; i < points ; i ++ ){
            cout << i << ": ";
            for(auto i : g[i]){
                cout << i->b << " ";
            }
            cout << endl;
        }
    }

};