图论

理论

基本概念

假设平面上的n个点，把其中的一些点对用曲线或直线连接起来，不考虑点的位置与连线曲直长短，形成的一个关系结构称为一个图。记

G = (V(G), E(G)), V = V(G) 是顶点集，E = E(G) 是边集。

设ν ∈ V(G),若ν是边e ∈ E(G)的端点，则称ν与e相关联， 与顶点ν关联的边数之和称为该顶点的次数（度数），记为d(ν)。可以证明握手定理

∑_{ν ∈ V(G)}d(ν) = 2|E(G)| ,

且由此可知：奇次顶点的总数是偶数，且所有 顶点的次数之和是边数的两倍。次数为奇数顶点称为奇点，否则称为偶点。所以我们在一些建模问题中，为了消去奇次顶点，可以两两配对进行加边。

常用d(ν)表示图G 中与顶点ν关联的边的数目， d(ν)称为顶点ν的度数. 与顶点ν出关联的边的数目称为出度，记作d⁺(ν), 与顶点ν入关联的边的数目称为入度，记作d⁻(ν)。用N(ν)表示图G 中所有与顶点ν相邻的顶点的集合.

有结论:
∑_ν ∈ Vd⁺(ν) = ∑_ν ∈ Vd⁻(ν) = |E|

这是显然的，每条弧必然连接两个顶点，也对应一个入度和一个出度，所以所有顶点的入度之和等于所有顶点的出度之和

若对于每条边是有指向的,则称为有向图;若每条边是不区分指向的,则称为无向图。若有的边有向，有的边无向，则称为混合图。

特殊的结构

self-loop（自环） 一个节点指向自己的边，比如网络爬虫中我们需要遍历所有网页，但有的网页会给出自己的url（链接到自己），这就需要用自环描述
mutiedge(多重边) 一个城市到另一个城市有很多条不同的航班，要用多重边描述。

图的邻接矩阵(adjacency matrix)表示法

将邻接矩阵理解为一种数据结构
图G = (V, E)的邻接矩阵C = (c_ij)是如下定义 $$c_{ij}=\begin{cases}1,(v_i,v_j)\in E\\0,(v_i,v_j)\not\in E\end{cases}$$

也就是说，
1 如果两节点之间有一条弧,则邻接矩阵中对应的元素为1;否则为0。这一数据结构便于我们查找图的情况与节点连接情况。
2 如果图中的每条边都有一个（或多个）实数与之对应，称这样的图为赋权图。同样,对于网络中的权,也可以用这样的邻接矩阵表示。只是此时一条弧所对应的元素不再是1,而是相应的权

邻接矩阵表示为 $\begin{pmatrix}0&1&1&0&0\\0&0&0&1&0\\0&1&0&0&0\\0&0&1&0&0\\0&0&1&1&0\end{pmatrix}$
注意到
无向图的邻接矩阵是一个对称阵
如果网络比较稀疏,这种表示法会浪费大量的存储空间,而且增加了在网络中查找弧的时！

关联矩阵表示法(incidence matrix)

图G = (V, E)的关联矩阵B = (b_ij)定义为： $$b_{ij}=\begin{cases}1,&\exists v_k\in V,s.t.e_j=(v_i,v_k)\in E\\-1,&\exists v_k\in V,s.t.e_j=(v_k,v_i)\in E\\0,&其他\end{cases}$$ 也就是说，节点v_i是边e_j的起点时，b_ij = 1,是终点时，b_ij = −1,否则为b_ij = 0。 ·关联矩阵中，每一行对应一个节点；每一列对应一条边。·对于简单图，每一列只有2个非0元(一个1，一个-1)。·对于赋权图，可以把关联矩阵增加一行，把每一条弧所对应的权存储在增加的行中。

Dijkstra算法

算法目标：在一个有权重的图中，给出一个起始点，我们可以求出到达其他所有点的最短路径。

有一个极其重要的图论定理:最短路径的子路径仍然是最短路径

（最短路径的子路径最优性质）： 如果在带权图中从顶点u到顶点v存在一条最短路径P，并且路径P经过中间顶点w，那么从u到w的子路径Q1和从w到v的子路径Q2分别也是u到w和w到v的最短路径。

https://zhuanlan.zhihu.com/p/454373256

Dijkstra算法是把从起点开始到其他点的所有路径按长度从小到大的顺序列举了出来，保证前一次列出的路径的长度一定小于下一次，这样的话，当某个节点第一次作为终点出现时，一定是最短路径，因为后续列出的路径一定比这一次要长

具体来说，Dijkstra算法的执行过程如下：

1，找出此时路状态表中最短的一条，这一定是我们要求的d[]=M.(因为倘若这不是我们要求的d，那么我们要求的d一定在由起始点从其他节点过来的路上，但那些路必然包含着大于M的子路径，归谬！所以此时状态表中最短的d[]就是我们要求的d[]).记录st[t]=true，并记录t作为下一次延伸节点
2从t向外再延伸一次得到一系列新的待比较的d[]，与原有d[]取min留下，得到从t向外延伸一次后新的d[]表
重复到1步骤

这本质上实在逐步构建最短路径树。

c艹代码

#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

const int N = 510;
int dist[N];//dist[i]表示结点i到起点的距离
int g[N][N];//g[i][j]表示结点i到结点j的边的长度
bool st[N];//st[i]表示该结点是否确定了最小距离，1是确定，0是未确定
int n, m;


void dijkstra()
{
    memset(dist, 0x3f, sizeof dist);//把距离初始化为正无穷
    dist[1] = 0;
    
    int iter = n;
    while(iter--)//n个点，循环n次
    {
        int t = -1;
        //t随便初始化了一个不存在的结点，它最终用来存储未确定最小距离的结点，且该结点与其它结点相比目前到起点的距离最小
        for(int i = 1; i <= n; i++)
            if(st[i] == 0 && (t == -1 || dist[i] < dist[t]))
                t = i;
                
        st[t] = true;
        //用结点t依次取更新其它结点到起点的距离，dist[i] = min(dist[i], dist[t] + g[t][i]);
        for(int i = 1; i <= n; i++)
            if(st[i] == 0)
                dist[i] = min(dist[i], dist[t] + g[t][i]);
                
    }
    
}

int main()
{
    
    cin >> n >> m;
    
    memset(g, 0x3f, sizeof g);//将边先初始化为正无穷
    
    while(m--)
    {
        int x, y, z;
        cin >> x >> y >> z;
        g[x][y] = min(g[x][y], z);//存在重边
        //对于自环，不做处理，它不影响结果的计算
    }
    
    
    dijkstra();
    
    
    if(dist[n] == 0x3f3f3f3f)
        cout << "-1" << endl;
    else
        cout << dist[n] << endl;
    

    return 0;
}

eg: 请帮助该公司设计一张城市 c₁到其它城市间的票价最便宜的路线图。

某公司在六个城市c₁, c₂, ⋯, c₆中有分公司，从 c_i到c_j的直接航程票价记在下述矩阵的(i, j)位置上(∞表示无直接航路) $$\begin{pmatrix}0&50&\infty&40&25&10\\50&0&15&20&\infty&25\\\infty&15&0&10&20&\infty\\40&20&10&0&10&25\\25&\infty&20&10&0&55\\10&25&\infty&25&550\end{pmatrix}$$

py代码

import networkx as nx
# create a undirected graphs.
G = nx.Graph()
G.add_node(1,name="1")
G.add_node(2)
G.add_node(3)
G.add_node(4)
G.add_node(5)
G.add_node(6)
# add edges with weight: price
G.add_edge(1, 2, price=50)
G.add_edge(1, 4, price=40)
G.add_edge(1, 5, price=25)
G.add_edge(1, 6, price=10)
G.add_edge(2, 3, price=15)
G.add_edge(2, 4, price=20)
G.add_edge(2, 6, price=25)
G.add_edge(3, 4, price=10)
G.add_edge(3, 5, price=20)
G.add_edge(4, 5, price=10)
G.add_edge(4, 6, price=25)
G.add_edge(5, 6, price=55)

sp= nx.dijkstra_path(G,1,4, weight='price') #路径
print(sp)


# 使用 Dijkstra 算法找到最短路径的长度  
sp_length = nx.dijkstra_path_length(G, 1, 4, weight='price')  
print("最短路径的总价格:", sp_length)


# 获取最短路径的长度  ，不一定是dij算法，会根据数据结构调整算法
shortest_path_length = nx.shortest_path_length(G, source=1, target=4, weight='price')  
print("从节点 1 到节点 4 的最短路径总价格:", shortest_path_length)

matlab

G = graph();  
  
 
G = addnode(G,6);  
 
% 添加带权重的边  
G = addedge(G, 1, 2, 50);  
G = addedge(G, 1, 4, 40);  
G = addedge(G, 1, 5, 25);  
G = addedge(G, 1, 6, 10);  
G = addedge(G, 2, 3, 15);  
G = addedge(G, 2, 4, 20);  
G = addedge(G, 2, 6, 25);  
G = addedge(G, 3, 4, 10);  
G = addedge(G, 3, 5, 20);  
G = addedge(G, 4, 5, 10);  
G = addedge(G, 4, 6, 25);  
G = addedge(G, 5, 6, 55);  
  

[dist, path] = shortestpath(G, 1, 4);  %注意接口顺序
plot(G) 
% 打印最短路径  
disp('最短路径长度：');  
disp(dist);  
disp('最短路径为：');  
disp(path);