图论最短路径问题（一）

 图的基本概念

总概念：图论中的图是由若干给定的点及连接两点的线构成的图形，表示事物之间的特定关系

点：表示事物

线：表示相应两个事物之间具有某种的特定关系

数学语言描述：G(V(G),E(G)),V表示顶点集，E表示图的边集

图的分类：

• 边是否有方向：分为有向图（无向图的特例）和无向图
• 边上是否有权值：分为有权图和无权图

在线作图网站

​​https://csacademy.com/app/graph_editor/​​

MATLAB作图

无向图制作

无权重

%% Matlab作无向图
% （1）无权重（每条边的权重默认为1）
% 函数graph(s,t)，s和t表示对应的结点
% s 和 t 都必须具有相同的维数
% 这些节点必须都是从1开始的连续的正整数
s1 = [1,2,3,4];
t1 = [2,3,1,1];
G1 = graph(s1, t1);
plot(G1)

% 字符串元胞数组用大括号包
s2 = {'学校','电影院','网吧','酒店'};
t2 = {'电影院','酒店','酒店','KTV'};
G2 = graph(s2, t2);
plot(G2)

% 不显示坐标
set( gca, 'XTick', [], 'YTick', [] );  

有权重

% 可在s和t中的对应节点之间以w的权重创建边
s = [1,2,3,4];
t = [2,3,1,1];
w = [3,8,9,2];
G = graph(s, t, w);
plot(G, 'EdgeLabel', G.Edges.Weight)   %调用权重的标签

有向图制作

% 无权图 digraph(s,t)
s = [1,2,3,4,1];
t = [2,3,1,1,4];
G = digraph(s, t);
plot(G)  

% 有权图 digraph(s,t,w)
s = [1,2,3,4];
t = [2,3,1,1];
w = [3,8,9,2];
G = digraph(s, t, w);
plot(G, 'EdgeLabel', G.Edges.Weight)   

权重邻接矩阵

无向图

• 无向图对应的权重邻接矩阵是对称矩阵
• 主对角线元素为0
• 表示第i个节点到第j个节点的权重

有向图

• 有向图对应的权重邻接矩阵不一定是对称矩阵
• 主对角线元素为0
• 表示第i个节点到第j个节点的权重