图数据结构国彩网10.哈密顿图

在本国彩网中，我们将学习哈密顿图。

定义：

包含哈密顿回路的图称为哈密顿图。

哈密​​顿回路是什么？

一条仅穿过每个顶点一次的路径称为汉密尔顿电路。它应该返回到原始的起始顶点。

例：

现在我们必须查找是否有哈密顿回路？

如果我们遍历-> b -> c -> d -> e -> a

我们有一条哈密尔顿式的道路。因此，该图是哈密顿图。

这是一个NP完全问题。没有多项式解。

哈密​​顿路径：

如果存在一条从顶点开始并访问所有顶点但无法返回到初始顶点的路径。这称为哈密顿路径。

例：

如果我们遵循以下路径-> b -> c -> d ->e。在这里，我们只访问了所有顶点一次，但是不能返回到初始顶点。这称为哈密顿路径。

进一步阅读：

AJ关于DS和算法的权威指南。单击此处以学习算法和数据结构国彩网的完整列表。 85多个章节可供学习。

该网站上可用的国彩网列表：