- 场景:需要采用不同的算法实现功能。定义一列算法,把他们封装起来,并且使他们可以相互替换。
- 解决1:使用if … else… 进行维护。解决2:对类实现不同的算法策略。比如姓名排序人,年龄排序人等。
- 解决1缺点:不容易扩展。解决2去缺点:耦合度太高。
- 改进,使用策略模式。把这些算法封装成一个一个的类,从而可以实现任意替换。
- 优点:1. 算法可以自由切换。2. 扩展性良好。3. 满足开闭原则。
- 缺点:1. 策略类很多。
- 实例:Arrays.sort以及比较器的实现。
自定义的类图如下:
使用策略模式封装二分图匹配算法。
- 使用JudgeMethod策略封装算法
- 实现两个算法:bfs或者dfs算法,用户也可以自己指定算法。
- 用户使用二分图类进行判断,可以自行指定所需要使用的算法,也可以自己实现相应的算法。
- 代码扩展性良好。满足了开闭原则。
package Graph; import java.util.ArrayDeque; import java.util.Arrays; import java.util.Comparator; import java.util.Queue; @FunctionalInterface interface JudgeMethod { public boolean isBipartite(int[][] grapth); } class JudegeBfs implements JudgeMethod{ private int[] color; private int[][] gapth; private int n; private boolean bfs(int bg) { Queueque = new ArrayDeque<>(); color[bg] = 1; que.add(bg); while (!que.isEmpty()) { int u = que.poll(); for (int v : gapth[u]) { if (color[v] == color[u]) return false; if (color[v] != 0) continue; // 颜色和它一样不用染色 color[v] = 3 - color[u]; que.add(v); } } return true; } @Override public boolean isBipartite(int[][] grapth) { this.gapth = grapth; for (int i = 0; i < n; i++) { if (color[i] == 0 && !bfs(i)) { return false; } } return true; } } class JudegeDfs implements JudgeMethod{ private int[] color; private int[][] gapth; private int n; private boolean dfs(int u) { for (int v :gapth[u]) { if (color[u] == color[v]) return false; if (color[v] != 0) continue; color[v] = 3 - color[u]; if (!dfs(v)) return false; } return true; } @Override public boolean isBipartite(int[][] grapth) { this.gapth = grapth; for (int i = 0; i < n; i++) { if (color[i] == 0) { color[i] = 1; if (!dfs(i)) return false; } } return true; } } public class Bipartite { public static boolean isBipartite(int[][] graph, JudgeMethod m) { return m.isBipartite(graph); } } class Test { public static void main(String[] args) { // 保证图没有重边,没有自环,无向图, 不保证连通。 int[][] G = { {1,2,3}, {4,5,6} }; boolean ans1 = Bipartite.isBipartite(G, new JudegeDfs()); // 使用bfs boolean ans2 = Bipartite.isBipartite(G, new JudegeBfs()); // 使用dfs boolean ans3 = Bipartite.isBipartite(G, new JudgeMethod() { @Override public boolean isBipartite(int[][] grapth) { return false; } }); // 用户自定义 System.out.println(ans1); System.out.println(ans2); System.out.println(ans3); } }