经典图论算法

① 数学图论中有哪些典型模型

偶图模型
凡涉及两类事物间的联系（即只考虑两类事物间的联系，而不考虑同类事物间的联系），均可抽象成偶图模型。作图时，将两类事物分成两行或者两列。这类模型通常被包含在后续的模型中，但因许多现实问题可抽象成该模型，所以单列出来讨论。
(1) 仓库与销售间
M：点代表仓库或销售点，连线代表仓库与销售店间的关联
(2) 上课安排问题
Q：学校有6位教师将开设6门课程。六位教师的代号是Xi（i=1,2,3,4,5,6)，六门课程代号是Yi （i=1,2,3,4,5,6)。已知，教师X1能够胜任课程Y2和Y3；教师X2能够胜任课程Y4和Y5；教师X3能够胜任课程Y2；教师X4能够胜任课程Y6和Y3；教师Y5能够胜任课程Y1和Y6；教师X6能够胜任课程Y5和Y6。
M：点表示教师或者课程，连线表示当且仅当该教师能胜任该课程
2.2 最短路模型
凡涉及到最小状态转换问题，均可转化为最短路模型。点表示允许的状态，连线表示状态的转换（可逆与不可逆分别对应于无向图、有向图）。
(1) 最短航线
M：点表示城市，连线表示当且仅当两城市有直达航线，并在该线上注明两城市的距离，即权值
A：问题转化为求两点间的最短路径
(2) 状态转换
Q：某两人有一只8升的酒壶装满了酒，还有两只空壶，分别为5升和3升。求最少的操作次数能均分酒。
M：设x1,x2,x3分别表示8,5,3升酒壶中的酒量，则
点表示组合(x1,x2,x3) ,连线表示当且仅当可通过倒酒的方式相互变换
A：问题转化为在该图中求点(8,0,0)到点(4,4,0)的一条最短路
(3) 狼羊菜渡河
Q：在一河岸有狼，羊和卷心菜。摆渡人要将它们渡过河去，由于船太小，每次只能载一样东西。由于狼羊，羊卷心菜不能单独相处。问摆渡人至少要多少次才能将其渡过河？
M：但是以下组合不能允许出现：狼羊菜，羊菜，狼羊，人，人狼，人菜，共6种。岸上只能允许出现10种组合：人狼羊菜，人狼羊，人狼菜，人羊，空，菜，羊，狼，狼菜，人羊菜。
点表示可允许的组合，连线当且仅当两种情况可用载人(或加一物)的渡船相互转变。
A：问题转化为求由顶点“人狼羊菜”到顶点“空”的一条最短路。
2.3 最小生成树模型
道路铺设
Q：道路铺设，使得任意两个地方均可达，并且费用最小
M：点表示工厂(假设是工厂)，任意两点连线，并标出铺设需要的费用
A：问题转化为求该图的最小生成树
2.4 欧拉图模型
通俗地讲，G是欧拉图当且仅当G存在经过每条边恰好一次，并且回到起始点的迹。
(1) 哥尼斯堡七桥问题
Q：能否从一点出发，走遍7座桥，且通过每座桥恰好一次，最后仍回到起始地点
M：点表示陆地，连线表示桥
A：问题转化为G是否存在E图
(2) 中国邮递员问题
Q：邮递员必须走过他投递范围内的每一条街道至少一次，选择一条尽可能短的路线
M：点表示路口，连线表示当且仅当两路口有直达街道
A：若G是E图，通过Fleury算法构造Euler环游，即为所求。否则，按一定规则添加重复边，再用Fleury算法构造Euler环游。
2.5 哈密尔顿圈模型
(1) 旅行售货员问题——TSP
一售货员要到若干城市去售货，每座城市只经历一次，问如何安排行走路线，使其行走的总路程最短。
例子：
Q：一电脑代理商要从她所在城市出发，乘飞机去六个城市，然后回到出发点，如果要求每个城市只经历一次，能否办到？给出行走方案。
M：点表示城市，连线表示两城市有直达航线
A：该图是否存在H圈
(2) 圆桌会议座位安排
Q：若干人围圆周开会，每个人会不同的语言，如何安排座位，使得每个人能够和他身边的交流
M：点表示人，连线表示当且仅当两个人能交流，即至少会同一种语言。(可能你一下子想到的偶图模型，的确该问题可以抽象成偶图模型，但很难转化为图论问题)
A：给出该图的一个H圈
2.6 匹配模型
(1) 旅游座位安排
Q：有一个旅行团要组织一批人去旅游，其中一些人是朋友他们要乘坐公共汽车去，而车上的位子是成对的。因此为了让大家旅途更愉快，旅行团负责人需要将成对的朋友安排在一起。给出一种安排方案。
M：点表示旅行团的人，连线表示当且仅当两人是朋友
A：求该图的最大匹配
(2) 研究生找工作
Q：学生能找到理想工作吗？
M：点表示研究生或者工作，连线表示当且仅当学生申请了该工作
A：问题转化为求饱和每个顶点的一个匹配，即完美匹配
(3) 最优分派问题
M：点表示工作或者人员，构造完全偶图，边的权值表示该工人做此份工作的效率
A：问题转化为求该图的最优匹配
2.7 平面图模型
平面模型可以这样理解，交通网络，使得不交叉，且无需修高架桥、隧道（这里的隧道显然跟山洞不同）
(1) 电路板设计问题
Q: 连接电路元件间的导线间不能交叉。否则，当绝缘层破损时，会出现短路故障。
M；点表示电路元器件，连线表示元器件间的连接
A；该图是否可平面
(2) 景区空调管道的设计
M：点表示景区，连线表示当且仅当两景点间要铺设空调管道
A：能否把上图画在平面上，使得边不会相互交叉？
(3) 3间房子和3种设施问题
Q：要求把3种公用设施(煤气，水和电)分别用煤气管道、水管和电线连接到3间房子里，要求任何一根线或管道不与另外的线或管道相交，能否办到？
M：点表示公用设施或者房子，连线表示该类公用设施连接到该房子
A：抽象出来的图是否可平面嵌入
2.8 着色模型
点着色问题对应于顶点集合的一种划分方式，对应于分类问题。边着色对应于边集合的一种划分方式，也对应于分类问题。区分点着色模型和边着色模型，主要在于抽象出来的模型，是相邻的顶点还是相邻的边不能着同一种颜色。
(1) 点着色模型
① 考试时间安排
Q：使得学生们不会有相互冲突的考试，最小安排数
M：点表示待考的课程，连线表示至少有一个学生同时选择这两门课
A：问题转化为求该图的点色数(把互不冲突的课程、考试安排在同一个时间段完成)
② 课程安排问题
Q: 学生选择课程中，使得学生选课不会发生冲突，如何制订一张课时数尽可能小少的课表
M：点表示课程，连线表示当且仅当有某个学生同时选了这两门课程
A：问题转化为求该图的点色数
③ 交通灯的相位设置问题
Q：为了(最终)让所有的车辆都能够安全通过路口，对于交通灯来说，所需要的相位的最小数是多少
M：点表示车道，连线当且仅当两个车道上的车不能同时安全地进入路口
A：问题转化为求该图的点色数
(2)边着色模型
① 排课表问题
Q：设有m位教师，n个班级，其中教师xi要给班级yj上pij节课。求如何在最少节次排完所有课。
M：令X=｛x1,x2,…,xm｝, Y=｛y1,y2,…,yn｝,xi与yj间连pij条边，得偶图G=(X, Y)。
A：问题转化为求该图的边着色数
(2) 比赛安排问题
Q：最少天完成比赛
M：点表示参赛人，连线当且仅当两人有比赛
A:问题转化为求一种最优边着色，即用最少色数进行正常边着色
2.9 覆盖模型
覆盖模型，对应于控制问题，通俗地讲点覆盖对应于用最少的点来控制所有边(即任一边至少有一个顶点在点独立集中)，边覆盖对应于用最少的边控制所有的点。均对应于控制问题。
(1) 哨站设计
Q：城市设置哨岗，使得哨兵能监管所有街道的最少哨岗数
M：点表示交叉口，连线表示存在直达街道
A：问题转化为求该图的点覆盖
2.10 强连通性定向图模型
(1) 城市交通网设计问题
Q：一座城市为某种需要，要把所有街道改为单行道，使得人们在任意两个位置都可以相互到达。如何设计单行道方向
M：顶点表示街道交叉口，连线当且仅当存在直达街道
A：问题等价于在模型图中给出其强连通定向
(2) 竞赛图
M：循环比赛的结果可以用所谓的“竞赛图”来表示。u队战胜了v队，则由点u向v画一条有向边。显然，“竞赛图”是完全图的一种定向图。

② 求经典图论教材图论及其应用（邦迪）清晰点的电子版

邮 箱？？？？？

③ 图论算法的教材

我想很多学习图论的人都知道J.A. Bondy和U.S.R. Murty着的《Graph Theory with Application》(Elsevier,1976)是图论教材中的经典，时至今日，仍不失为初学者较好的入门书。还记得兰州交通大学的张忠辅教授说过，国内第一届图论学会就是把大家集中起来学习邦迪的《Graph Theory with Application》，由此可见这本书对国内图论届的影响是如此之大。吴望名等人将其译成中文版本《图论及其应用》（北京：科学出版社，1984），1988年张克民等人编写了该书的参考答案《图论及其应用习题解答》（清华大学出版社，1988）。
在2008年J.A. Bondy和U.S.R. Murty出了新书《Graph Theory》(GTM 244, Springer, 2008), 大家可不妨将其看成是《Graph Theory with Application》的第二版，这本书在内容上做了重新调整，毕竟在第一版出版后的近30年里涌现出了很多新的结果，所以《Graph Theory》在内容上加进了一些新的结果，这本书我只是读了其中的几章，觉得写的非常棒，建议大家能够读读，这里也值得一提的是将第一版最后提出的50个问题进行了更新，并补充了一些新的问题。总之，我个人认为，《Graph Theory》的确是一部很优秀的图论教材。
中国科学技术大学出版社出版的《图论及其算法》，融有向图和无向图为一整体，系统地阐述了图论的基本概念、理论、方法及其算法，内容包括图的基本概念、Euler图与Hamilton图、图论算法、树及其应用、平面图、独立集与匹配、网络流和Petri网。 书中附有大量例题和习题，而且大部分习题有详细解答。 该书选材精炼全面，内容处理恰当且有新意，立论严谨，叙述条理清晰，语言流畅。 该书可用作高校计算机、电子、信息、管理、数学等专业本科生必修课教材，也可供相关专业的研究人员、教师及图论工作者参考。

④ 推荐几本图论入门教程或者经典书籍

关于图论的入门书，我之前研究过几本，对于初学者来讲有非常大的帮助的，而且我还觉得，对中级学习的人作为进阶学习也是非常不错的，基本上初中级学习者，可以得到很大的进步，下面我介绍给你，并帮你分析一下缘由。

经过我的研究，我觉得图与图之间的相似性可能会受到数据挖掘算法的影响，虽然我以前从未学过，而数学系理论严重的不应该是研究的课题，相似性不是很明确的尺度吗？但是计算机部门可能有一项研究，可以看看这本书：《挖掘异构信息网络：原则和方法》。

总结：

所以我觉得如果是初学图论的话，对于这种图与图之间的相似计算研究，还是慢慢来学习比较好，一定要打好基础，不然后面会非常难，很多人就是因为基础不好，学到一半就放弃了，学习这门学科是要有一定的耐心的，如果不能沉下心来学习，到后面实际操作的时候是非常困难的。

⑤ 理解图论算法有什么意义

随着计算机的出现和发展，图论得到了快速的发展，其应用范围覆盖了从自然科学到社会科学的广阔的领域，包括:电信网络、电力网络、可靠性理论、运输能力、控制论、计算机程序设计、人工智能、地图着色、情报检索、社会结构、运筹学、经济学、遗传学等。

⑥ 请问什么是算法

也就是说，能够对一定规范的输入，在有限时间内获得所要求的输出。如果一个算法有缺陷，或不适合于某个问题，执行这个算法将不会解决这个问题。不同的算法可能用不同的时间、空间或效率来完成同样的任务。一个算法的优劣可以用空间复杂度与时间复杂度来衡量。 一个算法应该具有以下五个重要的特征： 算法可以使用自然语言、伪代码、流程图等多种不同的方法来描述。1、有穷性（Finiteness） 算法的有穷性是指算法必须能在执行有限个步骤之后终止2、确切性(Difiniteness) 算法的每一步骤必须有确切的定义；3、输入项(Input) 一个算法有0个或多个输入，以刻画运算对象的初始情况，所谓0个输入是指算法本身定出了初始条件；4、输出项(Output) 一个算法有一个或多个输出，以反映对输入数据加工后的结果。没有输出的算法是毫无意义的；5、可行性(Effectiveness) 算法中执行的任何计算步都是可以被分解为基本的可执行的操作步，即每个计算步都可以在有限时间内完成。（也称之为有效性） 计算机科学家尼克劳斯-沃思曾着过一本着名的书《数据结构十算法= 程序》，可见算法在计算机科学界与计算机应用界的地位。编辑本段算法的复杂度 同一问题可用不同算法解决，而一个算法的质量优劣将影响到算法乃至程序的效率。算法分析的目的在于选择合适算法和改进算法。一个算法的评价主要从时间复杂度和空间复杂度来考虑。时间复杂度 算法的时间复杂度是指执行算法所需要的时间。一般来说，计算机算法是问题规模n 的函数f(n)，算法的时间复杂度也因此记做 T(n)=Ο(f(n)) 因此，问题的规模n 越大，算法执行的时间的增长率与f(n) 的增长率正相关，称作渐进时间复杂度（Asymptotic Time Complexity）。空间复杂度 算法的空间复杂度是指算法需要消耗的内存空间。其计算和表示方法与时间复杂度类似，一般都用复杂度的渐近性来表示。同时间复杂度相比，空间复杂度的分析要简单得多。 详见网络词条"算法复杂度"编辑本段算法设计与分析的基本方法1.递推法 递推法是利用问题本身所具有的一种递推关系求问题解的一种方法。它把问题分成若干步，找出相邻几步的关系，从而达到目的，此方法称为递推法。2.递归 递归指的是一个过程：函数不断引用自身，直到引用的对象已知3.穷举搜索法 穷举搜索法是对可能是解的众多候选解按某种顺序进行逐一枚举和检验，并从众找出那些符合要求的候选解作为问题的解。4.贪婪法 贪婪法是一种不追求最优解，只希望得到较为满意解的方法。贪婪法一般可以快速得到满意的解，因为它省去了为找最优解要穷尽所有可能而必须耗费的大量时间。贪婪法常以当前情况为基础作最优选择，而不考虑各种可能的整体情况，所以贪婪法不要回溯。5.分治法 分治法是把一个复杂的问题分成两个或更多的相同或相似的子问题，再把子问题分成更小的子问题……直到最后子问题可以简单的直接求解，原问题的解即子问题的解的合并。6.动态规划法 动态规划是一种在数学和计算机科学中使用的，用于求解包含重叠子问题的最优化问题的方法。其基本思想是，将原问题分解为相似的子问题，在求解的过程中通过子问题的解求出原问题的解。动态规划的思想是多种算法的基础，被广泛应用于计算机科学和工程领域。7.迭代法 迭代法是数值分析中通过从一个初始估计出发寻找一系列近似解来解决问题（一般是解方程或者方程组）的过程，为实现这一过程所使用的方法统称为迭代法。编辑本段算法分类 算法可大致分为基本算法、数据结构的算法、数论与代数算法、计算几何的算法、图论的算法、动态规划以及数值分析、加密算法、排序算法、检索算法、随机化算法、并行算法。 算法可以宏泛的分为三类： 有限的，确定性算法 这类算法在有限的一段时间内终止。他们可能要花很长时间来执行指定的任务，但仍将在一定的时间内终止。这类算法得出的结果常取决于输入值。 有限的，非确定算法 这类算法在有限的时间内终止。然而，对于一个（或一些）给定的数值，算法的结果并不是唯一的或确定的。 无限的算法 是那些由于没有定义终止定义条件，或定义的条件无法由输入的数据满足而不终止运行的算法。通常，无限算法的产生是由于未能确定的定义终止条件。编辑本段举例 经典的算法有很多，如："欧几里德算法，割圆术，秦九韶算法"。编辑本段算法经典专着 目前市面上有许多论述算法的书籍，其中最着名的便是《计算机程序设计艺术》（The Art Of Computer Programming) 以及《算法导论》（Introction To Algorithms）。编辑本段算法的历史 “算法”即算法的大陆中文名称出自《周髀算经》；而英文名称Algorithm 来自于9世纪波斯数学家al-Khwarizmi，因为al-Khwarizmi在数学上提出了算法这个概念。“算法”原为"algorism"，意思是阿拉伯数字的运算法则，在18世纪演变为"algorithm"。欧几里得算法被人们认为是史上第一个算法。 第一次编写程序是Ada Byron于1842年为巴贝奇分析机编写求解解伯努利方程的程序，因此Ada Byron被大多数人认为是世界上第一位程序员。因为查尔斯·巴贝奇(Charles Babbage)未能完成他的巴贝奇分析机，这个算法未能在巴贝奇分析机上执行。 因为"well-defined procere"缺少数学上精确的定义，19世纪和20世纪早期的数学家、逻辑学家在定义算法上出现了困难。20世纪的英国数学家图灵提出了着名的图灵论题，并提出一种假想的计算机的抽象模型，这个模型被称为图灵机。图灵机的出现解决了算法定义的难题，图灵的思想对算法的发展起到了重要作用的。 求素数的埃拉托塞尼筛法和求方根的开方的方法公式（算法不等于公式，公式却是提供一种算法）

⑦ 求C++和数据结构经典算法。

给你个我整理的列表吧，这些书上面的题目都做出来，直接去谷歌、苹果、Facebook找工作吧。

难度系数3颗星
《挑战编程》http://book.douban.com/subject/3879470/
《算法竞赛入门经典》http://book.douban.com/subject/4138920/
《程序设计实践》http://book.douban.com/subject/1173548/
《算法之道》http://book.douban.com/subject/4249686/
难度系数4颗星
《计算机算法的设计与分析》http://book.douban.com/subject/1683278/
《算法导论》http://book.douban.com/subject/1885170/
《编程珠玑》http://book.douban.com/subject/1230206/
《编程珠玑2》http://book.douban.com/subject/3234692/
《编程之美》http://book.douban.com/subject/3004255/
《算法设计手册》The Algorithm Design Manual
《算法设计与分析基础》http://book.douban.com/subject/1173877/
《算法引论》http://book.douban.com/subject/1436134/
《算法.Sedgewick》 http://book.douban.com/subject/1143801/
难度系数5颗星
《算法艺术与信息学竞赛》http://book.douban.com/subject/1154204/
《具体数学》http://book.douban.com/subject/1390010/
《计算机程序设计艺术》http://book.douban.com/subject/1418402/
《计算机程序的构造和解释》http://book.douban.com/subject/1148282/
《高级数据结构》http://book.douban.com/subject/3328585/

专题类的算法
《随机算法》http://book.douban.com/subject/3269796/
《近似算法》http://book.douban.com/subject/1823807/
《如何求解问题：现代启发式方法》http://book.douban.com/subject/1232071/
《组合优化》http://book.douban.com/subject/1823805/
《网络流》http://book.douban.com/subject/1316052/
《计算几何》http://book.douban.com/subject/1445320/
《概率与计算》http://book.douban.com/subject/2056370/
《柔性字符串匹配》http://book.douban.com/subject/2038862/
《应用密码学》http://book.douban.com/subject/1088180/

数学类，太多，少推荐几本
《怎样解题》http://book.douban.com/subject/1013762/
《陶哲轩教你学数学》http://book.douban.com/subject/3921816/
《什么是数学》http://book.douban.com/subject/1320282/
《图论》http://book.douban.com/subject/1921943/
《组合数学》http://book.douban.com/subject/1231452/
《计数组合学》http://book.douban.com/subject/1193832/

⑧ 用图论做一个求迷宫最短路径的算法

01.#include <stdio.h>
02.#define MAXN 10
03.int dx[] = {-1, 1, 0, 0}, dy[] = {0, 0, -1, 1};
04.char name[] = {'U', 'D', 'L', 'R'};
05.int q[MAXN * MAXN]; //队列，保存当前结点编号
06.int vis[MAXN][MAXN], nMap[MAXN][MAXN];
07.int m, n; //行、列数
08.int dir[MAXN * MAXN];
09.int fa[MAXN][MAXN], dis[MAXN][MAXN], last_dir[MAXN][MAXN];
10.void funcInit();
11.void bfs(int x, int y);
12.void funcInput();
13.void print_path(int x, int y);
14.int main()
15.{
16. funcInput();
17. funcInit();
18. bfs(0, 0);
19. print_path(m - 1, n - 1);
20. return 0;
21.}
22.void funcInit()
23.{
24. int i, j;
25. for (i = 0; i != m; ++i)
26. {
27. for (j = 0; j != n; ++j)
28. {
29. vis[i][j] = 0;
30. dis[i][j] = 0;
31. }
32. }
33.}
34.void funcInput()
35.{
36. int i, j;
37. scanf("%d %d", &m, &n);
38. for (i = 0; i != m; ++i)
39. {
40. for (j = 0; j != n; ++j)
41. {
42. scanf("%d", &nMap[i][j]);
43. }
44. }
45.}
46.void bfs(int x, int y)
47.{
48. int front = 0, rear = 0;
49. int d, u; //方向标记、结点编号
50.
51. u = x * m + y;
52. vis[x][y] = 1;
53. fa[x][y] = u;
54. q[rear++] = u; //将当前结点编好放入队列
55.
56. while (front != rear)
57. {
58. u = q[front++];
59. x = u / m; y = u % m;
60. for (d = 0; d != 4; ++d)
61. {
62. int nx = x + dx[d], ny = y + dy[d];
63. if (nx >= 0 && nx < m && ny >= 0 && ny < n && !vis[nx][ny] && !nMap[nx][ny])
64. {
65. int v = nx * m + ny;
66. q[rear++] = v;
67. vis[nx][ny] = 1;
68. fa[nx][ny] = u;
69. dis[nx][ny] = dis[x][y] + 1; //记录路径长度
70. last_dir[nx][ny] = d; //记录移动方向标记
71. }
72. }
73. }
74.}
75.void print_path(int x, int y)
76.{
77. int c = 0;
78.
79. while (1)
80. {
81. int fx = fa[x][y] / m;
82. int fy = fa[x][y] % m;
83. if (fx == x && fy == y) break;
84. dir[c++] = last_dir[x][y];
85. x = fx; y = fy;
86. }
87. while (c--)
88. {
89. putchar(name[dir[c]]);
90. putchar('/n');
91. }
92. printf("最短路径长度为:%d/n", dis[m-1][n-1]);
93.}

⑨ 网络爬虫设计类图论中的哪些经典算法

根据PageRank的思想，编程在网络爬虫中实现。它的核心思想是能够发现权威超链接，通常的实现方法是将新分析出来的超链接与旧的超链接比对，使超链接的权重增加，从而抓取权重高的超链接。因为我们无法收录所有的超链接只能捡重要的收录。