Python和C++全球导航卫星系统和机器人姿态触觉感知二分图算法

🎯要点

🎯马尔可夫随机场网格推理学习 | 🎯二维伊辛模型四连网格模型推理 | 🎯统计物理学模型扰动与最大乘积二值反卷积 | 🎯受限玻尔兹曼机扰动和最大乘积采样 | 🎯视觉概率生成模型测试图像

🎯机器人图算法：运动建模、定位、姿态同时定位和绘图和基于地标的同时定位和绘图 | 🎯共轭梯度优化、视觉里程计、视觉同时定位和绘图图算法 | 🎯机器人运动最小二乘问题图算法 | 🎯全球导航卫星系统移动物体定位图算法 | 🎯机器人触觉估算物体姿态图算法

📜图模型用例

📜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-可着色的。以下是一个简单的算法，用于确定给定图是否是二分图：

1. 将红色分配给源顶点（放入 U 组中）。
2. 将所有邻居涂上蓝色（放入集合 V 中）。
3. 将所有邻居的邻居涂成红色（放入 U 组）。
4. 这样，为所有顶点分配颜色，使其满足 m 路着色问题（其中 m = 2）的所有约束。
5. 在分配颜色时，如果我们找到与当前顶点颜色相同的邻居，则该图不能用 2 个顶点着色（或者图不是二分图）

C++代码算法：

#include <iostream>
#include <queue>
#define V 4using 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 = Vself.graph = [[0 for column in range(V)] \for row in range(V)]def isBipartite(self, src):colorArr = [-1] * self.VcolorArr[src] = 1queue = []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 Falsereturn 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 = Vself.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 Falsefor v in range(self.V):if (self.graph[u][v] == 1 andself.colorArr[v] == -1):self.colorArr[v] = 1 - self.colorArr[u]queue.append(v)elif (self.graph[u][v] == 1 andself.colorArr[v] == self.colorArr[u]):return Falsereturn Truedef 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 Falsereturn 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")

👉参阅、更新：计算思维 | 亚图跨际