图论算法理论实现及
① 图论算法matlab实现问题
参考楼上给的链接，稍微做了一点修改，供参考。
修改的地方包括：
1、原程序为函数，提供了邻接矩阵和关联矩阵的双向转换，这里针对楼主的需求改为脚本，直接运行即可将邻接矩阵转为关联矩阵。
2、部分语句修改更符合MATLAB的通行写法，如：
sum(sum(F))改为sum(F(:))，
W(i,k)=1; W(j,k)=1;改为W([i j],k)=1;
3、考虑到邻接矩阵为对称阵，第二个for循环改为只针对半个矩阵，减少计算量（对于楼主的这个具体作用微乎其微）。
4、原程序有错误，在else分支fprint为fprintf之误（其实我看到该程序的第一眼就注意到了这个错误，担心还存在其它问题，所以进行了改写）。
F=[0 1 1 1;1 0 1 1;1 1 0 1;1 1 1 0]; % 邻接矩阵
m = sum(F(:))/2; % 图的边数
n = size(F,1); % 顶点数
W = zeros(n,m);
k=1;
for i = 1:n
for j = 1:i
if F(i,j)~=0
W([i j],k)=1;
k = k + 1;
end
end
end
W
② 简介图论算法
图论101
图论是数学的一个非常广泛哪誉的分支，非常适用于现实世界中的问题。 最初，图论是"发明"来解决现实问题的，此后，它像所有其他数学分支一样，被抽象数学家所劫持。
在本教程和后续教程中，我们将介绍一些图论算法及其在python中的实现。 现在，回到主题。
简而言之，图是一组顶点/节点和边。 如果您对" set"不满意，请用collection代替。
在上图中，顶点/节点将是人物。
顶点是图的基本单位。 它几乎可以代表任何实体，通常以圆圈表示。
在上图中，连接袭缓陪人的线是边。
顶点之间的线或连接称为边。 它可以表示顶点之间的任何类型的关系。
边上具有方向的图称为有向图。 它可以用来显示与前辈（从父母到孩子的箭头）或祖先（从孩子到父母的箭头）的关系。
边上没有方向的边的图称为无向图。 它可用于显示双向道路。
边上带有数字的图形，代表交易成本，旅途公平，城市之间的距离等。它可以具有任何类型的边。
没有循环的无向图是一棵树。 在这里，循环意味着只有一种方法可以通过跟随给定其他节点的边缘来到达节点。
一棵树的所有节点都通过一条边连接到其他某个节点，并且有N个节点的N-1个边。
表示图形的方法有很多，最常见的两种是：
假设图中有N个节点。 我们可以使用具有N行和N列的矩阵来表示它，其中该矩阵的行和列将代表一个节点，并且其中的条目代表有向边（有或没有权重）。
它们形成代表行的节点到代表列的节点。 通常，0或无穷大用于表示节点之间没有边缘。 在Python中，邻接矩阵可以表示为：
类似地，对于拍蠢N个节点的图，我们可以使用邻接表来表示该图，其中节点的所有边都保留在元组列表（节点，权重）中。 在python中，它可以表示为：
我使用嵌套字典（这就是我所说的）和带集合的字典（如果节点没有权重的边）来表示图。
在下一篇文章中，我将使用不同的方法发布精心设计的图类的Python代码，我们将使用该代码来实现图算法。
(本文翻译自sleepingFish的文章《Graph Theory Algorithms "Simplified"》，参考：https://medium.com/better-programming/graph-theory-algorithms-simplified-9a6868cc222)
③ 求图论的生成子图算法，要求生成尽可能多的子图
在图论的历史中，还有一个最着名的问题－－四色猜想。这个猜想说，在一个平面或球面上的任何地图能够只用四种颜色来着色，使得没有两个相邻的国家有相同的颜色。每个国家必须由一个单连通域构成，而两个国家相邻是指它们有一段公共的边界，而不仅仅只有一个公共点。20世纪80-90年代曾邦哲的综合系统论（结构论）观将“四色猜想”命题转换等价为“互邻面最大的多面体是四面体”。四色猜想有一段有趣的历史。每个地图可以导出一个图，其中国家都是点，当相应的两个国家相邻时这两个点用一条线来连接。所以四色猜想是图论中的一个问题。它对图的着色理论、平面图理论、代数拓扑图论等分支的发展起到推动作用。 （下图是在上下对折再左右对折以后形成一个轮胎形状，有7个区域两两相连，就是说在一个环面上作图，需要7种颜色，外国数学家构造林格证明：Np=[(7+√1+48p)/2]，p=1，N1=7。
图论中最着名的四色猜想解决办法 韩世君利用三角形性质和数学归纳法解决了四色猜想 摘要：将平面图的不相连点使其相连（这样增加着色难度），形成有许多三角形相连的平面图，根据三角形的稳定性，利用数学归纳法，平面图进行着色最多需4种颜色。 定理：在平面图中,对不同顶点进行着色,相邻顶点着不同颜色,不相邻顶点着相同颜色,则最多需4种颜色。 证明：在平面图中，不在同一直线上的三点决定一个平面，那么三点构成的三角形是平面图中最基本、最简单、最稳定、密闭的图形。 由于在对地图着色过程中不考虑图的具体形状只考虑点是否相邻，将平面图的不相连点使其相连（这样增加着色难度），形成有许多三角形相连的平面图（三点以下肯定成立）。如图1：添加辅助线（不相邻的点使其相邻，这样就增加了着色的色数，有利于证明），将图1分解为4个△ABC。 在平面图中的无数点中，任取相邻三点构成各点相邻的△ABC（见图2），则需3种颜色A B C,在平面图中再任取一点 D 与 A B C 三点相邻,同时D又与A B C三点相连后形成三角形。任取一点E与 A、B、C、D四色相连，E必与四色之一色相同即E点在△ABD中与C色相同、在△ACD中与B色相同、在△BCD中与A色相同、在△ABC外与D色相同，E与另外三色相连形成新的三角形。 在三角形的三点之外任取一点只有在三角形的内部和外部两种情况且这两种情况的点不会相邻，该点最多与三角形的三点相连且又形成新的三角形。 继续选取一点进行着色，该点同样最多与三角形的三点相连且又形成新的三角形，该点至少为四色中的一色。逐点（第n点）着色至将所有点（第n+1点）着色只须A、B、C、D四色其中一色。 图的着色方法：任意一张地图，将孤立的点用一种颜色着色（A色），不能形成密闭图形的相连的点用两种颜色（A、B色）。将剩余的点不相连的用虚线使其相连形成许多三角形，完全不相连的图不进行相连。任取相连三点着三种颜色（A、B、C色），再取与其相连的点，如果与A、B、C三色的点都相连着D色，否则着与其不相连的其中一色，用虚线相连的点可以用同一种颜色也可以用两种颜色，依次取与着色的点相连的点用以上方法进行着色。这样对所有的点进行着色最多用四色（A、B、C、D色）。 图论的广泛应用，促进了它自身的发展。20世纪40-60年代，拟阵理论、超图理论 、极图理论，以及代数图论、拓扑图论等都有很大的发展 拓扑学在泛函分析、李群论、微分几何、微分方程和其他许多数学分支中都有广泛的应用。 （右图是：下面的三叉安在上面的环面上，就是有3个洞的9个两两相连区域，上面的图上下对折再左右对折就是一个轮胎形状环面图2）
左图是亏格为4时10个两两相连区域构造，上图上下对折，再左右对折，形成一个轮胎形状，再把下面的四叉按照A,B,C,D编号安上，就是有4个洞的两两相连区域图3（王晓明构造）。
④ 图论算法的介绍
图论算法在计算机科学中扮演着很重要的角色，它提供了对很多问题都有效的一种简单而系统的建模方式。很多问题都可以转化为图论问题，然后用图论的基本算法加以解决。遗传算法是解优化问题的有效算法，而并行遗传算法是遗传算法研究中的一个重要方向，受到了研究人员的高度重视。
⑤ 图论算法及其MATLAB实现的图书目录
第1章 图论的基础知识1
1.1图论的起源1
1.2着名的图论学者——欧拉1
1.3图2
1.4特殊图类3
1.5有向图4
1.6图的矩阵表示5
1.6.1邻接矩阵5
1.6.2关联矩阵5
1.7图论的基本性质和定理6
1.8计算有向图的可达矩阵的算法及其MATLAB实现6
1.9关联矩阵和邻接矩阵的相互转换算法及其MATLAB实现7
习题一11
第2章 最短路12
2.1路12
2.2最短路问题13
2.3求连通图最短距离矩阵的算法及其MATLAB实现14
2.4求两点间最短路的Dijkstra算法及其MATLAB实现15
2.4.1 Dijkstra算法16
2.4.2 Dijkstra算法的MATLAB实现16
2.5求两点间最短路的改进的Dijkstra算法及其MATLAB实现18
2.5.1 Dijkstra矩阵算法Ⅰ18
2.5.2 Dijkstra矩阵算法Ⅱ18
2.6 求两点间最短路的WarshallFloyd算法及其MATLAB实现21
2.6.1 Floyd算法的基本思想22
2.6.2 Floyd算法的基本步骤22
2.6.3 WarshallFloyd算法的MATLAB实现22
2.7求任意两点间最短路的算法及其MATLAB实现25
2.8求从一固定点到其他所有点最短路的算法及其MATLAB实现27
2.9求必须通过指定两个点的最短路的算法及其MATLAB实现29
2.10求图的两顶点间最短路与次短路的算法及其MATLAB实现32
2.11求最大可靠路的算法及其MATLAB实现34
2.12求最大期望容量路的算法及其MATLAB实现36
习题二38
第3章 连通图40
3.1判断图的连通性算法及其MATLAB实现40
3.2连通图的中心和加权中心的算法及其MATLAB实现42
3.3连通无向图一般中心的算法及其MATLAB实现44
习题三46
第4章 树48
4.1树及其性质48
4.2割点、割边、割集50
4.3二元树与Huffman树51
4.3.1有序二元树51
4.3.2 Huffman树51
4.4求Huffman树及其MATLAB实现52
4.5广度优先搜索算法及其MATLAB实现55
4.6深度优先搜索算法及其MATLAB实现57
4.7求割点算法及其MATLAB实现61
4.8生成树及其个数65
4.9求无向图的生成树算法及其MATLAB实现67
4.10求有向图的生成树算法及其MATLAB实现69
4.11求有向连通图的外向树与内向树数目的算法及其MATLAB实现71
4.12最小生成树问题73
4.13求最小生成树的Kruskal算法及其MATLAB实现74
4.13.1 Kruskal算法的基本思想74
4.13.2 Kruskal算法的MATLAB实现74
4.14求最小生成树的Prim算法及其MATLAB实现76
4.14.1 Prim算法的基本思想76
4.14.2 Prim算法的MATLAB实现77
习题四79
第5章Euler图和Hamilton图81
5.1 Euler图81
5.2“一笔画”问题及其理论81
5.3中国邮递员问题82
5.4 Fleury算法及其MATLAB实现82
5.4.1 Fleury算法的步骤82
5.4.2 Fleury算法的MATLAB实现82
5.5 Hamilton图87
5.6旅行售货员问题88
5.7改良圈算法及其MATLAB实现89
习题五92
第6章 匹配问题及其算法93
6.1问题起源——婚配问题93
6.2二分图的有关知识93
6.3匹配、完美匹配、最大匹配93
6.4匹配的基本定理94
6.5应用案例——BernolliEuler错放信笺问题95
6.6寻求图的一个较大基数匹配算法及其MATLAB实现95
6.7人员分配问题97
6.8匈牙利算法及其MATLAB实现97
6.8.1匈牙利算法基本步骤97
6.8.2匈牙利算法的MATLAB实现98
6.8.3案例及其MATLAB实现100
6.9最优分配问题101
6.10 KuhnMunkres算法及其MATLAB实现101
6.10.1 KuhnMunkres算法的基本思想101
6.10.2利用可行顶点标记求最佳匹配的KuhnMunkras算法步骤102
6.10.3 KuhnMunkres算法的MATLAB实现102
6.10.4简单实验105
习题六107
第7章 网络流的算法108
7.1网络、流和割108
7.1.1网络和流108
7.1.2割109
7.2网络的最大流问题110
7.3最大流最小割定理110
7.4 FordFulkerson标号算法及其MATLAB实现111
7.4.1 FordFulkerson标号算法的基本步骤111
7.4.2 FordFulkerson 标号算法的MATLAB实现112
7.4.3案例及其MATLAB实现113
7.5 Dinic算法及其MATLAB实现114
7.5.1 Dinic算法的基本思想114
7.5.2 Dinic算法的MATLAB实现115
7.5.3案例
⑥ 基于图论的最小多边形自动搜索算法
图是由点集和边集所构成的抽象概念，图的性质实质上可以表现为拓扑关系。如图4.8b所示，点集由分叉点构成(4个分叉点，分别是1，2，3，4)，边集则由地层线构成(7条地层线，分别是①，②，③，④，⑤，⑥，⑦)。需要说明的是，这里的边是广义上的边，可能是直线段，也可能是多线段。
最小多边形的自动搜索在GIS的空间分析中应用较多，搜索可分为无拓扑和含拓扑两类。无拓扑自动搜索则完全依靠几何计算来判断，如夹角变化趋势的多边形自动搜索算法(梁晓文等，2005)，该算法主要依靠弧段间夹角计算来判断，通过“左转”或“右转”的方法能够唯一确定最小多边形，原理简单，但程序设计过程极其烦琐。采用图论的方法来实现，原理相对复杂，需要掌握数据结构知识，但程序代码设计过程比较简洁，具有扩展性。
为了简单起见，以图4.8b中地层线①为例，说明搜索过程。从分叉点1开始，沿地层线①在分叉点2与地层线②和③邻接，地层线②和③又分别在分叉点3和4与两地层线邻接。整个邻接关系可以用一个树(tree)型结构来表示(图4.10)，终止条件是回到分叉点1，形成闭合回路或者出现自相交，则停止搜索。这样，产生4条有意义的多边形为：1-①-2-②-3-⑥-1，1-①-2-②-3-④-4-⑤-1，1-①-2-③-4-④-3-⑥-1，1-①-2-③-4-⑤-1。
图4.10 分叉点1沿①为起始方向的连通图
在上述4条连通多边形中，面积最小者对应的就是一个最小多边形(周秋生，1996)。若多边形点对为(x1，y1)，(x2，y2)，…，(xn，yn)，面积可采用下式来计算：
S=
最终，得到3个最小多边形。从图论的观点来看，所研究的图是一个连通的平面图。若图有n个分叉点，m条广义边，p个最小多边形，则平面图的面数(包括外部面)f=p+1。
根据欧拉公式(孙家广，1998)：
f+m-n=2 (4.2)
可以得到最小多边形数目为
p=m-n+1 (4.3)
见图4.4b中，m=7，n=5，则p=7-5+1=3。据此可以作为搜索结果正确与否的判断方式之一。
⑦ 图论算法及其MATLAB实现的图书前言
图论算法广泛应用于物理、化学、运筹学、计算机科学、电子学、信息论、控制论、网络理论、管理科学、社会科学等众多学科领域。随着这些学科的发展，特别是计算机科学的快速发展，又大大促进了图论和其他学科的发展。
图论算法是计算机科学的核心。近几年，随着强有力的MATLAB等数学软件的迅速发展，图论算法在数学和计算机等各学科方面的应用越来越广泛，从而使各学科的研究者越来越多地重视图论算法及其MATLAB实现和典型案例，而市场上又缺少这方面的指导性书籍。
本书将图论的基础知识、图论的着名问题以及相应的MATLAB程序代码和简单实例完美地结合在一起，力求语言简洁易懂，问题广泛有趣，算法科学，实例浅显，增强MATLAB实现的技巧性和操作性。读者可以通过简单案例，把图论的重要算法与MATLAB编程完美结合。
本书力求内容丰富，各章节相互联系，具备指导性书籍的系统性、科学性、实用性和引导性；同时，各章又相对独立，自成体系，为读者提供极大方便。
本书的创新之处在于，每一章均以着名实际问题为引入点，以图论算法为指导线，运用简单案例达到与MATLAB实现的完美结合，真正让各层次的读者学会运用图论理论解决实际问题，从而培养读者的图论思维，使读者惊叹图论方法的美妙与魅力。最后还为读者提供了当今图论标号方面等未解决的问题。
本书将在每一章节中给出着名图论的算法步骤及其一般MATLAB程序；同时，紧随每个案例分析，均给出解决问题的MATLAB源程序，这样对于初学者来说，具有很强的编程操作性。
本书是在中国地质大学（北京）王海英多年专业讲义的基础上重新修订编写而成，其中，山东体育学院体育运动学校的李传涛完成了本书程序的编写工作；中国科学院数学与系统科学院的黄强完成了本书全部程序的调试、修改和图形绘制等工作，