图论的基本介绍

由于博主专业，在此不再赘述图论的基本知识算法。
想了解基础知识，请参考图论（一）基本概念与邻接矩阵

顺带一提：

• 对于有向图，只要写出邻接矩阵，直接使用Matlab命令：sparse，可以将邻接矩阵转化为稀疏矩阵的表示方式。
• 对于无向图，由于邻接矩阵是对称的，Matlab中只需要使用邻接矩阵的下三角元素
• 稀疏矩阵可以使用full命令变成普通矩阵。

最短路径问题

两个顶点之间的最短问题

Dijkstra算法

基本步骤：

1. 首先，定义一个数组 D，D[v] 表示从源点 s 到顶点 v 的边的权值，如果没有边则将 D[v] 置为无穷大。
2. 把图的顶点集合划分为两个集合 S 和 V-S。第一个集合 S 表示距源点最短距离已经确定的顶点集，即一个顶点如果属于集合 S 则说明从源点 s 到该顶点的最短路径已知。其余的顶点放在另一个集合 V-S 中。
3. 每次从尚未确定最短路径长度的集合 V-S 中取出一个最短特殊路径长度最小的顶点 u，将 u 加入集合 S，同时修改数组 D 中由 s 可达的最短路径长度。若加入集合 S 的 u 作为中间顶点时，vi 的最短路特殊路径长度变短，则修改 vi 的距离值（即当D[u] + W[u, vi] < D[vi]时，令D[vi] = D[u] + W[u, vi]）。
4. 重复第 3 步的操作，一旦 S 包含了所有 V 中的顶点，D 中各顶点的距离值就记录了从源点 s 到该顶点的最短路径长度。

Matlab代码及例子

Matlab代码实现

clc,clear all
a=zeros(6);
a(1,2)=50;a(1,4)=40;a(1,5)=25;a(1,6)=10;               
a(2,3)=15;a(2,4)=20;a(2,6)=25;
a(3,4)=10;a(3,5)=20;
a(4,5)=10;a(4,6)=25;
a(5,6)=55;
a=a+a'                                                  
a(find(a==0))=inf %将a=0的数全部替换为无强大               
pb(1:length(a))=0;pb(1)=1;  %当一个点已经求出到原点的最短距离时，其下标i对应的pb(i)赋1
index1=1; %存放存入S集合的顺序
index2=ones(1,length(a)); %存放始点到第i点最短通路中第i顶点前一顶点的序号
d(1:length(a))=inf;d(1)=0;  %存放由始点到第i点最短通路的值
temp=1;  %temp表示c1,算c1到其它点的最短路。
while sum(pb)<length(a)  %看是否所有的点都标记为P标号
tb=find(pb==0); %找到标号为0的所有点,即找到还没有存入S的点
d(tb)=min(d(tb),d(temp)+a(temp,tb));%计算标号为0的点的最短路，或者是从原点直接到这个点，又或者是原点经过r1,间接到达这个点
tmpb=find(d(tb)==min(d(tb)));  %求d[tb]序列最小值的下标
temp=tb(tmpb(1));%可能有多条路径同时到达最小值，却其中一个，temp也从原点变为下一个点
pb(temp)=1;%找到最小路径的表对应的pb(i)=1
index1=[index1,temp];  %存放存入S集合的顺序
temp2=find(d(index1)==d(temp)-a(temp,index1));
index2(temp)=index1(temp2(1)); %记录标号索引
end
d, index1, index2

Java代码实现

public class DijkstraAlgorithm {private final static int N = 10000;     // 约定 10000 代表距离无穷大public static void main(String[] args) {char[] vertexes = { 'A', 'B', 'C', 'D', 'E', 'F', 'G' };    // 顶点int[][] weight = {  	// 图的邻接矩阵/*A*//*B*//*C*//*D*//*E*//*F*//*G*//*A*/{0,   5,   7,   N,   N,   N,   2},/*B*/{5,   0,   N,   9,   N,   N,   3},/*C*/{7,   N,   0,   N,   8,   N,   N},/*D*/{N,   9,   N,   0,   N,   4,   N},/*E*/{N,   N,   8,   N,   0,   5,   4},/*F*/{N,   N,   N,   4,   5,   0,   6},/*G*/{2,   3,   N,   N,   4,   6,   0}};int source = 6; // 源点下标int[] dis = dijkstra(source, vertexes, weight);	// 使用迪杰斯特拉查找最短路径// 输出最短路径长度for (int i=0; i<dis.length; i++){System.out.println(vertexes[source] + "->" + vertexes[i] + " = " + dis[i]);}}/*** 迪杰斯特拉算法求解最短路径问题* @param source    源点下标* @param vertexes  顶点集合* @param weight    邻接矩阵* @return int[]    源点到各顶点最短路径距离*/public static int[] dijkstra(int source, char[] vertexes, int[][] weight){int[] dis;     // 记录源点到各顶点的最短路径长度,如 dis[2] 表示源点到下标为 2 的顶点的最短路径长度ArrayList<Character> S = new ArrayList<>(); // 存储已经求出到源点最短路径的顶点，即算法步骤中的 S 集合。/* 初始化源点 */dis = weight[source];S.add(vertexes[source]);/* 当 S 集合元素个数等于顶点个数时，说明最短路径查找完毕 */while(S.size() != vertexes.length){int min = N;int index = -1; // 记录已经求出最短路径的顶点下标/* 从 V-S 的集合中找距离源点最近的顶点 */for (int j=0; j<weight.length; j++){if (!S.contains(vertexes[j]) && dis[j] < min){min = weight[source][j];index = j;}}dis[index] = min;   // 更新源点到该顶点的最短路径长度S.add(vertexes[index]); // 将顶点加入到 S 集合中，即表明该顶点已经求出到源点的最小路径/* 更新源点经过下标为 index 的顶点到其它各顶点的最短路径 */for (int m=0; m<weight.length; m++){if (!S.contains(vertexes[m]) && dis[index] + weight[index][m] < dis[m]){dis[m] = dis[index] + weight[index][m];}}}return dis;}
}

每个顶点之间的最短路径

迭代使用n-1次Dijkstra算法

Floyd算法

Floyd算法是一个经典的动态规划算法。用通俗的语言来描述的话，首先我们的目标是寻找从点i到点j的最短路径。从动态规划的角度看问题，我们需要为这个目标重新做一个诠释（这个诠释正是动态规划最富创造力的精华所在）。
从任意节点i到任意节点j的最短路径不外乎两种可能：

• 一是直接从i到j，
• 二是从i经过若干个节点k到j。

所以，我们假设Dis(i,j)为节点u到节点v的最短路径的距离，对于每一个节点k，我们检查Dis(i,k) + Dis(k,j) < Dis(i,j)是否成立。
如果成立，证明从i到k再到j的路径比i直接到j的路径短，我们便设置Dis(i,j) = Dis(i,k) + Dis(k,j)，这样一来，当我们遍历完所有节点k，Dis(i,j)中记录的便是i到j的最短路径的距离。

c语言实现

#include <iostream>
#include <cstring>
#include <stack>
#include <queue>
using namespace std;const int MAX = 65535;class Graph{private:int** G;					// 邻接矩阵int** dist;					// 距离数组 int** path;					// 路径数组 int Nv;						// 顶点数public://构造函数Graph(int nv, int ne){this->Nv = nv;G = new int*[nv+1];dist = new int*[nv+1];path = new int*[nv+1]; for(int i = 0 ; i < nv+1 ; i++){G[i] = new int[nv+1];dist[i] = new int[nv+1];path[i] = new int[nv+1];memset(path[i],-1,sizeof(path[0][0])*(nv+1));for(int j = 0 ; j < nv+1 ; j++){this->G[i][j] = this->dist[i][j] = MAX;} this->G[i][i] = this->dist[i][i] = 0; }cout<<"请输入边与权重:"<<endl;for( i = 0 ; i < ne ; i++){int v1,v2,weight;cin>>v1>>v2>>weight;this->G[v1][v2] = this->G[v2][v1] = weight;this->dist[v1][v2] = this->dist[v2][v1] = weight;}	}//Floyd算法(多源最短路径算法) bool Floyd(){for(int k = 1 ; k < this->Nv+1 ; k++){	//k代表中间顶点 for(int i = 1  ; i < this->Nv+1 ; i++){//i代表起始顶点 for(int j = 1 ; j < this->Nv+1 ; j++){//j代表终点 if(this->dist[i][k] + this->dist[k][j] < this->dist[i][j]){this->dist[i][j] = this->dist[i][k] + this->dist[k][j];if(i == j && this->dist[i][j] < 0){//发现了负值圈 return false;}this->path[i][j] = k;}					}}}return true; }// 分治法寻找start到end最短路径的中间结点 void Find(queue<int> &q ,int start,int end){int mid = this->path[start][end];if(mid == -1){return;}Find(q,start,mid);q.push(mid);Find(q,mid,end);}//打印start顶点到end顶点的路径 void Print_Path(int start,int end){queue<int> queue;queue.push(start);this->Find(queue,start,end); queue.push(end);cout<<queue.front();queue.pop();while(!queue.empty()){cout<<"->"<<queue.front();queue.pop();}cout<<endl;}void Print_Floyd(){int i,j,k;for( i = 1 ; i < this->Nv+1 ; i++){for(int j = 1 ; j < this->Nv+1 ; j++){cout<<this->path[i][j]<<" ";}cout<<endl;} cout<<"	length		path"<<endl; for(i = 1 ; i < this->Nv+1 ; i++){for(j = i+1 ; j < this->Nv+1 ; j++){cout<<i<<"->"<<j<<"	";cout<<this->dist[i][j]<<"		"; 	this->Print_Path(i,j);}cout<<endl;}}
};int main()
{cout<<"请输入顶点数与边长数:"<<endl;int nv,ne;cin>>nv>>ne; Graph graph(nv,ne);if(graph.Floyd()){cout<<"各个顶点的最短路径为："<<endl; graph.Print_Floyd();}return 0;}

运行结果：

最小生成树

连通的无圈图叫作树，度为1的叫作叶子结点。

应用问题例子：欲修筑连接$n$个城市的铁路，已知$i$城与$j$城之间的铁路造价为$c_{ij}$,设计一个路线图，使得总造价最低。

Prim算法（以点为主，每次选择下一个中最小权重）

基本思想

例子：

Matlab实现：

clc;clear;
a=zeros(7);
a(1,2)=50;a(1,3)=60;
a(2,4)=65;a(2,5)=40;
a(3,4)=52;a(3,7)=45;
a(4,5)=50;a(4,6)=30;a(4,7)=42;
a(5,6)=70;
a=a+a';a(find(a==0))=inf;
result=[];
p=1;      %起点为1
tb=2:length(a);
while length(result)~=length(a)-1temp=a(p,tb);temp=temp(:);d=min(temp);[jb,kb]=find(a(p,tb)==d);j=p(jb(1));k=tb(kb(1));result=[result,[j;k;d]];p=[p,k];tb(find(tb==k))=[];
end
result

Kruskal算法(以边为主，每次选最小)

基本思想

将图的n个顶点看作n个分离的部分树，每个树具有一个顶点，算法的每一步就是选择连接两个分离树的具有最小权值的边，将两个树合二为一，直到只有一个树为止（进行n-1步）得到最小生成树。

例子：

我们使用边权矩阵进行存储数据，边权矩阵就是按列写入，每列由出发顶点、接收顶点和边的权值组成，如下所示：

%边权矩阵，每一列都表示一条边，从上到下分别为两个顶点以及它们边的权值
b = [1 1 1 2 2 3 3 4;2 4 5 3 5 4 5 5;8 1 5 6 7 9 10 3];
%sortrows函数对某一列进行比较排序，所以我们先转置b矩阵，然后对第三列也就是权值进行排序
[B,i]=sortrows(b',3);
%再将其转置回来
B=B';
%m为边的条数，n为点的个数
m=size(b,2);n=5;
%t数组用来标记选中的边，k用来计数，T矩阵用来存储选中的边，c计算最小生成树的总长度
t=1:n;k=0;T=[];c=0;for i=1:mif t(B(1,i))~=t(B(2,i))k=k+1;T(k,1:2)=B(1:2,i),c=c+B(3,i);tmin=min(t(B(1,i)),t(B(2,i)));tmax=max(t(B(1,i)),t(B(2,i)));for j=1:nif t(j)==tmaxt(j)=tmin;endendendif k==n-1break;end
end
T,c,

网络最大流

何为最大流问题？

参考博客网络流——最大流（全）

Matlab实现

最大流问题(maximum flow problem)，一种组合最优化问题，就是要讨论如何充分利用装置的能力，使得运输的流量最大，以取得最好的效果。管道网络中每条边的最大通过能力（容量）是有限的，实际流量不超过容量。

在数学建模的过程中时长会遇到这种问题，存在专门的算法去解决这一问题，但其实现较为复杂。

MATLAB提供了解决这一问题所使用的函数，即maxflow函数。

语法:

mf = maxflow(G,s,t)
mf = maxflow(G,s,t,algorithm)
[mf,GF] = maxflow(___)
[mf,GF,cs,ct] = maxflow(___)

符号说明：

• mf = maxflow(G,s,t) 返回节点 s 和 t 之间的最大流。如果图 G 未加权（即 G.Edges 不包含变量 Weight），则 maxflow 将所有图边的权重视为 1。
• mf = maxflow(G,s,t,algorithm) 指定要使用的最大流算法。此语法仅在 G 为有向图时可用。
• [mf,GF] = maxflow(___) 还使用上述语法中的任何输入参数返回有向图对象 GF。GF 仅使用 G 中具有非零流值的边构造。
• [mf,GF,cs,ct] = maxflow(___) 还返回源和目标节点 ID cs 和 ct，表示与最大流相关联的最小割。

创建并绘制一个加权图。加权边表示流量。

s = [1 1 2 2 3 4 4 4 5 5];
t = [2 3 3 4 5 3 5 6 4 6];
weights = [0.77 0.44 0.67 0.75 0.89 0.90 2 0.76 1 1];
G = digraph(s,t,weights);
plot(G,'EdgeLabel',G.Edges.Weight,'Layout','layered');

确定节点1到6的最大流:

mf = maxflow(G,1,6)

结果：

mf =1.2100

参考博客图的最大流问题（含matlab函数使用方法）

Matlab图论工具箱