[
![]() |
图(Graph)是一种比树更复杂的数据结构。
让我们复习一下离散数学的知识,图 = 点集 + 边集,n个节点的图,边数最多C(n,2)。
一、图的存储(n个节点, e条边):
邻接矩阵
最常用的图静态存储办法,用一个n x n的数组存储任意两节点的连通情况(一般情况下同时存放权值),特点是创建,查找操作非常方便,查询两个节点是否连接的时间复杂度是O(1),不过空间开销很大S(n^2),求节点的入度出度为O(n)。
邻接表
S(n) = n + e
逆邻接表
十字链表(有向图)
邻接多重表(无向图)
让我们复习一下离散数学的知识,图 = 点集 + 边集,n个节点的图,边数最多C(n,2)。
一、图的存储(n个节点, e条边):
邻接矩阵
最常用的图静态存储办法,用一个n x n的数组存储任意两节点的连通情况(一般情况下同时存放权值),特点是创建,查找操作非常方便,查询两个节点是否连接的时间复杂度是O(1),不过空间开销很大S(n^2),求节点的入度出度为O(n)。
邻接表
S(n) = n + e
逆邻接表
十字链表(有向图)
邻接多重表(无向图)
小婉
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

