图论

图的存储（记录常用的三种

一.邻接矩阵

直接通过二维数组存储，例如

1
2
3
4
map[i][j] // i 维度 表示边的起点，其所对应的 j 维度的每个点都是与 i 点相连的终点

// 由此可见，此法所表示的每一条边都是有向边，如果解决问题所需的是无向边，只需 i->j 和 j->i 各记录一次即可。
//值得一提的是，如此表示无向边，要注意数组的大小，要是两倍边数以上才可以

二.vector 存储

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
#include <vector>
using namespace std;

int V = 5; // 顶点数
vector<vector<int>> adjList(V);

// 添加边
void addEdge(int u, int v, bool directed = false)
{
    adjList[u].push_back(v);
    // 判断边是否有向
    if (!directed)
    {
        adjList[v].push_back(u); // 无向图需要双向添加
    }
}

三.伪邻接表（链式向前星

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
#include <iostream>
using namespace std;
const int v = 5; // 顶点数
struct ty
{
  int t, next; // 顶点 和 下一边“指针”
}edge[100];
int head[100]; // 第i个点的下一边“指针”  初始化为-1
int cnt = 0;
void insertedge(int x, int y)
{
  edge[++cnt].t = y;
  edge[cnt].next = head[x];
  head[x] = cnt;
}

欧拉图

具有欧拉回路的图就是欧拉图

如果图中的一个路径包含几个边恰好一次，该路径就是欧拉路径

如果一个回路是欧拉路径，该回路就是欧拉回路

以上的前提就是，该图为连通图，一旦有不连通的点，上面条件都不可能达到

实则就是计算机图的连通性以及每个点的度数

拓扑排序

该排序常常用来判断有向图是否有环

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
#include <iostream>
#include <cstring>
#include <queue>
#include <vector>
using namespace std;
int n, m; // 图的点数和边数
struct ty
{
  int t, next;
}edge[100010];
int cnt = 0; //边的数量
int head[1010];
void insertedge(int x, int y)
{
  edge[++cnt].t = y;
  edge[cnt].next = head[x];
  head[x] = cnt;
}
int inc[1010]; // 每个点的入度
vector<int> ans; //记录答案
queue<int> q;
// 拓扑排序
void tuopu()
{
  for (int i = 1; i <= n; i++)
  {
    //入度为0，则入队删除此点
    if (inc[i] == 0) q.push(i);
  }
  while (!q.empty())
  {
    int x = q.front();
    q.pop();
    ans.push_back(x);
    // 接下来，将所有与“删除点”有关的边全部去掉，也就是，将有与“删除点”直接连接的点的入度都减一
    for (int i = head[x]; i != -1; i = edge[i].next)
    {
      // 这些点入度减一
      inc[edge[i].t]--;
      // 发现有点入度为0，继续入队等待删除
      if (inc[edge[i].t] == 0) q.push(edge[i].t);
    }
  }
}

int main()
{
  cin >> n >> m;
  //初始化，起初所有点都是独立的，没有与其他点相连接
  memset(head, -1, sizeof(head));
  for (int i = 1; i <= m; i++)
  {
      int x, y;
      scanf("%d%d", &x, &y);
      // 记得计算点的入度
      inc[y]++;
      insertedge(x, y);
  }
  tuopu();
  // 拓扑排序结束，仍然有剩余点，意味着，剩余点必然是构成环，导致无法继续排序，输出-1
  if (ans.size() < n) cout << -1 << endl;
  else
  {
    for (auto i : ans)
    {
      cout << i << endl;
    }
  }
  return 0;
}

下面代码和算法具体解释，等有空再写

最短路

树中的最短路------一般采用dfs解决
有向无环图--------一般采用拓扑排序解决
边权全相等--------一般采用bfs解决

当然还有以下算法用于求其他类型图中的最短路（下面代码的图存储都采用伪邻接表

一.Dijkstra（迪杰斯特拉

djs 算法常常用来解决没有负权边的图

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
#include <iostream>
#include <cstring>
#include <queue>
using namespace std;
struct ty
{
    int t, len, next;
}edge[200010];
int head[1010];
int vis[1010];
int dis[1010];
int cnt = 0;
struct ty1
{
    int x, dist;
    bool operator<(const ty1& a) const
    {
        return dist > a.dist;
    }
};
void addedge(int x, int y, int v)
{
    edge[++cnt].t = y;
    edge[cnt].len = v;
    edge[cnt].next = head[x];
    head[x] = cnt;
}
priority_queue<ty1> q;
int djs(int s, int t)
{
    memset(dis, 0x3f, sizeof(dis));
    memset(vis, 0, sizeof(vis));
    dis[s] = 0;
    ty1 tmp1;
    tmp1.x = s, tmp1.dist = 0;
    q.push(tmp1);
    while (!q.empty())
    {
        ty1 tmp2 = q.top();
        q.pop();
        if (vis[tmp2.x]) continue;
        vis[tmp2.x] = 1;
        for (int i = head[tmp2.x]; i != -1; i = edge[i].next)
        {
            int x = edge[i].t;
            int k = edge[i].len;
            if (k + dis[tmp2.x] < dis[x])
            {
                dis[x] = k + dis[tmp2.x];
                ty1 nex;
                nex.x = x, nex.dist = dis[x];
                q.push(nex);
            }
        }
    }
    if (dis[t] >= 0x3f3f3f3f) return -1;
    else return dis[t];
}
int main()
{
    //n 为顶点数，m 为边数， s 为起点， t 为终点
    int n, m, s, t;
    cin >> n >> m >> s >> t;
    memset(head, -1, sizeof(head));
    for (int i = 1; i <= m; i++)
    {
        int x, y, v;
        cin >> x >> y >> v;
        addedge(x, y, v);
        addedge(y, x, v);
    }
    cout << djs(s, t) << endl;
    return 0;
}

二.由 Bellman-Ford 优化后的 SPFA 算法

spfa 算法一般只有在出现了负权边的情况下才使用，因为它在极坏情况下可能退化为 o(n^3)的时间复杂度，很大概率被卡

如果图中出现 负环 ，此算法会出现死循环，当然反过来也就可以通过 卡循环次数 来判断图中是否含有 负环

如果同一个点被入队 n 次，即可证明图中必然存在 负环

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
#include <iostream>
#include <cstring>
#include <queue>
using namespace std;
struct ty
{
    int t, len, next;
}edge[200010];
int dis[1010];
int vis[1010];
int head[1010];
int cnt = 0;
void addedge(int x, int y, int v)
{
    edge[++cnt].t = y;
    edge[cnt].len = v;
    edge[cnt].next = head[x];
    head[x] = cnt;
}
queue<int> q;
int spfa(int s, int t)
{
    memset(dis, 0x3f, sizeof(dis));
    memset(vis, 0, sizeof(vis));
    dis[s] = 0;
    q.push(s);
    vis[s] = 1;
    while (!q.empty())
    {
        int tmp = q.front();
        q.pop();
        vis[tmp] = 0;
        for (int i = head[tmp]; i != -1; i = edge[i].next)
        {
            if (dis[tmp] + edge[i].len < dis[edge[i].t])
            {
                dis[edge[i].t] = dis[tmp] + edge[i].len;
                if (vis[edge[i].t] == 0)
                {
                    q.push(edge[i].t);
                    vis[edge[i].t] = 1;
                }
            }
        }
    }
    if (dis[t] >= 0x3f3f3f3f) return -1;
    else return dis[t];
}
int main()
{
    int n, m, s, t;
    cin >> n >> m >> s >> t;
    memset(head, -1, sizeof(head));
    for (int i = 1; i <= m; i++)
    {
        int x, y, v;
        cin >> x >> y >> v;
        addedge(x, y, v);
        addedge(y, x, v);
    }
    cout << spfa(s, t) << endl;
    return 0;
}