数码资讯
15天算法系列-第十五天（以下）
选购提示
关注价格、性能、续航、售后和真实使用场景，理性比较后再下单。
今天是大结局，最后一个是下一个图，最小生成树和最短路径。
1：最小生成树
1。概念
首先，看下一张图片，我不知道你能总结什么。
对于连通图G，如果所有的顶点和边的一部分形成一个子图G1，当G1满足时：
（1）是连接所有图的顶点。在vertex.g1没有回路称为G的生成树
事实上，一句话的总结是，生成树是把原图所有顶点都映射到最小边的子图，它不能得到下面两个生成树。
（2）对于一个加权连通图，当生成的树不同时，每个边上的权重之和也是不同的。如果生成树的权重最小，则为最小生成树。
2。场景
在实际应用中，最小生成树仍然具有实用价值。在教科书中，有这样一句话：如果用一个图形来表示一个运输系统，每个顶点代表一个城市。
边缘代表两个城市之间的距离。当有n个城市时，可能有n个（n-1） 2个边。那么我们如何选择（n-1）边来最小化城市之间的总距离
抽象模型是寻找最小生成树的问题。
三.普利姆算法
当然，如何找到最小生成树问题，前人已经给了我们一个很好的总结，我们就拿葫芦来画瓢。
第一步：我们设置了集合V，u
第二步：我们将V1插入到U集合中，并标记V1顶点作为访问点。
第三步：我们寻找V1（V2，V3，V5）的邻接点。V1和V2之间的权重最小。然后我们将V2放入U集，并将V2标记为一个访问。
这次是U（V1，V2）。
第四步：在u集合中寻找V1和V2的邻接边。痉挛后，我们发现V1（V5）的权重最小。此时，V5被添加到U集，合并标记为访问。
u的集合元素是（V1、V2、V5）。
第五步：在这一点上，我们在（V1，V2，V5）的基础上寻找相邻边的最小权重。我们发现，V5的权重（V4）是最小的，然后我们添加V4 U集合并标签。
访问，U的集合元素（V1，V2，V5、V4）。
第六步：像第五步形式一样，我们发现（V1，V3）的最小权重，将V3添加到U集，并将其标记为访问。最后，U元素（V1，V2，V3，V4，V5，）。
发现所有顶点都被访问，最小生成树诞生了。
复制代码代码如下所示：
最小生成树的Prim算法得到#区
X
获取最小生成树算法。
X
X
公共无效Prim（matrixgraph图，出int和）
{
已访问的标记
int = 0；
非邻接顶点标记
国际noadj = - 1；
定义输出变量的总权重
总和= 0；
用于存储邻接点权重的临时数组
int { }重量=新国际vertexnum } {图；
用于存储顶点信息的临时数组
int { } tempvertex =新国际vertexnum } {图；
删除邻接矩阵的第一行数据，删除第一个顶点和右边以及存储在临时数据中的信息。
为（int i = 1；i < graph.vertexnum；i++）
{
存储在相邻点之间的权重中
重量{图}。边缘{ 0，}；
等于0表示V1没有边缘和邻居节点。
如果（重量{我} =短。次）
我tempvertex { } = noadj；
其他的
tempvertex {我} = int（图解析。顶点{ 0 }）；
}
将该节点移除，只需设置已访问的节点，0组权重
VaR指标= tempvertex { 0 } =用；
VaR最小=体重{ 0 } = short.maxvalue；
查找相邻节点中的最小权重节点
为（int i = 1；i < graph.vertexnum；i++）
{
索引= i；
min = short.maxvalue；
为（j = 1；J < graph.vertexnum；j++）
{
当前节点的权重：查找接入点中最小的非相邻点
如果（重量{ } { J J <<民tempvertex }！= 0）
{
最小重量= { }；
索引= j；
}
}
累积值
总和=最小；
控制台。写入（）（（{ 0 }，{ 1 }）
用于访问的最小节点 id
体重指数= short.maxvalue { }；
tempvertex {指数} = 0；
从最新的节点开始，节点权重分配
为（j = 0；J < graph.vertexnum；j++）
{
以当前节点为起点，选择最小边缘
如果（图。边{指数、J } { } { <量{J}. tempvertex J }！=使用）
{
权重{ = } =图.边缘{索引，j }；
这里的目标将是在相邻点边缘的一个节点的长/短边覆盖点。
tempvertex { } = int（图解析{J}.。顶点{指数}）；
}
}
}
}
#铁心端部定点
二：最短路径
1。概念
寻找最短路径问题也具有很大的实用价值。映射到交通系统图是寻找两个城市之间的最短路径，或看到这张图片。例如，我们可以很容易地看到这一点。
V1到图中每个顶点的最短路径。
右边的，2。
到右边3。
（3）转让权v1 -> -> V4 V5是3 + 2 = 5。
到右侧3。
，
2。Dijkstra算法
我们的学习需要站在巨人的肩膀上。因此，对于现实中非常复杂的问题，我们不能用肉眼来观察，而是以某些算法为基础。
Dijkstra思想是一步看一步的原则。
第一步是：我们需要一组u，然后把V1放在u集合中。既然我们走了一步，我们就得看一看。比较V1的邻接点（V2、V3、V5）。
发现（V1，V2）的权重是最小的，然后我们将V2放入U集合，表示我们找到了V1到V2的最短路径。
第二步：然后，V2会做中间点，继续寻找最小权重的最近邻居。发现只有V4可以连接。然后V4重量改变（V1，V2）+（V2，V4）= 6。
在这一点上，我们得看一看。我们发现，在V1重量最小（V3，V4，V5）是（V1，V5）。此时，V5被放置在U组中，这意味着我们已经找到了它。
从V1到V5的最短路径。
第三步：以V5为中间点，继续寻找最小权重的最近邻。我们发现，V3和V4可以连接。当我们想修复V3的重量时，我们发现（V1，V3）的权重。
不到现在，我们不修改它，把V3放到U集合中，最后我们找到从V1到V3的最短路径。
第四步：由于V5还没有完成，所以我们继续使用V5做中间点。在这个时候，我们只能连接（V5、V4）。当我们想要修改的权重，我们发现原来的V4（V1，V2）重量+（V2，V4）。
现在的体重是5，低于此前的6，当原始重量的变化到5，和V4放入收藏。最后，我们找到的最短路径从V1到V4。
复制代码代码如下所示：
#区Dijkstra找到最短路径
X
只是Dijkstra的最短路径
X
X
公共无效Dijkstra（matrixgraph G）
{
int { }重量=新国际g.vertexnum } {；
int { } { } =新国际g.vertexnum路径；
int { } tempvertex =新国际g.vertexnum } {；
console.writeline（请输入源点的数量：；
/允许用户输入遍历的起始点
int顶点= int（console.readline解析（1））；
为（int i = 0；i < g.vertexnum；i++）
{
初始权重
重量{我} = g.edges {点}，我；
如果（重量{ 0 }）
路径{ = } =顶点；
我tempvertex { } = 0；
}
tempvertex {点} = 1；
重量{顶点} = 0；
为（int i = 0；i < g.vertexnum；i++）
{
INT MIN = short.maxvalue；
索引=顶点；
为（j = 0；J < g.vertexnum；j++）
{
查找最小的顶点权重
如果（tempvertex { } = = 0 J重{ J } <分钟）
{
最小重量= { }；
索引= j；
}
}
tempvertex {指数} = 1；
以当前索引作为中间点，找到最小的权重
为（j = 0；J < g.vertexnum；j++）
{
如果（tempvertex { } = 0体重指数{J}. { } + g.edges {指数、J } { } <重J）
{
{ } = {体重，体重指数} + g.edges {指数、J }；
路径{ = }索引；
}
}
}
console.writeline（最短的路径顶点{ 0 }每个顶点：（终点<源点）+ g.vertex {点}）；
最终输出
为（int i = 0；i < g.vertexnum；i++）
{
如果（tempvertex {我} = 1）
{
var索引= i；
而（指数）！=顶点）
{
var =索引；
控制台。写入（{ 0 } <
索引=路径{索引}；
}
console.writeline（{ 0 }
}
其他的
{
console.writeline（{ 0 }，{ 1 }：没有路径，g.vertex {我}，g.vertex {点}）；
}
}
}
#铁心端部定点
最后到总运行代码
复制代码代码如下所示：
使用系统；
使用system.collections.generic；
使用LINQ系统；
使用系统文本；
命名空间matrixgraph
{
程序公开课
{
static void main（String { } args）
{
matrixgraphmanager经理=新matrixgraphmanager（）；
创建地图
matrixgraph图= manager.creatematrixgraph（）；
Manager.OutMatrix（图）；
int＝0；
管理器（图，和）；
console.writeline（重量最小生成树是：+和；
经理Dijkstra（图）；
/ / console.write（广度递归： T ）；
/ / manager.bfstraverse（图）；
/ / console.write（深度递归：；
/ / manager.dfstraverse（图）；
Console.ReadLine（）；
}
}
该#区域邻接矩阵的结构图
X
图邻接矩阵x的结构
X
matrixgraph公共类
{
保存顶点信息
公共字符串{ }顶点；
保存侧信息
公共边缘；
深搜索和宽搜索遍历标记
公共istrav bool { }；
顶点的数量
public int vertexnum；
边缘数
public int edgenum；
图表类型
public int图类型；
X
公共存储容量初始化
X
X
X
X
公共matrixgraph（int，int vertexnum，edgenum图类型，int）
{
this.vertexnum = vertexnum；
this.edgenum = edgenum；
this.graphtype =图类型；
顶点=新的字符串vertexnum } {；
边缘=新国际vertexnum vertexnum {，}；
istrav =新vertexnum bool { }；
}
}
#铁心端部定点
X
只是操作类的一张地图
X
matrixgraphmanager公共类
{
#区域图的创建
X
创建映射
X
X
公共matrixgraph creatematrixgraph（）
{
console.writeline（请输入的创作图，顶点的边数，该数是否是一个无向图（0,1），已由一个逗号分开。）；
var = console.readline（initdata）。Split（），选择（我= int（我）（解析）。列出）；
matrixgraph图=新matrixgraph（initdata { 0 }，{ 1 } initdata，initdata { 2 }）；
我们默认正无穷大，没有边。
为（int i = 0；i < graph.vertexnum；i++）
{
为（j = 0；J < graph.vertexnum；j++）
{
图。边{我} = short.maxvalue {J}.；
}
}
console.writeline（请输入每个顶点信息：）；
为（int i = 0；i < graph.vertexnum；i++）
{
控制台。写入（）+（i + 1）+ 顶点是：；
VaR单= console.readline（）；
将顶点信息放入集合中
图.顶点{ } =单个；
}
console.writeline（请输入构成两个顶点的边和权重，用逗号分隔。；
为（int i = 0；i < graph.edgenum；i++）
{
控制台。写入（）+（i + 1）+边缘：；
initdata = console.readline（。分）（'），选择（J = int（J）（解析）。列出）；
起始= initdata { 0 }；
INT端= initdata { 1 }；
体重= initdata { 2 }；
指定位置分配/矩阵的坐标
图.边缘{开始- 1，结束- 1 } =重量；
如果图是无方向的，那么数据是两个，四象限对称的。
如果（graph.graphtype = 1）
{
图.边缘{ - 1，开始- 1 } =重量；
}
}
返回图；
}
#铁心端部定点
#输出矩阵数据区域
X
公共数据输出矩阵
X
X
公共无效outmatrix（matrixgraph图）
{
为（int i = 0；i < graph.vertexnum；i++）
{
为（j = 0；J < graph.vertexnum；j++）
{
如果（图。边{我，J } =短。次）
（console.write - T ）；
其他的
控制台。写入（图形；
}
包装
console.writeline（）；
}
}
#铁心端部定点
#区域广度优先
X
X广度优先
X
X
公共无效BFSTraverse（matrixgraph图）
{
默认情况下初始化访问令牌。
为（int i = 0；i < graph.vertexnum；i++）
{
图。istrav {我} = false；
}
遍历每个顶点
为（int i = 0；i < graph.vertexnum；i++）
{
/ /广度遍历访问过的顶点
如果（！图istrav {我}）。
{
（参考图，我BFSM）；
}
}
}
X
x广度遍历算法
X
X
public void BFSM（REF matrixgraph图，int顶点）
{
这里是队列系统
队列=新队列（）；
挂起/顶点
Enqueue（顶点）队列；
这次访问被标记为
图istrav {点} =真；
输出顶点
控制台。写入（++图。顶点{ }）；
相邻顶点点/广度遍历
而（queue.count！= 0）
{
VaR温度=队列。Dequeue（）；
横坐标 /遍历矩阵
为（int i = 0；i < graph.vertexnum；i++）
{
如果（！图。istrav {我}图。边{温度}，我！= 0）
{
图istrav { } =真实的我；
Enqueue（我）队列；
/ /输出未访问过的顶点
控制台。写入（++图。顶点{ }）；
}
}
}
}
#铁心端部定点
#区深度优先
X
先改变深度
X
X
公共无效DFSTraverse（matrixgraph图）
{
默认情况下初始化访问令牌。
为（int i = 0；i < graph.vertexnum；i++）
{
图。istrav {我} = false；
}
遍历每个顶点
为（int i = 0；i < graph.vertexnum；i++）
{
/ /广度遍历访问过的顶点
如果（！图istrav {我}）。
{
有限状态机（参考图，我）；
}
}
}
递归#区域深度的具体算法
X
x中递归算法的深度
X
X
X
公共无效的状态机（参考matrixgraph图，int顶点）
{
控制台。写入（++图。顶点{ }）；
标记为访问
图istrav {点} =真；
六点遍历
为（int i = 0；i < graph.vertexnum；i++）
{
如果（图。istrav {我} {假=图。边的顶点，我} = 0！）
{
/ /深度递归
有限状态机（参考图，我）；
}
}
}
#铁心端部定点
#铁心端部定点
最小生成树的Prim算法得到#区
X
获取最小生成树算法。
X
X
公共无效Prim（matrixgraph图，出int和）
{
已访问的标记
int = 0；
非邻接顶点标记
国际noadj = - 1；
定义输出变量的总权重
总和= 0；
用于存储邻接点权重的临时数组
int { }重量=新国际vertexnum } {图；
用于存储顶点信息的临时数组
Int{} tempvertex = new int{graph.vertexNum};
删除邻接矩阵的第一行数据，删除第一个顶点和右边以及存储在临时数据中的信息。
为（int i = 1；i < graph.vertexnum；i++）
{
存储在相邻点之间的权重中
重量{图}。边缘{ 0，}；
等于0表示V1没有边缘和邻居节点。
如果（重量{我} =短。次）
我tempvertex { } = noadj；
其他的
tempvertex {我} = int（图解析。顶点{ 0 }）；
}
将该节点移除，只需设置已访问的节点，0组权重
VaR指标= tempvertex { 0 } =用；
VaR最小=体重{ 0 } = short.maxvalue；
查找相邻节点中的最小权重节点
为（int i = 1；i < graph.vertexnum；i++）
{
索引= i；
min = short.maxvalue；
为（j = 1；J < graph.vertexnum；j++）
{
当前节点的权重：查找接入点中最小的非相邻点
如果（重量{ } { J J <<民tempvertex }！= 0）
{
最小重量= { }；
索引= j；
}
}
累积值
总和=最小；
控制台。写入（）（（{ 0 }，{ 1 }）
用于访问的最小节点 id
体重指数= short.maxvalue { }；
tempvertex {指数} = 0；
从最新的节点开始，节点权重分配
为（j = 0；J < graph.vertexnum；j++）
{
以当前节点为起点，选择最小边缘
如果（图。边{指数、J } { } { <量{J}. tempvertex J }！=使用）
{
权重{ = } =图.边缘{索引，j }；
这里的目标将是在相邻点边缘的一个节点的长/短边覆盖点。
tempvertex { } = int（图解析{J}.。顶点{指数}）；
}
}
}
}
#铁心端部定点
#区Dijkstra找到最短路径
X
只是Dijkstra的最短路径
X
X
公共无效Dijkstra（matrixgraph G）
{
int { }重量=新国际g.vertexnum } {；
int { } { } =新国际g.vertexnum路径；
int { } tempvertex =新国际g.vertexnum } {；
console.writeline（请输入源点的数量：；
/允许用户输入遍历的起始点
int顶点= int（console.readline解析（1））；
为（int i = 0；i < g.vertexnum；i++）
{
初始权重
重量{我} = g.edges {点}，我；
如果（重量{ 0 }）
路径{ = } =顶点；
我tempvertex { } = 0；
}
tempvertex {点} = 1；
重量{顶点} = 0；
为（int i = 0；i < g.vertexnum；i++）
{
INT MIN = short.maxvalue；
索引=顶点；
为（j = 0；J < g.vertexnum；j++）
{
查找最小的顶点权重
如果（tempvertex { } = = 0 J重{ J } <分钟）
{
最小重量= { }；
索引= j；
}
}
tempvertex {指数} = 1；
以当前索引作为中间点，找到最小的权重
为（j = 0；J < g.vertexnum；j++）
{
如果（tempvertex { } = 0体重指数{J}. { } + g.edges {指数、J } { } <重J）
{
{ } = {体重，体重指数} + g.edges {指数、J }；
路径{ = }索引；
}
}
}
console.writeline（最短的路径顶点{ 0 }每个顶点：（终点<源点）+ g.vertex {点}）；
最终输出
为（int i = 0；i < g.vertexnum；i++）
{
如果（tempvertex {我} = 1）
{
var索引= i；
而（指数）！=顶点）
{
var =索引；
控制台。写入（{ 0 } <
索引=路径{索引}；
}
console.writeline（{ 0 }
}
其他的
{
console.writeline（{ 0 }，{ 1 }：没有路径，g.vertex {我}，g.vertex {点}）；
}
}
}
#铁心端部定点
}
}
快速算法系列结束了这一切，公司的算法培训在星期五完成了，呵呵，并同步了。最后，我希望您能注意算法。
学习算法，终身收入。
1：最小生成树
1。概念
首先，看下一张图片，我不知道你能总结什么。
对于连通图G，如果所有的顶点和边的一部分形成一个子图G1，当G1满足时：
（1）是连接所有图的顶点。在vertex.g1没有回路称为G的生成树
事实上，一句话的总结是，生成树是把原图所有顶点都映射到最小边的子图，它不能得到下面两个生成树。
（2）对于一个加权连通图，当生成的树不同时，每个边上的权重之和也是不同的。如果生成树的权重最小，则为最小生成树。
2。场景
在实际应用中，最小生成树仍然具有实用价值。在教科书中，有这样一句话：如果用一个图形来表示一个运输系统，每个顶点代表一个城市。
边缘代表两个城市之间的距离。当有n个城市时，可能有n个（n-1） 2个边。那么我们如何选择（n-1）边来最小化城市之间的总距离
抽象模型是寻找最小生成树的问题。
三.普利姆算法
当然，如何找到最小生成树问题，前人已经给了我们一个很好的总结，我们就拿葫芦来画瓢。
第一步：我们设置了集合V，u
第二步：我们将V1插入到U集合中，并标记V1顶点作为访问点。
第三步：我们寻找V1（V2，V3，V5）的邻接点。V1和V2之间的权重最小。然后我们将V2放入U集，并将V2标记为一个访问。
这次是U（V1，V2）。
第四步：在u集合中寻找V1和V2的邻接边。痉挛后，我们发现V1（V5）的权重最小。此时，V5被添加到U集，合并标记为访问。
u的集合元素是（V1、V2、V5）。
第五步：在这一点上，我们在（V1，V2，V5）的基础上寻找相邻边的最小权重。我们发现，V5的权重（V4）是最小的，然后我们添加V4 U集合并标签。
访问，U的集合元素（V1，V2，V5、V4）。
第六步：像第五步形式一样，我们发现（V1，V3）的最小权重，将V3添加到U集，并将其标记为访问。最后，U元素（V1，V2，V3，V4，V5，）。
发现所有顶点都被访问，最小生成树诞生了。
复制代码代码如下所示：
最小生成树的Prim算法得到#区
X
获取最小生成树算法。
X
X
公共无效Prim（matrixgraph图，出int和）
{
已访问的标记
int = 0；
非邻接顶点标记
国际noadj = - 1；
定义输出变量的总权重
总和= 0；
用于存储邻接点权重的临时数组
int { }重量=新国际vertexnum } {图；
用于存储顶点信息的临时数组
int { } tempvertex =新国际vertexnum } {图；
删除邻接矩阵的第一行数据，删除第一个顶点和右边以及存储在临时数据中的信息。
为（int i = 1；i < graph.vertexnum；i++）
{
存储在相邻点之间的权重中
重量{图}。边缘{ 0，}；
等于0表示V1没有边缘和邻居节点。
如果（重量{我} =短。次）
我tempvertex { } = noadj；
其他的
tempvertex {我} = int（图解析。顶点{ 0 }）；
}
将该节点移除，只需设置已访问的节点，0组权重
VaR指标= tempvertex { 0 } =用；
VaR最小=体重{ 0 } = short.maxvalue；
查找相邻节点中的最小权重节点
为（int i = 1；i < graph.vertexnum；i++）
{
索引= i；
min = short.maxvalue；
为（j = 1；J < graph.vertexnum；j++）
{
当前节点的权重：查找接入点中最小的非相邻点
如果（重量{ } { J J <<民tempvertex }！= 0）
{
最小重量= { }；
索引= j；
}
}
累积值
总和=最小；
控制台。写入（）（（{ 0 }，{ 1 }）
用于访问的最小节点 id
体重指数= short.maxvalue { }；
tempvertex {指数} = 0；
从最新的节点开始，节点权重分配
为（j = 0；J < graph.vertexnum；j++）
{
以当前节点为起点，选择最小边缘
如果（图。边{指数、J } { } { <量{J}. tempvertex J }！=使用）
{
权重{ = } =图.边缘{索引，j }；
这里的目标将是在相邻点边缘的一个节点的长/短边覆盖点。
tempvertex { } = int（图解析{J}.。顶点{指数}）；
}
}
}
}
#铁心端部定点
二：最短路径
1。概念
寻找最短路径问题也具有很大的实用价值。映射到交通系统图是寻找两个城市之间的最短路径，或看到这张图片。例如，我们可以很容易地看到这一点。
V1到图中每个顶点的最短路径。
右边的，2。
到右边3。
（3）转让权v1 -> -> V4 V5是3 + 2 = 5。
到右侧3。
，
2。Dijkstra算法
我们的学习需要站在巨人的肩膀上。因此，对于现实中非常复杂的问题，我们不能用肉眼来观察，而是以某些算法为基础。
Dijkstra思想是一步看一步的原则。
第一步是：我们需要一组u，然后把V1放在u集合中。既然我们走了一步，我们就得看一看。比较V1的邻接点（V2、V3、V5）。
发现（V1，V2）的权重是最小的，然后我们将V2放入U集合，表示我们找到了V1到V2的最短路径。
第二步：然后，V2会做中间点，继续寻找最小权重的最近邻居。发现只有V4可以连接。然后V4重量改变（V1，V2）+（V2，V4）= 6。
在这一点上，我们得看一看。我们发现，在V1重量最小（V3，V4，V5）是（V1，V5）。此时，V5被放置在U组中，这意味着我们已经找到了它。
从V1到V5的最短路径。
第三步：以V5为中间点，继续寻找最小权重的最近邻。我们发现，V3和V4可以连接。当我们想修复V3的重量时，我们发现（V1，V3）的权重。
不到现在，我们不修改它，把V3放到U集合中，最后我们找到从V1到V3的最短路径。
第四步：由于V5还没有完成，所以我们继续使用V5做中间点。在这个时候，我们只能连接（V5、V4）。当我们想要修改的权重，我们发现原来的V4（V1，V2）重量+（V2，V4）。
现在的体重是5，低于此前的6，当原始重量的变化到5，和V4放入收藏。最后，我们找到的最短路径从V1到V4。
复制代码代码如下所示：
#区Dijkstra找到最短路径
X
只是Dijkstra的最短路径
X
X
公共无效Dijkstra（matrixgraph G）
{
int { }重量=新国际g.vertexnum } {；
int { } { } =新国际g.vertexnum路径；
int { } tempvertex =新国际g.vertexnum } {；
console.writeline（请输入源点的数量：；
/允许用户输入遍历的起始点
int顶点= int（console.readline解析（1））；
为（int i = 0；i < g.vertexnum；i++）
{
初始权重
重量{我} = g.edges {点}，我；
如果（重量{ 0 }）
路径{ = } =顶点；
我tempvertex { } = 0；
}
tempvertex {点} = 1；
重量{顶点} = 0；
为（int i = 0；i < g.vertexnum；i++）
{
INT MIN = short.maxvalue；
索引=顶点；
为（j = 0；J < g.vertexnum；j++）
{
查找最小的顶点权重
如果（tempvertex { } = = 0 J重{ J } <分钟）
{
最小重量= { }；
索引= j；
}
}
tempvertex {指数} = 1；
以当前索引作为中间点，找到最小的权重
为（j = 0；J < g.vertexnum；j++）
{
如果（tempvertex { } = 0体重指数{J}. { } + g.edges {指数、J } { } <重J）
{
{ } = {体重，体重指数} + g.edges {指数、J }；
路径{ = }索引；
}
}
}
console.writeline（最短的路径顶点{ 0 }每个顶点：（终点<源点）+ g.vertex {点}）；
最终输出
为（int i = 0；i < g.vertexnum；i++）
{
如果（tempvertex {我} = 1）
{
var索引= i；
而（指数）！=顶点）
{
var =索引；
控制台。写入（{ 0 } <
索引=路径{索引}；
}
console.writeline（{ 0 }
}
其他的
{
console.writeline（{ 0 }，{ 1 }：没有路径，g.vertex {我}，g.vertex {点}）；
}
}
}
#铁心端部定点
最后到总运行代码
复制代码代码如下所示：
使用系统；
使用system.collections.generic；
使用LINQ系统；
使用系统文本；
命名空间matrixgraph
{
程序公开课
{
static void main（String { } args）
{
matrixgraphmanager经理=新matrixgraphmanager（）；
创建地图
matrixgraph图= manager.creatematrixgraph（）；
Manager.OutMatrix（图）；
int＝0；
管理器（图，和）；
console.writeline（重量最小生成树是：+和；
经理Dijkstra（图）；
/ / console.write（广度递归： T ）；
/ / manager.bfstraverse（图）；
/ / console.write（深度递归：；
/ / manager.dfstraverse（图）；
Console.ReadLine（）；
}
}
该#区域邻接矩阵的结构图
X
图邻接矩阵x的结构
X
matrixgraph公共类
{
保存顶点信息
公共字符串{ }顶点；
保存侧信息
公共边缘；
深搜索和宽搜索遍历标记
公共istrav bool { }；
顶点的数量
public int vertexnum；
边缘数
public int edgenum；
图表类型
public int图类型；
X
公共存储容量初始化
X
X
X
X
公共matrixgraph（int，int vertexnum，edgenum图类型，int）
{
this.vertexnum = vertexnum；
this.edgenum = edgenum；
this.graphtype =图类型；
顶点=新的字符串vertexnum } {；
边缘=新国际vertexnum vertexnum {，}；
istrav =新vertexnum bool { }；
}
}
#铁心端部定点
X
只是操作类的一张地图
X
matrixgraphmanager公共类
{
#区域图的创建
X
创建映射
X
X
公共matrixgraph creatematrixgraph（）
{
console.writeline（请输入的创作图，顶点的边数，该数是否是一个无向图（0,1），已由一个逗号分开。）；
var = console.readline（initdata）。Split（），选择（我= int（我）（解析）。列出）；
matrixgraph图=新matrixgraph（initdata { 0 }，{ 1 } initdata，initdata { 2 }）；
我们默认正无穷大，没有边。
为（int i = 0；i < graph.vertexnum；i++）
{
为（j = 0；J < graph.vertexnum；j++）
{
图。边{我} = short.maxvalue {J}.；
}
}
console.writeline（请输入每个顶点信息：）；
为（int i = 0；i < graph.vertexnum；i++）
{
控制台。写入（）+（i + 1）+ 顶点是：；
VaR单= console.readline（）；
将顶点信息放入集合中
图.顶点{ } =单个；
}
console.writeline（请输入构成两个顶点的边和权重，用逗号分隔。；
为（int i = 0；i < graph.edgenum；i++）
{
控制台。写入（）+（i + 1）+边缘：；
initdata = console.readline（。分）（'），选择（J = int（J）（解析）。列出）；
起始= initdata { 0 }；
INT端= initdata { 1 }；
体重= initdata { 2 }；
指定位置分配/矩阵的坐标
图.边缘{开始- 1，结束- 1 } =重量；
如果图是无方向的，那么数据是两个，四象限对称的。
如果（graph.graphtype = 1）
{
图.边缘{ - 1，开始- 1 } =重量；
}
}
返回图；
}
#铁心端部定点
#输出矩阵数据区域
X
公共数据输出矩阵
X
X
公共无效outmatrix（matrixgraph图）
{
为（int i = 0；i < graph.vertexnum；i++）
{
为（j = 0；J < graph.vertexnum；j++）
{
如果（图。边{我，J } =短。次）
（console.write - T ）；
其他的
控制台。写入（图形；
}
包装
console.writeline（）；
}
}
#铁心端部定点
#区域广度优先
X
X广度优先
X
X
公共无效BFSTraverse（matrixgraph图）
{
默认情况下初始化访问令牌。
为（int i = 0；i < graph.vertexnum；i++）
{
图。istrav {我} = false；
}
遍历每个顶点
为（int i = 0；i < graph.vertexnum；i++）
{
/ /广度遍历访问过的顶点
如果（！图istrav {我}）。
{
（参考图，我BFSM）；
}
}
}
X
x广度遍历算法
X
X
public void BFSM（REF matrixgraph图，int顶点）
{
这里是队列系统
队列=新队列（）；
挂起/顶点
Enqueue（顶点）队列；
这次访问被标记为
图istrav {点} =真；
输出顶点
控制台。写入（++图。顶点{ }）；
相邻顶点点/广度遍历
而（queue.count！= 0）
{
VaR温度=队列。Dequeue（）；
横坐标 /遍历矩阵
为（int i = 0；i < graph.vertexnum；i++）
{
如果（！图。istrav {我}图。边{温度}，我！= 0）
{
图istrav { } =真实的我；
Enqueue（我）队列；
/ /输出未访问过的顶点
控制台。写入（++图。顶点{ }）；
}
}
}
}
#铁心端部定点
#区深度优先
X
先改变深度
X
X
公共无效DFSTraverse（matrixgraph图）
{
默认情况下初始化访问令牌。
为（int i = 0；i < graph.vertexnum；i++）
{
图。istrav {我} = false；
}
遍历每个顶点
为（int i = 0；i < graph.vertexnum；i++）
{
/ /广度遍历访问过的顶点
如果（！图istrav {我}）。
{
有限状态机（参考图，我）；
}
}
}
递归#区域深度的具体算法
X
x中递归算法的深度
X
X
X
公共无效的状态机（参考matrixgraph图，int顶点）
{
控制台。写入（++图。顶点{ }）；
标记为访问
图istrav {点} =真；
六点遍历
为（int i = 0；i < graph.vertexnum；i++）
{
如果（图。istrav {我} {假=图。边的顶点，我} = 0！）
{
/ /深度递归
有限状态机（参考图，我）；
}
}
}
#铁心端部定点
#铁心端部定点
最小生成树的Prim算法得到#区
X
获取最小生成树算法。
X
X
公共无效Prim（matrixgraph图，出int和）
{
已访问的标记
int = 0；
非邻接顶点标记
国际noadj = - 1；
定义输出变量的总权重
总和= 0；
用于存储邻接点权重的临时数组
int { }重量=新国际vertexnum } {图；
用于存储顶点信息的临时数组
Int{} tempvertex = new int{graph.vertexNum};
删除邻接矩阵的第一行数据，删除第一个顶点和右边以及存储在临时数据中的信息。
为（int i = 1；i < graph.vertexnum；i++）
{
存储在相邻点之间的权重中
重量{图}。边缘{ 0，}；
等于0表示V1没有边缘和邻居节点。
如果（重量{我} =短。次）
我tempvertex { } = noadj；
其他的
tempvertex {我} = int（图解析。顶点{ 0 }）；
}
将该节点移除，只需设置已访问的节点，0组权重
VaR指标= tempvertex { 0 } =用；
VaR最小=体重{ 0 } = short.maxvalue；
查找相邻节点中的最小权重节点
为（int i = 1；i < graph.vertexnum；i++）
{
索引= i；
min = short.maxvalue；
为（j = 1；J < graph.vertexnum；j++）
{
当前节点的权重：查找接入点中最小的非相邻点
如果（重量{ } { J J <<民tempvertex }！= 0）
{
最小重量= { }；
索引= j；
}
}
累积值
总和=最小；
控制台。写入（）（（{ 0 }，{ 1 }）
用于访问的最小节点 id
体重指数= short.maxvalue { }；
tempvertex {指数} = 0；
从最新的节点开始，节点权重分配
为（j = 0；J < graph.vertexnum；j++）
{
以当前节点为起点，选择最小边缘
如果（图。边{指数、J } { } { <量{J}. tempvertex J }！=使用）
{
权重{ = } =图.边缘{索引，j }；
这里的目标将是在相邻点边缘的一个节点的长/短边覆盖点。
tempvertex { } = int（图解析{J}.。顶点{指数}）；
}
}
}
}
#铁心端部定点
#区Dijkstra找到最短路径
X
只是Dijkstra的最短路径
X
X
公共无效Dijkstra（matrixgraph G）
{
int { }重量=新国际g.vertexnum } {；
int { } { } =新国际g.vertexnum路径；
int { } tempvertex =新国际g.vertexnum } {；
console.writeline（请输入源点的数量：；
/允许用户输入遍历的起始点
int顶点= int（console.readline解析（1））；
为（int i = 0；i < g.vertexnum；i++）
{
初始权重
重量{我} = g.edges {点}，我；
如果（重量{ 0 }）
路径{ = } =顶点；
我tempvertex { } = 0；
}
tempvertex {点} = 1；
重量{顶点} = 0；
为（int i = 0；i < g.vertexnum；i++）
{
INT MIN = short.maxvalue；
索引=顶点；
为（j = 0；J < g.vertexnum；j++）
{
查找最小的顶点权重
如果（tempvertex { } = = 0 J重{ J } <分钟）
{
最小重量= { }；
索引= j；
}
}
tempvertex {指数} = 1；
以当前索引作为中间点，找到最小的权重
为（j = 0；J < g.vertexnum；j++）
{
如果（tempvertex { } = 0体重指数{J}. { } + g.edges {指数、J } { } <重J）
{
{ } = {体重，体重指数} + g.edges {指数、J }；
路径{ = }索引；
}
}
}
console.writeline（最短的路径顶点{ 0 }每个顶点：（终点<源点）+ g.vertex {点}）；
最终输出
为（int i = 0；i < g.vertexnum；i++）
{
如果（tempvertex {我} = 1）
{
var索引= i；
而（指数）！=顶点）
{
var =索引；
控制台。写入（{ 0 } <
索引=路径{索引}；
}
console.writeline（{ 0 }
}
其他的
{
console.writeline（{ 0 }，{ 1 }：没有路径，g.vertex {我}，g.vertex {点}）；
}
}
}
#铁心端部定点
}
}
快速算法系列结束了这一切，公司的算法培训在星期五完成了，呵呵，并同步了。最后，我希望您能注意算法。
学习算法，终身收入。
声明：本文内容用于数码产品信息整理与选购参考，具体价格、库存、售后政策以官方渠道和电商页面实时信息为准。