计算机考研:数据结构常用算法精析(7)
2013.12.11 14:39

  

  数据结构是计算机考研408计算机学科专业基础综合的重要组成部分,考生需要认真复习,尤其是对于数据结构中一些常用的算法问题,考生一定要弄懂弄会,理解的去掌握。新东方在线小编下面一一为大家分析一下,帮助考生更好地去掌握。

  第七章:

  对于无向图,e的范围是:

  数据结构中所讨论的图都是简单图,任意两结点间不会有双重的边。

  对于有向图,e的范围是:

  图的各种存储结构

  邻接矩阵很方便访问任意两点的边,但是不方便计算其邻接点。在深度和广度遍历中广泛的需要求某点的邻接点。所以邻接矩阵只在Floyed和Prim和Dijstra中采用。

  邻接表能很方便的求某顶点的邻接点,索引对于与遍历有关的算法大多都采用邻接表。如深度、广度、拓扑排序、关键路径。但他也有不足的地方,就是不方便求入度或是那些点可以到他的操作。所以有人引进逆邻接表。最后人们把这两种表结合到一起就是十字链表和邻接多重表。一个是存储有向图,另一个是存储无向图。

  在十字链表和邻接多重表很方便求邻接点的操作和对应的逆操作。所以实际应用中,凡是能用邻接表实现的一定能用十字链表和邻接多重表实现。并且它们的存储效率更高。

  1.邻接矩阵(有向图和无向图和网)又称为数组表示法

  typedef struct

  { vextype vexs[maxn]; ∥顶点存储空间∥

  adjtype A[maxn][maxn]; ∥邻接矩阵∥

  int vexnum,arcnum; //图的顶点数和边数

  GraphKind Kind; //图的类型

  } mgraph;

  2.邻接表(有向图和无向图和网)

  typedef struct node ∥边

  { int adj; int w; ∥邻接点、权∥

  struct node *next; ∥指向下一弧或边∥

  }linknode;

  typedef struct ∥顶点类型∥

  { vtype data; ∥顶点值域∥

  linknode *farc; ∥指向与本顶点关联的第一条弧或边∥

  }Vnode;

  typedef struct

  {

  Vnode G[maxn]; ∥顶点表∥

  int vexnum,arcnum;

  GraphKind kind;

  }ALGraph;

  adjvexnextarcinfo

  边结点

  datafirstarc

  顶点结点

  3.十字链表(有向图和有向网)

  headvextaivexhlinktlinkinfo

  边结点

  datafirstinfirstout

  顶点结点

  4.邻接多重表(无向图)

  markivexjvexilinkjlinkinfo

  边结点

  datafirstedge

MORE+

    相关阅读 MORE+

    版权及免责声明
    1.凡本网注明"稿件来源:新东方在线"的所有文字、图片和音视频稿件,版权均属北京新东方迅程网络科技有限公司所有,任何媒体、网站或个人未经本网协议授权不得转载、链接、转贴或以其他方式复制发表。已经本网协议授权的媒体、网站,在下载使用时必须注明"稿件来源:新东方在线",违者本网将依法追究责任。
    2.本网末注明"稿件来源:新东方在线"的文/图等稿件均为转载稿,本网转载出于传递更多信息之目的,并不意味着赞同其观点或证实其内容的真实性。如其他媒体、网站或个人从本网下载使用,必须保留本网注明的"稿件来源",并自负版权等法律责任。如擅自篡改为"稿件来源:新东方在线”,本网将依法追究责任。
    3.如本网转载稿涉及版权等问题,请作者致信weisen@xdfzx.com,我们将及时外理

    Copyright © 2011-202

    All Rights Reserved