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

{% embed url="https://viadean.notion.site/Python-C-626e87286edb41f69e70ed9d73de7475" %}

{% content-ref url="../zhi-dian-mi-jin-brief" %}
[zhi-dian-mi-jin-brief](../zhi-dian-mi-jin-brief)
{% endcontent-ref %}

### 🎯要点

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

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

#### 📜图模型用例

📜[Python问题决策影响图结构化概率模型](python-wen-ti-jue-ce-ying-xiang-tu-jie-gou-hua-gailmo-xing)

📜[Python汽车油耗活塞循环原木纱强度及电阻覆盖率现实统计模型计算](python-qi-che-you-hao-huo-sai-xun-huan-yuan-mu-sha-qiang-du-ji-dian-zu-fu-gailxian-shi-tong-ji-mo-xi)

📜[Python | R | MATLAB群体消息和遗传病筛选多元统计模型](python-r-matlab-qun-ti-xiao-xi-he-yi-chuan-bing-shai-xuan-duo-yuan-tong-ji-mo-xing)

📜[Python神经模型评估微分方程图算法](../ji-qi-xue-xi-machine-learning/python-shen-jing-mo-xing-ping-gu-wei-fen-fang-cheng-tu-suan-fa)

📜[Python精神病算法和自我认知异类数学模型](python-jing-shen-bing-suan-fa-he-zi-wo-ren-zhi-yi-lei-shu-xue-mo-xing)

📜[Python蜂窝通信Wi-Fi和GPU变分推理及暴力哈希加密协议图消息算法](python-feng-wo-tong-xin-wifi-he-gpu-bian-fen-tui-li-ji-bao-li-ha-xi-jia-mi-xie-yi-tu-xiao-xi-suan-fa)

### 🍪语言内容分比

{% @mermaid/diagram content="pie title 语言分比
 "Python":90
 "C++":80" %}

{% @mermaid/diagram content="pie title 内容分比
"图模型算法":90
"数学":60
"概率":50
"马尔可夫随机场网格":10
"二维伊辛模型":10
"统计物理学模型":10
"机器人运动":40
"全球导航卫星系统":40" %}

### 🍇Python和C++二分图判断算法

二分图是一种图，其顶点可以分为两个独立的集合 U 和 V，并且每条边 (u, v) 要么连接从 U 到 V 的顶点，要么连接从 V 到 U 的顶点。换句话说，对于每条边 (u, v)，要么 u 属于 U 且 v 属于 V，要么 u 属于 V 且 v 属于 U。我们也可以说没有边连接同一集合的顶点。

{% @mermaid/diagram content="flowchart LR 
 subgraph 图1
 A1[1] & A2[2] & A3[3] & A4[4] & A5[5]
 end
 subgraph 图2
 B1[1] & B2[2] & B3[3] & B4[4]
 end
 A1---B1 & B3
 A2---B1 & B4
 A3 & A4---B2
 A5---B3" %}

如果可以使用两种颜色对图进行着色，使得集合中的顶点用相同的颜色着色，则二分图是可能的。请注意，可以使用两种颜色对偶数环的循环图进行着色。例如，参见下图。

{% @mermaid/diagram content="flowchart LR
classDef c1 fill:#140
classDef c2 fill:#500
A((A)):::c1---B((B)):::c2---C((C)):::c1---D((D)):::c2---E((E)):::c1---F((F)):::c2---A" %}

不可能使用两种颜色对具有奇数循环的循环图进行着色。

{% @mermaid/diagram content="flowchart LR
classDef c1 fill:#140
classDef c2 fill:#500
A((A)):::c1---B((B)):::c2---C((C)):::c1---D((D)):::c2---E((E)):::c2---A" %}

检查图是否为二分图的算法：一种方法是在着色问题中使用回溯算法来检查图是否是 2-可着色的。以下是一个简单的算法，用于确定给定图是否是二分图：

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

C++代码算法：

```cpp
#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算法：

```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++算法：

```cpp
#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算法：

```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")
```
