【算法概论】图论算法：二部图的判断-白红宇

【算法概论】图论算法：二部图的判断

阅读量：4178 次

发布时间：2019-05-26

本文共 1283 字，大约阅读时间需要 4 分钟。

将原贴中判断二分图的代码按自己的习惯改了一下：

#include 
   
    #include 
    
     #include 
     
      #include 
      
       using namespace std;int vexnum, edgenum;bool dfs(vector
       
         color, vector
        
         
          > node, int v, int c);void solve(vector
          
            color, vector
           
            
             > node);int main(){ cout << "请输入顶点和边的个数:" << endl; cin >> vexnum >> edgenum; vector
             
              
               > node(vexnum); vector
               
                 color(vexnum, 0); cout << "请输入边的顶点信息:" << endl; for (int i = 0; i < edgenum; ++i) { int u, v; cin >> u >> v; //因为是无向图，所以要双向插入顶点 node[u].push_back(v); //在u点后插入v顶点 node[v].push_back(u); //在v点后插入u顶点 } solve(color, node); return 0;}void solve(vector
                
                  color, vector
                 
                  
                   > node){ for (int i = 0; i < vexnum; ++i) { //遍历所有顶点 if (color[i] == 0) { //如果未染色，就进入深搜 if (!dfs(color, node, i, 1)) { printf("NOT BICOLORABLE.\n"); //如果返回false值，就不是二分图 return; //结束搜索 } } } printf("BICOLORABLE.\n"); //未出现相邻同色，就是二分图}bool dfs(vector
                   
                     color, vector
                    
                     
                      > node, int v, int c){ color[v] = c; //为当前顶点上色 for (int i = 0; i < int(node[v].size()); ++i) { //遍历所有与之连接的顶点，即相邻顶点 if (color[node[v][i]] == c) //如果相邻的顶点同色，就返回false { return false; } if (color[node[v][i]] == 0 && !dfs(color, node, node[v][i], -c)) //如果相邻顶点未染色，就将其染为相反颜色即-c，并继续dfs { return false; //返回false } } return true; //直到所有顶点都被染色，且没出现相邻同色顶点，就返回true}