网站建设三站合一,搜索风云排行榜,电商培训一般培训什么,系统重装后 怎么装wordpress文章目录 1. 代码仓库2. 单源路径2.1 思路2.2 主要代码 3. 所有点对路径3.1 思路3.2 主要代码 4. 路径问题的优化-提前结束递归4.1 思路4.2 主要代码 5. 检测环5.1 思路5.2 主要代码 6. 二分图6.1 思路6.2 主要代码6.2.1 遍历每个联通分量6.2.2 递归判断相邻两点的颜色是否一致… 文章目录 1. 代码仓库2. 单源路径2.1 思路2.2 主要代码 3. 所有点对路径3.1 思路3.2 主要代码 4. 路径问题的优化-提前结束递归4.1 思路4.2 主要代码 5. 检测环5.1 思路5.2 主要代码 6. 二分图6.1 思路6.2 主要代码6.2.1 遍历每个联通分量6.2.2 递归判断相邻两点的颜色是否一致 1. 代码仓库 https://github.com/Chufeng-Jiang/Graph-Theory 2. 单源路径
2.1 思路 构造visited数组和pre数组 1.1 visited数组记录当前节点是否访问过 也可以不使用visited数组pre数组全部初始化为-1联通的顶点对应的pre数组的值为前一个节点pre数组中值为-1的都是不连通的顶点。 1.2 pre数组记录当前节点的前一个节点使用pre数组对终点进行反推回源点并记录将终点到原点的路径反序输出 2.2 主要代码 public SingleSourcePath(Graph G, int s){ //单源路径要把源s传进来而且只考虑与s连通的顶点不连通的不考虑G.validateVertex(s);this.G G;this.s s;visited new boolean[G.V()];pre new int[G.V()];dfs(s, s);}private void dfs(int v, int parent){ //参数一当前顶点 参数二上一个顶点visited[v] true;pre[v] parent;for(int w: G.adj(v)) //跟v相邻的所有顶点相当于v是源遍历与当前顶点相邻的所有点if(!visited[w])dfs(w, v); //顶点源}public IterableInteger path(int t){ //从源到t的路径ArrayListInteger res new ArrayListInteger();if(!isConnectedTo(t)) return res; int cur t; // 从t往回找while(cur ! s){res.add(cur); //添加当前节点循环内不包含源cur pre[cur]; //pre[cur]的值是cur的上一个节点}res.add(s); //添加源Collections.reverse(res);return res;}3. 所有点对路径
3.1 思路 对所有顶点进行遍历创建每一个点的单源路径数组。 3.2 主要代码
public AllPairsPath(Graph G){this.G G;paths new SingleSourcePath[G.V()];for(int v 0; v G.V(); v )paths[v] new SingleSourcePath(G, v);
}4. 路径问题的优化-提前结束递归
4.1 思路
在填充visited和pre数组的时候如果遇到了目标节点直接结束。剩下的节点不进行处理。 if(v t) return true; //程序出口当到达t顶点时返回true提前结束递归而不仅仅是返回return 4.2 主要代码 private boolean dfs(int v, int parent){visited[v] true;pre[v] parent;if(v t) return true; //程序出口当到达t顶点时返回true提前结束递归而不仅仅是返回returnfor(int w: G.adj(v)) //遍历与v相邻的顶点if(!visited[w]) //如果相邻的顶点没有被访问过if(dfs(w, v)) //递归遍历相邻的顶点如果到达 vt则值为truereturn true; //提前返回truereturn false; // 转一圈没法达到t就可以返回false}5. 检测环
5.1 思路 从某一点v出发找到了点ww被访问过并且w不是v的前一个节点 5.2 主要代码
public CycleDetection(Graph G){this.G G;visited new boolean[G.V()];//要对所有的连通分量进行环检测for(int v 0; v G.V(); v )if(!visited[v]) //如果没有访问过if(dfs(v, v)){ //则进行深度搜索如果深度搜索出来的是true说明有环则进入循环breakhasCycle true;break;}
}private boolean dfs(int v, int parent){visited[v] true;for(int w: G.adj(v))if(!visited[w]){ //case1如果w没有被访问过if(dfs(w, v)) //如果dfs返回true则说明有环。因为dfs有环才会返回true那么进入if选择语句return true提前结束return true;}else if(w ! parent) // case2从v出发找到了ww还被访问过并且w不是v的前一个节点return true; // 此时找到了环//其他的情况找一圈没有找到环返回falsereturn false;
}6. 二分图 6.1 思路 二分图可以通过染色过程把顶点区分开 [-1:顶点还没染色] [0:一种颜色] [1:另外一种颜色] 6.2 主要代码
6.2.1 遍历每个联通分量
dfs(v, 0) 返回true代表相连的两点颜色不一样暂未出现矛盾dfs(v, 0) 返回false代表相连的两点颜色一样不符合二分图的定义因此进入if语句块设置isBipartite false;并且提前结束循环。
for(int v 0; v G.V(); v )if(!visited[v]) //如果没有被访问// 起始的时候把v统一染成0色如果dfs返回的false进入下面结构体否则跳出执行vif(!dfs(v, 0)){ isBipartite false; // 检测出错了就设置成falsebreak; // 后续的循环就不需要进行了}6.2.2 递归判断相邻两点的颜色是否一致
private boolean dfs(int v, int color){ //参数一顶点 参数二颜色visited[v] true;colors[v] color;//依次判断相邻顶点w的颜色for(int w: G.adj(v))if(!visited[w]){ //如果w没有被访问过则进入判断if(!dfs(w, 1 - color)) //如果v的颜色是0那么w的颜色应该是1。如果v的颜色是1那么w的颜色应该是0.return false; //如果相邻的两个顶点颜色一样那么就不是二分图}else if(colors[w] colors[v]) //如果相邻的两个顶点颜色一样那么就不是二分图return false;return true;
}
