策略模式

1. 场景：需要采用不同的算法实现功能。定义一列算法，把他们封装起来，并且使他们可以相互替换。
2. 解决1：使用if … else… 进行维护。解决2：对类实现不同的算法策略。比如姓名排序人，年龄排序人等。
3. 解决1缺点：不容易扩展。解决2去缺点：耦合度太高。
4. 改进，使用策略模式。把这些算法封装成一个一个的类，从而可以实现任意替换。
5. 优点：1. 算法可以自由切换。2. 扩展性良好。3. 满足开闭原则。
6. 缺点：1. 策略类很多。
7. 实例：Arrays.sort以及比较器的实现。

代码示例

自定义的类图如下：

使用策略模式封装二分图匹配算法。

• 使用JudgeMethod策略封装算法
• 实现两个算法：bfs或者dfs算法，用户也可以自己指定算法。
• 用户使用二分图类进行判断，可以自行指定所需要使用的算法，也可以自己实现相应的算法。
• 代码扩展性良好。满足了开闭原则。

package Graph;

import java.util.ArrayDeque;
import java.util.Arrays;
import java.util.Comparator;
import java.util.Queue;

/**
 * @author: Zekun Fu
 * @date: 2022/8/8 17:05
 * @Description: 判断是否是二分图，使用二分图匹配算法
 *
 * 1. 使用策略模式
 * 2. 保证没有重边和自环
 */

@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) {
        Queue<Integer> que = 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);
    }
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114