一个简陋的个人小项目，也是个人第一个真正意义上的独立项目——Graph

由来

我最早接触到图这个概念是在大二的离散数学当中图论相关的内容，当时是以著名的哥尼斯堡七桥问题引出图论的概念，现在依然记忆犹新（不过只是记得这个名字，具体的解题思路我重新温习了一下才想起来），当时也提出了求最短路径的迪杰斯特拉算法，不过没有用编程语言具体实现。

之后在数据结构的学习中，又出现了图的相关知识，提出了在计算机中存储图的几种方式，我们学校的课程中学习的是邻接表和邻接矩阵，同时也用编程语言实现了具体的算法。

离散数学中的图用几何图形表示，清晰明了，但实现算法时步骤不清晰；邻接矩阵和邻接表适合实现算法，但可视化效果不好，只能用字符串输出。那么能不能写一个小项目，既能实现算法，又能用可视化较好的形式显示出来呢？之前其他人可能也写过同样功能的项目，但这个想法是我自己独立提出的，而且我有一套自己独特的实现方法，至于实现方法，请看下文详细讲解。

DOT 语言

DOT 语言是贝尔实验室发明的绘图语言，它可以非常方便地绘制出数学概念中的图，包括有向图和无向图，可以在顶点内添加信息，也可以在边上添加信息，还可以设置不同的顶点形状和边的形状等等功能，它的文档在此：https://graphviz.gitlab.io/_pages/doc/info/lang.html

下面我给出一个 DOT 语言的使用示例，代码和绘图效果如下：

graph g{
    a--b--c,d--a
}

我是在使用 Markdown Preview Enhanced 插件的过程中了解到了 DOT 语言。在 Graph 项目中，DOT 语言是非常重要的一环，它就可以实现将文本到可视化图形的转换

DOT 语言最早是在桌面端的一个应用程序叫做 Graphviz 中实现的，不过现在已经有人在浏览器端用一个名为 Viz.js 的工具来实现了，也正符合了那句话：“能用 js 实现的功能，最终一定会用 js 实现”。Viz.js 也是这个项目主要的依赖文件

Graph 项目目前实现的功能

• 输入邻接矩阵生成无向图
• 输入邻接矩阵生成有向图
• 输入邻接表生成无向图
• 输入邻接表生成有向图
• 输入邻接矩阵、开始点和结束点的信息，计算最短路径并生成可视化结果
• 输入邻接表、开始点和结束点的信息，计算最短路径并生成可视化结果

Graph 项目的简要工作流程

Graph 项目的 Github 地址

GitHub - aopstudio/Graph: 将邻接矩阵和邻接表转换为可视化的图 将邻接矩阵和邻接表转换为可视化的图. Contribute to aopstudio/Graph development by creating an account on GitHub. GitHub - github.com

生成的 HTML 文件的位置

• 完整的有向图或无向图：D:/graph.html
• 要求的最短路径示意图：D:/shortestPath.html

主函数代码分析和使用效果

目前我还没有写输入模块，只能在源代码中给定数据来生成图。在源代码中给出五个顶点，

String[] nodes= {"北京","上海","台北","泰州","宁波"};

初始化邻接矩阵的边矩阵，再给定边的权值

int[][] m=new int[nodes.length][nodes.length];
m[0][1]=1213;
m[1][4]=200;
m[1][2]=900;
m[4][2]=600;
m[0][3]=1200;
m[3][4]=400;

将存储边信息的 m 和存储顶点信息的 node 包装成我自定义的数据结构 MatrixGraph

MatrixGraph mg=new MatrixGraph(m,nodes);

调用 MatrixGraph 的 generateDG 方法生成完整图的 DOT 语言代码，调用 shortestPath 生成最短路径示意图的 DOT 语言代码，这里输入的参数 0 和 4 代表顶点编号，0 是指北京，4 是指宁波，也就是求从北京到宁波的最短路径

String graph=mg.generateDG();
String shortestPath=mg.printShortestPath(0, 4);

再将 DOT 语言代码嵌入到 HTML 代码中

String html1=GenerateHTML.Generate(graph);
String html2=GenerateHTML.Generate(shortestPath);

最后将 HTML 代码写入文件

WriteFile.write(html1);
WriteFile.writeShortest(html2);

生成的效果如下：

• 完整图
  
• 最短路径示意图