二叉树模型怎么画？详细图文解析绘制专业模型图

叉树是一种数据结构，是由结点个数大于或等于0的结点所构成的结点有限集，或为空树（即结点个数等于0），或有一个根结点和两颗分别称为左子树和右子树的互不相交的二叉树构成。二叉树每个结点的度不大于2（即每个结点最多只有两个子结点），且子树有左右之分，不可随意颠倒顺序。

二叉树模型常见用途

二叉树的应用很广泛，可基于二叉树前中后遍历的遍历法则用于文件夹管理上，可用于输出某个文件夹下的所有文件名称、统计某个文件夹的大小等。二叉树作为一种数据结构，也可用于数据库系统的排序和检索等。二叉树中的哈夫曼树还可用于文本压缩编码，哈夫曼编码是一种最基本的压缩编码方法。

二叉树模型绘制方法

使用亿图图示软件来绘制二叉树的操作十分简便快捷，通过以下几个步骤的进行就可轻松绘制出一幅专业美观的二叉树模型图啦。

第一步，下载并安装“亿图图示”软件桌面端，安装完成后双击启动软件，开始作图。也可浏览器输入网址直接访问亿图图示在线版。

第二步，新建二叉树模型图。依次点击“文件”-“新建”，在出现页面上方的搜索栏中输入“二叉树”，点击“搜索”按钮，下方就会展开相应的模板库。

第三步，从下方出现的模板库中选取一个自己喜欢的模板，点击使用，打开模板。

第四步，双击文本框，替换二叉树模板内的文字。可根据自身需求增删或移动模板内的节点个数及位置，也可根据自己的喜好个性化二叉树模型图。

第五步，绘制完成后，可点击左上角的文件按钮，对绘制好的二叉树模型图进行保存、另存为、导出等操作。

二叉树模型绘制软件——亿图图示

亿图图示是一款跨平台综合办公绘图类的国产软件，适用于Windows、Mac以及Linux多个系统平台。支持绘制的绘图类型多达260多种，且对各个绘图类型，软件内置了丰富的模板可供用户挑选使用，具有丰富的绘图素材可帮助使用者快速绘制，二叉树模型图、项目流程图、思维导图、商务图表、组织结构图、甘特图、UML以及网络拓扑图等多种图表类型，提高工作学习效率。
使用亿图图示绘制二叉树模型图，直接搜索套用模板，可快速绘制出专业美观的二叉树模型图，有效节约时间成本！

为什么选择亿图图示绘制二叉树模型

支持跨平台使用：软件支持Windows、Mac和Linux多个系统平台使用，同时具有亿图在线版可支持在各个主流浏览器下直接输入相应网址进行使用。
导入格式丰富：支持导入Visio，SVG文件，也可批量转化一整个目录的Visio文件到Edraw文件，轻松实现文件格式转变。
导出格式丰富：可将图表导出为JPG、PNG、GIF、HTML、PDF等多种格式，满足不同的分享使用需求。
海量的符号资源库：亿图软件内置超26000种图形模板和矢量符号，可供用户随心挑选使用，快速绘制出漂亮美观的图表。
操作简单：软件采用拖曳式操作，自带模板，无需绘图基础，操作门槛低。

自hackernoon，作者：javinpaul，机器之心编译，机器之心编辑部。

同学，你会手写二叉树吗？近来正值秋招季节，很多编程面试都要求手写数据结构手推机器学习算法。各位同学为了面试也会刷各种编程题，其中数据结构与排序搜索算法又是最为基础的内容。在本文中，我们为各位读者准备了 48 道基础面试题，它可以帮助我们更深地理解数据结构。本文所有面试题都提供了 Java 解决方案，并介绍了比较流行的 GitHub 面试题项目。

很多计算机科学专业毕业生和程序员都会去滴滴出行、这样的独角兽公司，或者亚马逊、微软和谷歌这样的科技巨头申请编程和软件开发职位。你在申请这些工作时，肯定很想知道面试官会问到哪些问题。

在本文中，作者会分享一些常见的编程面试问题，这些问题来自于针对不同经验层次的程序员的面试——从应届毕业生到具有一两年经验的程序员。

编程面试题通常包含数据结构和基于算法的问题，以及一些逻辑问题，例如：如何在不使用临时变量的情况下交换两个整数？

为了清晰，编程面试题需要划分为不同主题。我们在面试中经常看到的领域是数组、链表、字符串、二叉树以及有关算法的问题（例如字符串算法、快速排序或基数排序等排序算法），本文将介绍这些内容。

虽然本文无法覆盖你在面试中将要面临的所有问题，但是它可以给你提供足够的思路，让你在面试时对于各种挑战有所准备。

一旦解决了这些问题，你就可以有信心面对任何电话面试或现场面试了。

当然，如果你对于基本数据结构和算法没有足够的知识储备，那么直接接触以下问题将对你没有帮助。

算法和编程面试题 TOP 48

废话少说，这里有一份「编程面试最常见的问题列表」：

1. 数组编程面试问题

数组是最基本的数据结构，它将元素储存在连续的内存空间中。数组也是面试官最喜欢问的主题之一，在任何编程面试中都能听到非常多关于数组的问题，例如反转数组、排序数组或搜索数组元素等。

数组这种数据结构的主要优点在于如果给定索引，那么它会提供 O(1) 复杂度的搜索，这种搜索速度非常迅速。但是从数组中添加或移除元素会比较慢，因为一旦创建了数组，我们就很难再更改它的大小。如果需要更长或更短的数组，我们就需要重新创建新数组，并将老数组的所有元素复制到新数组中。

解决数组问题的关键是对数组数据结构有比较深的理解，同时还需要了解循环、递归和基本运算子等常见的编程结构。以下是一些常见的数组编程面试问题：

1. 在一个元素为 1 到 100 的整数数组中，如何搜索缺失元素？

解决方案：http://javarevisited.blogspot.com/2014/11/how-to-find-missing-number-on-integer-array-java.html

2. 给定一个数组，如何搜索重复元素？

解决方案：http://javarevisited.blogspot.com/2014/01/how-to-remove-duplicates-from-array-java-without-collection-API.html

3. 给定一个乱序数组，如何搜索最大和最小元素？

解决方案：http://java67.blogspot.com/2014/02/how-to-find-largest-and-smallest-number-array-in-java.html

4. 给定一个数值，如何搜索整数数组中加和为该数值的成对元素？

解决方案：http://javarevisited.blogspot.com/2014/08/how-to-find-all-pairs-in-array-of-integers-whose-sum-equal-given-number-java.html

5. 如果数组包含多个重复值，如何搜索所有重复值？

解决方案：http://javarevisited.blogspot.com/2014/03/3-ways-to-find-first-non-repeated-character-String-programming-problem.html

6. 给定一个数组，如何用 Java 删除重复元素？如何在不使用库的情况下移除数组中的重复元素？

解决方案：http://javarevisited.blogspot.com/2014/01/how-to-remove-duplicates-from-array-java-without-collection-API.html

7. 如何使用快速排序算法对整数数组进行排序？

解决方案：http://javarevisited.blogspot.com/2014/08/quicksort-sorting-algorithm-in-java-in-place-example.html

8. 如何使用 Java 反转一个数组？

解决方案：http://javarevisited.blogspot.com/2013/03/how-to-reverse-array-in-java-int-String-array-example.html

这些问题不仅能帮助我们提高解决问题的能力，同时也能提升我们关于数组数据结构的理解。

如果你需要了解更多基于数组的深度问题，你可以在 GitHub 或 Coursera 上多找找关于数据结构的课程与资料，例如在 GitHub 中，就有非常多关于数组的学习资料，下面我们介绍了一份中文版的谷歌的面试资料，它在 GitHub 上有 6 万多的收藏量。

项目地址：https://github.com/jwasham/coding-interview-university/blob/master/translations/README-cn.md

2. 链表编程面试问题

链表是补充数组数据结构的另一种常见数据结构。与数组类似，它也是线性数据结构，以线性方式存储元素。

然而，与数组不同的是，它不会将元素存储在连续的位置；相反，它会将其分散存储在内存中，彼此通过节点相互连接。链表是节点列表，其中每个节点包含存储的值和下一个节点的地址。

由于这种结构，在链表中添加或删除元素变得很简单，因为你只需要改变链接而不是创建数组，但是这样会使搜索变得困难，并且经常需要 O(n) 的时间复杂度才能在单个链表中找到某个元素。

这篇文章（https://javarevisited.blogspot.com/2013/07/difference-between-array-and-linked-list-java.html）提供了更多关于数组和链表数据结构之间差异的信息。

链表还有多种变体，如单链表，即允许在一个方向（正向或反向）上遍历；双链表则允许你在两个方向（向前或向后）遍历；最后是循环链表，它形成一个循环。

要解决关于链表的问题，掌握递归知识很重要，因为链表是递归数据结构。

如果你从链表中取出一个节点，剩下的数据结构仍然是链表，因此，许多链表问题的递归解比迭代解更简单。

以下是关于链表的一些常见问题和解决方案：

9. 如何在一次传递中找到单链表的中间元素？

解决方案：http://javarevisited.blogspot.sg/2012/12/how-to-find-middle-element-of-linked-list-one-pass.html

10. 如何检查给定的链表是否包含循环？如何找到循环的起始节点？

解决方案：http://javarevisited.blogspot.sg/2013/05/find-if-linked-list-contains-loops-cycle-cyclic-circular-check.html

11. 如何反转链表？

解决方案：http://www.java67.com/2016/07/how-to-reverse-singly-linked-list-in-java-example.html

12. 在没有递归的情况下如何反转单链表？

解决方案：http://javarevisited.blogspot.sg/2017/03/how-to-reverse-linked-list-in-java-using-iteration-and-recursion.html

13. 如何删除乱序链表中的重复节点？

解决方案：https://www.geeksforgeeks.org/remove-duplicates-from-an-unsorted-linked-list/

14. 如何测量单链表的长度？

解决方案：http://javarevisited.blogspot.sg/2016/05/how-do-you-find-length-of-singly-linked.html

15. 如何从单链表的末端找出第三个节点？

解决方案：http://javarevisited.blogspot.sg/2016/07/how-to-find-3rd-element-from-end-in-linked-list-java.html

16. 如何使用堆栈算出两个链表的总和？

解决方案：https://www.geeksforgeeks.org/sum-of-two-linked-lists/

这些问题有助于你发展解决问题的技能，并提升你对链表数据结构的了解。目前有非常多的资源可以帮助我们理解链表，例如在 GitHub 上一个交互式的编码实践中，它使用 Jupyter Notebook 提供了数据结构与算法的各种练习，其中就包括了很多链表问题及实践。

项目地址：https://github.com/donnemartin/interactive-coding-challenges

3. 字符串编码面试问题

除了数组和链表数据结构，字符串也是编程工作面试中的另一热点话题。我参加过的编码面试基本都问过关于字符串的问题。

如果你了解数组，那么你就能轻易地解决基于字符串的问题，因为字符串就是字符数组。因此，你通过解决数组编程问题学到的所有技巧，也能用来解决字符串编程问题。

以下是编程工作面试中常问的字符串编程问题列表：

17. 如何打印字符串中重复的字符？

解决方案：http://java67.blogspot.sg/2014/03/how-to-find-duplicate-characters-in-String-Java-program.html

18. 如何检查两个字符串是否互为逆序？

解决方案：http://javarevisited.blogspot.sg/2013/03/Anagram-how-to-check-if-two-string-are-anagrams-example-tutorial.html

19. 如何打印字符串中首个非重复字符？

解决方案：http://javarevisited.blogspot.sg/2014/03/3-ways-to-find-first-non-repeated-character-String-programming-problem.html

20. 如何使用递归反转给定字符串？

解决方案：http://javarevisited.blogspot.sg/2012/01/how-to-reverse-string-in-java-using.html

21. 如何检查一个字符串是否仅包含数字？

解决方案：http://javarevisited.blogspot.sg/2012/10/regular-expression-example-in-java-to-check-String-number.html

22. 如何搜索字符串中的重复字符？

解决方案：http://java67.blogspot.sg/2014/03/how-to-find-duplicate-characters-in-String-Java-program.html

23. 给定一个字符串，如何统计元音数和辅音数？

解决方案：http://java67.blogspot.sg/2013/11/how-to-count-vowels-and-consonants-in-Java-String-word.html

24. 给定一个字符，如同计算它在字符串中出现的次数？

解决方案：http://javarevisited.blogspot.sg/2012/12/how-to-count-occurrence-of-character-in-String.html

25. 如何搜索一个字符串的所有排列情况？

解决方案：http://javarevisited.blogspot.com/2015/08/how-to-find-all-permutations-of-string-java-example.html

26. 在不使用任何库的情况下，如何反转给定句子中的单词？

解决方案：http://java67.blogspot.com/2015/06/how-to-reverse-words-in-string-java.html

27. 如何检查两个字符串是不是互为旋转（rotation）？

解决方案：http://www.java67.com/2017/07/string-rotation-in-java-write-program.html

28. 给定一个字符串，如何检查它是不是回文结构？

解决方案：http://java67.blogspot.com/2015/06/how-to-check-is-string-is-palindrome-in.html

这些问题可以提升你对字符串数据结构的了解。如果你能独立解决所有这些字符串问题，说明你的状态很好。

如果想深入了解一些更复杂的问题，我推荐你去看 Steven Skiena 的《The Algorithm Design Manual》，这本书里有最难的算法问题。

网上也有该书的 PDF 版，下载地址：http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.471.4772&rep=rep1&type=pdf

如果你需要更多的练习，这里还有另外 20 个关于字符串编程的问题：

http://javarevisited.blogspot.sg/2015/01/top-20-string-coding-interview-question-programming-interview.html

4. 二叉树编程面试问题

现在我们只了解了线性数据结构方面的问题，但是真实世界中的所有信息不可能全是线性的，这就需要树数据结构了。

树数据结构允许以层级形式存储数据。根据存储数据的方式，有多种树类型，如二叉树。

和它的近亲二叉查找树一样，它也是最流行的树数据结构之一。因此，你会看到很多相关的有趣问题。例如，如何遍历树、计算节点数量、找出深度，以及检查是否平衡。

解决二叉树问题的关键在于深厚的理论知识，如二叉树的大小或深度、什么是叶节点、什么是节点，以及了解流行的遍历算法。

以下是软件工程师或开发工作面试中常见的二叉树相关编程问题：

29. 如何实现二叉查找树？

解决方案：http://javarevisited.blogspot.sg/2015/10/how-to-implement-binary-search-tree-in-java-example.html#axzz4wnEtnNB3

30. 如何对给定二叉树执行前序遍历？

解决方案：http://javarevisited.blogspot.sg/2016/07/binary-tree-preorder-traversal-in-java-using-recursion-iteration-example.html#axzz5ArdIFI7y

31. 如何在没有递归的情况下对给定二叉树执行前序遍历？

解决方案：http://www.java67.com/2016/07/binary-tree-preorder-traversal-in-java-without-recursion.html

32. 如何对给定二叉树执行中序遍历？

解决方案：http://www.java67.com/2016/08/binary-tree-inorder-traversal-in-java.html

33. 如何在没有递归的情况下通过对给定二叉树执行中序遍历来打印所有节点？

解决方案：http://www.java67.com/2016/08/binary-tree-inorder-traversal-in-java.html

34. 如何实现后序遍历算法？

解决方案：http://www.java67.com/2016/10/binary-tree-post-order-traversal-in.html

35. 如何在没有递归的情况下对给定二叉树执行后序遍历？

解决方案：http://www.java67.com/2017/05/binary-tree-post-order-traversal-in-java-without-recursion.html

36. 如何打印二叉查找树的所有叶节点？

解决方案：http://www.java67.com/2016/09/how-to-print-all-leaf-nodes-of-binary-tree-in-java.html

37. 如何计算给定二叉树中叶节点的数量？

解决方案：http://javarevisited.blogspot.sg/2016/12/how-to-count-number-of-leaf-nodes-in-java-recursive-iterative-algorithm.html

38. 如何在给定数组中执行二元搜索？

解决方案：http://javarevisited.blogspot.sg/2015/10/how-to-implement-binary-search-tree-in-java-example.html#axzz4wnEtnNB3

如果你认为自己对二叉树编程的了解不足，无法解决这些问题，我建议你先熟练掌握数据结构和算法知识，比如你可以上这门课《From 0 to 1: Data Structures & Algorithms in Java》。同样，你也可以查阅准备 Google 面试的一套完整手册，这套 GitHub 手册前面已经介绍了，但它在二叉树等数据结构上真的有非常多的案例与教程。

项目地址：https://github.com/jwasham/coding-interview-university

如果你需要更多推荐，可以参考：

http://javarevisited.blogspot.sg/2015/07/5-data-structure-and-algorithm-books-best-must-read.html
http://javarevisited.blogspot.sg/2018/01/top-5-free-data-structure-and-algorithm-courses-java—c-programmers.html

5. 其它编程面试问题

除了数据结构方面的问题，大部分编程工作面试也会问关于算法、设计、位运算和通用的逻辑问题。

针对性练习很重要，因为有时在实际面试中它们会有点难解。事先练习不仅能够让你熟悉这些问题，还能让你在向面试官解释答案时更加自信。

39. 如何实现冒泡排序算法（bubble sort algorithm）？

解决方案：http://javarevisited.blogspot.sg/2014/08/bubble-sort-algorithm-in-java-with.html#axzz5ArdIFI7y

40. 如何实现迭代快速排序算法（iterative quicksort algorithm）？

解决方案：http://javarevisited.blogspot.sg/2016/09/iterative-quicksort-example-in-java-without-recursion.html#axzz5ArdIFI7y

41. 如何实现插入排序算法（insertion sort algorithm）？

解决方案：http://www.java67.com/2014/09/insertion-sort-in-java-with-example.html

42. 如何实现归并排序算法（merge sort algorithm）？

解决方案：http://www.java67.com/2018/03/mergesort-in-java-algorithm-example-and.html

43. 如何实现桶排序算法（bucket sort algorithm）？

解决方案：http://javarevisited.blogspot.sg/2017/01/bucket-sort-in-java-with-example.html

44. 如何实现计数排序算法（counting sort algorithm）？

解决方案：http://www.java67.com/2017/06/counting-sort-in-java-example.html

45. 如何实现基数排序算法（radix sort algorithm）？

解决方案：http://www.java67.com/2018/03/how-to-implement-radix-sort-in-java.html

46. 如何在不使用第三个变量的前提下交换两个数字？

解决方案：http://www.java67.com/2015/08/how-to-swap-two-integers-without-using.html

47. 如何确认两个矩形是否重叠？

解决方案：http://javarevisited.blogspot.sg/2016/10/how-to-check-if-two-rectangle-overlap-in-java-algorithm.html

48. 如何设计自动贩卖机？

解决方案：http://javarevisited.blogspot.sg/2016/06/design-vending-machine-in-java.html

如果你想查看更多此类编程问题，可以阅读这本书《Cracking the Coding Interview: 189 Programming Questions and Solutions》，适合短时间内准备编程工作面试。

下载地址：http://lib1.org/_ads/fcb49f53d5e943ce8acdc4469f63dc5d

你练习的问题越多，准备就越充分。因此，如果你认为 48 道题不够的话，可以查看：

https://javarevisited.blogspot.com/2015/02/50-programmer-phone-interview-questions-answers.html
http://javarevisited.blogspot.sg/2016/06/top-5-books-for-programming-coding-interviews-best.html
http://javarevisited.blogspot.sg/2018/02/10-courses-to-prepare-for-programming-job-interviews.html

现在你已经准备好面试了

这部分将介绍一些数据结构和算法之外的常见问题，可以帮助你在面试中取得更好的表现。

我的博客中还有很多此类问题，详见：http://www.java67.com/

这些常见的编程、数据结构和算法问题是你去任何一家公司面试都必须知道的，不管是大公司还是小公司，不管面试的职位高或低。

如果你正在寻找编程或软件开发工作，那么你可以先使用这些编程问题开始准备。该列表提供了一些不错的面试准备话题，能够帮助你评估自己的面试准备工作是否充分。

熟练掌握数据结构和算法知识是编程工作面试成功的关键，你应该更多地关注这些问题。

扩展阅读：

Data Structures and Algorithms: Deep Dive Using Java：https://click.linksynergy.com/fs-bin/click?id=JVFxdTr9V80&subid=0&offerid=323058.1&type=10&tmpid=14538&RD_PARM1=https%3A%2F%2Fwww.udemy.com%2Fdata-structures-and-algorithms-deep-dive-using-java%2F
10 Books to Prepare Technical Programming/Coding Job Interviews：http://www.java67.com/2017/06/10-books-to-prepare-technical-coding-job-interviews.html
10 Algorithm Books Every Programmer Should Read：http://www.java67.com/2015/09/top-10-algorithm-books-every-programmer-read-learn.html
Top 5 Data Structure and Algorithm Books for Java Developers：http://javarevisited.blogspot.sg/2016/05/5-free-data-structure-and-algorithm-books-in-java.html#axzz4uXETWjmV
From 0 to 1: Data Structures & Algorithms in Java：https://click.linksynergy.com/fs-bin/click?id=JVFxdTr9V80&subid=0&offerid=323058.1&type=10&tmpid=14538&RD_PARM1=https%3A%2F%2Fwww.udemy.com%2Ffrom-0-to-1-data-structures%2F
Data Structure and Algorithms Analysis—Job Interview：https://click.linksynergy.com/fs-bin/click?id=JVFxdTr9V80&subid=0&offerid=323058.1&type=10&tmpid=14538&RD_PARM1=https%3A%2F%2Fwww.udemy.com%2Fdata-structure-and-algorithms-analysis%2F

原文链接：https://hackernoon.com/50-data-structure-and-algorithms-interview-questions-for-programmers-b4b1ac61f5b0

和图的概念

图是一种特殊的数据结构，由点和边构成，它可以用来描述元素之间的网状关系，这个网状没有顺序，也没有层次，就是简单的把各个元素连接起来。

图的概念和基本性质

图（graph）：图（graph）由边（edge）的集合及顶点（vertex）的集合组成。通常记为：G=(V,E)。对于两个图G和G’，如果G’的顶点集合与边集合均为G的顶点集合与边集合的子集，那么称G’是G的子图。子图实际上就是一张图里面小一点的图，也可以是点，不难理解。

图常用来表示“多对多”的关系，如常说的：六度空间理论（Six Degrees Separation）

顶点（vertex）的属性：

度数（degree），与该顶点相关联的总边数，一个图G的总度数d(V)等于总边数2倍：2E。当图的边具有方向时，一个顶点又分为出度（out-degree）和入度（in-degree），出度是以该顶点为起点的边数，入度是以该顶点为终点的边数。
阶数（order），图G中顶点集V的大小为G的阶数。

边又称为线（line）或弧（arc），边(u,v)中表示u和v邻接（adjacent），(u, v) ∈ E，

边（edge）的属性：

一条边是一个顶点对(u,v)，u, v ∈ V，按照图的顶点对是否有序，顶点对有序的图称为有向图（directed graph, digraph），此时边(u,v)和(v,u)是两条不同的边，顶点对无序的图称为无向图（undirected graph），此时边(u,v)和(v,u)是两条相同的边，无向图可看作一个特殊的有向图

具有成分的边包含：权（weight）、值（cost/value），此时图由可分为有权图（weighted graph）和无权图（unweighted graph），无权图可以看作是所有边权值相同的有权图。

路径（path），一条路径是一个顶点序列u1, u2, u3, …, un，(ui, u(i+1)) ∈E，1<=i<n。路径长等于路径的边数：n-1，不包含边的路径长为0。

简单路径：路径上所有顶点互异，起点和终点可以相同

环或圈（cycle），此时u1=un，而且路径长至少为1，有向图(u,v)和(v,u)是一个圈，无向图(u,v)和(v,u)通常不被认为是一个圈。其中无圈图（acyclic graph）中没有圈，无圈有向图又称为DAG（directed acyclic graph）

自环边（self loop），两个顶点都相同的边。
重边或平行边（parallel edges），连接两个顶点的边数超过一条，又称为多重边（multiple edges）

连通图（connected graph），无向图中每个顶点到任意顶点都存在一条路径，连通的有向图称为强连通（strongly connected），非连通的有向图，去掉方向其基础图（underlying graph）是连通的，则成为弱连通的（weakly connected）

完全图（complete graph），图中任意一对顶点都存在一条边

稀疏图（sparse graph），每个顶点的度数较小的图

图的基本基本概念

顶点的度：无向图中连着顶点的边的数目。
顶点的入度和出度：有向图中，以这个顶点为起点的边的数量称为这个顶点的出度；以这个顶点为终点的边称为这个顶点的入度。
边权：边的费用，可以形象的理解为“过路费”。对于一张存在边权的图，我们称为“带权图”。
连通：如果图中两点U,V之间存在一条由U经过若干边、点到达V的路径，则称U，V是连通的。
回路：起点和终点相同的路径，称为“回路”或“环”。另外，不存在环的有向图称为Directed Acyclic Graph(DAG)。
完全图：每个点都与其它所有的点有连边的图。
无向图：图的边没有方向，可以双向。
有向图：图的边有方向，只能按箭头方向从一点到另一点。
网络：带权重的图
连通：如果从v 到w存在一条（无向）路径，则称v和w是连通的
路径：v到w的路径是一系列顶点的集合，其中任意一对相邻的顶点间都有图中的边。
路径的长度：是路径中的边数（如果带权，则是所有边的权重和）。如果v和w之间的所有顶点都不同，则称简单路径
连通图：图中任意两顶点都连通
连通分量：无向图的极大连通子图
极大顶点数：再加一个顶点就不连通了
极大边数：包含子图中所有顶点相连的所有边
强连通：有向图中顶点v和w之间存在双向路劲，则称v和w是强连通的
强连通图：有向图中任意两顶点均强连通
弱连通图：不符合强连通图的条件，但是若是将边的方向都去掉，如果是连通的，则称为弱连通图
强连通分量：有向图的极大强连通子图

图的简单应用

图的应用很广泛，这里举几个简单的例子。

航空系统：顶点表示机场，边表示时间、距离或飞行的费用，一般最好有强连通的航空系统，另外常见的需求问题有：求任意两个机场的最佳航线。
交通流：顶点表示街道的交叉口或红绿灯点，边表示速度限度或车辆容量，这时可以求最可能参数交通瓶颈的位置，或找出一条最短路。
社交网络：顶点表示用户，用户的活动、推荐或好友代表边，这样可以表示一个完整的社交用户网络。
电商推荐系统：顶点表示用户已浏览、收藏、购物过等相关的商品，边表示两个商品的相似性，可表示为有权图，权值为相似性的大小。

另外图论又可用于研究物理学和化学中的分子

图的遍历

深度优先搜索（Depth Firsh Search, DFS)：走一步，看一步，走不通后返回到上一个能走通的结点
广度优先搜索（Breadth First Search, BFs)：出队一个，访问一圈，访问的同时入队，相当于树的层序遍历（计划性非常强，个人感觉用这种遍历方式更好一些）

本系列主要讲二叉树，关于图，推荐阅读文章有：

数据结构与算法之图的概念、存储结构及遍历方式 https://www.cnblogs.com/ivy-zheng/p/10995510.html
图的概念、存储及遍历 https://blog.csdn.net/qq_39914766/article/details/90182084
图论(graph theory)算法原理、实现和应用全解 www.srcmini.com/1635.html

转载本站文章《讲透学烂二叉树(一)：图的概念和定义—各种属性特征浅析》,请注明出处：https://www.zhoulujun.cn/html/theory/algorithm/TreeGraph/8281.html

在线咨询

上一篇：明明都是正常的文件，为什么被提示是木马呢？
下一篇：webpack5打包html

您的项目需求

*请认真填写需求信息，我们会在24小时内与您取得联系。

整合营销服务商