2014计算机考研临考指导:数据结构常用算法精析7
数据结构是计算机考研408计算机学科专业基础综合的重要组成部分，考生需要认真复习，尤其是对于数据结构中一些常用的算法问题，考生一定要弄懂弄会，理解的去掌握，下面是第7章节有关数据结构算法，希望对大家有所帮助。第七章：
对于无向图，e的范围是：
数据结构中所讨论的图都是简单图，任意两结点间不会有双重的边。
对于有向图，e的范围是：
图的各种存储结构
邻接矩阵很方便访问任意两点的边，但是不方便计算其邻接点。在深度和广度遍历中广泛的需要求某点的邻接点。所以邻接矩阵只在Floyed和Prim和Dijstra中采用。
邻接表能很方便的求某顶点的邻接点，索引对于与遍历有关的算法大多都采用邻接表。如深度、广度、拓扑排序、关键路径。但他也有不足的地方，就是不方便求入度或是那些点可以到他的操作。所以有人引进逆邻接表。最后人们把这两种表结合到一起就是十字链表和邻接多重表。一个是存储有向图，另一个是存储无向图。
在十字链表和邻接多重表很方便求邻接点的操作和对应的逆操作。所以实际应用中，凡是能用邻接表实现的一定能用十字链表和邻接多重表实现。并且它们的存储效率更高。
1.邻接矩阵(有向图和无向图和网)又称为数组表示法
typedef struct
{ vextype vexs; ∥顶点存储空间∥
adjtype A; ∥邻接矩阵∥
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; ∥顶点表∥
int vexnum,arcnum;
GraphKind kind;
}ALGraph;
adjvexnextarcinfo
边结点
datafirstarc
顶点结点
3.十字链表(有向图和有向网)
headvextaivexhlinktlinkinfo
边结点
datafirstinfirstout
顶点结点
4.邻接多重表(无向图)
markivexjvexilinkjlinkinfo
边结点
datafirstedge
顶点结点
有向无环图(DAG)：是描述含有公共子式的表达式的有效工具。二叉树也能表示表达式，但是利用有向无环图可以实现对相同子式的共享，从而节省存储空间。
顶点的度：
无向图：某顶点V的度记为D(V)，代表与V相关联的边的条数
有向图：顶点V的度D(V)=ID(V)+OD(V)
强连通分量:在有向图中，若图中任意两顶点间都存在路径，则称其是强连通图。图中极大 强连通子图称之为强连通分量
“极大”在这里指的是：往一个连通分量中再加入顶点和边，就构不成原图中的一个 连通子图，即连通分量是一个最大集的连通子图。有向图的连通就是指该有向图是
强连通的
遍历图的过程实质上是_对每个顶点查找其邻接点的过程___ 其耗费的时间主要取决于采用的存储结构。当用邻接矩阵存储图时，查找每个顶点的邻接点所需的时间O( )，其中n是图中顶点数。而当用邻接表存储图时，找邻接点的所需时间为O(e)，其中e为图中边的个数或有向弧的个数，由此，当以邻接表作为存储结构时，深度优先搜索遍历图的时间复杂度O(n+e). (责任编辑：tq2013)
页:
[1]