Little Data Structure

TIP

本笔记尚未修改

术语 Terminology

  • 图：对元素的限定更少，应用更强
  • G = (V; E)
  • vertex: n=|V|
  • edge: e=|E|
  • 邻接关系 adjacency：v~v 顶点与顶点的关系
  • 关联关系 incidence：v~e 顶点和边的关系
  • 无向边 undirected edge: 邻接定点 u 和 v 的次序无所谓(u,v)=(v,u)
  • 无向图 undigraph：所有的边都是无向的
  • 有向边 directed edge：(u,v)中 u 为尾，v 为头
  • 有向图 digraph
  • 混合图 mixed graph：既有有向边又有无向边
  • 无向图和混合图可以通过转换为一对对有向边用有向图来表示
  • 简单路径：不含重复节点的路径
  • 简单环路：不含其余重复节点的环路
  • 不简单路径
  • 不简单环路
  • 有向无环图 DAG:directed acyclic graph
  • 欧拉环路 eulerian tour：覆盖了所有的边的环路
  • 哈密尔顿环路 hamiltonian tour：经过所有顶点恰好一次

实现 Implementation

方法一：图模版类

template <typename Tv, typename Te>
class Graph
{
private:
    void reset() //所有顶点、边的辅助信息复位
    {
        for (int i = 0; i < n; i++) //顶点
        {
            status(i) = UNDISCOVERED;
            dTime(i) = fTime(i) = -1;
            parent(i) = -1;
            priority(i) = INT_MAX;
            for (int j = 0; j < n; j++) //边
                if (exists(i, j))
                    status(i, j) = UNDETERMINED;
        }
    }
public:
    //顶点
    int n;
    Tv &vertex(int i) = 0;
    int inDegree(int i) { return V[i].inDegree; }
    int outDegree(int i) { return V[i].outDegree; }
    VStatus &status(int i) { return V[i].status; }
    int &dTime(int i) { return V[i].dTime; }
    int &fTime(int i) { return V[i].fTime; }
    int &parent(int i) { return V[i].parent; }
    int &priority(int i) { return V[i].priority; }
    //边
    int e;
    bool exists(int, int) = 0;
    void insert(T)(Te const&, int, int, int) = 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

方法二：邻接矩阵

#include "../Vector.h"
//#include "../Graph.h"

//顶点
typedef enum
{
    UNDISCOVERED,
    DISCOVERED,
    VISITED
} VStatus;
template <typename Tv>
struct Vertex
{
    Tv data;
    int inDegree, outDegree;
    VStatus status;
    int dTime, fTime; //记录被发现和被访问完毕的时刻
    int parent;       //在遍历树中的父节点
    int priority;     //在遍历树中的优先级（最短通路、极短跨边等）
    // Constructor
    Vertex(Tv const &d) : data(d), inDegree(0), outDegree(0), status(UNDISCOVERED), dTime(-1), fTime(-1), parent(-1), priority(INT_MAX) {}
};

//边
typedef enum{ UNDETERMINED, TREE, CROSS, FORWARD, BACKWARD } EStatus;
template <typename Te>
struct Edge{
    Te data;
    int weight;
    EStatus status;
    //Constructor
    Edge(Te const &d, int w): data(d), weight(w), status(UNDETERMINED){}
    //操作接口
};

//邻接矩阵
//已对vector中[]进行重载
template <typename Tv, typename Te>
class GraphMatrix : public Graph<Tv, Te>
{
private:
    Vector<Vertex<Tv> > V;         //顶点集
    Vector<Vector<Edge<Te> *> > E; //边集
public:
    GraphMatrix() { n = e = 0; }
    ~GraphMatrix()
    {
        for (int j = 0; j < n; j++)
            for (int k = 0; k < n; k++)
                delete E[j][k];
    }

    //顶点的基本操作
    Tv &vertex(int i) { return V[i].data; }
    int inDegree(int i) { return V[i].inDegree; }
    int outDegree(int i) { return V[i].outDegree; }
    VStatus &status(int i) { return V[i].status; }
    int &dTime(int i) { return V[i].dTime; }
    int &fTime(int i) { return V[i].fTime; }
    int &parent(int i) { return V[i].parent; }
    int &priority(int i) { return V[i].priority; }
    int nextNbr(int i, int j)
    {
        while ((j > -1) && (!exists(i, --j)))
            ;
        return j;
    }

    int firstNbr(int i, int n)
    {
        return nextNbr(i, n);
    }


    //顶点的动态操作
    int insert(Tv const &vertex)
    {
        for (int i = 0; i < n; i++)
        {
            E[i].insert(NULL);
        }
        n++;
        E.insert(Vector<Edge<Te> *>(n, n, NULL));
        return V.insert(Vertex<Tv>(vertex));
    }

    Tv remove(int i)
    {
        for (int j = 0; j < n; j++)
        {
            if (exists(i, j))
            {
                delete E[i][j];
                V[j].inDegree--; //j的入度减一
            }
        }
        E.remove(i);
        n--;
        for (int j = 0; j < n; j++)
        {
            if (exists(j, i))
            {
                delete E[j].remove(i);
                V[j].outDegree--;
            }
        }
        Tv v = vertex(i); //备份顶点i的信息
        V.remove(i);
        return v;
    }

    //边的确认操作
    bool exists(int i, int j)
    {
        return (i >= 0) && (i < n) && (j >= 0) && (j < n) && E[i][j] != NULL;
    }

    //边的基本操作

    //边的动态操作
};
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

算法 Algorithm

找邻居

virtual int
1
  • 图的广度优先遍历等价于树的层次遍历，后者是前者的特例，前者是后者的推广。
  • 该搜索规则下形成了一棵支撑树，也是无环图。
  • 支撑树 Spanning Tree：树中涵盖了所有的顶点。
//全图
template <typename Tv, typename Te>
void Graph<Tv, Te>::bfs(int s)
{
    reset();
    int clock = 0;
    int v = s;
    do
    {
        if (status(v) == UNDISCOVERED)
            BFS(v, clock);
    } while (s != (v = (++v % n)));
}

//单连通域
template <typename Tv, typename Te>
void Graph<Tv, Te>::BFS(int v, int &clock)
{
    Queue<int> Q;
    status(v) = DISCOVERED;
    Q.enqueue(v);
    while (!Q.empty())
    {
        int v = Q.dequeue();
        dTime(v) = ++clock;
        for (int u = firstNbr(v); u > -1; u = nextNbr(v, u))
        {
            if (status(u) == UNDISCOVERED)
            {
                status(u) = DISCOVERED;
                Q.enqueue(u);
                status(v, u) = TREE;
                parent(u) = v;
            }
            else
                status(v, u) = CROSS;
        }
        status(v) = VISITED;
    }
}
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
  • backward/forward 是根据遍历的顺序判断的
  • cross 是指没有直系血缘关系的节点的连边
  • 两个点的 dTime 和 fTime 可用来判断是否存在血缘关系.祖先的时间包含后代的。无血缘关系的时间无交集。

有向图算法实现

//全图
template <typename Tv, typename Te>
void Graph<Tv, Te>::dfs(int s)
{
    reset();
    int clock = 0;
    int v = s;
    do
    {
        if (status(v) == UNDISCOVERED)
            DFS(v, clock);
    } while (s != (v = (++v % n)));
}

//单个连通域
template <typename Tv, typename Te>
void Graph<Tv, Te>::DFS(int v, int &clock)
{
    dTime(v) = ++clock;
    status(v) = DISCOVERED;
    for (int u = firstNbr(r); u > -1; u = nextNbr(v, u))
    {
        switch (status(u))
        {
        case UNDISCOVERED:
            status(v, u) = TREE;
            parent(u) = v;
            DFS(u, clock);
            break;
        case DISCOVERED:
            status(v, u) = BACKWARD;
            break;
        default: //VISITED, 有向图
            status(v, u) = dTime(v) < dTime(u) ? FORWARD : CROSS;
            break;
        }
    }
    status(v) = VISITED;
    fTime(v) = ++clock;
}
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
Last Updated: 2021/11/22 03:17:18
Contributors: oddnaveed