hellowordapi
zh_coder
采纳率0%
2015-04-21 14:42 阅读 1.8k

请教算法设计这本书。谢谢

请教一下各位看过算法设计这本书的前辈。我需要着重了解这本书的什么思想和重要的地方。小弟大一略懂C C++ 看过严版的数据结构和高一凡和数据结构。但是树和图还有算法搞不懂

  • 点赞
  • 写回答
  • 关注问题
  • 收藏
  • 复制链接分享

9条回答 默认 最新

  • caozhy 从今以后生命中的每一秒都属于我爱的人 2015-04-21 15:00

    推荐你看《编程珠玑》《编程珠玑续编》这两本书,它是非常好的算法入门。而且没有枯燥和长篇大论。

    点赞 1 评论 复制链接分享
  • zzkjliu zzkjliu 2015-04-21 14:54

    在电脑上运行运行,多看几遍,回搞懂的。

    树和图都是非线性的数据结构。图相对于树来说,是更加抽象和复杂的。可以认为树是图的基础,树是一种更简单意义上的图。
    在树型结构中,每一个数据元素都可能和下一层中多个元素(即孩子结点)相关,但却只能与上一层中的一个元素(即双亲结点)相关。而在图形结构中,结点之间的关系可以是任意的,图中任意两个数据之间都可能相关。
    先看一个简单的图。(实线部分)
    树与图的简单比较 - SunShine - 学而时习之

    图(1)
    这个简单的图同时是一棵简单的树。我们首先根据树的结构给出相关概念。
    AB……称之为树的结点。在这里我们把D结点看做树的根结点,那么这个树就是一个简单的二叉树。则,A结点和C结点就可以称为D结点的子树或孩子,D结点是A结点和C结点的双亲。在这里,结点拥有的子树个数称为结点的度。因为我们把D结点看做根结点,也就是说除去叶子节点,每个结点的度都是2.。在树中,无论从哪一个结点出发,按着一定得路径总能遍历完所有的结点。对于一个拥有n个结点的树来说,它就拥有n-1条边,这样才能保证形成一个树,才能保证可以从任意结点遍历所有结点。
    我们在根据图型结构给出相关概念。图中的概念比树中较多,但本质上是相通的。
    AB……称为图的顶点。在图中没有所谓的根结点问题。每个顶点都是独立的,并不附属于其他任何顶点。这就与树中的双亲和孩子结点有一定区别。在这样一个图中,顶点之间的连线时无向的,此时的图称为无向图,顶点之间的连线称为边。上文提到树中,结点拥有的子树个数称为结点的度。在图中,每个顶点射出(射入)的边都称为顶点的度。(在有向图中有入度和出度之分)
    如果我们把上图中的AB,DG之间做两条连线的话,如上图虚线所示。这样一连接,图(1)
    就不再是一个树了,而变身为一个比较复杂的图。至此我们发现,图中的边更加复杂,这也就使得顶点之间的连接更加简单方便。但这样会给遍历所有顶点带来麻烦,在此不再叙述。
    图(1)是比较简单的图,图中任意两个顶点之间都是连通的。所谓连通,就是指两个顶点之间有路径。这个路径可以是直接(AB)的,也可以是间接(AC)的。显然,在未加虚线时,每个顶点之间也是连通的,不过就是少了两条直接的路径而已。加上虚线所示的两条直接路径,使得寻找顶点之间的连通路径更加方便快捷。
    现在我们把上图改作图(2)所示,再看一下它的特征。
    图(2)
    树与图的简单比较 - SunShine - 学而时习之

    对于这样一个连通图,它有7个顶点,共9条边。其中在AB之间出现了不唯一的路径,我们可以从A顶点直接到B顶点,也可以从A经D、C再到B顶点。而且在所有组成环的顶点,都有不同路径出现。这就意味着要从一个顶点通向另一个顶点,可能会有不同的路径可循。如果我们把所有双向的路径都化简,使任意两个顶点之间都存在且只存在唯一的路径。就会得到图(3)所示
    图(3)
    树与图的简单比较 - SunShine - 学而时习之
    在图(3)中,还是7个顶点,但只有6条边,但任意两个顶点之间依然是连通的。这就是图(2)连通图的极小连通子图。我们看到这个极小连通子图中包含所有的顶点,但只有足以构成一棵树的边(可参照上文树的介绍),这样的连通子图称作连通图的生成树。对于一个拥有n个顶点的连通图,它的生成树包含n个顶点,n-1条边。
    综上,可以得出以下结论:
    (1) 一个树肯定是一个连通图,但并不是所有的连通图都是树。
    (2) 对于n个顶点的图,要想构成连通图,它必须首先成为一棵树,即,n个顶点的连通图至少要拥有n-1条边。
    小结:关于树与图的对比,本想从更高层次上来探究,却发现自己只能理解到这样一个很浅显的层面。

    点赞 评论 复制链接分享
  • zzkjliu zzkjliu 2015-04-21 14:59
  • zzkjliu zzkjliu 2015-04-21 15:09

    树最直观的用途就是如人类社会的族谱和各种社会组织机构都可用树形象表示。一切具有层次关系的问题都可用树来描述。

    在图中结点之间的关系是任意的,任何两个结点都可能相关,因此图能用来解决现实世界中一些极其复杂问题.

    自己的理解:树是一种“层次”关系,图是“网络”关系

    树是图,图不一定是树

    树是图的子集
    树有一个根节点,图没有
    树可以递归遍历,图要看情况
    树有层次划分,图没有

    点赞 评论 复制链接分享
  • huangshanchun huangshanchun 2015-04-21 23:42

    算法不仅要看书还要刷题目。

    点赞 评论 复制链接分享
  • haitunxiaomo 如影随从 2015-04-22 02:26

    感觉算法这东西不仅要看,主要还是要用,不用就白学了

    点赞 评论 复制链接分享
  • lx417147512 ltree98 2015-04-22 07:31

    先看算法,了解大概的原理,
    然后可以根据代码一步步走一遍,
    然后就是找题刷一刷,可以做OJ的题目,网上很多的(比如,要做 Kruskacl最小生成树的题,就搜索 OJ的最小生成树的题目,然后做一下)

    点赞 评论 复制链接分享
  • zhanggaoju lein_zhang 2015-04-22 14:58

    你可以在网上下写面试题目做下,如编程之美,c/c++面试宝典等,自己多写代码。另外,多上leetcode这样的算法网站看看,锻炼下也不错

    点赞 评论 复制链接分享
  • u013295579 mockingbird~ 2015-04-23 06:50

    觉得楼主应该先去学学离散数学,图论,数论,在概念上有个初步认识,随后可以试着去解决些实际问题,可以做一些编程练习题专题练习,坚持学习总结,相信一定会有很大的收获,坚持啦

    点赞 评论 复制链接分享

相关推荐