离散数学第二集----判断二分图
大家好！ 今天一起学习二分图吧。 二分图是离散数学图论中的重要概念，有助于解决生活中的人员分配等问题。 首先，让我们来理解一下那个概念。
定义：二分图又称二部图，是图论中的一种特殊模型。 G=(V，e )该图将顶点集合划分为V1、V2，并且V1和V2构成v上的一个划分，对于边集合e，任一边的端点分别在V1和V2时，该图被称为二分图。
那么，如何判断一个图是否是二分图呢？ 为了解决这个问题，介绍染色法的方法。
基于染色法的思路分析：首先，考虑用双色染色此图，如果相邻两个顶点颜色相同，则此图不是二分图。 相反，如果在这张图上找不到这样的点，这张图就是一分为二的图。
本文针对该问题采用BFS宽度优先搜索算法实现了该问题，相关代码实现如下。
# include iostream # include queue # includevectorusingnamespacestd； 用int main () /染色法判断一个图是否为二分图，用广度优先搜索判断int Graph[100][100]={ 0 }； int node_color[100]={ 0 }； int node_num； 请输入cout '节点数。' endl； cin node_num； 请输入cout '图的关联矩阵。' endl； for(intI=1； i=node_num； I ) for(intj=1； j=node_num； j({CINgraph[I][j]； }cout endl； }for(intI=0； inode_num； I ) {node_color[i]=0； //将颜色初始化为0 (0) 0}queueintque； que.push(1； //将第一个节点入队到node_color[1]=1的int Judge=0； while (！ que.empty () ) {int temp=que.front； que.pop (； for(intj=1； j=node_num； j () if (graph [ temp ] [ j ]==1node _ color [ j ]==0) ) /确定相邻节点是否已染色node _ color [ j ]=-node //将其节点入队到continue中； } else if (node _ color [ temp ]=node _ color [ j ] ) /相邻节点颜色相同的Judge=1； 黑； }if(judge==1) {break； }if(judge==1) {cout此图不是二分图！ ' endl； }else {cout此图为二分图！' endl； }return 0； }芯片输入5个顶点的图的相关矩阵，测试结果如下。
伙伴们也可以自己输入几个相关矩阵哦。 今天的分享到此为止！ 加油！