图论和深度优先搜索

快捷方式: 差异，相似，杰卡德相似系数，参考。

图论和深度优先搜索之间的区别

图论 vs. 深度优先搜索

图论（Graph theory）是组合数学的一个分支，和其他数学分支，如群论、矩阵论、拓扑学有着密切关系。图是图论的主要研究对象。图是由若干给定的顶点及连接两顶点的边所构成的图形，这种图形通常用来描述某些事物之间的某种特定关系。顶点用于代表事物，连接两顶点的边则用于表示两个事物间具有这种关系。 图论起源于著名的柯尼斯堡七桥问题。该问题于1736年被欧拉解决，因此普遍认为欧拉是图论的创始人。 图论的研究对象相当于一维的单纯复形。. 深度优先搜索算法（Depth-First-Search，DFS）是一种用于遍历或搜索树或图的算法。沿着树的深度遍历树的节点，尽可能深的搜索树的分支。当节点v的所在边都己被探寻过，搜索将回溯到发现节点v的那条边的起始节点。这一过程一直进行到已发现从源节点可达的所有节点为止。如果还存在未被发现的节点，则选择其中一个作为源节点并重复以上过程，整个进程反复进行直到所有节点都被访问为止。属于盲目搜索。 深度优先搜索是图论中的经典算法，利用深度优先搜索算法可以产生目标图的相应拓扑排序表，利用拓扑排序表可以方便的解决很多相关的图论问题，如最大路径问题等等。 因发明“深度优先搜索算法”，約翰·霍普克洛夫特与罗伯特·塔扬共同获得计算机领域的最高奖：图灵奖。.

广度优先搜索

广度优先搜索算法（Breadth-First-Search，縮寫為BFS），又譯作寬度優先搜索，或橫向優先搜索，是一種圖形搜索演算法。簡單的說，BFS是從根節點開始，沿着树的宽度遍历树的节点。如果所有节点均被访问，则算法中止。广度优先搜索的实现一般采用open-closed表。.

图论和广度优先搜索 · 广度优先搜索和深度优先搜索 · 查看更多 »

图 (数学)

在數學的分支图论中，图（Graph）用于表示物件與物件之間的關係，是圖論的基本研究對象。一张圖由一些小圓點（稱為頂點或結點）和連結這些圓點的直線或曲線（稱為邊）組成。西尔维斯特在1878年首次提出“图”这一名词。.

图 (数学)和图论 · 图 (数学)和深度优先搜索 · 查看更多 »