黑色吊椅的博客

网状结构（图）及其应用【学习要点及目的】掌握图的基本概念及基本术语。 掌握邻接矩阵。 熟练掌握图的深度优先遍历DFS、广度（宽度）优先遍历BFS算法。 了解和掌握图的常用算法，包括最短路径、最小生成树、拓扑排序及关键路径等。 能利用图的常用算法，解决实际问题。各类大学生竞赛中常见的图论算法类型主要有如下三种：图的连通性问题（常见字眼有：可达性，能否到达） 最短路径问题（常见...

网状结构（图）的基本知识专栏导读及目录https://blog.csdn.net/createprogram/article/details/86741044 如果说树型结构是种层次结构的话，图则是网状结构。可以说，树是图的一种特例。学习图论后，树的很多问题可以通过图论算法实现。图的基本概念（1）图、无向图和有向图设图G由两个集合V和E组成，记为：G=（V，E）。其中：...

专栏导读及目录https://blog.csdn.net/createprogram/article/details/86741044图的连通性（1）路径在无向图G中，若存在一个顶点序列Vp，V1，V2，……，Vm，Vq，使得（Vp，V1），（V1，V2），…，（Vm,Vq）均属于E(G)，则称顶点Vp到顶点Vq存在一条路径。在有向图中，路径也是有的，它由E(G)中的有向边<...

图的存储结构——邻接矩阵与边集数组专栏导读及目录https://blog.csdn.net/createprogram/article/details/86741044用计算机处理图论问题，首先要用某种表达方式将图存放在计算机中，这里介绍两种最常用的存储结构，即邻接矩阵和边集数组。邻接矩阵（1）矩阵定义用邻接矩阵表表示顶点之间相邻关系的矩阵。在图的邻接矩阵表示法中：用邻接矩...

专栏导读及目录https://blog.csdn.net/createprogram/article/details/86741044图的最小生成树——Prim（普里姆）算法和Kruskal（卡鲁斯卡尔）算法（1）最小生成树的概念通常如果确定一个问题是最小生成树问题，那么你需要构建这样一个带权图：保证构建的图是连通图。 图中所有边权值之和最小。 为了使权值之和最小，因此图中不存...

最优布线问题题目描述 Description农民约翰被选为他们镇的镇长！他其中一个竞选承诺就是在镇上建立起互联网，并连接到所有的农场。当然，他需要你的帮助。 约翰已经给他的农场安排了一条高速的网络线路，他想把这条线路共享给其他农场。为了使花费最少，他想铺设最短的光纤去连接所有的农场。 你将得到一份各农场之间连接费用的列表，你必须找出能连接所有农场并所用光纤最短的方案。 每两个农场间的距离不...

专栏导读及目录https://blog.csdn.net/createprogram/article/details/86741044深度优先搜索DFS基本思想基本步骤：1.从图中某个顶点v0出发，首先访问v0;  2.访问结点v0的第一个邻接点，以这个邻接点vt作为一个新节点，访问vt所有邻接点。直到以vt出发的所有节点都被访问到，回溯到v0的下一个未被访问过的邻接点，以这个...

专栏导读及目录https://blog.csdn.net/createprogram/article/details/86741044求图的最短路径（详谈Floyd和Dijkstra）（注：在这一部分起点、源点意思相近；点的距离、边的长度、权值意思相近）（再注：这里面包含一个隐含知识点，遇到有关图的问题时部分同学会感到无从下手，无法把握数据规模，其实一个包含n个点的图，最多包含n*（n...

产生数题目描述 Description　　给出一个整数 n（n<10^30) 和 k 个变换规则（k<=15）。　　规则：　　　一位数可变换成另一个一位数：　　　规则的右部不能为零。　　例如：n=234。有规则（k＝2）：　　　　2－> 5　　　　3－> 6　　上面的整数 234 经过变换后可能产生出的整数为（包括原数）:　　　234　　　534...

邻接表我们发现，当图中的边数相对于顶点较少时，邻接矩阵是对存储空间的极大浪费。我们可以考虑对边或弧使用链式存储的方式来避免空间浪费的问题。回忆树结构的孩子表示法，将结点存入数组，并对结点的孩子进行链式存储，不管有多少孩子，也不会存在空间浪费问题。应用这种思路，我们把这种数组与链表相结合的存储方法称为邻接表（Adjacency List）。邻接表的处理办法是这样。1）图中顶点用一...