WOLFRAM

Wolfram 语言与系统参考资料中心

FindHamiltonianPath[g]

找出图 g 中总长最短的哈密顿路径.

FindHamiltonianPath[g,s,t]

找出从 s 到 t 的总长度最短的哈密顿路径.

更多信息和选项
Details and Options Details and Options
范例  
基本范例  
范围  
选项  
DistanceFunction  
应用  
属性和关系  
参见
相关指南
历史
按以下格式引用：

FindHamiltonianPath

FindHamiltonianPath[g]

找出图 g 中总长最短的哈密顿路径.

FindHamiltonianPath[g,s,t]

找出从 s 到 t 的总长度最短的哈密顿路径.

更多信息和选项

范例

打开所有单元 关闭所有单元

基本范例  (1)

找到通过图中顶点的哈密顿路径：

Wolfram Language code: g = PolyhedronData["Dodecahedron", "Skeleton"];
Wolfram Language code: FindHamiltonianPath[g]

突出显示路径：

Wolfram Language code: HighlightGraph[g, PathGraph[%]]

找到图中两个独立顶点间的哈密顿路径：

Wolfram Language code: g = PolyhedronData["Dodecahedron", "Skeleton"];
Wolfram Language code: FindHamiltonianPath[g, 1, 5]

突出显示路径：

Wolfram Language code: HighlightGraph[g, PathGraph[%]]

范围  (3)

FindHamiltonianPath 可用于无向图：

Wolfram Language code: FindHamiltonianPath[[image]]

加权图：

Wolfram Language code: FindHamiltonianPath[[image]]

FindHamiltonianPath 可用于大规模图：

Wolfram Language code: g = RandomGraph[{1000, 5000}];
Wolfram Language code: Timing[FindHamiltonianPath[g]]//Short

选项  (1)

DistanceFunction  (1)

这里定义一个六个点之间的稀疏距离矩阵：

Wolfram Language code: d = SparseArray[{{1, 2} -> 1, {2, 1} -> 1, {6, 1} -> 1, {6, 2} -> 1, {5, 1} -> 1, {1, 5} -> 1, {2, 6} -> 1, {2, 3} -> 10, {3, 2} -> 10, {3, 5} -> 1, {5, 3} -> 1, {3, 4} -> 1, {4, 3} -> 1, {4, 5} -> 15, {4, 1} -> 1, {5, 4} -> 15, {5, 2} -> 1, {1, 4} -> 1, {2, 5} -> 1, {1, 6} -> 1}, {6, 6}, Infinity];
Wolfram Language code: g = [image];

找到哈密顿路径：

Wolfram Language code: path = FindHamiltonianPath[g, DistanceFunction -> (d[[#1, #2]]&)]

突出显示路径：

Wolfram Language code: HighlightGraph[g, PathGraph[path]]

应用  (2)

找到使国际象棋中骑士在8×8的棋盘上恰好经过每个方块依次的一系列移动：

Wolfram Language code: g = KnightTourGraph[8, 8];
Wolfram Language code: path = FindHamiltonianPath[g]

骑士的移动：

Wolfram Language code: checkerboard = ArrayPlot[Table[Mod[j + i, 2], {i, 8}, {j, 8}], ColorRules -> {1 -> RGBColor[0, .55, .77], 0 -> RGBColor[.67, .9, .99]}, Frame -> False, DataRange -> {{1, 8}, {1, 8}}];
Wolfram Language code: Show[{checkerboard, HighlightGraph[g, PathGraph[path], GraphHighlightStyle -> "DehighlightHide", EdgeStyle -> Directive[Thick, Red]]}]

找到在欧洲从希腊到德国的哈密顿路径：

Wolfram Language code: europe = CountryData["Europe"];

地理中心的经纬度：

Wolfram Language code: pos = GeoPosition[CountryData[#, "CenterCoordinates"]]& /@ europe;

构建欧洲的加权图：

Wolfram Language code: adj = Table[QuantityMagnitude@GeoDistance[i, j], {i, pos}, {j, pos}] /. Quantity[0., _] -> Infinity;
Wolfram Language code: g = WeightedAdjacencyGraph[europe, adj];
Wolfram Language code: FindHamiltonianPath[g, Entity["Country", "Greece"], Entity["Country", "Germany"]]//Shallow

显示巡回路线：

Wolfram Language code: GeoGraphics[{Thick, Red, GeoPath[%]}]

属性和关系  (2)

有哈密顿路径的图不一定有哈密顿圈：

Wolfram Language code: g = [image];
Wolfram Language code: FindHamiltonianPath[g]
Wolfram Language code: HamiltonianGraphQ[g]

有哈密顿圈的图也有哈密顿路径：

Wolfram Language code: g = GraphData["Foster038A"]
Wolfram Language code: HamiltonianGraphQ[g]
Wolfram Language code: FindHamiltonianPath[g]
Wolfram Research (2015)，FindHamiltonianPath，Wolfram 语言函数，https://reference.wolfram.com/language/ref/FindHamiltonianPath.html.

文本

Wolfram Research (2015)，FindHamiltonianPath，Wolfram 语言函数，https://reference.wolfram.com/language/ref/FindHamiltonianPath.html.

CMS

Wolfram 语言. 2015. "FindHamiltonianPath." Wolfram 语言与系统参考资料中心. Wolfram Research. https://reference.wolfram.com/language/ref/FindHamiltonianPath.html.

APA

Wolfram 语言. (2015). FindHamiltonianPath. Wolfram 语言与系统参考资料中心. 追溯自 https://reference.wolfram.com/language/ref/FindHamiltonianPath.html 年

BibTeX

@misc{reference.wolfram_2026_findhamiltonianpath, author="Wolfram Research", title="{FindHamiltonianPath}", year="2015", howpublished="\url{https://reference.wolfram.com/language/ref/FindHamiltonianPath.html}", note=[Accessed: 07-October-2026]}

BibLaTeX

@online{reference.wolfram_2026_findhamiltonianpath, organization={Wolfram Research}, title={FindHamiltonianPath}, year={2015}, url={https://reference.wolfram.com/language/ref/FindHamiltonianPath.html}, note=[Accessed: 07-October-2026]}