前言:
现时大家对“深度优先算法广度优先算法”都比较讲究,小伙伴们都想要学习一些“深度优先算法广度优先算法”的相关资讯。那么小编同时在网上收集了一些有关“深度优先算法广度优先算法””的相关文章,希望小伙伴们能喜欢,我们快快来学习一下吧!度:某个顶点的度就是依附于该顶点的边的个数
子图:一幅图中所有边(包含依附边的顶点)的子集
路径:是由边顺序连接的一系列定点组成
环:至少含有一条边且终点和起点相同的路径
连通图:如果图中任一个到另一个节点都存在一条路径,该图就叫连通图。
图的存储方式
1.邻接矩阵:
空间复杂度较高。
2.邻接表
图结构的java实现代码
import java.util.LinkedList;import java.util.Queue;/** * 无向图 * 数组索引代表顶点的值 */public class Graph { private int V; //顶点数量 private int E; //边数量 private Queue<Integer>[] adj; //邻接表 public Graph(int vertical) { this.V = vertical; this.adj = new Queue[vertical]; for (int i = 0; i < vertical; i++) { adj[i] = new LinkedList<>(); } } public int getV() { return V; } public int getE() { return E; } /** * 向图中某一顶点加一条边 * 无向图是没有方向的,需要让w出现在v的邻接表中,还需要让v出现在w的邻接表中 * * @param w * @param v */ public void addEdge(int v, int w) { adj[v].add(w); adj[w].add(v); this.E++; } /** * 获取和某一顶点关联的所有顶点 * * @param v * @return Queue */ public Queue<Integer> adj(int v) { return adj[v]; }}
深度优先搜索:指的是如果遇到一个子节点既有兄弟节点又有子节点,那么先找子节点,再找兄弟节点
实现代码如下:
/** * 深度优先搜索 */public class DepthFirstSearch { private int sCount; //记录多少个节点与s节点相通 private boolean[] marked; //代表顶点是否被搜索过 //找出g中与顶点s所有相邻的节点 public DepthFirstSearch(Graph g, int s) { marked = new boolean[g.getV()]; //初始化跟顶点s相通的数量 this.sCount = 0; dfs(g, s); } //找出g中与顶点v所有相通的节点 private void dfs(Graph graph, int v) { //将v节点标识为已搜索 marked[v] = true; for (Integer w : graph.adj(v)) { if (!marked[w]) { dfs(graph, w); } } sCount++; } private boolean marked(int w) { //判断w顶点与s顶点是否相通 return marked[w]; } private int count() {//获取所有与s顶点相通的总数 return sCount; }}
广度优先搜索:指的是如果遇到一个子节点既有兄弟节点又有子节点,那么先找兄弟节点,再找子节点,类似于层次遍历
代码如下:
import java.util.LinkedList;import java.util.Queue;/** * 广度优先搜索 */public class BreadthFirstSearch { private int sCount; //记录多少个节点与s节点相通 private final boolean[] marked; //代表顶点是否被搜索过 private final Queue<Integer> waitSearch; //存储带搜索顶点 //找出g中与顶点s所有相邻的节点 public BreadthFirstSearch(Graph g, int s) { marked = new boolean[g.getV()]; //初始化跟顶点s相通的数量 this.sCount = 0; waitSearch = new LinkedList<>(); bfs(g, s); } //找出g中与顶点v所有相通的节点 private void bfs(Graph graph, int v) { waitSearch.add(v); while (!waitSearch.isEmpty()) { Integer wait = waitSearch.poll(); for (Integer w : graph.adj(wait)) { if (!marked(w)) { marked[w] = true; sCount++; waitSearch.add(w); } } } } public boolean marked(int w) { //判断w顶点与s顶点是否相通 return marked[w]; } public int count() {//获取所有与s顶点相通的总数 return sCount; }}
版权声明:
本站文章均来自互联网搜集,如有侵犯您的权益,请联系我们删除,谢谢。
标签: #深度优先算法广度优先算法