<html xmlns="http://www.w3.org/1999/xhtml">
<head>
<meta charset="utf-8">
<meta name="generator" content="pdf2htmlEX">
<meta http-equiv="X-UA-Compatible" content="IE=edge,chrome=1">
<link rel="stylesheet" href="https://static.pudn.com/base/css/base.min.css">
<link rel="stylesheet" href="https://static.pudn.com/base/css/fancy.min.css">
<link rel="stylesheet" href="https://static.pudn.com/prod/directory_preview_static/6273d54cf0a4f84830c0c9c8/raw.css">
<script src="https://static.pudn.com/base/js/compatibility.min.js"></script>
<script src="https://static.pudn.com/base/js/pdf2htmlEX.min.js"></script>
<script>
try{
pdf2htmlEX.defaultViewer = new pdf2htmlEX.Viewer({});
}catch(e){}
</script>
<title></title>
</head>
<body>
<div id="sidebar" style="display: none">
<div id="outline">
</div>
</div>
<div id="pf1" class="pf w0 h0" data-page-no="1"><div class="pc pc1 w0 h0"><img class="bi x0 y0 w1 h1" alt="" src="https://static.pudn.com/prod/directory_preview_static/6273d54cf0a4f84830c0c9c8/bg1.jpg"><div class="c x0 y1 w2 h2"><div class="t m0 x1 h3 y2 ff1 fs0 fc0 sc0 ls0 ws0">专业教程</div><div class="t m0 x2 h3 y3 ff1 fs0 fc0 sc0 ls0 ws0">理论讲解部分</div><div class="t m0 x3 h4 y4 ff1 fs1 fc0 sc1 ls0 ws0">网络游戏开发</div><div class="t m0 x3 h4 y5 ff2 fs1 fc0 sc1 ls0 ws0">——<span class="ff1">高级应用</span></div><div class="t m0 x4 h5 y6 ff1 fs2 fc0 sc1 ls0 ws0">第<span class="_ _0"> </span><span class="ff3">6<span class="_ _0"> </span></span><span class="sc0">章 寻路算法</span></div></div></div><div class="pi" data-data='{"ctm":[0.937615,0.000000,0.000000,0.937615,0.000000,0.000000]}'></div></div>
</body>
</html>
<div id="pf2" class="pf w0 h0" data-page-no="2"><div class="pc pc2 w0 h0"><img class="bi x0 y0 w1 h1" alt="" src="https://static.pudn.com/prod/directory_preview_static/6273d54cf0a4f84830c0c9c8/bg2.jpg"><div class="c x0 y1 w2 h2"><div class="t m0 x5 h6 y7 ff1 fs3 fc0 sc1 ls0 ws0">第<span class="_ _1"> </span><span class="ff4">6<span class="_ _1"> </span></span>章 寻路算法</div><div class="t m0 x6 h3 y8 ff1 fs0 fc1 sc1 ls0 ws0">图论</div><div class="t m0 x6 h3 y9 ff1 fs0 fc1 sc1 ls0 ws0">深度优先算法</div><div class="t m0 x6 h3 ya ff1 fs0 fc1 sc1 ls0 ws0">广度优先算法</div><div class="t m0 x6 h3 yb ff1 fs0 fc1 sc1 ls0 ws0">深度优先算法</div><div class="t m0 x6 h3 yc ff1 fs0 fc1 sc1 ls0 ws0">广度优先算法</div><div class="t m0 x6 h3 yd ff1 fs0 fc1 sc1 ls0 ws0">深度优先算法</div><div class="t m0 x6 h3 ye ff1 fs0 fc1 sc1 ls0 ws0">广度优先算法</div><div class="t m0 x7 h3 yf ff1 fs0 fc1 sc1 ls0 ws0"> <span class="_ _2"> </span>了解图论的基础知识</div><div class="t m0 x7 h3 y10 ff1 fs0 fc1 sc1 ls0 ws0"> <span class="_ _2"> </span>掌握深度优先算法的原理</div><div class="t m0 x7 h3 y11 ff1 fs0 fc1 sc1 ls0 ws0"> <span class="_ _3"> </span>掌握广度优先算法的原理</div></div></div><div class="pi" data-data='{"ctm":[0.937615,0.000000,0.000000,0.937615,0.000000,0.000000]}'></div></div>
<div id="pf3" class="pf w0 h0" data-page-no="3"><div class="pc pc3 w0 h0"><img class="bi x0 y0 w1 h1" alt="" src="https://static.pudn.com/prod/directory_preview_static/6273d54cf0a4f84830c0c9c8/bg3.jpg"><div class="c x0 y1 w2 h2"><div class="t m0 x3 h7 y12 ff4 fs4 fc1 sc1 ls0 ws0">6.1 <span class="_ _4"> </span><span class="ff1">图论</span></div><div class="t m0 x8 h8 y13 ff4 fs5 fc1 sc1 ls0 ws0">6.1.1 <span class="_ _5"> </span><span class="ff1">图论基础</span></div><div class="t m0 x5 h6 y7 ff1 fs3 fc0 sc1 ls0 ws0">第<span class="_ _1"> </span><span class="ff4">6<span class="_ _1"> </span></span>章 寻路算法</div><div class="t m0 x9 h3 y14 ff1 fs0 fc1 sc1 ls0 ws0">图论（<span class="_ _3"> </span><span class="ff5">Graph Theory<span class="_"> </span></span>）是数学的一个分支，它以图为研究对象。图论中的</div><div class="t m0 xa h3 y15 ff1 fs0 fc1 sc1 ls0 ws0">图是由若干给定的点及连接两点的线所构成的图形，这种图形通常用来描述某</div><div class="t m0 xa h3 y16 ff1 fs0 fc1 sc1 ls0 ws0">些事物之间的某种特定关系，用点代表事物，用连接两点的线表示相应两个事</div><div class="t m0 xa h3 y17 ff1 fs0 fc1 sc1 ls0 ws0">物间具有这种关系。</div><div class="t m0 xb h9 y18 ff1 fs6 fc1 sc1 ls0 ws0">四色猜想：可以用<span class="_ _6"></span>四种不同的颜色将<span class="_ _6"></span>接壤的国家分开<span class="_ _6"></span>表示</div></div></div><div class="pi" data-data='{"ctm":[0.937615,0.000000,0.000000,0.937615,0.000000,0.000000]}'></div></div>
<div id="pf4" class="pf w0 h0" data-page-no="4"><div class="pc pc4 w0 h0"><img class="bi x0 y0 w1 h1" alt="" src="https://static.pudn.com/prod/directory_preview_static/6273d54cf0a4f84830c0c9c8/bg4.jpg"><div class="c x0 y1 w2 h2"><div class="t m0 x3 ha y19 ff4 fs7 fc1 sc1 ls0 ws0">6.1 <span class="_ _7"> </span><span class="ff1">图论</span></div><div class="t m0 xc hb y1a ff4 fs8 fc1 sc1 ls0 ws0">6.1.2 <span class="_ _7"> </span><span class="ff1">图的定义</span></div><div class="t m0 xd hc y1b ff4 fs9 fc1 sc1 ls0 ws0">1<span class="_ _8"> </span><span class="ff1">．图的表示方<span class="_ _6"></span>式</span></div><div class="t m0 x5 h6 y7 ff1 fs3 fc0 sc1 ls0 ws0">第<span class="_ _1"> </span><span class="ff4">6<span class="_ _1"> </span></span>章 寻路算法</div><div class="t m0 x9 h3 y14 ff1 fs0 fc1 sc1 ls0 ws0">图（<span class="_ _3"> </span><span class="ff5">Graph<span class="_"> </span></span>）是由非空的节点集合和一个描述节点之间关系（边或者弧）</div><div class="t m0 xa h3 y15 ff1 fs0 fc1 sc1 ls0 ws0">的集合组成。</div><div class="t m1 xe hd y1c ff5 fsa fc1 sc1 ls0 ws0">)}<span class="_ _9"></span>,<span class="_ _a"></span>(<span class="_ _b"></span>,<span class="_ _c"></span>|<span class="_ _d"></span>)<span class="_ _e"></span>,<span class="_ _f"></span>{(</div><div class="t m1 xf hd y1d ff5 fsa fc1 sc1 ls0 ws0">}<span class="_ _10"></span>|<span class="_ _11"></span>{</div><div class="t m1 x10 hd y1e ff5 fsa fc1 sc1 ls0 ws0">)<span class="_ _12"></span>,<span class="_ _13"></span>(</div><div class="t m1 x11 hd y1c ff6 fsa fc1 sc1 ls0 ws0">vj<span class="_ _f"></span>vi<span class="_ _14"></span>P<span class="_ _15"></span>V<span class="_ _16"></span>vj<span class="_ _f"></span>vi<span class="_ _17"></span>vj<span class="_ _f"></span>vi<span class="_ _18"></span>E</div><div class="t m1 x12 hd y1d ff6 fsa fc1 sc1 ls0 ws0">d<span class="_ _19"></span>at<span class="_ _19"></span>a<span class="_ _19"></span>ob<span class="_ _19"></span>ject<span class="_ _1a"></span>vi<span class="_ _1b"></span>vi<span class="_ _1c"></span>V</div><div class="t m1 x13 hd y1e ff6 fsa fc1 sc1 ls0 ws0">E<span class="_ _1d"></span>V<span class="_ _1e"></span>G</div><div class="t m1 x14 he y1c ff7 fsa fc1 sc1 ls0 ws0"><span class="_ _1b"></span><span class="_ _1f"></span></div><div class="t m1 x15 he y1d ff7 fsa fc1 sc1 ls0 ws0"><span class="_ _20"></span></div><div class="t m1 x16 he y1e ff7 fsa fc1 sc1 ls0 ws0"></div><div class="t m0 x17 h3 y1f ff5 fs0 fc1 sc1 ls0 ws0">G<span class="_"> </span><span class="ff1">表示图、<span class="_ _21"> </span></span>V<span class="_"> </span><span class="ff1">表示节点的集合、<span class="_ _21"> </span></span>E<span class="_ _3"> </span><span class="ff1">表示边的集合。</span></div></div></div><div class="pi" data-data='{"ctm":[0.937615,0.000000,0.000000,0.937615,0.000000,0.000000]}'></div></div>
<div id="pf5" class="pf w0 h0" data-page-no="5"><div class="pc pc5 w0 h0"><img class="bi x0 y0 w1 h1" alt="" src="https://static.pudn.com/prod/directory_preview_static/6273d54cf0a4f84830c0c9c8/bg5.jpg"><div class="c x0 y1 w2 h2"><div class="t m0 x3 ha y19 ff4 fs7 fc1 sc1 ls0 ws0">6.1 <span class="_ _7"> </span><span class="ff1">图论</span></div><div class="t m0 xc hb y1a ff4 fs8 fc1 sc1 ls0 ws0">6.1.2 <span class="_ _7"> </span><span class="ff1">图的定义</span></div><div class="t m0 xd hc y1b ff4 fs9 fc1 sc1 ls0 ws0">1<span class="_ _8"> </span><span class="ff1">．图的表示方<span class="_ _6"></span>式</span></div><div class="t m0 x5 h6 y7 ff1 fs3 fc0 sc1 ls0 ws0">第<span class="_ _1"> </span><span class="ff4">6<span class="_ _1"> </span></span>章 寻路算法</div><div class="t m0 x9 h3 y14 ff1 fs0 fc1 sc1 ls0 ws0">给定一个图：</div><div class="t m0 x17 h3 y1f ff1 fs0 fc1 sc1 ls0 ws0">用数学方式表示为：</div></div><div class="c x18 y20 w3 hf"><div class="t m2 x19 h10 y21 ff5 fsb fc1 sc1 ls0 ws0">V1<span class="_ _22"> </span>V2</div><div class="t m2 x1a h10 y22 ff5 fsb fc1 sc1 ls0 ws0">V5<span class="_ _23"></span>V4</div><div class="t m2 xc h10 y23 ff5 fsb fc1 sc1 ls0 ws0">V3</div></div><div class="c x0 y1 w2 h2"><div class="t m3 x1b h11 y24 ff5 fsc fc1 sc1 ls0 ws0">)}<span class="_ _24"></span>5<span class="_ _13"></span>,<span class="_ _25"></span>2<span class="_ _26"></span>(<span class="_ _27"></span>),<span class="_ _28"></span>5<span class="_ _13"></span>,<span class="_ _29"></span>3<span class="_ _24"></span>(<span class="_ _27"></span>),<span class="_ _2a"></span>4<span class="_ _2b"></span>,<span class="_ _29"></span>3<span class="_ _24"></span>(<span class="_ _27"></span>),<span class="_ _2c"></span>3<span class="_ _13"></span>,<span class="_ _25"></span>2<span class="_ _26"></span>(<span class="_ _27"></span>),<span class="_ _2a"></span>4<span class="_ _2b"></span>,<span class="_ _2d"></span>1<span class="_ _2e"></span>(<span class="_ _27"></span>),<span class="_ _2a"></span>2<span class="_ _2b"></span>,<span class="_ _2d"></span>1<span class="_ _2f"></span>{(</div><div class="t m3 x1c h11 y25 ff5 fsc fc1 sc1 ls0 ws0">}<span class="_ _30"></span>5<span class="_ _13"></span>,<span class="_ _25"></span>4<span class="_ _2b"></span>,<span class="_ _29"></span>3<span class="_ _13"></span>,<span class="_ _25"></span>2<span class="_ _2b"></span>,<span class="_ _2d"></span>1<span class="_ _13"></span>{</div><div class="t m3 x1d h11 y24 ff6 fsc fc1 sc1 ls0 ws0">v<span class="_ _14"></span>v<span class="_ _31"></span>v<span class="_ _2f"></span>v<span class="_ _32"></span>v<span class="_ _2f"></span>v<span class="_ _31"></span>v<span class="_ _14"></span>v<span class="_ _33"></span>v<span class="_ _34"></span>v<span class="_ _33"></span>v<span class="_ _34"></span>v<span class="_ _35"></span>E</div><div class="t m3 x1e h11 y25 ff6 fsc fc1 sc1 ls0 ws0">v<span class="_ _14"></span>v<span class="_ _2f"></span>v<span class="_ _14"></span>v<span class="_ _34"></span>v<span class="_ _36"></span>V</div><div class="t m3 x1f h12 y24 ff7 fsc fc1 sc1 ls0 ws0"></div><div class="t m3 x1f h12 y25 ff7 fsc fc1 sc1 ls0 ws0"></div></div></div><div class="pi" data-data='{"ctm":[0.937615,0.000000,0.000000,0.937615,0.000000,0.000000]}'></div></div>
