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

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

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

1. 将红色分配给源顶点（放入 U 组中）。

2. 将所有邻居涂上蓝色（放入集合 V 中）。

3. 将所有邻居的邻居涂成红色（放入 U 组）。

4. 这样，为所有顶点分配颜色，使其满足 m 路着色问题（其中 m = 2）的所有约束。

5. 在分配颜色时，如果我们找到与当前顶点颜色相同的邻居，则该图不能用 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")