二分图(二部图)判别和最大匹配问题(匈牙利算法)

二分图(二部图)

如何判断一个图是否是二分图,二分图就是可以将图分为两个部分,边都是在两个部分之间,而每个部分内部不可以有边相连。

这样如果二部图中存在一个环,那么这个环中的边数必须是偶数,可以画图验证一下三角形、四边形和五边形就知道了。

那么环中的边数是偶数,就可以利用染色算法来进行判别,环是偶数则两种颜色可以交替,否则必定有两个相邻的节点颜色相同。

可以利用BFS算法(结合队列)对二分图进行判别。关键代码如下:

输入:

7
1 4
1 5
1 6
2 5
3 5
3 6
3 4
2 6
 public static void main(String[] args) throws Exception{
       
        Scanner sc = new Scanner(System.in);
        //读入数据,并构建邻接表
        int n = sc.nextInt();
        int [] colors = new int[n];
        HashMap <Integer, ArrayList<Integer>> hm = new HashMap<>();
        for (int i = 0; i < n; i++) {
            hm.put(i, new ArrayList<>());
        }
        while (sc.hasNext()) {
            int forward = sc.nextInt();
            int backward = sc.nextInt();
            hm.get(forward).add(backward);
            hm.get(backward).add(forward);
        }
        System.out.println(hm);
        //这里节点的标识与数组的下表一一对应,也是为了简化问题,如果不是一一对应的情况,可能还需要做一次 index -> node 的转换

        for (int i = 0; i < n; i++) {
            int color = colors[i];
            if (color == 0) {
                boolean valid = BFS(hm, colors, i);
                if (!valid) {
                    System.out.println("not valid");
                    System.out.println(Arrays.toString(colors));
                    return;
                }
            }
        }
        System.out.println("valid!");
        System.out.println(Arrays.toString(colors));
    }

    public static boolean BFS(HashMap<Integer, ArrayList<Integer>> hm, int [] colors, int node) {
        LinkedList<Integer> queue = new LinkedList<>();
        colors[node] = 1;
        queue.offerLast(node);
        while(queue.size() != 0) {
            int curNode = queue.pollFirst();
            for (int neighber : hm.get(curNode)) {
                if (colors[neighber] == 0) {
                    colors[neighber] = - colors[curNode];
                    queue.offerLast(neighber);
                } else if (colors[neighber] == colors[curNode]){
                    return false;
                }
            }
        }
        return true;
    }

二分图中一个很重要的问题就是最大匹配问题,最大匹配问题利用匈牙利算法进行求解。

输入:

8
1 1
1 2
2 2
2 3
3 1
3 2
4 3
4 4

关键代码如下:

    static int maxn = 100;
    //通过邻接矩阵进行图构建
    static int [][] matrix = new int[maxn][maxn];
    static boolean [] used = new boolean[maxn]; //表示某个轮次中女生是否被匹配过,每轮都初始化
    static int [] nxt = new int[maxn];  //表示整个过程中与女生匹配的男生id ,nxt[1]=2, 表示女1和男2匹配
    static int n = 5;  //表示男生数量为4(数值多1是为了和输入的id从1开始相匹配)
    static int m = 5;  //表示女生数量为4
    public static void main(String[] args) throws Exception {
        Scanner sc = new Scanner(System.in);
        //构建邻接矩阵
        int k = sc.nextInt();
        for (int i = 0; i < k; i++) {
            int a = sc.nextInt();
            int b = sc.nextInt();
            matrix[a][b] = 1;
        }
        
        //开始遍历每个男生,尝试为每个男生匹配女生
        int res = 0;
        for (int i = 1; i <= n; i++) {
            //每轮都要初始化女生是否匹配数组,因为dfs(递归)找增广路的时候需要标识来调整策略
            used = new boolean[m];
            if (DFS(i)) res ++;
        }
        System.out.println(res);
    }
    
    //这个方法是匈牙利算法的核心,函数标识在当前情况下,是否(返回值)能为男x成功匹配到女生。该函数还会修改每次初始化的used数组和nxt全局数组。
    public static boolean DFS(int x) {
        //遍历每个女生看看能不能和男生x匹配上
        for (int i = 1; i <= m; i++) {
            // 如果该女生和男生x存在可匹配的边,并且女生在这一轮没有匹配过
            if (matrix[x][i] == 1 && !used[i]) {
                //标识此轮中该女生被从尝试匹配过,防止递归找增广路的时候重复访问(增广路不是环,因此不能重复访问)
                
                used[i] = true;
                //如果这次循环没有找到,会对其他轮次的循环造成影响吗,因为你修改了used数组
                //不会,因为如果存在一条增广路,经过了上次不成立的增广路,那么上次的也是一条增广路,产生矛盾。

                //如果当前女生没有匹配的男生 || 当前女生有匹配的男生,并且可以让那个匹配的男生去找一个新的女生
                if (nxt[i] == 0 || DFS(nxt[i])) {

                    nxt[i] = x;
                    return true;
                }
            }
        }
        return false;
    }

单单看代码注释还是很难理解,可能过一阵子就忘了,结合代码单个步骤调试会更加形象,后面有空整一个视频讲解吧。

参考文献

私钥、公钥、数字签名、数字证书

一些概念:公钥 与 私钥 、摘要、数字签名、数字证书

利用一个公认的证书颁发机构记录信息发布者的公钥信息(防止公钥被伪造),同时这个信息用这个公信机构的私钥进行加密,信息发布者就在自己的签名(摘要+私钥加密)的基础上额外附带自己的数据证书。

接收方收到数据后,如果认可证书管理机构,就用改管理机构的公钥将数字证书解密,得到信息发布者的公钥,进一步通过改公钥解密数字签名获得摘要,最后通过摘要验证收到的信息是否一致。

公钥私钥的两种应用场景

  • 加密,那肯定是不希望别人知道发送给我的消息,所以只有我才能解密,所以可得出别人用公钥负责加密自己用私钥负责解密
  • 签名,那肯定是不希望有人冒充我发送消息,只有我才能发布这个签名,所以可得出自己用私钥负责签名,别人用公钥负责验证是我发送的消息

私钥和公钥是一对,谁都可以加解密,只是谁加密谁解密是看情景来用的:
第一种情景是签名,使用私钥加密,公钥解密,用于让所有公钥所有者验证私钥所有者的身份并且用来防止私钥所有者发布的内容被篡改(摘要用私钥加密,公钥持有者解密后可以验证摘要一致性).但是不能来保证内容不被他人获得(公钥大家都有)。
第二种情景是加密,用公钥加密,私钥解密,用于向公钥所有者发布信息,这个信息可能被他人篡改(中间截获信息进行修改),但是无法被他人获得(无法获取明文)。

https://blog.csdn.net/qq_23167527/article/details/80614454

https://blog.csdn.net/mengzuchao/article/details/78682060

数据库事务的ACID和隔离级别

数据库事务的ACID四个基本特性

  • 原子性(Atomicity)
  • 一致性(Consistency)
  • 隔离性(Isolation)
  • 持久性(Durability)

通俗解释:原子性就是一个事物,要么就全部都执行,要么到就全部都不执行;一致性是指执行事务前后数据库都要保持一致性状态(满足主键约束、业务逻辑约束等);隔离性是指数据库一个事务的执行不受=其他事务的影响, 持久性是指事务一旦提交所做的更改是永久的。

数据库事务并发的三种问题:

脏读:一个事务在执行的过程中读到了另一个事务还未提交的修改。

不可重复读:事务A读到了一个输入,然后事务B对这个数据进行修改并提交,事务A1重新读取这个数据的时候发现不一致(针对update)

幻度:事务A通过一定的条件读到了一批数据,在这期间事务B对符合这个条件的数据进行了删除或者插入,那么数据A重新读到某条件下的一批数据时,数据的条数变化了(针对delete和insert)

数据库事务的四种隔离级别

  • 读未提交(Read Uncommitted)
  • 读提交(Read Committed)
  • 可重复读(Repeated Read)
  • 串行化(Serializable)

读未提交:可以读到未提交的内容;会产生“脏读”、“不可重复读”、“幻读”。如无特殊情况,基本是不会使用这种隔离级别的。

读提交:只能读到已经提交的内容。是SQL Server和Oracle的默认隔离级别。这种隔离级别能够有效的避免脏读,无法避免“不可重复读”和“幻读”。

可重复读:专门针对“不可重复读”这种情况而制定的隔离级别,它就可以有效的避免“不可重复读”(加update锁)(是MySql的默认隔离级别),不能避免“幻读”,因为幻读是由于“插入或者删除操作(Insert or Delete)”而产生的。

串行化:这是数据库最高的隔离级别,这种级别下,事务“串行化顺序执行”,“脏读”、“不可重复读”、“幻读”都可以被避免,执行效率差,开销大。

总结下面内容摘自: https://baijiahao.baidu.com/s?id=1611918898724887602&wfr=spider&for=pc

为什么会出现“脏读”?因为没有“select”操作没有规矩。

为什么会出现“不可重复读”?因为“update”操作没有规矩。

为什么会出现“幻读”?因为“insert”和“delete”操作没有规矩。

“读未提(Read Uncommitted)”能预防啥?啥都预防不了。

“读提交(Read Committed)”能预防啥?使用“快照读(Snapshot Read)”,避免“脏读”,但是可能出现“不可重复读”和“幻读”。

“可重复读(Repeated Red)”能预防啥?使用“快照读(Snapshot Read)”,锁住被读取记录,避免出现“脏读”、“不可重复读”,但是可能出现“幻读”。

“串行化(Serializable)”能预防啥?排排坐,吃果果,有效避免“脏读”、“不可重复读”、“幻读”,不过效果谁用谁知道。

参考资料:

https://baijiahao.baidu.com/s?id=1611918898724887602&wfr=spider&for=pc