数据结构 八 图

无向图

无向图的邻接矩阵实现

接口声明

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
//无向图 邻接矩阵

#ifndef _GRAPH_H_
#define _GRAPH_H_

#include <iostream>
#include <time.h>
#include <stdlib.h>
#include <memory.h>
#include <stack>
#include <deque>

#define VERTEX_MAX 100

typedef struct _VERTEX
{
    int key;
} * Vertex;

typedef struct _GRAPH
{
    //顶点集合
    //顶点数量
    //边的数量
    //边的集合 使用邻接矩阵或者邻接表进行表示
    Vertex vertex[VERTEX_MAX];
    int vertex_num;
    int edge_num;
    int matrix[VERTEX_MAX][VERTEX_MAX];
} * Graph;

//图不可以是一个空图
//初始化一个图
Graph init(int vertex_num);
//自动随机填充图 vertex_num 个顶点
Graph random_fill_graph(Graph graph, int vertex_num);

//图的遍历
//深度优先搜索 DFS
void DFS(Graph graph);
void DFS_Vertex(Graph graph, int v_seq, int is_sacn[VERTEX_MAX]);
//广度优先搜索
void BFS(Graph graph);

#endif

接口定义

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
127
128
#include "graph.h"

//图不可以是一个空图
//初始化一个图
Graph init(int vertex_num)
{
    Graph graph = (Graph)malloc(sizeof(struct _GRAPH));
    graph->edge_num = 0;
    graph->vertex_num = 0;
    memset(graph->matrix, 0, sizeof(graph->matrix));
    graph = random_fill_graph(graph, vertex_num);
    return graph;
}
Graph random_fill_graph(Graph graph, int vertex_num)
{
    srand(time(NULL));
    int totle_vertex_num = vertex_num + graph->vertex_num;
    for (int i = 1; i <= vertex_num; i++)
    {
        int key = rand() % VERTEX_MAX;
        Vertex v = (Vertex)malloc(sizeof(struct _VERTEX));
        if (!v)
            exit(EXIT_FAILURE);
        v->key = key;
        graph->vertex[graph->vertex_num] = v;
        int source = graph->vertex_num++;
        int degree = 0;
        if (totle_vertex_num > 1)
            degree = rand() % (totle_vertex_num - 1) + 1;
        for (int j = 1; j <= degree; j++)
        {
            int destination = rand() % (totle_vertex_num - 1);
            if (destination != source)
            {
                if (graph->matrix[source][destination] == 0)
                {
                    graph->matrix[source][destination] = 1;
                    graph->matrix[destination][source] = 1;
                    graph->edge_num++;
                }
            }
        }
    }
    return graph;
}
//图的遍历
//深度优先搜索 DFS 递归
void DFS(Graph graph)
{
    printf("DFS\n");
    //任意找一个顶点开始进行递归深度搜索。
    int is_sacn[VERTEX_MAX];
    memset(is_sacn, 0, sizeof(is_sacn));
    DFS_Vertex(graph, 0, is_sacn);
    printf("\n");
}
void DFS_Vertex(Graph graph, int v_seq, int is_sacn[VERTEX_MAX])
{
    //如果没有被扫描过则输出
    //扫描其所有相连的 访问一个没有被访问过的 若所有与之相连接的结点都被访问过 则返回
    if (!is_sacn[v_seq])
    {
        is_sacn[v_seq] = 1;
        printf("%d ", graph->vertex[v_seq]->key);
    }
    for (int i = 0; i <= graph->vertex_num - 1; i++)
    {
        if (graph->matrix[v_seq][i] == 1 && !is_sacn[i])
        {
            DFS_Vertex(graph, i, is_sacn);
        }
    }
}
//非递归遍历
void DFS_none_recursive(Graph graph)
{
    printf("DFS_none_recursive\n");
    //将遇到的每一个未访问过的结点放入栈中 依次弹出访问 直到栈空
    int is_scan[VERTEX_MAX];
    memset(is_scan, 0, sizeof(is_scan));
    std::stack<int> s;
    s.push(0);
    while (!s.empty())
    {
        int seq = s.top();
        s.pop();
        //访问这个结点 可能有多个结点与该节点相连则该节点就入栈多次 但是访问一次即可
        if (!is_scan[seq])
            printf("%d ", graph->vertex[seq]->key);
        else
            continue;
        is_scan[seq] = 1;
        //将这个结点所连接的节点中未访问过的结点push
        for (int i = 0; i <= graph->vertex_num - 1; i++)
        {
            if (graph->matrix[seq][i] == 1 && !is_scan[i])
                s.push(i);
        }
    }
    printf("\n");
}
//广度优先搜索
void BFS(Graph graph)
{
    printf("BFS\n");
    //层次搜索 和树一样
    std::deque<int> q;
    int is_scan[VERTEX_MAX];
    memset(is_scan, 0, sizeof(is_scan));
    q.push_back(0);
    while (!q.empty())
    {
        int seq = q.front();
        q.pop_front();
        if (!is_scan[seq])
            printf("%d ", graph->vertex[seq]->key);
        else
            continue;
        is_scan[seq] = 1;
        //将下一层入队
        for (int i = 0; i <= graph->vertex_num - 1; i++)
        {
            if (graph->matrix[seq][i] == 1 && !is_scan[i])
                q.push_back(i);
        }
    }
    printf("\n");
}

接口使用

1
2
3
4
5
6
7
8
9
10
#include "graph.cpp"

int main()
{
    Graph graph = init(10);
    DFS(graph);
    DFS_none_recursive(graph);
    BFS(graph);
    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
//无向图 邻接表

#ifndef _GRAPH_H_
#define _GRAPH_H_

#include <iostream>
#include <time.h>
#include <stdlib.h>
#include <memory.h>
#include <stack>
#include <deque>

#define VERTEX_MAX 100

typedef struct _ENODE
{
    int seq;
    struct _ENODE *next;
} * Enode;

typedef struct _VERTEX
{
    int key;          //顶点数据
    Enode first_edge; //该顶点的第一个弧
} * Vertex;

typedef struct _GRAPH
{
    //邻接表 图中存放顶点 每一个顶点有一个链表将自己相连的顶点存储到链表中
    //顶点数目
    //边的数目
    //顶点
    int vertex_num;
    int edge_num;
    Vertex vertex[VERTEX_MAX];
} * Graph;

//图不可以是一个空图
//初始化一个图
Graph init(int vertex_num);
//自动随机填充图 vertex_num 个顶点
Graph random_fill_graph(Graph graph, int vertex_num);
void append_table(Graph graph, int source, int insert);
//图的遍历
//深度优先搜索 DFS
void DFS(Graph graph);
void DFS_Vertex(Graph graph, int v_seq, int is_scan[VERTEX_MAX]);
//广度优先搜索
void BFS(Graph graph);
void BFS_Vertex(Graph graph, int v_seq, int is_scan[VERTEX_MAX]);
#endif

接口定义

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
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
#include "graph.h"

//图不可以是一个空图
//初始化一个图
Graph init(int vertex_num)
{
    Graph graph = (Graph)malloc(sizeof(struct _GRAPH));
    graph->edge_num = 0;
    graph->vertex_num = 0;
    memset(graph->vertex, 0, sizeof(graph->vertex));
    graph = random_fill_graph(graph, vertex_num);
    return graph;
}
Graph random_fill_graph(Graph graph, int vertex_num)
{
    srand(time(NULL));
    //int totle_vertex_num = vertex_num + graph->vertex_num;
    //随机产生一个顶点 随机产生一个度 随机产生每一个度连接的顶点 更新顶点的邻接表
    for (int i = 1; i <= vertex_num; i++)
    {
        int source = graph->vertex_num++;
        graph->vertex[source] = (Vertex)malloc(sizeof(struct _VERTEX));
        graph->vertex[source]->first_edge = NULL;
        int destination = 0;
        int key = rand() % VERTEX_MAX;
        graph->vertex[source]->key = key;
        int degree = 0;
        if (source != 0)
            degree = rand() % (source) + 1; //1 - source-1
        else
            continue;
        for (int i = 1; i <= degree; i++)
        {
            destination = rand() % (source);
            //更新source的邻接表
            append_table(graph, source, destination);
            //更新destination的邻接表
            append_table(graph, destination, source);
        }
    }
    return graph;
}
void append_table(Graph graph, int source, int insert)
{
    //将 source 的邻接表插入一位 insert
    Enode p = graph->vertex[source]->first_edge;
    if (!p)
    {
        Enode e = (Enode)malloc(sizeof(struct _ENODE));
        e->next = NULL;
        e->seq = insert;
        graph->vertex[source]->first_edge = e;
        return;
    }
    //p不空，append
    if (p->seq == insert)
        return;
    while (p->next)
    {
        p = p->next;
        //邻接表中已经存在 insert 了，不需要存入
        if (p->seq == insert)
            return;
    }
    Enode e = (Enode)malloc(sizeof(struct _ENODE));
    e->next = NULL;
    e->seq = insert;
    p->next = e;
    return;
}
//图的遍历
//深度优先搜索 DFS 递归
void DFS(Graph graph)
{
    printf("DFS\n");
    //从0开始遍历邻接表
    int is_scan[VERTEX_MAX];
    memset(is_scan, 0, sizeof(is_scan));
    DFS_Vertex(graph, 0, is_scan);
    printf("\n");
}
void DFS_Vertex(Graph graph, int v_seq, int is_scan[VERTEX_MAX])
{
    //如果没有被扫描过则输出
    //扫描其所有相连的 访问一个没有被访问过的 若所有与之相连接的结点都被访问过 则返回
    if (!is_scan[v_seq])
        printf("%d ", graph->vertex[v_seq]->key);
    is_scan[v_seq] = 1;
    Enode p = graph->vertex[v_seq]->first_edge;
    while (p)
    {
        //遍历邻接表
        if (!is_scan[p->seq])
            DFS_Vertex(graph, p->seq, is_scan);
        p = p->next;
    }
}
//非递归遍历
void DFS_none_recursive(Graph graph)
{
    printf("DFS_none_recursive\n");
    //将遇到的每一个未访问过的结点放入栈中 依次弹出访问 直到栈空
    int is_scan[VERTEX_MAX];
    memset(is_scan, 0, sizeof(is_scan));
    std::stack<int> s;
    s.push(0);
    while (!s.empty())
    {
        int seq = s.top();
        s.pop();
        if (!is_scan[seq])
        {
            is_scan[seq] = 1;
            printf("%d ", graph->vertex[seq]->key);
        }
        //将临界表内元素全部push
        Enode p = graph->vertex[seq]->first_edge;
        while (p)
        {
            if (!is_scan[p->seq])
                s.push(p->seq);
            p = p->next;
        }
    }
    printf("\n");
}

//广度优先搜索 递归
void BFS(Graph graph)
{
    printf("BFS\n");
    int is_scan[VERTEX_MAX];
    memset(is_scan, 0, sizeof(is_scan));
    std::deque<int> q;
    q.push_back(0);
    while (!q.empty())
    {
        int seq = q.front();
        q.pop_front();
        if (!is_scan[seq])
            printf("%d ", graph->vertex[seq]->key);
        is_scan[seq] = 1;
        Enode p = graph->vertex[seq]->first_edge;
        while (p)
        {
            if (!is_scan[p->seq])
                q.push_back(p->seq);
            p = p->next;
        }
    }
    printf("\n");
}

接口使用

1
2
3
4
5
6
7
8
9
10
#include "graph.cpp"

int main()
{
    Graph graph = init(20);
    DFS(graph);
    DFS_none_recursive(graph);
    BFS(graph);
    return 0;
}

图的相关算法

拓扑排序

AOV网

若使用DAG图（有向无环图）表示一个工程（施工的先后顺序，项目依赖），顶点表示活动，使用有向边<a,b>表示活动a先于活动b。这种网称为AOV网，其中a是b的后继，b是a的前驱。

拓扑排序

在图论中，由一个DAG图的顶点组成的序列，当满足如下条件的时候，称为该图的一个拓扑排序。

  1. 每一个顶点只出现一次。
  2. 若在序列中A在B的前面，则图中不存在从B到A的路径。

拓扑排序的步骤

1.在AOV网中选择一个没有前驱的结点，输出并删掉相关的边。
2.重复直到网空或者不存在没有前驱的结点。

逆拓扑排序

顾名思义即将拓扑排序逆着来。

选择一个只有前驱没有后继的结点，输出并删除其入度的边，重复直到完成。

最小生成树

  • 一个连通图的生成树包含图中的所有顶点，并且只包含尽可能少的边。对于生成树来说，若砍去一条边则生成树不连通，若加上一条边则会形成回路。
  • 对于一个带权的图来讲，最小生成树即为所有生成树中路径权值的和最小的那一颗。
  1. 最小生成树不唯一
  2. 最小生成树的权值和唯一

prim算法

树中顶点集合TD，图中顶点集合GD，图中边的集合GE，树中边的集合TE。

初始树的集合为空，从图中任取一个顶点加入树的顶点集。从该顶点集所连的所有边中选择满足以下条件的边。

  1. 该边未被加入树中
  2. 将该边加入树不会造成回路。
  3. 该边的权值为所有可选边中最小的

将该边及其对应的顶点加入树中，重复直至所有顶点都已经加入到了树中。

kruskal算法

树中顶点集合TD，图中顶点集合GD，图中边的集合GE，树中边的集合TE。

prim算法是选择顶点，kruskal算法是选择边。

依次将权值最小的边及其两端顶点加入树中。该边也要满足以下条件

  1. 该边未被加入树中
  2. 将该边加入树不会造成回路。
  3. 该边的权值为所有可选边中最小的

最短路径

最短路径是两个点之间所经权值最下的一条路径。当图中所有路径的权值一样的时候可以使用广度优先搜索。当带权图的权值不一样的时候使用以下两种算法。

最短路径算法依赖于这条性质：

两点之间的最短路径包含了路径上其他顶点的最短路径。

dijkstra 算法

单源点最短路径

迪杰斯特拉算法思想

每一个顶点都知道自己到源点的最短路径，不直接和源点相连的顶点距离设为无穷远，直接相连的设为弧的权值。每一次选择一个新的结点，该结点要满足是所有可选择的新结点中距源点最近的一条。求出其路径长度。现在相当于多了一个知道自己最短路径长度的顶点，其他顶点根据自己的信息改变自己的最短长度。

算法说明

假设要求结点距离结点0的最短路径。源结点为结点0。顶点集合为v

  1. 设置一个数组dist存储每一个结点到源结点的最短路径值。
    1. 源节点到自身的路径长度设为0。
    2. 若不相连则设为正无穷。
  2. 设置一个path数组存储每一个结点到源节点的最短路径上的前驱。
  3. 设置一个集合s存储当前已经确定的最短路径的结点，初始元素为源节点本身。v=v-s，为方便计算路径，初始v不用减去源点。
  4. 从集合v中选取一个结点j加入s（第一次选取的结点肯定为源点本身），要求满足：
    1. dist[j]=min{dist[i]},其中i为v中所有顶点。
  5. v=v-s
  6. 对于v中的顶点以j为依据更新最短路径长度。
    1. dist[i] = dist[i] < dist[j] + arcs[i][j]?dist[i]:dist[j] + arcs[i][j];
    2. 即能不能根据j寻一条更短的道儿。
    3. 将path[i]=j, 即顶点i的最短路径的前驱经过j.
  7. 重复直到v空。

floyd 算法

顶点对最短路径

弗洛伊德算法思想

弗洛伊德算法要求出每对顶点的最短距离，依次选取每一个顶点作为中转结点，以此来更新dist[][]

算法说明

  1. 设置一个方阵存储每一对顶点的最短距离dist[][]，初始化为：
    1. 若两个顶点之间有弧则为弧长
    2. 没有弧为正无穷。
    3. 自己到自己的距离为0.
  2. 依次选取每一个顶点k作为中转结点
    1. 遍历所有顶点对更新最短距离。设当前顶点对为 <i,j>
      1. dist[i][j]= dist[i][j] < dist[i][k] + dist[k][j] ? dist[i][j] : dist[i][k] + dist[k][j];

关键路径

AOE网

在带权有向图中，以顶点代表事件，以有向边代表活动，以边上的权值代表活动的开销。称之为右边表示活动的网络，简称AOE网。

  1. 只有在入度弧代表的活动全部完成之后才可以顶点代表的时间。
  2. 只有顶点代表的事件发生之后才可以开始出度弧代表的活动。

事件的最早发生时间ve(k)
从源点到顶点k的最长路径长度。

ve(源点)=0

ve(k)=max(ve(i)+weight(i,k)); i为k的前驱

事件的最迟发生时间vl(k)

vl(汇点)=ve(汇点)

vl(k)=min(vl(j) - weight(k,j)); k为j的前驱

活动ai最早发生时间e(i)

e(i)=ve(k) (边<k,j>代表活动ai)

活动ai最迟发生时间l(i)

l(i)=vl(j)-weight(k,j) (边<k,j>代表活动ai)

活动ai可拖延时间d(i)
d(i)=l(i)=d(i)