啊哈算法（8）——更多精彩的算法

逃离我推掉我的手 2022-05-15 06:48 279阅读 0赞

1、图的最小生成树（Kruskal算法）  
对于一个给定的图，找出其最小生成树，用最少的边让n个顶点的图连通，很显然若要让n个顶点的图连通，最少要n-1条边，最小生成树还需要满足这n-1条边的权重和最小。例如对于如下输入实例：

6 9
    2 4 11
    3 5 13
    4 6 3
    5 6 4
    2 3 6
    4 5 7
    1 2 1
    3 4 9
    1 3 2

第一行n和m，n表示有n个顶点，m表示有m条路径，接下来的m行形如a b c表示顶点a到顶点b的权重为c。  
Kruskal算法的核心为：首先对边按照权重进行排序，每一次从剩余的边中选择权值较小的并且不会产生回路的边，加入到生成树中，直到加入了n-1条边为止。实现如下：

/*Kruskal算法，最小生成树*/
    
    #include<iostream>
    
    using namespace std;
    
    struct edge {
        int u;
        int v;
        int w;
    };//为了方便按照边来排序使用一个结构体来存放边的信息
    
    struct edge e[10];// 结构体数组存放边的信息
    
    int f[7];    //最多输入1000个节点
    int n, m;//节点个数和线索数目
    
    //对边进行排序
    void quicksort(int left, int right)
    {
        //选择基准
        struct edge t = e[left];
        if (left > right)
            return;
        int i = left;
        int j = right;
        while (i!=j)
        {
            while (e[j].w >=t.w&&i < j)
                j--;
            while (e[i].w <=t.w&&i < j)
                i++;
    
            //交换
            if (i < j)
            {
                struct edge temp = e[i];
                e[i] = e[j];
                e[j] = temp;
            }
        }
        //基准归位
        e[left] = e[i];
        e[i] = t;
        quicksort(left, i - 1); //递归处理左边
        quicksort(i+1,right); //递归处理右边
    }
    
    //使用并查集来判断两个边是不是在一个集合中 ，比用DFS快
    void init()   //刚开始每个节点都是孤立的
    {
        for (int i = 1; i <= n; i++)
        {
            f[i] = i;
        }
    }
    
    //寻找祖宗的过程
    int getf(int v)
    {
        if (f[v] == v)
            return v;
        else
        {
            //向上继续寻找其祖宗，并且在递归函数返回的时候，把中间的父节点都改为最终找到的祖宗的编号
            //这其实就是路径压缩，可以提高以后找到最高祖宗的速度
            f[v] = getf(f[v]);
            return f[v];
        }
    }
    
    //合并两个子集合
    int merge(int v, int u)
    {
        int t1 = getf(v);
        int t2 = getf(u);
        if (t1 != t2)
        {
            f[t2] = t1;// 遵循靠左合并的原则
            return 1;//不在一个集合中 就返回1
        }
        return 0;
    }
    
    int main()
    {
        int sum = 0;
        int count = 0;
        cin >> n >> m;
        for (int i = 1; i <= m; ++i)
        {
            cin >> e[i].u >> e[i].v >> e[i].w;
        }
        quicksort(1, m);  //对边进行排序
    
    
        //并查集初始化 最开始每个节点都是一个独立的节点
        init();
    
        //Kruskal算法
        for (int i = 1; i <= m; ++i)
        {
            //判断两个顶点是不是在同一个集合中
            if (merge(e[i].u, e[i].v))
            {
                //不在一个树中就将这条边加入生成树中
                cout << e[i].u << " " << e[i].v << " " << e[i].w << endl;
                count++;
                sum += e[i].w;
            }
    
            if (count == n - 1)    //当选用了n-1条边之后 就退出
                break;
        }
    
        cout << sum;
        system("pause");
    }

Kruskal算法的时间复杂度为：对边进行快排是O(MlogM)，在m条边中找出n-1条边是O(MlogN)，所以Kruskal算法的时间复杂度为O(MlogM+MlogN)。

2、最小生成树（prim算法）  
prim算法的核心步骤如下：

1.  从任意一个定点开始构造生成树，假设从一号顶点开始。首先将一号顶点加入生成树中，用一个数组book来标记哪些顶点已经加入到生成树中了。
2.  用dis数组记录生成树到各个顶点的距离。最初生成树中只有一号顶点，有直连边时，数组dis中存储的就是1号顶点到该顶点的边的权值，没有直连边的时候就是无穷大，即初始化dis数组。
3.  从数组中选出离生成树最近的顶点（假设顶点为j）加入到生成树中（在dis数组中找到最小值）。在以j为中间点，更新生成树到每一个非树顶点的距离（松弛），即如果dis\[k\]>e\[j\]\[k\]则更新dis\[k\]=e\[j\]\[k\]。
4.  重复第三步  
    例如对于如下示例：

6 9
    2 4 11
    3 5 13
    4 6 3
    5 6 4
    2 3 6
    4 5 7
    1 2 1
    3 4 9
    1 3 2

第一行n和m，n表示有n个顶点，m表示有m条路径，接下来的m行形如a b c表示顶点a到顶点b的权重为c。实现代码如下：

/*prim算法，使用邻接矩阵存图*/
    
    #include<iostream>
    
    using namespace std;
    
    #define inf 99999
    
    int e[7][7], dis[7], book[7];
    int n, m;   //顶点数和边数
    int main()
    {
        cin >> n >> m;
    
        //邻接矩阵初始化
        for(int i=1;i<=n;++i)
            for (int j = 1; j <= n; ++j)
            {
                if (i == j)
                    e[i][j] = 0;
                else
                    e[i][j] = inf;
            }
    
        int a, b, c;
        for (int i = 1; i <= m; ++i)     //读入边，由于为无向图所以两边都要存一下
        {
            cin >> a >> b >> c;
            e[a][b] = c;
            e[b][a] = c;               
        }
    
        //初始化dis数组，假定从1号顶点开始
        for (int i = 1; i <= n; ++i)
            dis[i] = e[1][i];
    
        int count = 0;
        //1号顶点加入到生成树中
        book[1] = 1;
        count++;
    
        //prim算法核心语句
        int sum = 0; //最小生成树路径
        while (count<n)                  //总共n-1条边就可以使得图连通
        {
            //从非树节点集合中选择 离生成树中最近的点加入到生成树中
            int min = inf;
            int pos = 0;
            for (int i = 1; i <= n; ++i)
            {
                if (book[i]==0&&dis[i] < min)   
                {
                    min = dis[i];
                    pos = i;
                }
            }
            book[pos] = 1;
            sum += min;
            count++;
            //以pos点为中心，更新各个非树节点到生成树的距离
            for (int i = 1; i <= n; ++i)
            {
                if (book[i] == 0 && dis[i] > e[pos][i])
                    dis[i] = e[pos][i];
            }
        }
    
        cout << sum << endl;
        system("pause");
    }

上面这种算法的时间复杂度为O(N^2)，如果使用堆，每一次选边的时间复杂度是O(logM)，然后使用邻接表来存储整个图时间复杂度会降低到O(MlogN)。实现代码如下：  
使用三个数组，dis数组用来记录生成树到各个顶点的距离。数组h是一个最小堆，堆里面存储的是顶点编号。这里并不是按照顶点的编号来建立最小堆，而是按照顶点在dis数组中的数值来建立最小堆的，此外还需要一个数组pos来记录每个顶点在最小堆中的位置。

/*prim算法实现：使用邻接表来存储图并且使用堆优化*/
    
    #include<iostream>
    #define inf 999999;
    
    using namespace std;
    
    int dis[7], book[7];// 记录各个顶点到生成树的最小距离，判断顶点是否在生成树中
    int h[7], pos[7]; //h用来保存堆，pos用来保存堆中每一个顶点的位置   
    int h_size; //size用来表示堆的大小
    
    void swap(int x,int y)
    {
        int t = h[x];
        h[x] = h[y];
        h[y] = t;
    
        //同步更新pos
        t = pos[h[x]];
        pos[h[x]] = pos[h[y]];
        pos[h[y]] = t;
    }
    
    void siftdown(int i)  //对堆中编号为i的节点实时向下调整
    {
        int t, flag = 0;  //flag用来标记是否需要继续向下调整
        while (i*2<= h_size&&flag==0)  //左孩子存在 
        {
            if (dis[h[i]] > dis[h[2 * i]])
                t = i * 2;
            else
                t = i;
    
            //如果有右儿子急需判断
    
            if (i * 2 + 1 <= h_size)
            {
                if (dis[h[t]] > dis[i * 2 + 1])
                    t = i * 2 + 1;
            }
    
            if (t != i)
            {
                swap(t, i);
                i = t;       //便于接下来继续向下调整
            }
            else
                flag = 1;//不在需要向下调整了
        }
    }
    
    void siftup(int i)   //对编号i进行向上调整
    {
        int flag = 0;
        if (i == 1)
            return;//在堆顶直接返回
    
        //不在堆顶并
        while (i != 1&&flag==0)
        {
            //与父节点进行比较
            if (dis[h[i / 2]] > dis[h[i]])
                swap(i, i / 2);
            else
                flag = 1;
            i = i / 2;   //更新节点方便下一次使用
        }
    }
    void create() //创建一个堆
    {
        //从最后一个非叶节点开始实行向下调整
        for (int i = h_size / 2; i >= 1; --i)
            siftdown(i);
    }
    
    //从堆顶中取出一个元素
    int pop()
    {
        int t = h[1];
        pos[t] = 0;
        h[1] = h[h_size];
        pos[h[1]] = 1;       //更新顶点h[1]在堆中的位置
        h_size--;
        siftdown(1);        //向下调整
        return t;
    }
    int main()
    {
        int n, m;//顶点个数和边的个数
    
        int u[19], v[19], w[19]; //采用邻接矩阵来存储图 表示顶点u[i]到顶点v[i]的权重为w[i]  由于为无向图实际的大小为2*m+1
        int first[7];           //存储的是节点i的第一条边的编号为first[i]，大小为n+1;
        int next[19];           //存储的是编号为i的边的下一条边的编号next[i]。
    
        cin >> n >> m;
        for (int i = 1; i <= m; ++i)
        {
            cin >> u[i] >> v[i] >> w[i];
        }
    
        //由于为无向图所以还需要存储一遍
        for (int i = m + 1; i <= 2 * m; ++i)
        {
            u[i] = v[i - m];
            v[i] = u[i - m];
            w[i] = w[i - m];
        }
    
        //采用邻接表来存储图，首先对first数组初始化，最开始没有读入边 所以记录为-1；
        for (int i = 1; i <= n; ++i)
            first[i] = -1;
    
        for (int i = 1; i <= 2 * m; ++i)
        {
            next[i] = first[u[i]];
            first[u[i]] = i;
        }
    
        //prim算法核心
        int count = 0;
        int sum = 0;
        //1号顶点加入到生成树中
        book[1] = 1;
        count++;
    
        //初始化dis数组
        dis[1] = 0;
        for (int i = 2; i <= n; ++i)
            dis[i] = inf;
        int k = first[1];  //1号节点的第一条边的编号
        while (k!=-1)
        {
            dis[v[k]] = w[k];
            k = next[k];
        }
    
        //初始化堆
        h_size = n;
        for (int i = 1; i <= h_size; ++i)
        {
            h[i] = i;
            pos[i] = i;
        }
        create();
        pop();//先弹出堆顶元素 此时堆顶元素是一号顶点
    
        while (count<n)
        {
            //堆顶元素加入到生成树当中
            int j = pop();
            book[j] = 1;
            count++;
            sum += dis[j];
    
            //以j为中心对边进行松弛
            int k = first[j];
            while (k!=-1)
            {
                if (book[v[k]] == 0 && dis[v[k]] > w[k])
                {
                    dis[v[k]] = w[k]; //更新距离
                    siftup(pos[v[k]]);  //对该顶点在堆中的位置进行松弛，pos[i]中存放的是节点i在堆中的位置
                }
                k = next[k];
            }
        }
        cout << sum << endl;
        system("pause");
    }

3、图的割点  
对于一个给定的图，求出图中的割点，采用深度优先搜索时访问到了k点，此时图就会被k点分割成两个部分，一部分是已经被访问过的点，另一部分是没有访问过的点。如果k点是割点，那么剩下的没有被访问过的点中至少会有一个点在不经过k点的情况下，是无论如何再也回不到已访问过的点。算法的关键在于：当深度优先遍历访问到顶点u时，其孩子顶点v还是没有访问过的，如何判断顶点v在不经过其父节点u的情况下可以回到祖先。为此使用两个数组：1、num记录dfs访问到每个节点时的时间戳，2、low记录每个顶点在不经过其父节点时，能够回到的最小时间戳。对于某个顶点u，对于其孩子v，使得low\[v\]>=num\[u\],即不能回到祖先，那么u点就为割点。对于如下输入：

6 7
    1 4
    1 3
    4 2
    3 2
    2 5
    2 6
    5 6

第一行为节点个数和边的个数，实现代码如下：

#include<iostream>
    
    using namespace std;
    
    int n, m, e[7][7], root;
    
    //num记录dfs访问到每个节点时的时间戳,low记录每个顶点在不经过其父节点时，能够回到的最小时间戳。
    //flag标记某个点是否为割点，index为时间戳
    int num[7], low[7], flag[7], index;  
    
    
    int min(int a, int b)
    {
        return a < b ? a : b;
    }
    
    //割点算法核心
    void dfs(int cur, int father)   //传入两个参数，当前顶点的编号和父节点的编号
    {
        int child = 0, i, j;      //child记录生成树中当前顶点cur的儿子个数
    
        index++;                 //时间戳加1
        num[cur] =index;         //当前顶点的时间戳
        low[cur] = index;        //当前顶点能够访问到的时间戳，最开始就是自己
        for (int i = 1; i <= n; ++i)  //枚举当前顶点相连的边
        {
            if (e[cur][i] == 1)
            {
                if (num[i] == 0)      //如果当前顶点的时间戳为0，说明顶点i还没有被访问到
                {
                    child++;
                    dfs(i, cur);    //对此孩子进行升入遍历
    
                    //更新当前顶点能够访问到最早顶点的时间戳 不能通过父节点就只能通过孩子节点
                    low[cur] = min(low[cur], low[i]);
    
                    //如果当前顶点不是根节点并且满足low[i]>=num[cur]，则当前顶点为割点
                    if (cur != root && low[i] >= num[cur])
                        flag[cur] = 1;
    
                    //如果当前顶点是根节点，在生成树中根节点必须要有两个儿子，那么这个根节点才是割点
                    if (cur == root &&child == 2)
                        flag[cur] = 1;
                }
                //否则如果当前顶点被访问过，并且这个顶点不是当前顶点cur的父亲，则要更新当前节点最早可以访问到的顶点的时间戳
                else if (i != father)  
                    low[cur] = min(low[cur], num[i]);
            }
        }
    }
    
    int main()
    {
        cin >> n >> m;
        for (int i = 1; i <= n; ++i)
            for (int j = 1; j <= n; ++j)
                e[i][j] = 0;
    
        int x, y;
        for (int i = 1; i <= m; ++i)
        {
            cin >> x >> y;
            e[x][y] = 1;
            e[y][x] = 1;
        }
    
        root = 1;
        dfs(1, root);
    
        for (int i = 1; i <= n; ++i)
        {
            if (flag[i] = 1)
                cout << i << " ";
        }
        system("pause");
    }

上述采用邻接矩阵来实现，这样时间复杂度都会在O(N^2)，这与使用蛮力，删除一个点然后判断剩余的点是否连通是一样的，因此要采用邻接表来存储图，时间复杂度为O(N+M)，下面采用邻接表存图的割点算法实现代码为：

/*割点算法，采用邻接表实现*/
    
    #include<iostream>
    
    using namespace std;
    
    int u[19], v[19], w[19];   //采用邻接表来存储图，由于为无向图，所以大小为2*m+1
    int first[7];
    int nex[19];
    int n, m;
    int num[7], low[7], index;
    int child, root; //child记录一个节点的孩子节点 root根节点 
    int flag[7];    //用来标记哪些节点为割点
    int min(int a, int b)
    {
        return a < b ? a : b;
    }
    void dfs(int cur, int father) //要传入两个节点，当前节点和当前节点的父节点
    {
        index++;
        num[cur] = index;        //访问到当前节点的时间戳
        low[cur] = index;        //最开始不经过父节点所能访问到的节点的时间戳就是本身
    
        int k = first[cur];        //当前节点的第一条边
        while (k!=-1)
        {
            if (num[v[k]] == 0)      //要访问的节点时间戳为0，则说明还没有访问
            {
                child++;
                dfs(v[k], u[k]);    // 继续深入访问孩子节点,此时u[k]为v[k]的父节点 dfs遍历就是得到一颗生成树
                //就更新当前节点不经过父节点所能访问到的节点的时间戳即low
                low[u[k]] = min(low[u[k]], low[v[k]]);  //由于一个节点要访问其他节点并且不过父节点只能经过孩子节点，所以与low[v[k]]进行比较
    
                if (u[k] != root && low[v[k]] >=num[u[k]])  //不为根节点并且v[k]不过父节点u[k]最早能访问到的节点的时间戳小于父节点u[k]的时间戳 那么u[k]就为割点
                    flag[u[k]] = 1;
                if(u[k]==root && child==2)   //为根节点并且有两个孩子就为割点
                    flag[u[k]] = 1;
    
            }
            //如果当前节点的所有边都已经访问，并且它所能到达的顶点不为其父节点，就更新其不经过父节点所能访问到的节点的时间戳
            else if (v[k] != father)
                low[u[k]] = min(low[u[k]], num[v[k]]);
            k = nex[k];   //编号为k的边的下一条边   
        }
    }
    int main()
    {
        cin >> n >> m;
    
        //使用邻接表存储图像
        for (int i = 1; i <= m; ++i)
        {
            cin >> u[i] >> v[i];
            w[i] = 1;
        }
    
        //由于为双向图
        for (int i = m + 1; i <= 2 * m; ++i)
        {
            u[i] = v[i - m];
            v[i] = u[i - m];
            w[i] = 1;
        }
    
        //初始化first数组，由于开始没有读入边的信息，所以节点第一条边的编号为-1
        for (int i = 1; i <= n; ++i)
            first[i] = -1;
    
        //读入边
        for (int i = 1; i <= 2 * m; ++i)
        {
            nex[i] = first[u[i]];
            first[u[i]] = i;   
        }
    
        root = 1;
        dfs(1, root);
    
        for (int i = 1; i <= n; ++i)
        {
            if (flag[i] == 1)
                cout << i << " ";
        }
        system("pause");
    }

4、图的割边  
割边也称为桥，在一个无向连通图中，如果删除某条边之后图不载连通，这与求图的割点类似，在求割点的时候（u为父节点，v为子节点）判断low\[v\]>=num\[u\]即在不经过父节点的情况下子节点最早能到的节点最早为父节点，在求割边的时候将判断条件改为low\[v\]>num\[u\]说明子节点v连父节点都到达不了，那么就说明u->v这条边就为割边，因为v回不到祖先，并且也没有另外一条路回到父节点，所以该边为割边，实现代码为：  
对于如下输入：

6 6
    1 4
    1 3
    4 2
    3 2
    2 5
    5 6

使用邻接表实现，复杂度为O(M+N)，实现的代码为：

/*割点算法，采用邻接表实现*/
    
    #include<iostream>
    
    using namespace std;
    
    int u[19], v[19], w[19];   //采用邻接表来存储图，由于为无向图，所以大小为2*m+1
    int first[7];
    int nex[19];
    int n, m;
    int num[7], low[7], index;
    int child, root; //child记录一个节点的孩子节点 root根节点 
    int flag[7];    //用来标记哪些节点为割点
    int min(int a, int b)
    {
        return a < b ? a : b;
    }
    void dfs(int cur, int father) //要传入两个节点，当前节点和当前节点的父节点
    {
        index++;
        num[cur] = index;        //访问到当前节点的时间戳
        low[cur] = index;        //最开始不经过父节点所能访问到的节点的时间戳就是本身
    
        int k = first[cur];        //当前节点的第一条边
        while (k!=-1)
        {
            if (num[v[k]] == 0)      //要访问的节点时间戳为0，则说明还没有访问
            {
                child++;
                dfs(v[k], u[k]);    // 继续深入访问孩子节点,此时u[k]为v[k]的父节点 dfs遍历就是得到一颗生成树
                //就更新当前节点不经过父节点所能访问到的节点的时间戳即low
                low[u[k]] = min(low[u[k]], low[v[k]]);  //由于一个节点要访问其他节点并且不过父节点只能经过孩子节点，所以与low[v[k]]进行比较
    
                if (u[k] != root && low[v[k]] > num[u[k]])  //不为根节点并且v[k]不过父节点u[k]最早能访问到的节点的时间戳小于父节点u[k]的时间戳 那么u[k]-v[k]就为割边
                    cout << u[k] << "-" << v[k] << endl;
            }
            //如果当前节点的所有边都已经访问，并且它所能到达的顶点不为其父节点，就更新其不经过父节点所能访问到的节点的时间戳
            else if (v[k] != father)
                low[u[k]] = min(low[u[k]], num[v[k]]);
            k = nex[k];   //编号为k的边的下一条边   
        }
    }
    int main()
    {
        cin >> n >> m;
    
        //使用邻接表存储图像
        for (int i = 1; i <= m; ++i)
        {
            cin >> u[i] >> v[i];
            w[i] = 1;
        }
    
        //由于为双向图
        for (int i = m + 1; i <= 2 * m; ++i)
        {
            u[i] = v[i - m];
            v[i] = u[i - m];
            w[i] = 1;
        }
    
        //初始化first数组，由于开始没有读入边的信息，所以节点第一条边的编号为-1
        for (int i = 1; i <= n; ++i)
            first[i] = -1;
    
        //读入边
        for (int i = 1; i <= 2 * m; ++i)
        {
            nex[i] = first[u[i]];
            first[u[i]] = i;   
        }
    
        root = 1;
        dfs(1, root);
    
        system("pause");
    }

当然也可以使用邻接矩阵来存图，但是时间复杂度至少为O(N^2)，这样完全没有意义，因为完全可以依次删除一条边来进行DFS或者BFS来判断整个图是不是连通的，这里还是给出实现代码：

#include<iostream>
    
    using namespace std;
    
    int n, m, e[7][7], root;
    
    //num记录dfs访问到每个节点时的时间戳,low记录每个顶点在不经过其父节点时，能够回到的最小时间戳。
    //flag标记某个点是否为割点，index为时间戳
    int num[7], low[7], flag[7], index;
    
    
    int min(int a, int b)
    {
        return a < b ? a : b;
    }
    
    //割点算法核心
    void dfs(int cur, int father)   //传入两个参数，当前顶点的编号和父节点的编号
    {
        int child = 0, i, j;      //child记录生成树中当前顶点cur的儿子个数
    
        index++;                 //时间戳加1
        num[cur] = index;         //当前顶点的时间戳
        low[cur] = index;        //当前顶点能够访问到的时间戳，最开始就是自己
        for (int i = 1; i <= n; ++i)  //枚举当前顶点相连的边
        {
            if (e[cur][i] == 1)
            {
                if (num[i] == 0)      //如果当前顶点的时间戳为0，说明顶点i还没有被访问到
                {
                    child++;
                    dfs(i, cur);    //对此孩子进行升入遍历
    
                                    //更新当前顶点能够访问到最早顶点的时间戳 不能通过父节点就只能通过孩子节点
                    low[cur] = min(low[cur], low[i]);
    
                    //如果当前顶点不是根节点并且满足low[i]>num[cur]，则cur-i为割边
                    if (cur != root && low[i] > num[cur])
                        cout << cur << "-" << i << endl;
    
                }
                //否则如果当前顶点被访问过，并且这个顶点不是当前顶点cur的父亲，则要更新当前节点最早可以访问到的顶点的时间戳
                else if (i != father)
                    low[cur] = min(low[cur], num[i]);
            }
        }
    }
    
    int main()
    {
        cin >> n >> m;
        for (int i = 1; i <= n; ++i)
            for (int j = 1; j <= n; ++j)
                e[i][j] = 0;
    
        int x, y;
        for (int i = 1; i <= m; ++i)
        {
            cin >> x >> y;
            e[x][y] = 1;
            e[y][x] = 1;
        }
    
        root = 1;
        dfs(1, root);
    
        system("pause");
    }

5、二分图最大匹配  
二分图：如果一个图的所有顶点可以被分为X和Y两个集合，并且所有边的两个顶点恰好一个属于集合X，另一个属于集合Y，即每个集合内的顶点每有边相连，那么此图就是二分图。  
二分图的最大匹配就是，两两通过边匹配（点不可以重复使用），求出最大的匹配树，最直观的解法：找出全部的匹配方案输出配对数最多的一种方案。但是时间复杂度很高。  
使用匈牙利算法解决这个问题，匈牙利算法过程如下：

1.  首先从任意一个未配对的点u开始，从点u的边中任意选择一条边（假设这条边是u->v）开始配对。如果此时点v还没有匹配，则配对成功，此时就找到了一条增广路。如果此时点v已经配对了，就要尝试进行连锁反应（即看看v先在配对的点还有没有其他的点可以配对），如果尝试成功就找到了一条增广路，此时需要更新原来的配对关系。这里使用一个match数组来记录配对关系，比如v与u匹配成功就记作match\[v\]=u和match\[u\]=v。配对成功后将配对数加1。配对过程使用DFS来实现
2.  如果刚才尝试失败，就从u的边中重新选择一条边进行尝试，直到点u匹配成功。
3.  接下来对剩下没有配对的点一一进行配对，直到所有的点尝试完毕  
    对于如下输入：

6 5
    1 4
    1 5
    2 5
    2 6
    3 4

其中1、2、3代表集合x中的元素，4、5、6代表集合Y中的元素，求出最大匹配对数，实现代码为：

/*匈牙利算法实现*/
    #include<iostream>
    
    using namespace std;
    
    int e[101][101];//使用邻接矩阵存储整个地图
    int match[101]; //用来记录配对的关系 比如v与u匹配成功就记作match[v]=u和match[u]=v。
    int book[101]; //用来标记某个顶点是否已经被尝试了
    int n, m;//顶点个数和边的数目
    
    int dfs(int u)
    {
    
        for (int i = 1; i <= n; ++i)  //尝试每一个顶点
        {
            if (book[i] == 0 && e[u][i] == 1)  //还没有尝试并且有边相连
            {
                book[i] = 1; //标记已经尝试
    
                //match[i]==0说明当前节点还没有匹配
                /*dfs(match[i]) 说明当前节点i已经匹配了节点假设为j，则让节点j与其他节点进行重新匹配看看是不是可以成功
                如果成功则当前节点就可以与节点j匹配*/
                if (match[i] == 0 || dfs(match[i]))
                {
                    //更新匹配关系
                    match[u] = i;
                    match[i] = u;
                    return 1;
                }
            }
        }
        return 0;
    }
    int main()
    {
        int sum = 0;
        cin >> n >> m;
        int x, y;
        for (int i = 1; i <= m; ++i)
        {
            cin >> x >> y;
            e[x][y] = 1;
            e[y][x] = 1;        //为无向图
        }
    
        //最开始没有匹配关系 初始化match数组
        for (int i = 1; i <= n; ++i)
            match[i] = 0;
    
        for (int i = 1; i <= n; ++i)
        {
            for (int j = 1; j <= n; ++j)
                book[j] = 0;      //清空上次搜索的记录
            if (dfs(i))
                sum++;            //寻找到一条
        }
        cout << sum << endl;
        system("pause");      
    }

如果二分图有n个点，那么最多找到n/2条增广路。如果图中有m条边，那么没找一条增广路就要把所有边遍历一遍，所花时间时m。所以总的时间复杂度是O(NM)。对于判断一个图是否是二分图，可以首先将任意一个顶点进行着红色，然后将相邻的点着蓝色，如果按照这样的着色可以将全部的顶点着色，并且相邻的顶点着色不同，那么该图就是二分图。