🏈指点迷津 | Brief🎯要点
🎯马尔可夫随机场网格推理学习 | 🎯二维伊辛模型四连网格模型推理 | 🎯统计物理学模型扰动与最大乘积二值反卷积 | 🎯受限玻尔兹曼机扰动和最大乘积采样 | 🎯视觉概率生成模型测试图像
🎯机器人图算法：运动建模、定位、姿态同时定位和绘图和基于地标的同时定位和绘图 | 🎯共轭梯度优化、视觉里程计、视觉同时定位和绘图图算法 | 🎯机器人运动最小二乘问题图算法 | 🎯全球导航卫星系统移动物体定位图算法 | 🎯机器人触觉估算物体姿态图算法
📜图模型用例
📜Python问题决策影响图结构化概率模型
📜Python汽车油耗活塞循环原木纱强度及电阻覆盖率现实统计模型计算
📜Python | R | MATLAB群体消息和遗传病筛选多元统计模型
📜Python神经模型评估微分方程图算法
📜Python精神病算法和自我认知异类数学模型
📜Python蜂窝通信Wi-Fi和GPU变分推理及暴力哈希加密协议图消息算法
🍪语言内容分比
🍇Python和C++二分图判断算法
二分图是一种图，其顶点可以分为两个独立的集合 U 和 V，并且每条边 (u, v) 要么连接从 U 到 V 的顶点，要么连接从 V 到 U 的顶点。换句话说，对于每条边 (u, v)，要么 u 属于 U 且 v 属于 V，要么 u 属于 V 且 v 属于 U。我们也可以说没有边连接同一集合的顶点。
如果可以使用两种颜色对图进行着色，使得集合中的顶点用相同的颜色着色，则二分图是可能的。请注意，可以使用两种颜色对偶数环的循环图进行着色。例如，参见下图。
不可能使用两种颜色对具有奇数循环的循环图进行着色。
检查图是否为二分图的算法：一种方法是在着色问题中使用回溯算法来检查图是否是 2-可着色的。以下是一个简单的算法，用于确定给定图是否是二分图：
这样，为所有顶点分配颜色，使其满足 m 路着色问题（其中 m = 2）的所有约束。
在分配颜色时，如果我们找到与当前顶点颜色相同的邻居，则该图不能用 2 个顶点着色（或者图不是二分图）
C++代码算法：
#include <iostream>
#include <queue>
#define V 4
using namespace std;
bool isBipartite(int G[][V], int src)
{
int colorArr[V];
for (int i = 0; i < V; ++i)
colorArr[i] = -1;
colorArr[src] = 1;
queue <int> q;
q.push(src);
while (!q.empty())
{
int u = q.front();
q.pop();
if (G[u][u] == 1)
return false;
for (int v = 0; v < V; ++v)
{
if (G[u][v] && colorArr[v] == -1)
{
colorArr[v] = 1 - colorArr[u];
q.push(v);
}
else if (G[u][v] && colorArr[v] == colorArr[u])
return false;
}
}
return true;
}
int main()
{
int G[][V] = {{0, 1, 0, 1},
{1, 0, 1, 0},
{0, 1, 0, 1},
{1, 0, 1, 0}
};
isBipartite(G, 0) ? cout << "Yes" : cout << "No";
return 0;
}
Python算法：
class Graph():
def __init__(self, V):
self.V = V
self.graph = [[0 for column in range(V)] \
for row in range(V)]
def isBipartite(self, src):
colorArr = [-1] * self.V
colorArr[src] = 1
queue = []
queue.append(src)
while queue:
u = queue.pop()
if self.graph[u][u] == 1:
return False;
for v in range(self.V):
if self.graph[u][v] == 1 and colorArr[v] == -1:
colorArr[v] = 1 - colorArr[u]
queue.append(v)
elif self.graph[u][v] == 1 and colorArr[v] == colorArr[u]:
return False
return True
g = Graph(4)
g.graph = [[0, 1, 0, 1],
[1, 0, 1, 0],
[0, 1, 0, 1],
[1, 0, 1, 0]
]
print ("Yes" if g.isBipartite(0) else "No")
上述算法仅在图连通时才有效。在上述代码中，我们始终从源 0 开始，并假设从该源访问顶点。一个重要的观察结果是，没有边的图也是二分图。请注意，二分图条件表示所有边都应从一个集合到另一个集合。我们可以扩展上述代码以处理图不连通的情况。对于所有尚未访问的顶点，重复调用上述方法。
C++算法：
#include <bits/stdc++.h>
using namespace std;
const int V = 4;
bool isBipartiteUtil(int G[][V], int src, int colorArr[])
{
colorArr[src] = 1;
queue<int> q;
q.push(src);
while (!q.empty()) {
int u = q.front();
q.pop();
if (G[u][u] == 1)
return false;
for (int v = 0; v < V; ++v) {
if (G[u][v] && colorArr[v] == -1) {
colorArr[v] = 1 - colorArr[u];
q.push(v);
}
else if (G[u][v] && colorArr[v] == colorArr[u])
return false;
}
}
return true;
}
bool isBipartite(int G[][V])
{
int colorArr[V];
for (int i = 0; i < V; ++i)
colorArr[i] = -1;
for (int i = 0; i < V; i++)
if (colorArr[i] == -1)
if (isBipartiteUtil(G, i, colorArr) == false)
return false;
return true;
}
int main()
{
int G[][V] = { { 0, 1, 0, 1 },
{ 1, 0, 1, 0 },
{ 0, 1, 0, 1 },
{ 1, 0, 1, 0 } };
isBipartite(G) ? cout << "Yes" : cout << "No";
return 0;
}
Python算法：
class Graph():
def __init__(self, V):
self.V = V
self.graph = [[0 for column in range(V)]
for row in range(V)]
self.colorArr = [-1 for i in range(self.V)]
def isBipartiteUtil(self, src):
queue = []
queue.append(src)
while queue:
u = queue.pop()
if self.graph[u][u] == 1:
return False
for v in range(self.V):
if (self.graph[u][v] == 1 and
self.colorArr[v] == -1):
self.colorArr[v] = 1 - self.colorArr[u]
queue.append(v)
elif (self.graph[u][v] == 1 and
self.colorArr[v] == self.colorArr[u]):
return False
return True
def isBipartite(self):
self.colorArr = [-1 for i in range(self.V)]
for i in range(self.V):
if self.colorArr[i] == -1:
if not self.isBipartiteUtil(i):
return False
return True
g = Graph(4)
g.graph = [[0, 1, 0, 1],
[1, 0, 1, 0],
[0, 1, 0, 1],
[1, 0, 1, 0]]
print ("Yes" if g.isBipartite() else "No")
