算法系列15天速成——第十五天 图【下】（大结局）

    首先看如下图，不知道大家能总结点什么。

    对于一个连通图G，如果其全部顶点和一部分边构成一个子图G1，当G1满足：

       ① 刚好将图中所有顶点连通。②顶点不存在回路。则称G1就是G的“生成树”。

           其实一句话总结就是：生成树是将原图的全部顶点以最小的边连通的子图，这不，如下的连通图可以得到下面的两个生成树。

       ② 对于一个带权的连通图，当生成的树不同，各边上的权值总和也不同，如果某个生成树的权值最小，则它就是“最小生成树”。

     

2. 场景

      实际应用中“最小生成树”还是蛮有实际价值的，教科书上都有这么一句话，若用图来表示一个交通系统，每一个顶点代表一个城市，

  边代表两个城市之间的距离，当有n个城市时，可能会有n(n-1)/2条边，那么怎么选择(n-1)条边来使城市之间的总距离最小，其实它

  的抽象模型就是求“最小生成树”的问题。

 

3. prim算法

    当然如何求“最小生成树”问题，前人都已经给我们总结好了，我们只要照葫芦画瓢就是了，

    第一步：我们建立集合“V,U"，将图中的所有顶点全部灌到V集合中，U集合初始为空。

    第二步： 我们将V1放入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，V5，V4，V3），

                最终发现顶点全部被访问，最小生成树就此诞生。

#region prim算法获取最小生成树

 /// summary 

/// prim算法获取最小生成树

/// /summary 

/// param name="graph" /param 

 public void Prim(MatrixGraph graph, out int sum)

 //已访问过的标志

 int used = 0;

 //非邻接顶点标志

 int noadj = -1;

 //定义一个输出总权值的变量

 sum = 0;

 //临时数组，用于保存邻接点的权值

 int[] weight = new int[graph.vertexNum];

 //临时数组，用于保存顶点信息

 int[] tempvertex = new int[graph.vertexNum];

 //取出邻接矩阵的第一行数据，也就是取出第一个顶点并将权和边信息保存于临时数据中

 for (int i = 1; i graph.vertexNum; i++)

 //保存于邻接点之间的权值

 weight[i] = graph.edges[0, i];

 //等于0则说明V1与该邻接点没有边

 if (weight[i] == short.MaxValue)

 tempvertex[i] = noadj;

 else

 tempvertex[i] = int.Parse(graph.vertex[0]);

 //从集合V中取出V1节点，只需要将此节点设置为已访问过，weight为0集合

 var index = tempvertex[0] = used;

 var min = weight[0] = short.MaxValue;

 //在V的邻接点中找权值最小的节点

 for (int i = 1; i graph.vertexNum; i++)

 index = i;

 min = short.MaxValue;

 for (int j = 1; j graph.vertexNum; j++)

 //用于找出当前节点的邻接点中权值最小的未访问点

 if (weight[j] min tempvertex[j] != 0)

 min = weight[j];

 index = j;

 //累加权值

 sum += min;

 Console.Write("({0},{1}) ", tempvertex[index], graph.vertex[index]);

 //将取得的最小节点标识为已访问

 weight[index] = short.MaxValue;

 tempvertex[index] = 0;

 //从最新的节点出发，将此节点的weight比较赋值

 for (int j = 0; j graph.vertexNum; j++)

 //已当前节点为出发点，重新选择最小边

 if (graph.edges[index, j] weight[j] tempvertex[j] != used)

 weight[j] = graph.edges[index, j];

 //这里做的目的将较短的边覆盖点上一个节点的邻接点中的较长的边

 tempvertex[j] = int.Parse(graph.vertex[index]);

 #endregion

二： 最短路径

1.   概念

        求最短路径问题其实也是非常有实用价值的，映射到交通系统图中，就是求两个城市间的最短路径问题，还是看这张图，我们可以很容易的看出比如

     V1到图中各顶点的最短路径。

      ① V1  -  V2              直达，     权为2。

      ② V1  -  V3              直达        权为3。

      ③ V1- V5- V4           中转       权为3+2=5。

      ④ V1  -  V5               直达      权为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）的权值

                小于（V1- V5- V3),此时我们就不修改，将V3放入U集合中，最后我们找到了V1到V3的最短路径。

     第四步：因为V5还没有走完，所以继续用V5做中间点，此时只能连通(V5,V4),当要修改权值的时候，发现原来的V4权值为(V1,V2)+(V2,V4),而

                现在的权值为5，小于先前的6，此时更改原先的权值变为5，将V4放入集合中，最后我们找到了V1到V4的最短路径。

#region dijkstra求出最短路径

 /// summary 

/// dijkstra求出最短路径

/// /summary 

/// param name="g" /param 

 public void Dijkstra(MatrixGraph g)

 int[] weight = new int[g.vertexNum];

 int[] path = new int[g.vertexNum];

 int[] tempvertex = new int[g.vertexNum];

 Console.WriteLine("\n请输入源点的编号：");

 //让用户输入要遍历的起始点

 int vertex = int.Parse(Console.ReadLine()) - 1;

 for (int i = 0; i g.vertexNum; i++)

 //初始赋权值

 weight[i] = g.edges[vertex, i];

 if (weight[i] short.MaxValue weight[i] 0)

 path[i] = vertex;

 tempvertex[i] = 0;

 tempvertex[vertex] = 1;

 weight[vertex] = 0;

 for (int i = 0; i g.vertexNum; i++)

 int min = short.MaxValue;

 int index = vertex;

 for (int j = 0; j g.vertexNum; j++)

 //顶点的权值中找出最小的

 if (tempvertex[j] == 0 weight[j] min)

 min = weight[j];

 index = j;

 tempvertex[index] = 1;

 //以当前的index作为中间点，找出最小的权值

 for (int j = 0; j g.vertexNum; j++)

 if (tempvertex[j] == 0 weight[index] + g.edges[index, j] weight[j])

 weight[j] = weight[index] + g.edges[index, j];

 path[j] = index;

 Console.WriteLine("\n顶点{0}到各顶点的最短路径为：（终点 源点） " + g.vertex[vertex]);

 //最后输出

 for (int i = 0; i g.vertexNum; i++)

 if (tempvertex[i] == 1)

 var index = i;

 while (index != vertex)

 var j = index;

 Console.Write("{0} ", g.vertex[index]);

 index = path[index];

 Console.WriteLine("{0}\n", g.vertex[index]);

 else

 Console.WriteLine("{0} - {1}: 无路径\n", g.vertex[i], g.vertex[vertex]);

 #endregion

最后上一下总的运行代码

using System;

using System.Collections.Generic;

using System.Linq;

using System.Text;

namespace MatrixGraph

 public class Program

 static void Main(string[] args)

 MatrixGraphManager manager = new MatrixGraphManager();

 //创建图

 MatrixGraph graph = manager.CreateMatrixGraph();

 manager.OutMatrix(graph);

 int sum = 0;

 manager.Prim(graph, out sum);

 Console.WriteLine("\n最小生成树的权值为：" + sum);

 manager.Dijkstra(graph);

 //Console.Write("广度递归:\t");

//manager.BFSTraverse(graph);

//Console.Write("\n深度递归:\t");

//manager.DFSTraverse(graph);

 Console.ReadLine();

 #region 邻接矩阵的结构图

 /// summary 

/// 邻接矩阵的结构图

/// /summary 

 public class MatrixGraph

 //保存顶点信息

 public string[] vertex;

 //保存边信息

 public int[,] edges;

 //深搜和广搜的遍历标志

 public bool[] isTrav;

 //顶点数量

 public int vertexNum;

 //边数量

 public int edgeNum;

 //图类型

 public int graphType;

 /// summary 

/// 存储容量的初始化

/// /summary 

/// param name="vertexNum" /param 

/// param name="edgeNum" /param 

/// param name="graphType" /param 

 public MatrixGraph(int vertexNum, int edgeNum, int graphType)

 this.vertexNum = vertexNum;

 this.edgeNum = edgeNum;

 this.graphType = graphType;

 vertex = new string[vertexNum];

 edges = new int[vertexNum, vertexNum];

 isTrav = new bool[vertexNum];

 #endregion

 /// summary 

/// 图的操作类

/// /summary 

 public class MatrixGraphManager

 #region 图的创建

 /// summary 

/// 图的创建

/// /summary 

/// param name="g" /param 

 public MatrixGraph CreateMatrixGraph()

 Console.WriteLine("请输入创建图的顶点个数，边个数，是否为无向图(0,1来表示)，已逗号隔开。");

 var initData = Console.ReadLine().Split(,).Select(i = int.Parse(i)).ToList();

 MatrixGraph graph = new MatrixGraph(initData[0], initData[1], initData[2]);

 //我们默认“正无穷大为没有边”

 for (int i = 0; i graph.vertexNum; i++)

 for (int j = 0; j graph.vertexNum; j++)

 graph.edges[i, j] = short.MaxValue;

 Console.WriteLine("请输入各顶点信息：");

 for (int i = 0; i graph.vertexNum; i++)

 Console.Write("\n第" + (i + 1) + "个顶点为:");

 var single = Console.ReadLine();

 //顶点信息加入集合中

 graph.vertex[i] = single;

 Console.WriteLine("\n请输入构成两个顶点的边和权值，以逗号隔开。\n");

 for (int i = 0; i graph.edgeNum; i++)

 Console.Write("第" + (i + 1) + "条边:\t");

 initData = Console.ReadLine().Split(,).Select(j = int.Parse(j)).ToList();

 int start = initData[0];

 int end = initData[1];

 int weight = initData[2];

 //给矩阵指定坐标位置赋值

 graph.edges[start - 1, end - 1] = weight;

 //如果是无向图，则数据呈“二，四”象限对称

 if (graph.graphType == 1)

 graph.edges[end - 1, start - 1] = weight;

 return graph;

 #endregion

 #region 输出矩阵数据

 /// summary 

/// 输出矩阵数据

/// /summary 

/// param name="graph" /param 

 public void OutMatrix(MatrixGraph graph)

 for (int i = 0; i graph.vertexNum; i++)

 for (int j = 0; j graph.vertexNum; j++)

 if (graph.edges[i, j] == short.MaxValue)

 Console.Write("∽\t");

 else

 Console.Write(graph.edges[i, j] + "\t");

 //换行

 Console.WriteLine();

 #endregion

 #region 广度优先

 /// summary 

/// 广度优先

/// /summary 

/// param name="graph" /param 

 public void BFSTraverse(MatrixGraph graph)

 //访问标记默认初始化

 for (int i = 0; i graph.vertexNum; i++)

 graph.isTrav[i] = false;

 //遍历每个顶点

 for (int i = 0; i graph.vertexNum; i++)

 //广度遍历未访问过的顶点

 if (!graph.isTrav[i])

 BFSM(ref graph, i);

 /// summary 

/// 广度遍历具体算法

/// /summary 

/// param name="graph" /param 

 public void BFSM(ref MatrixGraph graph, int vertex)

 //这里就用系统的队列

 Queue int queue = new Queue int 

 //先把顶点入队

 queue.Enqueue(vertex);

 //标记此顶点已经被访问

 graph.isTrav[vertex] = true;

 //输出顶点

 Console.Write(" - " + graph.vertex[vertex]);

 //广度遍历顶点的邻接点

 while (queue.Count != 0)

 var temp = queue.Dequeue();

 //遍历矩阵的横坐标

 for (int i = 0; i graph.vertexNum; i++)

 if (!graph.isTrav[i] graph.edges[temp, i] != 0)

 graph.isTrav[i] = true;

 queue.Enqueue(i);

 //输出未被访问的顶点

 Console.Write(" - " + graph.vertex[i]);

 #endregion

 #region 深度优先

 /// summary 

/// 深度优先

/// /summary 

/// param name="graph" /param 

 public void DFSTraverse(MatrixGraph graph)

 //访问标记默认初始化

 for (int i = 0; i graph.vertexNum; i++)

 graph.isTrav[i] = false;

 //遍历每个顶点

 for (int i = 0; i graph.vertexNum; i++)

 //广度遍历未访问过的顶点

 if (!graph.isTrav[i])

 DFSM(ref graph, i);

 #region 深度递归的具体算法

 /// summary 

/// 深度递归的具体算法

/// /summary 

/// param name="graph" /param 

/// param name="vertex" /param 

 public void DFSM(ref MatrixGraph graph, int vertex)

 Console.Write("- " + graph.vertex[vertex]);

 //标记为已访问

 graph.isTrav[vertex] = true;

 //要遍历的六个点

 for (int i = 0; i graph.vertexNum; i++)

 if (graph.isTrav[i] == false graph.edges[vertex, i] != 0)

 //深度递归

 DFSM(ref graph, i);

 #endregion

 #endregion

 #region prim算法获取最小生成树

 /// summary 

/// prim算法获取最小生成树

/// /summary 

/// param name="graph" /param 

 public void Prim(MatrixGraph graph, out int sum)

 //已访问过的标志

 int used = 0;

 //非邻接顶点标志

 int noadj = -1;

 //定义一个输出总权值的变量

 sum = 0;

 //临时数组，用于保存邻接点的权值

 int[] weight = new int[graph.vertexNum];

 //临时数组，用于保存顶点信息

 int[] tempvertex = new int[graph.vertexNum];

 //取出邻接矩阵的第一行数据，也就是取出第一个顶点并将权和边信息保存于临时数据中

 for (int i = 1; i graph.vertexNum; i++)

 //保存于邻接点之间的权值

 weight[i] = graph.edges[0, i];

 //等于0则说明V1与该邻接点没有边

 if (weight[i] == short.MaxValue)

 tempvertex[i] = noadj;

 else

 tempvertex[i] = int.Parse(graph.vertex[0]);

 //从集合V中取出V1节点，只需要将此节点设置为已访问过，weight为0集合

 var index = tempvertex[0] = used;

 var min = weight[0] = short.MaxValue;

 //在V的邻接点中找权值最小的节点

 for (int i = 1; i graph.vertexNum; i++)

 index = i;

 min = short.MaxValue;

 for (int j = 1; j graph.vertexNum; j++)

 //用于找出当前节点的邻接点中权值最小的未访问点

 if (weight[j] min tempvertex[j] != 0)

 min = weight[j];

 index = j;

 //累加权值

 sum += min;

 Console.Write("({0},{1}) ", tempvertex[index], graph.vertex[index]);

 //将取得的最小节点标识为已访问

 weight[index] = short.MaxValue;

 tempvertex[index] = 0;

 //从最新的节点出发，将此节点的weight比较赋值

 for (int j = 0; j graph.vertexNum; j++)

 //已当前节点为出发点，重新选择最小边

 if (graph.edges[index, j] weight[j] tempvertex[j] != used)

 weight[j] = graph.edges[index, j];

 //这里做的目的将较短的边覆盖点上一个节点的邻接点中的较长的边

 tempvertex[j] = int.Parse(graph.vertex[index]);

 #endregion

 #region dijkstra求出最短路径

 /// summary 

/// dijkstra求出最短路径

/// /summary 

/// param name="g" /param 

 public void Dijkstra(MatrixGraph g)

 int[] weight = new int[g.vertexNum];

 int[] path = new int[g.vertexNum];

 int[] tempvertex = new int[g.vertexNum];

 Console.WriteLine("\n请输入源点的编号：");

 //让用户输入要遍历的起始点

 int vertex = int.Parse(Console.ReadLine()) - 1;

 for (int i = 0; i g.vertexNum; i++)

 //初始赋权值

 weight[i] = g.edges[vertex, i];

 if (weight[i] short.MaxValue weight[i] 0)

 path[i] = vertex;

 tempvertex[i] = 0;

 tempvertex[vertex] = 1;

 weight[vertex] = 0;

 for (int i = 0; i g.vertexNum; i++)

 int min = short.MaxValue;

 int index = vertex;

 for (int j = 0; j g.vertexNum; j++)

 //顶点的权值中找出最小的

 if (tempvertex[j] == 0 weight[j] min)

 min = weight[j];

 index = j;

 tempvertex[index] = 1;

 //以当前的index作为中间点，找出最小的权值

 for (int j = 0; j g.vertexNum; j++)

 if (tempvertex[j] == 0 weight[index] + g.edges[index, j] weight[j])

 weight[j] = weight[index] + g.edges[index, j];

 path[j] = index;

 Console.WriteLine("\n顶点{0}到各顶点的最短路径为：（终点 源点） " + g.vertex[vertex]);

 //最后输出

 for (int i = 0; i g.vertexNum; i++)

 if (tempvertex[i] == 1)

 var index = i;

 while (index != vertex)

 var j = index;

 Console.Write("{0} ", g.vertex[index]);

 index = path[index];

 Console.WriteLine("{0}\n", g.vertex[index]);

 else

 Console.WriteLine("{0} - {1}: 无路径\n", g.vertex[i], g.vertex[vertex]);

 #endregion

}

 

算法速成系列至此就全部结束了，公司给我们的算法培训也于上周五结束，呵呵，赶一下同步。最后希望大家能对算法重视起来，

学好算法，终身收益。

秒懂算法 | 基于图神经网络的推荐算法 图神经网络(Graph Neural Networks,GNN)是近几年兴起的学科,用来作推荐算法自然效果也相当好,但是要学会基于图神经网络的推荐算法之前,需要对图神经网络自身有个了解。
数据结构和算法之图的认识 什么是图 ● 1. 一组顶点：通常用V(Vertex)表示顶点集合 ● 2. 一组边：通常用E(Edge)表示边的集合 ⅰ. 1. 边是顶点对：(v,w)属于E，其中v,w属于V ⅱ. 2. 有向边 v,w 表示从v指 ⅲ. 3.不考虑重边和自回路 抽象数据类型定义 ● 1.类型名称：图(Graph) ● 2. 数据对象集：G(V,E)由一个非空的有限顶点集合V和一个有限边集合E组成(可以一条边都没有，但不 能一个顶点都没有) ● 3. 操作集：对于任意图G属于Graph，以及v属于V，e属于E 1. Graph Create()：建立并返回空图
数据结构和算法之如何建立图 小白BG.1 邻接矩阵表示的图结点的结构 typedef struct GNode *PtrToGNode;//PtrToGNode是指向GNode的一个指针 struct GNode{ int Nv;//顶点数 int Ne;//边数 WeightType G[MaxVertexNum][MaxVertexNum]; DataType Data[MaxVertexNum];//存顶点的数据 typedef PtrToGNode MGraph;//以邻接矩阵存储的图类型。定义为指向节点的指针。因为要用到的时候 一个指针远远比一整个图来的快捷 小白BG.2 邻接矩阵表示的图——初始化
哈密顿路径在图G中找出一条包含所有顶点的简单路径，该路径称为哈密顿路径（1）图G是非完全有向图，且图G不一定存在哈密顿路径； ＞ （2）设计算法判断图G是否存在哈密顿路径，如果存在，输出一天哈密顿路径 哈密顿路径在图G中找出一条包含所有顶点的简单路径，该路径称为哈密顿路径（1）图G是非完全有向图，且图G不一定存在哈密顿路径； ＞ （2）设计算法判断图G是否存在哈密顿路径，如果存在，输出一天哈密顿路径