图论中搜索算法讲座.ppt

1、标题：图论中的搜索算法和最短路径算法、道路分宏Lu_、路径查找算法、2、图形理论中的搜索算法和最短路径算法、3、read Euler、read Euler、he is the mething、线表：线性结构、树：层次、图：节点之间的关系可以是任何一个。也就是说，两个数据元素都可以与图相关。例如：第一部分：图的基本概念，8，1图的定义和基本术语，图G是由g=(V(G)，E(G)，g=(V，E)记录的两组顶点集V(G)和边集E(G)，v是顶点的非空有限集合，e是两个顶点之间的关系。也就是说，有角的穷集，有9，无向图和有向图，无向图：的角是顶点的不对齐对。也就是说，边没有方向。向上方向图为G=(V，

2、E)，其中v=v1，v2，v3，v4，V5，e=(v1，v2)，(v1，v4)，(v2，)，10，直接图：相应的边具有顶点对齐对，即边的方向。V=v1、v2、v3、v4、E=、乳香图表上，边通常称为圆弧，表示顶点v1到v2的圆弧。V1称为弧尾，v2称为弧头。以上乳香图表可以用G=(V，E)表示。其中，11、转向图形(无方向网络)和转向图形(有方向网络)还指定了与图形的边或圆弧相关联的数值。此数字称为权重。具有此权重的图表通常称为网络。具有权重的直接图称为直接网络。具有权重的全向图称为全向网络。可以表示从一个顶点到另一个顶点的距离。可以表示从一个顶点到另一个顶点的成本消耗。12，子图，假定有两个

3、图G=(V，E)和G=(V，E)，如果为V，E，则称为G的子图。13，相邻和关联，对于无向地物G=(V，E)，边(V，v) E称为顶点V和V相邻的点，即V和V相邻的点。边(v，v)连接到顶点v和v，或(v，v)连接到顶点v和v。对于直接图形G=(V，E)，对于圆弧E，顶点V与顶点V相邻，顶点V与顶点V相邻。弧与顶点v、v相关联。14，对于顶点的度，无向图，顶点v的度是与v关联的边数，以TD(v)形式记录。顶点v3度为3，对于直接图形，顶点V的度TD(V)分为两部分打印，粒度。以顶点v为头的圆弧数称为v的入口图，并记录为id (v)。以顶点v结束的圆弧数称为v的“出”(out)，被记录为od (

4、v)。顶点v的度为TD(v)=ID(v) OD(v)。15，顶点v1为2，顶点v1为1，顶点v1为3，16，路径、链、简单路径、回路(环)、简单回路、顶点v0和vk分别称为路径w的起点和终点。路径的长度是路径中的边数。起点和终点相同的路径称为回路(环)。17，链是简单路径吗？简单路径是链吗？除了第一个和最后一个顶点以外，其馀顶点不重复的循环称为简单循环(简单循环)。18，路径：1，2，5，7，6，5，2，3路径长度：7简单路径：1，2，5，7，6回路：1，2，5，7，如果全向图g中的两个顶点VI、VJ V、VI和VJ都连接在一起，则g称为连接图。22，2子句图的存储结构，顺序存储，相邻矩阵，链

5、存储，相邻表，相邻多表，交叉列表，顶点之间的连接如何表示？每个元素AIJ定义为：的23，2.1相邻矩阵包含n个顶点信息和N2个边或圆弧信息。，示例有向图g，0 1 0，0 0 1，1 0 0，24，示例无向图g，0 1 0 0 1，0 1 0 1，0 1 0 1，0 1 0 1，1 0 1 0 1 0 0，0 1 0 0 0 0 0，优点3360，1。很容易确定两个顶点之间是否存在边或胡歌。2 .很容易获得每个顶点的度。25，无向图，顶点VI的度是相邻矩阵的I行或I列中元素的总和。在示例g中，v1的度为2。26、直接图形、顶点VI的打印是相邻矩阵中I行的元素之和。顶点VI的入射角是相邻矩阵中I

6、列的元素之和。V1的出度为2。粒度是1。27，无向图的邻接矩阵是对称矩阵。有向图的相邻矩阵通常不对称。因此，无向图是压缩存储方法，无向图，直接图，28，具有权重图(网络)的相邻矩阵，5 7，4，8 9，5，5，3 1，29，相邻矩阵存储的缺点：此存储方法的空间复杂性是图的节点数的平方，30，2.2相邻表格为图形中的每个顶点建立表示与该顶点相关联的边或弧的单一连结表格。表节点，头节点，adjvex3360相邻顶点位置，有关ArcInfo :边的信息，nextarc :下一个关联边节点，有关vexinfo :顶点的信息，firstarc :第一个关联边节点，31，顶点VI度是I链接列表中的节点数。

7、需要多少存储空间？n 2e，32，示例：方向图G，33，相邻矩阵和相邻表，存储空间，顶点的程度，查找顶点的相邻顶点，相邻表脂肪，类似地，确定两个顶点的连接性，相邻矩阵方便，34，3图的遍历，图的遍历算法是图的连接问题求解、拓扑排序和关键路径查找等算法的基础。通常具有两个横向图的路径：深度优先搜索，宽度优先搜索。图形的导航相对复杂，辅助布尔数组visited0可防止多次访问同一顶点.n-1表示是否访问了顶点。35，3.1深度优先搜索，深度优先搜索：主节点，从第一个相邻节点派生的子图表，从其他相邻顶点派生的子图表，深度优先搜索顺序：v1，v2，v4，V8，v3，V6，V7，36从地物的顶点v开始访

8、问此顶点。2 .然后，v中未访问的相邻点进行深度优先遍历。3 .在图中，直到访问了v和路径连接的所有顶点。4 .此时，如果地物上仍有无法访问的顶点，请重复上述过程，方法是选择其他地物上的未连接顶点作为起点，直到地物上的所有顶点都被访问。，算法描述：37，深度优先遍历算法(DFS)递归算法，38，visitedv=trueprintf(v)；/访问此顶点，return ok，39，流程分析，深度优先搜索顺序：v1，v2，v4，V8，V5，v3，V6，V7，40，堆栈深度优先搜索，41，init stack(s)；Visitedv=truePush (s，v)；printf(v)；getop (s

9、，v)；pop(s)；42，实现深度优先搜索的c语言：typedef struct node int adjvex/相邻点字段struct node *next，用于存储标题阵列中与Vi相邻的点的位置；/表示下一个角或圆弧JD的链域；/标头接点：typedef struct tnode int vexdata/存储顶点信息struct node * firstarc/表示第一个相邻点TD。TD gaM/渡边杏使用ga0，43，void travers (TD g，int n)int I；Static int visitedMfor(I=1)；I=n；I)visitedi=0；for(I=1)；

10、I=n；I) if (visiitedi=0) DFS (g，I，visited)；44，void DFS (TD g，int v，int visited)JD * w；int I；Printf(%d，v)；visitedv=1；W=gv.firstarcWhile(w！=NULL)I=w-adj vex；If (visiitedi=0) DFS (g，I，visited)；w=w-next；45，3.2宽度优先搜索，宽度优先搜索树层次遍历，宽度优先搜索顺序：v1，v2，v3，v4，v5，v6，v7，v8，仅在访问父节点后访问子节点！人工分层图，按层巡回图。46，1。从图形中的顶点v开始访问这

11、些顶点。2 .然后依次访问未访问v的每个相邻点。4.在图中，直到访问了v和路径连接的所有顶点。5 .如果此时尚未访问图形中的顶点，请选择其他图形中未访问的顶点作为起点，然后重复上述过程，直到访问了图形中的所有顶点。3.然后从接触点开始依次接近接触点。算法描述：47，流程分析，宽度优先搜索顺序：v1，v2，v3，v4，V5，V6，V7，V8，48，宽度优先遍历算法，49，50，队列实现宽度优先搜索，visitedv=trueEnqueue (q，v)；printf(v)；dequeue (q，u)；51，4最短路径，对于想要较少停靠点的旅客来说，ABCG，越是短途旅行越是考虑更好的乘客，ADEF

12、G，52，带权重图的最短路径计算问题，一般来说，船，铁路，船行都有方向，所以我将以最短路径算法为例说明。具有加权无向图的最短路径算法也很常见。从单个源到其馀顶点的最短路径算法。53、想法：贪心算法(局部最优)、路径长度增长顺序生成最短路径。贪心算法：使用局部最优计算全局最优。使用生成的顶点的最短路径计算另一顶点的最短路径。寻找从V0到其馀顶点的最短路径。1 .Di的值最初是从v0到VI的圆弧权重，Di表示从v0到VI的最短路径长度。Di的最小值D2是从v0到v2的最短路径长度，Path2=(v0，v2)，Pathi是从v0到VI的最短路径，54，如果下一条最短路径的终点是vk，则为最短路径，或

13、经过(v0，vk)，v2或v4到vk，2 .如何找到下一个最短路径？如果下一条最短路径的终点为VJ，则设置最短路径(v0，VJ)或v0通过v2到达VJ的路径。其中，如果取Di(D2除外)的最小值，则结果为v4，结果为Path4=(v0，v4)。3 .如何找到下一个最短路径？如果从Di(D2，D4除外)中取最小值，则结果为v3，Path3=(v0，v4，v3)。55，一般假设s是求最短路径终点的集合。也就是说，在下一个最短路径(设置为x)或圆弧(v0，x)或v0开始的中间，只有s的顶点通过，最后到达顶点x的路径。半增法：假定下一最短路径上有不在s上的顶点，可以设置v；在这种情况下，必须存在结束v的最短路径，其长度比该路径短。不可能以路径长度增加的顺序生成最短路径。也就是说，已经创建了长度小于该路径的所有路径。矛盾。，56，算法说明，使用相邻矩阵arcsij表示直接图形。