首页 > 代码库 > 图 --- 二分图

图 --- 二分图

2024-07-29 18:00:03   222人阅读

基本概念

图分为有向图和无向图 顶点集合V  边的集合E，连接俩点u和v的e=（u，v）表示，所以图 G=（V,E）；
俩个顶点相连表示俩个顶点相邻，相邻顶点的序列称为路径，起点和终点重合的路径叫做圈，任意俩点之间都有路径连接的图称为连通图，顶点连接边的个数称为度。
没有圈的连通图叫做树，没有圈的非连通图叫做森林。

图的表示

图的表示形式一般采取 邻接矩阵或是邻接表的形式来实现，以下笔记所示：


带权值图形：

邻接表存储：重边和自环


图的实现

#include <iostream>
#include <vector>
using namespace std;

const int MAX = 100;
vector<int> G[MAX];

/**
    struct edge{
        int to;
        int cost;
    };
    vector<edge> G[MAX];
*/
int main()
{
    int V,E;
    cin>>V>>E;
    for(int i=0;i<V;i++){
        int s,t;
        cin>>s>>t;
        G[s].push_back(t);
    }
    ...
}

图的简单实例：二分图，一个图中存在着n个顶点，相邻的顶点着上不同颜色，是否可以使用俩种颜色给图上色，是
输出 yes 否则输出No。yes 代表的图称为二分图
#include <iostream>
#include <vector>
using namespace std;

const int MAX = 100;
vector<int> G[MAX];
int V;
int color[MAX];

bool dfs(int v,int c){
    color[v] = c;
    for(unsigned int i=0;i<G[v].size();i++){
        if(color[G[v][i]] == c) return false;
        if(color[G[v][i]]==0 && !dfs(G[v][i],-c)) return false;
    }
    return true;
}
void slove(){
    for(int i=0;i<V;i++){
        if(color[i]==0){
            if(!dfs(i,1)){
                cout<<"No"<<endl;
                return;
            }
        }
    }
    cout<<"Yes"<<endl;
}
int main()
{
    cin>>V;
    for(int i=0;i<V;i++){
        int s,t;
        cin>>s>>t;
        G[s].push_back(t);
        G[t].push_back(s);
    }
    slove();
}

输入 4; 
0 1
1 3
3 4
4 0
输出：yes
输入：3
0 1
0 2
1 2
输出：No
例子是基于无向图。

图 --- 二分图


联系
我们