本文借鉴了 数学建模清风老师的课件与数据。下面内容如有错误，欢迎大家指出！

更详细的内容可以参考清风老师的视频讲解

清风数学建模：https://www.bilibili.com/video/BV1DW411s7wi

目录

图的基本概念（白话解释）

推荐的在线作图的网站（不用翻墙就可以用）

如果英文部分看得有点吃力可以右键用浏览器翻译成中文

表示图的一种较为清晰的方式——权重邻接矩阵

无向图的权重邻接矩阵

有向图的权重邻接矩阵

---

图的基本概念（白话解释）

什么是图？点+连接点的边

图拿来干嘛用的？ 描述事物之间的特定关系（点表示事物，边表示关系）

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

目前学的图可以怎么分类？有向图/无向图 有权图/无权图

推荐的在线作图的网站（不用翻墙就可以用）

CS AcademyCSAcademy is a next generation educational platform. Discover computer science with interactive lessons and a seamless online code editor.https://csacademy.com/app/graph_editor/

 

如果英文部分看得有点吃力可以右键用浏览器翻译成中文

入门方式：

左上角

Undirected 和 Directed 表示的是选择无向图和有向图

Node Count：就是节点数量

Graph Data:显示的是节点的编号和关系，可以手动修改来增减节点以及修改关系，比如这样

可以自己动手试一下咯！

 

中间的0-index和1-index表示节点是从0开始计数还是从1开始计数

右边则是一些关于使用的说明：

注意是要在对应的模式之下点击会有不同的效果，比如你要删除边，就点击到删除的那一栏，然后再点击节点就可以删除了，就像这样

删除模式（删除节点和边）

 

绘制模式（创建节点和边）

 

编辑模式（修改节点的标签以及边的权值）

 

配置模式（自己修改配置）

 

表示图的一种较为清晰的方式——权重邻接矩阵

邻接矩阵的作用：便于看清楚顶点之间的相邻关系

无向图的权重邻接矩阵

比如这样一张图

 

表示成邻接矩阵是这样子的

 

横竖表头表示节点的序号，因为是要表示两两点之间的关系，所以需要用二维的数组表示，表格中的

数据表示两个点之间的距离/权重，inf为infinite(无穷大)

看表格我们很容易得到结论：

(1)无向图对应的权重邻接矩阵D是一个对称矩阵，且主对角线上元素为0；

(3)第i行第j列表示第i个节点到第j个节点的权重。

有向图的权重邻接矩阵

以下面的图为例

 

画成邻接矩阵之后是这样的

 

看图可以得到结论：

有向图和无向图的画邻接矩阵的方式都一样，只是因为有向图带有方向，所以节点之间的关系不是都是双向的，所以矩阵也不都是对称的，但是主对角线元素依然为0（自己到自己距离都是0）

关于迪杰斯特拉以及贝尔曼福特算法的内容可以去网络上找其他详细的介绍，这里安利一个演示算法的APP

APP：算法动画图解

苹果下载：在AppleStore中有

安卓下载：

链接：百度网盘 请输入提取码 提取码：i061