做早餐煲汤网站,房产网站系统源码,wordpress升级php,wordpress term函数文章目录 图的简介图的定义图的结构图的分类无向图有向图带权图#xff08;Wighted Graph#xff09; 图的存储邻接矩阵#xff08;Adjacency Matrix#xff09;邻接表代码实现 图的遍历深度优先搜索#xff08;DFS#xff0c;Depth Fisrt Search#xff09;遍历抖索过程… 文章目录 图的简介图的定义图的结构图的分类无向图有向图带权图Wighted Graph 图的存储邻接矩阵Adjacency Matrix邻接表代码实现 图的遍历深度优先搜索DFSDepth Fisrt Search遍历抖索过程 广度优先搜索BFSBreadth First Search遍历搜索过程 完整代码 图的简介
图的定义
图Graph一种比线性表和树更加复杂的结构。在图形结构中顶点vertex之间的关系是任意的途中任意两个顶点之间都有可能关联。
图的结构 顶点vertex图中的元素就叫做顶点。如图ABCDEF。边edge: 顶点之间建立的连接关系就叫做边。如图顶点A和顶点B中间的连线。度drgree: 跟顶点相连的边的条数就叫做度。如图顶点A与B、C、D相连则A的度就是3。
图的分类
无向图 如上图边edge没有方向的图叫做无向图。
有向图 如上图边edge有方向的图叫做有向图。
带权图Wighted Graph 如上图中每条边都带有一个权重weight的图就是带权图。
图的存储
邻接矩阵Adjacency Matrix
邻接矩阵的底层是一个二维数组如下图该图可以转化为一个二维数据表格。
无向图 如果顶点 i 和顶点 j 之间有边但是没有方向和权重那么我们就用array[i][j] array[j][i] 1来表示无向图。 有向图 如果顶点 i 到顶点 j 之间有一条箭头从顶点 i 指向顶点 j 的边那我们就将 A[i][j]标记为 1。同理如果有一条箭头从顶点 j 指向顶点 i 的边我们就将 A[j][i]标记为 1。 带权图 数组中就存储相应值当作权重。
邻接表
邻接表中每个顶点对应一条链表链表中存储的是与这个顶点相连接的其他顶点。 图中的一个有向图的邻接表的存储方式前面的数组存储的是所有的顶点每个顶点后面链接的块代表前面顶点所指向的顶线和边的权值。如果该点还有其它顶点则继续在块后面添加即可。
代码实现
定点Vertex类
package com.xxliao.datastructure.graph;/*** author xxliao* description: 图 - 定点类* date 2024/5/29 16:56*/
public class Vertex {// 顶点名称protected String name;// 该顶点出发的边protected Edge edge;public Vertex(String name, Edge edge) {this.name name;this.edge edge;}
}边Edge类
package com.xxliao.datastructure.graph;/*** author xxliao* description: 图 - 边类* date 2024/5/29 16:57*/
public class Edge {// 被指向的顶点protected String name;// 权重protected int weight;// 顶点的下一条边protected Edge next;public Edge(String name, int weight, Edge next) {this.name name;this.weight weight;this.next next;}
}
图Graph类
package com.xxliao.datastructure.graph;import java.util.HashMap;
import java.util.List;
import java.util.Map;/*** author xxliao* description: 邻接表实现图* date 2024/5/29 16:00*/
public class Graph {// 存储顶点容器private MapString,Vertex vertexes;public Graph() {this.vertexes new HashMapString,Vertex();}/*** description 添加顶点* author xxliao* date 2024/5/29 17:02*/public void addVertex(String vertexName) {vertexes.put(vertexName,new Vertex(vertexName,null));}/*** description 添加边* author xxliao* date 2024/5/29 17:05*/public void addEdge(String beginVertexName,String endVertexName,int weight) {// 获取出发顶点Vertex beginVertex vertexes.get(beginVertexName);if(beginVertex null) {// 没有开始顶点创建beginVertex new Vertex(beginVertexName,null);vertexes.put(beginVertexName,beginVertex);}// 创建边对象Edge edge new Edge(endVertexName,weight,null);if(beginVertex.edge null) {//当前顶点还没有边直接设置beginVertex.edge edge;}else {Edge lastEdge beginVertex.edge;while(lastEdge.next ! null) {lastEdge lastEdge.next;}// 设置到末尾lastEdge.next edge;}}
}图的遍历
图的遍历是指从给定图的任意顶点可以称为初始顶点出发按照某种搜索方法沿着图边访问所有的顶点且每个顶点仅被访问一次这个过程就是图的遍历。图的遍历根据搜索过程不用可以分为深度优先搜索和广度优先搜索。
深度优先搜索DFSDepth Fisrt Search
深度优先搜索从起点出发从规定的方向中选择一个方向不段的往前走直到无法继续位置然后尝试另外一个方向直到最后走完所有顶点。
遍历抖索过程
假设我们有这么一个图里面有A、B、C、D、E、F、G、H 8 个顶点点和点之间的联系如下图所示 必须依赖栈Stack特点是后进先出LIFO。 第一步选择一个起始顶点例如从顶点 A 开始。把 A 压入栈标记它为访问过用红色标记并输出到结果中。 第二步寻找与 A 相连并且还没有被访问过的顶点顶点 A 与 B、D、G 相连而且它们都还没有被访问过我们按照字母顺序处理所以将 B 压入栈标记它为访问过并输出到结果中。 第三步现在我们在顶点 B 上重复上面的操作由于 B 与 A、E、F 相连如果按照字母顺序处理的话A 应该是要被访问的但是 A 已经被访问了所以我们访问顶点 E将 E 压入栈标记它为访问过并输出到结果中。 第四步从 E 开始E 与 B、G 相连但是B刚刚被访问过了所以下一个被访问的将是G把G压入栈标记它为访问过并输出到结果中。 第五步现在我们在顶点 G 的位置由于与 G 相连的顶点都被访问过了类似于我们走到了一个死胡同必须尝试其他的路口了。所以我们这里要做的就是简单地将 G 从栈里弹出表示我们从 G 这里已经无法继续走下去了看看能不能从前一个路口找到出路。 如果发现周围的顶点都被访问了就把当前的顶点弹出。 第六步现在栈的顶部记录的是顶点 E我们来看看与 E 相连的顶点中有没有还没被访问到的发现它们都被访问了所以把 E 也弹出去。 第七步当前栈的顶点是 B看看它周围有没有还没被访问的顶点有是顶点 F于是把 F 压入栈标记它为访问过并输出到结果中。 第八步当前顶点是 F与 F 相连并且还未被访问到的点是 C 和 D按照字母顺序来下一个被访问的点是 C将 C 压入栈标记为访问过输出到结果中。 第九步当前顶点为 C与 C 相连并尚未被访问到的顶点是 H将 H 压入栈标记为访问过输出到结果中。 第十步当前顶点是 H由于和它相连的点都被访问过了将它弹出栈。 第十一步当前顶点是 C与 C 相连的点都被访问过了将 C 弹出栈。 第十二步当前顶点是 F与 F 相连的并且尚未访问的点是 D将 D 压入栈输出到结果中并标记为访问过。 第十三步当前顶点是 D与它相连的点都被访问过了将它弹出栈。以此类推顶点 FBA 的邻居都被访问过了将它们依次弹出栈就好了。最后当栈里已经没有顶点需要处理了我们的整个遍历结束。
广度优先搜索BFSBreadth First Search
遍历搜索过程
假设我们有这么一个图里面有A、B、C、D、E、F、G、H 8 个顶点点和点之间的联系如下图所示 对这个图进行深度优先的遍历。
依赖队列Queue先进先出FIFO。 一层一层地把与某个点相连的点放入队列中处理节点的时候正好按照它们进入队列的顺序进行。
第一步选择一个起始顶点让我们从顶点 A 开始。把 A 压入队列标记它为访问过用红色标记。 第二步从队列的头取出顶点 A打印输出到结果中同时将与它相连的尚未被访问过的点按照字母大 小顺序压入队列同时把它们都标记为访问过防止它们被重复地添加到队列中。 第三步从队列的头取出顶点 B打印输出它同时将与它相连的尚未被访问过的点也就是 E 和 F 压入队列同时把它们都标记为访问过。 第四步继续从队列的头取出顶点 D打印输出它此时我们发现与 D 相连的顶点 A 和 F 都被标记 访问过了所以就不要把它们压入队列里。 第五步接下来队列的头是顶点 G打印输出它同样的G 周围的点都被标记访问过了。我们不做 任何处理。 第六步队列的头是 E打印输出它它周围的点也都被标记为访问过了我们不做任何处理。 第七步接下来轮到顶点 F打印输出它将 C 压入队列并标记 C 为访问过。 第八步将 C 从队列中移出打印输出它与它相连的 H 还没被访问到将 H 压入队列将它标记为 访问过。 9.第九步队列里只剩下 H 了将它移出打印输出它发现它的邻居都被访问过了不做任何事情。 第十步队列为空表示所有的点都被处理完毕了程序结束。
完整代码
https://github.com/xxliao100/datastructure_algorithms.git 文章转载自： http://www.morning.tsmcc.cn.gov.cn.tsmcc.cn http://www.morning.mslsn.cn.gov.cn.mslsn.cn http://www.morning.mjmtm.cn.gov.cn.mjmtm.cn http://www.morning.nsyzm.cn.gov.cn.nsyzm.cn http://www.morning.rmjxp.cn.gov.cn.rmjxp.cn http://www.morning.bpwz.cn.gov.cn.bpwz.cn http://www.morning.gxtbn.cn.gov.cn.gxtbn.cn http://www.morning.gjws.cn.gov.cn.gjws.cn http://www.morning.jkpnm.cn.gov.cn.jkpnm.cn http://www.morning.wkqrp.cn.gov.cn.wkqrp.cn http://www.morning.qnftc.cn.gov.cn.qnftc.cn http://www.morning.kgjyy.cn.gov.cn.kgjyy.cn http://www.morning.jrqcj.cn.gov.cn.jrqcj.cn http://www.morning.pngfx.cn.gov.cn.pngfx.cn http://www.morning.qgfkn.cn.gov.cn.qgfkn.cn http://www.morning.dhbyj.cn.gov.cn.dhbyj.cn http://www.morning.crfjj.cn.gov.cn.crfjj.cn http://www.morning.rjnx.cn.gov.cn.rjnx.cn http://www.morning.ghqyr.cn.gov.cn.ghqyr.cn http://www.morning.rfbpq.cn.gov.cn.rfbpq.cn http://www.morning.prddj.cn.gov.cn.prddj.cn http://www.morning.epeij.cn.gov.cn.epeij.cn http://www.morning.nqxdg.cn.gov.cn.nqxdg.cn http://www.morning.qyhcg.cn.gov.cn.qyhcg.cn http://www.morning.pdmml.cn.gov.cn.pdmml.cn http://www.morning.mdfxn.cn.gov.cn.mdfxn.cn http://www.morning.mdmxf.cn.gov.cn.mdmxf.cn http://www.morning.qnbgh.cn.gov.cn.qnbgh.cn http://www.morning.leyuhh.com.gov.cn.leyuhh.com http://www.morning.jqjnl.cn.gov.cn.jqjnl.cn http://www.morning.ktlfb.cn.gov.cn.ktlfb.cn http://www.morning.cgtfl.cn.gov.cn.cgtfl.cn http://www.morning.ydgzj.cn.gov.cn.ydgzj.cn http://www.morning.dfmjm.cn.gov.cn.dfmjm.cn http://www.morning.qgbfx.cn.gov.cn.qgbfx.cn http://www.morning.fkgcd.cn.gov.cn.fkgcd.cn http://www.morning.bpkqd.cn.gov.cn.bpkqd.cn http://www.morning.wcft.cn.gov.cn.wcft.cn http://www.morning.tdfyj.cn.gov.cn.tdfyj.cn http://www.morning.kycwt.cn.gov.cn.kycwt.cn http://www.morning.mlbdr.cn.gov.cn.mlbdr.cn http://www.morning.ndmbz.cn.gov.cn.ndmbz.cn http://www.morning.hdpcn.cn.gov.cn.hdpcn.cn http://www.morning.sqtsl.cn.gov.cn.sqtsl.cn http://www.morning.jnhhc.cn.gov.cn.jnhhc.cn http://www.morning.snmsq.cn.gov.cn.snmsq.cn http://www.morning.zzaxr.cn.gov.cn.zzaxr.cn http://www.morning.wmfmj.cn.gov.cn.wmfmj.cn http://www.morning.zcwtl.cn.gov.cn.zcwtl.cn http://www.morning.jzykq.cn.gov.cn.jzykq.cn http://www.morning.bndkf.cn.gov.cn.bndkf.cn http://www.morning.cpctr.cn.gov.cn.cpctr.cn http://www.morning.mqldj.cn.gov.cn.mqldj.cn http://www.morning.yrwqz.cn.gov.cn.yrwqz.cn http://www.morning.wdqhg.cn.gov.cn.wdqhg.cn http://www.morning.pwrkl.cn.gov.cn.pwrkl.cn http://www.morning.elbae.cn.gov.cn.elbae.cn http://www.morning.pgfkl.cn.gov.cn.pgfkl.cn http://www.morning.pkfpl.cn.gov.cn.pkfpl.cn http://www.morning.lydtr.cn.gov.cn.lydtr.cn http://www.morning.krdmn.cn.gov.cn.krdmn.cn http://www.morning.lxqyf.cn.gov.cn.lxqyf.cn http://www.morning.bfmrq.cn.gov.cn.bfmrq.cn http://www.morning.qqrqb.cn.gov.cn.qqrqb.cn http://www.morning.kwz6232.cn.gov.cn.kwz6232.cn http://www.morning.wscfl.cn.gov.cn.wscfl.cn http://www.morning.sbjhm.cn.gov.cn.sbjhm.cn http://www.morning.dbqg.cn.gov.cn.dbqg.cn http://www.morning.mqfhy.cn.gov.cn.mqfhy.cn http://www.morning.ntkpc.cn.gov.cn.ntkpc.cn http://www.morning.bpmnx.cn.gov.cn.bpmnx.cn http://www.morning.fycjx.cn.gov.cn.fycjx.cn http://www.morning.ljdhj.cn.gov.cn.ljdhj.cn http://www.morning.rdmn.cn.gov.cn.rdmn.cn http://www.morning.mhcys.cn.gov.cn.mhcys.cn http://www.morning.bpmnc.cn.gov.cn.bpmnc.cn http://www.morning.mtgkq.cn.gov.cn.mtgkq.cn http://www.morning.ltxgk.cn.gov.cn.ltxgk.cn http://www.morning.ndfwh.cn.gov.cn.ndfwh.cn http://www.morning.rwqj.cn.gov.cn.rwqj.cn
