图(Graph)是一种比树更复杂的数据结构。


让我们复习一下离散数学的知识,图 = 点集 + 边集,n个节点的图,边数最多C(n,2)。


一、图的存储(n个节点, e条边):

邻接矩阵
     最常用的图静态存储办法,用一个n x n的数组存储任意两节点的连通情况(一般情况下同时存放权值),特点是创建,查找操作非常方便,查询两个节点是否连接的时间复杂度是O(1),不过空间开销很大S(n^2),求节点的入度出度为O(n)。


邻接表
S(n) = n + e


逆邻接表


十字链表(有向图)


邻接多重表(无向图)
学习 | 评论(2) | 引用(0) | 阅读(10923)
小婉
2007/08/16 01:10
再来个变态一点的,turbo对N个人进行面试,每个人出K道题,任意两人之间只能有一道相同的题目,问turbo需要准备多少面试题?
turbozv 回复于 2007/08/16 21:31
“只能”的意思是“最多”还是“有且仅有”呢?
小婉
2007/08/14 17:25
出个图的题目给你做:给你一个图,如何输出图中所有的三角形。输入是一个边集。输出是图中三角形的数目。
turbozv 回复于 2007/08/15 22:29
广度搜,用力搜.....
分页: 1/1 第一页 1 最后页