算法系列15天快14天图[I]

今天我们来分享一下图，这是一个复杂的非线性数据结构。之所以复杂，是因为它们的数据元素之间的关系是任意的，而不是像树一样被几个性质定理所框住。各要素之间的关系非常明显。该图可以广泛应用，如网络爬虫、寻找最短路径等。但是不要害怕。越复杂的东西越能体现我们码农的核心竞争力。既然要学图，就要遵守图的游戏规则。1.概念图由一组“顶点”和一组“边”组成。写：g=(v，e)；1无向图意味着图中的边没有方向，所以边(V1、V2)自然等价于(V2、V1)，无向图的表达一般用“圆括号”。

2.有向图“graph”的边是有方向的，自然V1和V2的边不等同于V2和V1。有向图的表示一般用“尖括号”表示。

相邻点一侧的两个顶点称为相邻点，如(V1，V2)，(V1，V3)，(V1，V5)，但有向图中有“入边，出边”的概念，如V3的入边是V5，V3的出边是V2，V1，V4。顶点的度与“树”中的度具有相同的含义。但是有向图也分为“进度”和“出度”，相信大家都会明白。完全图的每两个顶点都有一条边，这是一种完美的表示，边的个数自然可以计算出来。无向图：边=n(n-1)/2；有向图：边=n(n-1)；//因为有向图有边，所以它必须是基于原图的‘X2’。

6子图如果G1的所有顶点和边都在G2，那么G1就是G2的子图，更不用说了。7.路径长度和循环(这些概念仍然很重要)路径：如果在Vm和Vn之间存在顶点序列。那么Vm到Vn就是一条路径。路径：路径中的“边数”。简单路径：如果路径的顶点不重复出现，则该路径是简单路径。循环：如果路径的第一个顶点和最后一个顶点相同，则它是一个循环。简单循环：第一个顶点与最后一个顶点相同，其他顶点不重复的循环是简单循环。8连通图和连通分支(对于无向图)连通图：在无向图中，如果任意两个顶点连通，则是连通图，例如，在V1、V2和V4之间。连通分支：无向图的最大连通子图是连通分支，一般的“连通分支”是图本身。除非是“非连通图”，下图是两个相连的组件。

9强连通图和强连通分支(对于有向图)这里主要关注的是“方向性”。V4可以去V3，但是V3不能去V4，所以不能称为强连通图。

网边有“权重”的图叫做网。很有意思，呵呵。二：“邻接矩阵”和“邻接表”常用于存储图的存储。邻接矩阵：技术是用两个数组，一个一维数组保存顶点信息，一个二维数组保存边缘信息，但缺点是占用空间比较大。邻接表：改进后的“邻接矩阵”缺点是不方便判断两个顶点之间是否有边，但节省了空间。3.创建一个图在这里，我们将使用邻接矩阵来保存这个图。一般操作如下：创建、遍历、复制代码如下： #区域邻接矩阵结构图////摘要///邻接矩阵结构图////摘要公共类矩阵图{//保存顶点信息公共字符串[]顶点；//保存边信息公共int[，]边；//深度搜索和广泛搜索的遍历标志：public bool[]IStrav；//顶点号public int vertexNum//公共int edgeNum的边数；//图类型public int graphType///summary////存储容量初始化/////summary//param name=' vertexNum '/param///param name=' edge num '/param///param name=' graph type '/param public matrix graph(int vertexNum，int edgeNum，int graph type){ this . vertexNum=vertexNum；this.edgeNum=edgeNumthis . graph type=graph type；vertex=新字符串[vertexNum]；edges=new int[VertixNum，VertixNum]；isTrav=new bool[VertixNum]；} } # endregion1创建一个图非常简单，让用户输入一些‘边、点、权重’来构建一个图。复制代码如下： # Region Graph的区域///Summary///Graph的创建///Summary//Param Name=' g '/Param公共矩阵图Create MatrixGraph () {Console。Writeline('请输入创建的图的顶点数和边数，以及它是否是无向图(。');var initData=Console。ReadLine()。拆分('，')。Select(i=int。解析(I))。to list()；matrix graph=new matrix graph(initData[0]，initData[1]，initData[2])；控制台。WriteLine('请输入每个顶点的信息：')；for(int I=0；i graph.vertexNumI){ console . write(' \ n(I 1)'顶点为： ')；var single=控制台。ReadLine()；//顶点信息被添加到集合中。graph . vertex[I]=single；}控制台。write line(' \ n请输入组成两个顶点的边和权重，用逗号分隔。\ n ')；for(int I=0；i graph.edgeNumI){控制台。write(edge : \ t ' in '(I 1)')；initData=控制台。ReadLine()。拆分('，')。选择(j=int。解析(j))。to list()；int start=initData[0]；int end=initData[1]；int weight=initData[2]；//将graph.edges [start-1，end-1]=权重赋给矩阵的指定坐标位置；//如果是无向图，则数据在“两个或四个”象限是对称的if (graph。graph type==1) {graph。边[end-1，start-1]=权重；} }返回图；} #endregion2广度优先针对下面的“图结构”，如何才能先给广度？其实我们只需要深刻理解广搜定义的规章制度。为了防止同一顶点在遍历过程中被多次访问，顶点的下标可以存储在sTrav[]的bool数组中，以识别该节点是否被访问过。步骤1:首先，我们从isTrav阵列中选择一个未访问的节点，例如V1。第二步：访问V1的相邻点V2、V3和V5，将这三个节点标记为真。第三步：第二步后，我们开始参观V2的邻近点V1和V3，但都被参观了。第四步：我们在第二步结束时从V3访问它的邻近点V2、V1、V5和V4。幸运的是，V4没有被访问，所以在这个时候标记它。第五步：我们访问了V5的相邻点V1、V3和V4，但都已经访问过了。第六步：在一些图中，一个顶点的“广度优先”不能遍历所有顶点。此时，我们可以通过重复步骤(1-5)来完成广度优先遍历。

复制代码如下： #区域广度优先///summary///广度优先///summary//param name=' graph '/param public void bfs traverse(矩阵图graph){//访问标记默认为初始化为(int I=0；i graph.vertexNumI){ graph . IStrav[I]=false；}//遍历(int I=0；i graph.vertexNumI) {//广泛遍历未访问的顶点if(！graph.isTrav[i]) { BFSM(ref graph，I)；} } }//summary////广度遍历算法////summary///param name=' graph '/param public void bfsm(ref matrix graph，int vertex){//这里，我们使用队列Queueint queue=new Queueint()；//加入队列中的顶点。先入队(顶点)；//标记该顶点已被访问。graph . iStrav[顶点]=true；//输出顶点控制台. write('-' graph . vertex[vertex])；//遍历顶点的相邻点，同时(排队。数数！=0) { var temp=queue。出列()；//遍历矩阵的横坐标为(int I=0；i graph.vertexNumi ) { if(！graph . iStrav[i]graph . edges[temp，I]！=0){ graph . iStrav[I]=true；排队。入队(I)；//输出未访问的顶点控制台. write('-' graph . vertex[I])；}}}} #endregion3深度优先也是图片。先看看如何实现深度。深度优先就像一个有着强健骨骼的勇者，遵循着“能进则进，不进则退”的原则。第一步是从isTrav阵列中选择一个未访问的节点，例如V1。第二步：然后游览V1的邻近景点，直到无路可退。当路线是V1、V2、v3、v4和V5时，访问相邻的V1点，发现V1被访问。这时，直到V1来访。第三步：在同一个图中，一个顶点的“深度优先”不能遍历所有顶点。此时，我们可以通过重复步骤(1-2)来完成深度优先遍历。

复制代码代码如下： #地区深度优先///摘要///深度优先////summary////param name=' graph '/param public void DFSTraverse(矩阵图图形){//访问标记默认初始化for(int I=0；i graph.vertexNumI){ graph。iSTRav[I]=false；} //遍历每个顶点for(int I=0；i graph.vertexNumi ) { //广度遍历未访问过的顶点if(！DFSM；} } } #地区深度递归的具体算法///摘要///深度递归的具体算法////summary////param name=' graph '/param///param name=' vertex '/param public void DFSM(ref matrix graph graph，int vertex) { Console .写(“-”图。顶点[顶点])；//标记为已访问图表。iStrav[顶点】=真；//要遍历的六个点for(int I=0；i graph.vertexNumI){ if(graph。iStrav[i]==假图形。边[顶点，我]！=0) { //深度递归DFSM(参考图，我)；} } } #endregion #endregion最后上一下总的代码复制代码代码如下：使用系统；使用系统。集合。通用；使用系统Linq .使用系统。文字；命名空间MatrixGraph{公共类程序{ static void Main(string[]args){ matrix graph manager manager=new matrix graph manager()；//创建图矩阵图=经理.CreateMatrixGraph()；经理OutMatrix(图表);控制台。写('广度递归： \ t ')；经理BFSTraverse(图形);控制台。写入(' \n深度递归： \ t ')；经理DFSTraverse(图形);控制台ReadLine()；} } #地区邻接矩阵的结构图///摘要///邻接矩阵的结构图////摘要公共类MatrixGraph { //保存顶点信息公共字符串[]顶点；//保存边信息公共int[，]边；//深搜和广搜的遍历标志public bool[]IStrav；//顶点数量public int VertixNum//边数量public int edgeNum//图类型public int graphType///摘要///存储容量的初始化////summary///param name=' vertexNum '/param///param name=' edge num '/param///param name=' graph type '/param public matrix graph(int vertexNum，int edgeNum，int graph type){ this。vertexNum=vertexNumthis.edgeNum=edgeNumthis。图形类型=图形类型；顶点=新字符串[VertixNum]；edges=new int[VertixNum，VertixNum]；isTrav=new bool[VertixNum]；} } #endregion ///summary///图的操作类////汇总公共类MatrixGraphManager { #区域图的创建///摘要///图的创建////summary////param name=' g '/param public matrix graph create matrix graph(){ Console .WriteLine(“”请输入创建图的顶点个数，边个数，是否为无向图(0,1来表示),已逗号隔开。');变量初始化数据=控制台.ReadLine().拆分(',')。选择(i=int .解析).to list()；矩阵图=新矩阵图(initData[0]，initData[1]，initData[2])；控制台WriteLine(“”请输入各顶点信息：');for(int I=0；I graph . vertexnumi){ 0控制台。写入(' \n第1 '个顶点为：');var single=控制台ReadLine()；//顶点信息加入集合中图表。顶点[I]=单个；}控制台WriteLine('\n请输入构成两个顶点的边和权值，以逗号隔开。

\ n ')；for(int I=0；I graph . EdgeNumi){ 0控制台。写('第1 '条边： \ t ')；initData=控制台ReadLine().拆分(',')。选择(j=int .解析(j)).to list()；int start=initData[0]；int end=initData[1]；int weight=initData[2]；//给矩阵指定坐标位置赋值graph.edges[start - 1，end - 1]=权重；//如果是无向图，则数据呈"二，四"象限对称if(图表。graph type==1){ graph。边[end-1，start-1]=权重；} }返回图；} #endregion #region输出矩阵数据///摘要///输出矩阵数据////summary///param name=' graph '/param public void OutMatrix(matrix graph){ for(int I=0；I graph . vertexnumi){ for(int j=0；j graph . vertexnumj){ 0控制台Write(graph . edge[I，j]' \ t ')；} //换行控制台WriteLine()；} } #endregion #region广度优先///摘要///广度优先////summary////param name=' graph '/param public void BFSTraverse(矩阵图图形){//访问标记默认初始化for(int I=0；i graph.vertexNumI){ graph。iSTRav[I]=false；} //遍历每个顶点for(int I=0；i graph.vertexNumi ) { //广度遍历未访问过的顶点if(！graph.isTrav[i]) { BFSM(ref graph，I)；} } } ///摘要///广度遍历具体算法////summary////param name=' graph '/param public void BFSM(ref matrix graph graph，int vertex) { //这里就用系统的队列Queueint queue=new Queueint()；//先把顶点入队排队。入队（顶点);//标记此顶点已经被访问图表。iStrav[顶点】=真；//输出顶点控制台。写(“-”图。顶点[顶点])；//广度遍历顶点的邻接点而(排队。数数！=0) { var temp=queue .出列();//遍历矩阵的横坐标for(int I=0；i graph.vertexNumi ) { if(！图表。iSTRav[I]图。边缘[温度，我]！=0){ graph。iStrav[I]=真；排队。入队；//输出未被访问的顶点控制台。写(“-”图。顶点[I])；} } } } #endregion #region深度优先///摘要///深度优先////summary////param name=' graph '/param public void DFSTraverse(矩阵图图形){//访问标记默认初始化for(int I=0；i graph.vertexNumI){ graph。iSTRav[I]=false；} //遍历每个顶点for(int I=0；i graph.vertexNumi ) { //广度遍历未访问过的顶点if(！DFSM；} } } #地区深度递归的具体算法///摘要///深度递归的具体算法////summary////param name=' graph '/param///param name=' vertex '/param public void DFSM(ref matrix graph graph，int vertex) { Console .写(“-”图。顶点[顶点])；//标记为已访问图表。iStrav[顶点】=真；//要遍历的六个点for(int I=0；i graph.vertexNumI){ if(graph。iStrav[i]==假图形。边[顶点，我]！=0) { //深度递归DFSM(参考图，我)；} } } #endregion #endregion }}代码中我们构建了如下的"图"。