图基础

, ,
图论算法在计算机科学中扮演着很重要的角色，它提供了对很多问题都有效的一种简单而系统的建模方式

概念

图由顶点(vertex, node)和边(edge)组成。顶点代表对象。我们可以给边赋予各种各样的属性，如权值(cost)。
图大体分为两种

1. 无向图

两个顶点间有连接，视为相邻。相邻顶点的序列称为路径。起点和终点重合的路径叫圈。任意两点间都有路径连接的图叫连通图。顶点连接的边数叫做这个顶点的度。没有圈的连通图就是树(tree)。
#####2. 有向图
入度，出度，没有圈的有向图叫DAG(Directed Acyclic Graph)。
对于每一个顶点给一个编号，第i号顶点叫做ViV_i。那么存在从顶点ViV_i到顶点VjV_j的边时就有i<ji<j成立，这样的编号方式叫做拓扑序。

拓扑序

看看就好

从 DAG 图中选择一个 没有前驱（即入度为0）的顶点并输出。
从图中删除该顶点和所有以它为起点的有向边。
重复 1 和 2 直到当前的 DAG 图为空或当前图中不存在无前驱的顶点为止。若当前图中不存在无前驱的顶点说明有向图中必存在环。

图的表示

稠密图用 邻接矩阵存储

稀疏图用 邻接表存储

邻接矩阵

邻接矩阵虽然好写，但是由于需要开一个二维数组，如果顶点数过大(一般不能超过1000)的题目便会超内存

代码实现：

  • 复杂版本：
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
/*************************************************************************
 > FileName:
 > Author:      HuangChangsheng
 > Mail:        lancelot_hcs@qq.com
 > Date:        9102.1.8
 > Description: Realization of Graph
 ************************************************************************/
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <queue>
#include <stack>
#include <vector>
#include <map>
#include <cstdlib>
#include <set>
#include <bitset>
#include <string>
#include <cmath>
#include <sstream>
using namespace std;
typedef long long ll;
const double pi = acos(-1.0);
const int eps = 1e-10;
const int mod = 1e9 + 7;
const int INF = 0x3f3f3f3f;                             //int2147483647 ll9e18 unsigned ll 1e19
const int maxn = 1005;
int a[maxn];

const int MaxVertexNum = maxn;
typedef int WeightType;
typedef int Vertex;//顶点
typedef struct GNode *MGraph;
struct GNode
{
    int Nv;//顶点数
    int Ne;//边数
    WeightType G[MaxVertexNum][MaxVertexNum];
};



MGraph CreateGraph(int VertexNum)
{
    Vertex V, W;
    MGraph Graph;

    Graph = (MGraph)malloc(sizeof(struct GNode));
    Graph->Nv = VertexNum;
    Graph->Ne = 0;
    for (V = 0; V < Graph->Nv; V++)
        for (W = 0; W < Graph->Nv; W++)
            Graph->G[V][W] = 0;
    return Graph;
}

typedef struct ENode *Edge;
struct ENode
{
    Vertex V1, V2;    //有向边<V1, V2>
    WeightType Weight;//权重
};

void InsertEdge(MGraph Graph, Edge E)
{
    Graph->G[E->V1][E->V2] = E->Weight;//插入边<V1, V2>
    Graph->G[E->V2][E->V1] = E->Weight;//无向图还要<V2, V1>
//    cout << E->V1 << E->V2;
}

/*
input case:
Nv Ne
V1 V2 Weight
*/

void PrintGraph(MGraph Graph)
{
    puts("");
    for (int i = 1; i <= Graph->Nv; i++)
    {
        for (int j = 1; j <= Graph->Nv; j++)
        {
            j == Graph->Nv ? printf("%d\n", Graph->G[i][j]) : printf("%d ", Graph->G[i][j]);
        }
    }
}

MGraph BuildGraph()
{
    MGraph Graph;
    Edge E;
    Vertex V;
    int Nv, i;

    scanf("%d", &Nv);
    Graph = CreateGraph(Nv);
    scanf("%d", &(Graph->Ne));
    if (Graph->Ne != 0)
    {
        E = (Edge)malloc(sizeof(struct ENode));
        for (i = 0; i < Graph->Ne; i++)
        {
            scanf("%d%d%d", &E->V1, &E->V2, &E->Weight);
            InsertEdge(Graph, E);
        }
        PrintGraph(Graph);
        //      for (V = 0; V < Graph->Nv; V++)//如果顶点有数据
        //           scanf("%d" , &(Graph->Data[V]));
        return Graph;
    }
    
}

int main()
{
    BuildGraph();
    return 0;
}

这里要提到malloc函数

malloc函数是一种分配长度为num_bytes字节的内存块的函数，可以向系统申请分配指定size个字节的内存空间。malloc的全称是memory allocation，中文叫动态内存分配，当无法知道内存具体位置的时候，想要绑定真正的内存空间，就需要用到动态的分配内存。
返回类型是 void* 类型。void* 表示未确定类型的指针。C,C++规定，void* 类型可以通过类型转换强制转换为任何其它类型的指针。

  • 使用时一般要强制类型转换*
1
2
MGraph Graph;
Graph = (MGraph)malloc(sizeof(struct GNode));
  • 简易版本：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
int G[maxn][maxn], Nv, Ne;
void BuildGraph()
{
    int i, j, v1, v2, w;

    scanf("%d", &Nv);
    //CreateGraph
    for (i = 0; i < Nv; i++)
        for (j = 0; j < Nv; j++)
            G[i][j] = 0;

    scanf("%d", &Ne);
    for (i = 0; i < Ne; i++)
        scanf("%d%d%d", &v1, &v2, &w);
    //InsertEdge
    G[v1][v2] = w;
    G[v2][v1] = w;
}
邻接表(链式前向星)


代码实现：

  • 简单版本
    vector实现
    stl是个好东西
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
/*************************************************************************
 > FileName:
 > Author:      Lance
 > Mail:        lancelot_hcs@qq.com
 > Date:        9102.1.8
 > Description:
 ************************************************************************/
//#include <bits/stdc++.h>
#pragma comment(linker, "/STACK:102400000,102400000")
#include <algorithm>
#include <iostream>
#include <cstdlib>
#include <cstring>
#include <sstream>
#include <vector>
#include <cstdio>
#include <bitset>
#include <string>
#include <cmath>
#include <deque>
#include <queue>
#include <stack>
#include <map>
#include <set>
using namespace std;
typedef long long ll;
const double pi = acos(-1.0);
const int eps = 1e-10;
const int mod = 1e9 + 7;
const int INF = 0x3f3f3f3f;//int2147483647//ll9e18//unsigned ll 1e19
const int maxn = 1005;

struct Node
{
    int v,w;
    Node(int _v, int _w) : v(_v), w(_w){}
};

vector<Node> Adj[maxn];

int main()
{
//    ios::sync_with_stdio(false);
    Adj[0].push_back(Node(1, 2));
    Adj[0].push_back(Node(4, 1));
    Adj[1].push_back(Node(0, 2));
    Adj[1].push_back(Node(2, 2));
    Adj[1].push_back(Node(4, 2));
    Adj[2].push_back(Node(1, 2));
    Adj[2].push_back(Node(3, 1));
    Adj[3].push_back(Node(2, 1));
    Adj[3].push_back(Node(4, 1));
    Adj[4].push_back(Node(0, 1));
    Adj[4].push_back(Node(1, 2));
    Adj[4].push_back(Node(3, 1));
    for (int i = 0; i < 5; i++)
    {
        for (int j = 0; j < Adj[i].size(); j++)
        {
            cout << "head:" << i << " ->" << Adj[i][j].v;
            j == Adj[i].size() - 1 ? cout << endl : cout << "->";
        }
    }
    return 0;
}
  • 复杂版本
    代码来自github
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
#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>
#include <string.h>
#include <time.h>

struct vertex;
struct vertex_adjs
{
    struct vertex *v;
    struct vertex_adjs *next;
};

struct vertex
{
    int data;
    struct vertex_adjs *adj;
};

#define MAX_GRAPH_VERTEX (1 << 8)
struct graph
{
    struct vertex *vxs[MAX_GRAPH_VERTEX];
};

void init_graph(struct graph *graph)
{
    int i;

    for (i = 0; i < MAX_GRAPH_VERTEX; i++)
        graph->vxs[i] = NULL;
}

struct vertex *create_vertex(int data)
{
    struct vertex *v;

    v = (vertex *)malloc(sizeof(struct vertex));

    if (v)
    {
        v->data = data;
        v->adj = NULL;
    }

    return v;
}

struct vertex_adjs *create_vertex_adj(struct vertex *v)
{
    struct vertex_adjs *v_adj;

    v_adj = (vertex_adjs *)malloc(sizeof(struct vertex_adjs));

    if (!v_adj)
        return NULL;

    v_adj->v = v;
    v_adj->next = NULL;
    return v_adj;
}

void insert_adj(struct vertex *v, struct vertex *adj)
{
    struct vertex_adjs **v_adj;

    v_adj = &v->adj;

    while (*v_adj)
        v_adj = &(*v_adj)->next;

    *v_adj = create_vertex_adj(adj);
}

void dump_raw(struct graph *graph)
{
    int i;

    for (i = 0; i < MAX_GRAPH_VERTEX; i++)
    {
        struct vertex *v = graph->vxs[i];
        struct vertex_adjs *adj;
        if (v == NULL)
            continue;

        printf("Vertex[%02d]: %8d ->", i, v->data);

        adj = v->adj;
        while (adj)
        {
            printf(" %8d,", adj->v->data);
            adj = adj->next;
        }
        printf("\n");
    }
}

/*
  1 ----- 2 ----- 3
  |     / |     /
  |    /  |    /
  |   /   |   /
  |  /    |  /
  | /     | /
  4 ----- 5
*/
void fake_a_graph(struct graph *graph)
{
    int i;

    init_graph(graph);

    for (i = 0; i < 5; i++)
        graph->vxs[i] = create_vertex(i + 1);

    /* connect 1 -> 2, 1 -> 4 */
    insert_adj(graph->vxs[0], graph->vxs[1]);
    insert_adj(graph->vxs[0], graph->vxs[3]);
    /* connect 2 -> 1, 2 -> 3, 2 -> 5, 2 -> 4 */
    insert_adj(graph->vxs[1], graph->vxs[0]);
    insert_adj(graph->vxs[1], graph->vxs[2]);
    insert_adj(graph->vxs[1], graph->vxs[4]);
    insert_adj(graph->vxs[1], graph->vxs[3]);
    /* connect 3 -> 2, 3 -> 5 */
    insert_adj(graph->vxs[2], graph->vxs[1]);
    insert_adj(graph->vxs[2], graph->vxs[4]);
    /* connect 4 -> 1, 4 -> 2, 4 -> 5 */
    insert_adj(graph->vxs[3], graph->vxs[0]);
    insert_adj(graph->vxs[3], graph->vxs[1]);
    insert_adj(graph->vxs[3], graph->vxs[4]);
    /* connect 5 -> 4, 5 -> 2, 5 -> 3 */
    insert_adj(graph->vxs[4], graph->vxs[3]);
    insert_adj(graph->vxs[4], graph->vxs[1]);
    insert_adj(graph->vxs[4], graph->vxs[3]);
}

int main()
{
    struct graph g;

    fake_a_graph(&g);
    dump_raw(&g);
    return 0;
}

图的遍历

事实上，深度优先搜索属于图算法的一种，英文缩写为DFS即Depth First Search.其过程简要来说是对每一个可能的分支路径深入到不能再深入为止，而且每个节点只能访问一次.

代码实现

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
/*************************************************************************
 > FileName:
 > Author:      lance
 > Mail:        lancelot_hcs@qq.com
 > Date:        9102.1.8
 > Description:
 ************************************************************************/
/*
该DFS 框架以2D 坐标范围为例，来体现DFS 算法的实现思想。
*/
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<iostream>
using namespace std;
const int maxn=105;
bool vis[maxn][maxn]; // 访问标记
char map[maxn][maxn]; // 坐标范围
int dir[8][2]={{2, 1}, {2, -1}, {1, -2}, {-1, -2}, {-2, -1}, {-2, 1}, {-1, 2}, {1, 2}}; // 方向向量，(x,y)周围的四个方向

bool test(int x, int y) // 边界条件和约束条件的判断
{
    if(!vis[x][y] && x >= 0 && y >= 0 && y < 9&& x < 10 && map[x][y] != '#') // 满足条件
        return 1;
    else // 与约束条件冲突
        return 0;
}
int flag = 0;
void dfs(int x, int y)
{
    vis[x][y]=1; // 标记该节点被访问过
    if(map[x][y]=='T') // 出现目标态G
    {
        flag = 1;
        return;
    }
    for(int i=0;i<8;i++)
    {
        if(test(x+dir[i][0],y+dir[i][1])) // 按照规则生成下一个节点
            dfs(x+dir[i][0],y+dir[i][1]);
    }
    return; // 没有下层搜索节点，回溯
}
int sx, sy;
int main()
{
    for (int i = 0; i < 10; i++)
    {
        for (int j = 0; j < 9; j++)
        {
            cin >> map[i][j];
            if (map[i][j] == 'S')
                sx = i, sy = j;
        }
    }
    dfs(sx, sy);
    puts(flag?"Yes":"No");
    return 0;
}

广度优先搜索算法（又称广度优先搜索）是最简便的图的搜索算法之一，这一算法也是很多重要的图的算法的原型。Dijkstra单源最短路径算法和Prim最小生成树算法都采用了和宽度优先搜索类似的思想。可以类比树的层序遍历，一般由队列实现。

2018蓝桥杯c++A组

就是一道很经典的bfs

P1126 机器人搬重物

洛谷这道题，其实挺水的，结果卡了我半天的剪枝…果然还是鄙人太菜

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
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
/*************************************************************************
 > FileName:
 > Author:      Lance
 > Mail:        lancelot_hcs@qq.com
 > Date:        9102.1.8
 > Description:
 ************************************************************************/
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <queue>
#include <stack>
#include <vector>
#include <map>
#include <set>
#include <bitset>
#include <string>
#include <cmath>
#include <sstream>
using namespace std;
typedef long long ll;
const double pi = acos(-1.0);
const int eps = 1e-10;
const int mod = 1e9 + 7;
const int INF = 0x3f3f3f3f;//int2147483647//ll9e18//unsigned ll 1e19
const int maxn = 55;

int dir0[4][3][2] = {{{1, 0}, {2, 0}, {3, 0}}, {{0, 1}, {0, 2}, {0, 3}}, {{-1, 0}, {-2, 0}, {-3, 0}}, {{0, -1}, {0, -2}, {0, -3}}};
int maze1[maxn][maxn], maze[maxn][maxn];
bool vis[4][maxn][maxn];
int n, m, starx, stary, stard, aimx, aimy;
string strl = "123";
char c;

struct node
{
    int x, y;
    int dir1, step;
    node(int _x, int _y, int _dir1, int _step) : x(_x), y(_y), dir1(_dir1), step(_step) {}
};

bool if_print(int x, int y, int s)
{
    if(x == aimx && y == aimy)
    {
        printf("%d\n", s);
        return 1;
    }
    return 0;
}

bool test(int x, int y, int dir)
{
    return x > 0 && y > 0 && x < n && y < m && !maze[x][y] && !vis[dir][x][y] ? 1 : 0;
}
/*0123代表senw*/
void bfs(int x, int y, int dir, int step)
{
    queue <node> q;
    q.push(node(x, y, dir, step));
    vis[dir][x][y] = 1;
    while(!q.empty())
    {
        node top = q.front();
        if (top.x == aimx && top.y == aimy)
        {
            printf("%d\n", top.step);
            //            cout << top.str << endl;
            return;
        }
        q.pop();
        int tx, ty, tdir = top.dir1, tstep = top.step + 1;
        for (int i = 0 ; i < 3; i++)
        {
            if (i == 0)
            {
                if (test(top.x + dir0[tdir][i][0], top.y + dir0[tdir][i][1], tdir))
                {

                    tx = top.x + dir0[tdir][i][0];
                    ty = top.y + dir0[tdir][i][1];
                    vis[tdir][tx][ty] = 1;
                    q.push(node(tx, ty, tdir, tstep));
                    if(if_print(tx, ty, tstep))
                        return;
                }
            }
            if (i == 1)
            {
                if (test(top.x + dir0[tdir][i][0], top.y + dir0[tdir][i][1], tdir) && !maze[top.x + dir0[tdir][i - 1][0]][top.y + dir0[tdir][i - 1][1]])
                {

                    tx = top.x + dir0[tdir][i][0];
                    ty = top.y + dir0[tdir][i][1];
                    vis[tdir][tx][ty] = 1;
                    q.push(node(tx, ty, tdir, tstep));
                    if(if_print(tx, ty, tstep))
                        return;
                }
            }
            else
            {
                if (test(top.x + dir0[tdir][i][0], top.y + dir0[tdir][i][1], tdir) && !maze[top.x + dir0[tdir][i - 1][0]][top.y + dir0[tdir][i - 1][1]] && !maze[top.x + dir0[tdir][i - 2][0]][top.y + dir0[tdir][i - 2][1]])
                {

                    tx = top.x + dir0[tdir][i][0];
                    ty = top.y + dir0[tdir][i][1];
                    vis[tdir][tx][ty] = 1;
                    q.push(node(tx, ty, tdir, tstep));
                    if(if_print(tx, ty, tstep))
                        return;
                }
            }

        }
        vis[tdir][top.x][top.y] = 1;
        if (tdir == 3)
        {

            if(!vis[tdir - 1][top.x][top.y])
            {
                q.push(node(top.x, top.y, tdir - 1, tstep));
                vis[tdir - 1][top.x][top.y] = 1;
            }

            if(!vis[0][top.x][top.y])
            {
                q.push(node(top.x, top.y, 0, tstep));
                vis[0][top.x][top.y] = 1;
            }

        }
        else if(tdir == 0)
        {
            if(!vis[tdir + 1][top.x][top.y])
            {
                q.push(node(top.x, top.y, tdir + 1, tstep));
                vis[tdir + 1][top.x][top.y] = 1;
            }

            if(!vis[3][top.x][top.y])
            {
                q.push(node(top.x, top.y, 3, tstep));
                vis[3][top.x][top.y] = 1;
            }

        }
        else
        {
            if(!vis[tdir + 1][top.x][top.y])
            {
                q.push(node(top.x, top.y, tdir + 1, tstep));
                vis[tdir + 1][top.x][top.y] = 1;
            }

            if(!vis[tdir - 1][top.x][top.y])
            {
                q.push(node(top.x, top.y, tdir - 1, tstep));
                vis[tdir - 1][top.x][top.y] = 1;
            }

        }
    }
    puts("-1");
    return;
}

int main()
{
    scanf("%d%d", &n, &m);
    for (int i = 0; i < n; i++)
    {
        for (int j = 0; j < m; j++)
        {
            scanf("%d", &maze1[i][j]);
        }
    }
    for (int i = 0 ; i < n ; i++)
    {
        for (int j = 0; j < m; j++)
        {
            if(maze1[i][j])
            {
                maze[i][j] = 1;
                maze[i + 1][j] = 1;
                maze[i][j + 1] = 1;
                maze[i + 1][j + 1] = 1;
            }
        }
    }
    scanf("%d%d%d%d %c", &starx, &stary, &aimx, &aimy, &c);
    if (c == 'S')/*0123代表senw*/
        stard = 0;
    else if(c == 'E')
        stard = 1;
    else if(c == 'N')
        stard = 2;
    else
        stard = 3;
    bfs(starx, stary, stard, 0);
    return 0;
}

用结构体构造函数的话还是挺方便的

1
2
3
4
5
6
struct node
{
    int x, y;
    int dir1, step;
    node(int _x = 0, int _y = 0, int _dir1 = 0, int _step = 0) : x(_x), y(_y), dir1(_dir1), step(_step) {}
};

虽然后面发现这样也是等价的

1
2
3
4
5
6
struct node
{
    int x, y;
    int dir1, step;
};
(node){_x, _y, _dir1, _step};

最短路问题(以下算法模板已上传github)

单源最短路问题

Single-Source Shortest Paths (SSSP) problem

Bellman-Ford算法
  • 使用邻接表比较方便
  • 适用前提：没有负环（或称为负权值回路），因为有负环的话距离为负无穷。
  • 若u->v是有向边，则d[v] <= d[u] + dis(u, v)，这个操作称为松弛操作
  • 优点：可以处理负权值，还可以发现负环
SPFA算法

SPFA的过程是BFS，它是不停扩展节点的。

本质Bellman-Ford算法的优化
SPFA(Shortest Path Faster Algorithm)是Bellman-Ford算法的一种队列优化，减少了不必要的冗余计算。

SPFA在形式上和BFS非常类似，不同的是BFS中一个点出了队列就不可能重新进入队列，但是SPFA中一个点可能在出队列之后再次被放入队列，也就是一个点松弛过其它的点之后，过了一段时间可能本身被松弛，于是要再次用来松弛其它的点，这样反复迭代下去。

spfa的队列优化
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
/*************************************************************************
 > FileName:
 > Author:      Lance
 > Mail:        lancelot_hcs@qq.com
 > Date:        9102.1.8
 > Description: 注意有向图和无向图，
 ************************************************************************/
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <queue>
#include <stack>
#include <vector>
#include <map>
#include <set>
#include <bitset>
#include <string>
#include <cmath>
#include <sstream>
using namespace std;
typedef long long ll;
const double pi = acos(-1.0);
const int eps = 1e-10;
const int mod = 1e9 + 7;
const ll INF = 2147483647;//int2147483647//ll9e18//unsigned ll 1e19
const int maxn = 100005;
int a[maxn];

struct node
{
    int v, dis;
    node(int _v = 0, int _dis = 0) : v(_v), dis(_dis) {}
};

vector<node> Adj[maxn];
int n, m, st, ed, weight[maxn];//n点，m边
int d[maxn], num[maxn];//d存的是起点到各点的最短路
bool inq[maxn];

bool SPFA(int s)//s为起点
{
    memset(inq, false, sizeof(inq));
    memset(num, 0, sizeof(num));
    fill(d, d + maxn, INF);
    queue<int> Q;
    Q.push(s);
    inq[s] = true;
    num[s]++;
    d[s] = 0;
    while (!Q.empty())
    {
        int u = Q.front();
        Q.pop();
        inq[u] = false;
        for (int j = 0; j < Adj[u].size(); j++)
        {
            int v = Adj[u][j].v;
            int dis = Adj[u][j].dis;
            if (d[u] + dis < d[v])
            {
                d[v] = d[u] + dis;
                if (!inq[v])
                {
                    Q.push(v);
                    inq[v] =true;
                    num[v]++;
                    if (num[v] >= n)
                        return false;
                }
            }
        }
    }
    return true;
}

int main()
{
    while (~scanf("%d%d", &n, &m))
    {
        if (n == 0 && m == 0)
            break;
        for (int i = 0; i < m; i++)
        {
            int a, b, c;
            scanf("%d%d%d", &a, &b, &c);
            Adj[a].push_back(node(b, c));
            Adj[b].push_back(node(a, c));
        }
        SPFA(1);
        printf("%d\n", d[n]);
        for (int i = 0; i <= n; i++)
        {
            Adj[i].clear();
        }
    }

    return 0;
}
//46MS  4728K

Dijkstra算法(贪心思想)

迪杰斯特拉

哲学意义————发散思维

  • 求图中给定两点v到u的最短路径，则计算v到所有其他点的最短路径，终能包含v到u的最短路径!
  • 时间复杂度比Bellman-Ford小，但是无法处理负权值的情况
    在稠密图中有不俗的表现.

基本思想

通过Dijkstra计算图G中的最短路径时，需要指定起点s(即从顶点s开始计算)。

此外，引进两个集合S和U。S的作用是记录已求出最短路径的顶点(以及相应的最短路径长度)，而U则是记录还未求出最短路径的顶点(以及该顶点到起点s的距离)。

初始时，S中只有起点s；U中是除s之外的顶点，并且U中顶点的路径是”起点s到该顶点的路径”。然后，从U中找出路径最短的顶点，并将其加入到S中；接着，更新U中的顶点和顶点对应的路径。 然后，再从U中找出路径最短的顶点，并将其加入到S中；接着，更新U中的顶点和顶点对应的路径。 … 重复该操作，直到遍历完所有顶点。

看这个

怎么优化呢?

我会zkw线段树!

我会斐波那契堆!

我会堆!

会个鬼

我们可以用堆对dis数组进行维护,用$$O(\log_{2}n)$$的时间取出堆顶元素并删除,用$$O(\log_{2}n)$$遍历每条边,
总复杂度$$O((n+m)\log_{2}n)$$

例如:

用Dijkstra就会出错。

迪杰斯特拉的优先队列优化
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
/*************************************************************************
 > FileName:
 > Author:      Lance
 > Mail:        lancelot_hcs@qq.com
 > Date:        9102.1.8
 > Description:
 ************************************************************************/
//#include <bits/stdc++.h>
#pragma comment(linker, "/STACK:102400000,102400000")//add_stack
#include <algorithm>
#include <iostream>
#include <cstdlib>
#include <cstring>
#include <sstream>
#include <vector>
#include <cstdio>
#include <bitset>
#include <string>
#include <cmath>
#include <deque>
#include <queue>
#include <stack>
#include <map>
#include <set>
using namespace std;
typedef long long ll;
const double pi = acos(-1.0);
const int eps = 1e-10;
const int mod = 1e9 + 7;
#define debug(a) cout << "*" << a << "*" << endl
const int INF = 0x3f3f3f3f;//int2147483647//ll9e18//unsigned ll 1e19
const int maxn = 1e3 + 5;

struct  node
{
    int v, dis;//目标顶点，边权
    bool operator < (const node &rhs) const
    {
        return dis > rhs.dis;//距离
    }
};
vector<node > Adj[maxn];
int n, m, s;
int d[maxn];
bool vis[maxn];

void Dijkstra(int s)
{
    priority_queue<node> que;

    memset(vis, 0, sizeof(vis));
    fill(d, d + maxn, INF);

    d[s] = 0;
    que.push((node){s, d[s]});
    while (!que.empty())
    {
        int now = que.top().v;
        node tp = que.top();
        que.pop();
        if (d[now] < tp.dis)//f=dis,s=v
            continue;
        for (int i = 0; i < Adj[now].size(); i++)
        {
            int v = Adj[now][i].v;
            if (d[v] > d[now] + Adj[now][i].dis)
            {
                d[v] = d[now] + Adj[now][i].dis;
                que.push((node){v, d[v]});
            }
        }
    }
}

int main()
{
    while (scanf("%d%d", &n, &m))
    {
        if (n == 0 && m == 0)
            break;
        for (int i = 0; i < m; i++)
        {
            int a, b, c;
            scanf("%d%d%d", &a, &b, &c);
            Adj[a].push_back((node){b, c});
            Adj[b].push_back((node){a, c});
        }
        Dijkstra(1);
        printf("%d\n",d[n]);
        for (int i = 0; i <= n; i++)
            Adj[i].clear();
    }
    return 0;
}
//15MS  1524K

多源最短路问题
(Floyd-Warshall算法)

弗洛伊德算法
本质
动态规划
map[i,j]记录结点i到j的最短路径的距离，则
map[i,j] = min{map[i,k] + maxp[k,j], map[i,j]};
同时，map[n,n] == 0，存在负权值也适用

py贼简洁

1
2
3
4
5
6
for k in range(self.V):
    for i in range(self.V):
        for j in range(self.V)
            if self.D[i][k] + self.D[k][j] < self.D[i][j]:
                self.D[i][j] = self.D[i][k] + self.D[k][j]
                self.S[i][j] = self.S[i][k]

其实是同一题hdu2544

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
/*************************************************************************
 > FileName:
 > Author:      Lance
 > Mail:        lancelot_hcs@qq.com
 > Date:        9102.1.8
 > Description: floyd，用的邻接矩阵
 ************************************************************************/
//#include <bits/stdc++.h>
#pragma comment(linker, "/STACK:102400000,102400000")//add_stack
#include <algorithm>
#include <iostream>
#include <cstdlib>
#include <cstring>
#include <sstream>
#include <vector>
#include <cstdio>
#include <bitset>
#include <string>
#include <cmath>
#include <deque>
#include <queue>
#include <stack>
#include <map>
#include <set>
using namespace std;
typedef long long ll;
const double pi = acos(-1.0);
const int eps = 1e-10;
const int mod = 1e9 + 7;
#define debug(a) cout << "*" << a << "*" << endl
const int INF = 0x3f3f3f3f;//int2147483647//ll9e18//unsigned ll 1e19
const int maxn = 1005;

int G[maxn][maxn];
int t, n, m;//n点，m边

void floyd()
{
    for (int k = 1; k <= n; k++)
        for (int i = 1; i <= n; i++)
            for (int j = 1; j <= n; j++)
                if (G[i][j] > G[i][k] + G[k][j])
                    G[i][j] = G[i][k] + G[k][j];
}

int main()
{
//    ios::sync_with_stdio(false);
    while (~scanf("%d%d", &n, &m))
    {
        if (n == 0 && m == 0)
            break;
        fill(G[0], G[0] + maxn * maxn, INF);
        for (int i = 0; i < m; i++)
        {
            int a, b, c;
            scanf("%d%d%d", &a, &b, &c);
            if (c < G[a][b])
                G[b][a] = G[a][b]= c;
        }
        floyd();
        printf("%d\n", G[1][n]);
    }
    return 0;
}
//46MS  5328K

最小生成树

Minimum Spanning Tree
最小生成树是在一个给定的无向图
稠密图用prim，稀疏图用kruskal

Prim算法(bfs思想)
Kruskal算法

(以上图论算法参考《算法笔记》-图算法专题)

图论进阶有空再补