有向图和无向图

本讲将简要介绍图论中的基本概念，并主要讲解图论中的最短路径问题。根据图的不同，我们将学习两种不同的算法：迪杰斯特拉Diijkstta算法和Bellman-Ford（贝尔曼-福特）算法。

图论中的图（Graph)是由若干给定的点及连接两点的线构成的图形，这种图形通常用来描述某些事物之间的某种特定关系，用点代表事物，用连接两点的线表示相应两个事物具有这种关系。

一个图可以用数学语言描述为G(V(G),E(G))。V表示的是图的顶点集，E指的是图的边集。

根据边是否有方向，可将图分为有向图和无向图。

另外，有些图的边上还可能有权值，这样的图成为有权图。

画图工具：

https://csacademy.com/app/graph_editor/ 这个网站进入时有点慢但是好玩的一批！

matlab做图

① 无向图：

函数graph(s,t)，可在s和t中的对应节点之间创建边，并生成一个图。

s和t都必须具有相同的元素数，这些节点必须都是从1开始的正整数，或都是字符串元胞组。

点的编号最好从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, linewidth, 2)  % 设置线的宽度
% 下面的命令是在画图后不显示坐标
set( gca, XTick, [], YTick, [] );

matlab做的图还是有一些模糊，如果节点数不是特别多的话还是建议使用线上作图的方式。

无向图的权重邻接矩阵

无向图对应的权重邻接矩阵： D i j = [ 0 i n f 3 3 i n f 0 i n f 5 3 i n f 0 2 3 5 2 0 ] D_{ij} = egin{bmatrix} 0& inf &3&3\ inf& 0 &inf&5\ 3& inf &0&2\ 3& 5 &2&0\ end{bmatrix} Dij=⎣ ⎡0inf33inf0inf53inf023520⎦ ⎤ 邻接矩阵表示从i到j的权重

结论： ①无向图对应的权重邻接矩阵 D i j D_{ij} Dij是一个对称矩阵； ②其主对角线上元素为0； ③ D i j D_{ij} Dij表示第 i i i 个节点到第 j j j个节点的权重；

有向图的权重邻接矩阵

有向图对应的权重邻接矩阵： D i j = [ 0 i n f 8 3 i n f 0 i n f 5 8 i n f 0 2 i n f i n f i n f 0 ] D_{ij} = egin{bmatrix} 0& inf &8&3\ inf& 0 &inf&5\ 8& inf &0&2\ inf& inf &inf&0\ end{bmatrix} Dij=⎣ ⎡0inf8infinf0infinf8inf0inf3520⎦ ⎤ 邻接矩阵表示从i到j的权重

结论： ①有向图对应的权重邻接矩阵 D i j D_{ij} Dij一般不是对称矩阵； ②其主对角线上的元素为0； ③ D i j D_{ij} Dij表示第 i i i个节点到第 j j j个节点的权重；