1 : 图: Graph:
图: 无向图, 有向图
2: 图表示: 图的邻接矩阵 和 图的邻接表
主要以 图的 邻接表为主:
邻接表表示法将图以邻接表(adjacency lists)的形式存储在计算机中。所谓图的邻接表,也就是图的所有节点的邻接表的集合;而对每个节点,它的邻接表就是它的所有出弧。邻接表表示法就是对图的每个节点,用一个单向链表列出从该节点出发的所有弧,链表中每个单元对应于一条出弧。为了记录弧上的权,链表中每个单元除列出弧的另一个端点外,还可以包含弧上的权等作为数据域。图的整个邻接表可以用一个指针数组表示。例如,例7所示的图,邻接表表示为
可以很方便的知道 点的邻接点
这种结构适合查找顶点及邻接点的信息,查顶点的度,增加或删除顶点和边(弧)也很方便,
但因指针多占用了存储空间,另外,某两顶点间是否有边(弧)也不如邻接矩阵那么清楚。
对有向图的邻接表,查顶点出度容易,而查顶点入度却困难,要遍历整个邻接表。
要想查入度象查出度那样容易,
就要建立逆邻接表
package com.algorithm.common.graph; import com.algorithm.common.Bag; /** * 无权重无向图 (邻接表表示) * @author lijunqing */ public class Graph { /** * 顶点数 */ private int V; /** * 边数 */ private int E; /** * 邻接表 */ private Bag<Integer>[] adj; public Graph(int v) { this.V=v; this.E=0; adj=(Bag<Integer>[])new Bag[V]; for(int i=0; i < V; i++) { // 初始化邻接表 adj[i]=new Bag<Integer>(); } } public void addEdge(int v, int w) { if(v < 0 || v > V) { throw new IndexOutOfBoundsException(); } if(w < 0 || w > V) { throw new IndexOutOfBoundsException(); } E++; adj[v].add(w); adj[w].add(v); } /** * 返回Iterable可以遍历 * @param v * @return */ public Iterable<Integer> adj(int v) { if(v < 0 || v > V) { throw new IndexOutOfBoundsException(); } return adj[v]; } public int V() { return V; } public int E() { return E; } }
相关推荐
2.1 自然语言表述到数学表示的转换 2.1.1 严格定义(well-Definedness) 2.1.2 相等、恒等和同一性 2.1.3 数学命名约定 2.1.4 数字 2.1.5 上下文 2.1.6 函数、参数和变量 2.1.7 指令和算法 2.2 集合论 ...
该书解释并比较了SQL Server 2000和SQL Server 2005在数据库开发相关问题上的解决方案,深入讨论了SQL Server 2005中新增的T-SQL编程特性,包含了大量的代码示例、表示例和逻辑难题以帮助数据库开发人员和管理员理解...
TTY232的DB-25端还配有跳线子用于选择接收电流环的性质:1-2短接(2-3断开)时接收的电流环有电流表示“1”(无电流表示“0”)、2-3短接(1-2断开)时接收的电流环无电流表示“1”(有电流表示“0”)。TTY232接收...
上架时间:2000-7-1 出版日期:2000 年4月 页码:423 版次:1-1 所属分类:计算机 > 计算机网络 > 网络协议 > TCP/IP 教材 > 研究生/本科/专科教材 > 工学 > 计算机 教材 > 计算机教材 > 本科/研究生 > 计算机专业...
图的创建完成,该图的邻接表表示为: 0:1-->1-->2-->NULL 1:2-->0-->3-->4-->NULL 2:3-->0-->5-->6-->NULL 3:4-->1-->7-->NULL 4:5-->7-->1-->NULL 5:6-->2--&...
2.1 自然语言表述到数学表示的转换27 2.1.1 严格定义(well-Definedness)28 2.1.2 相等、恒等和同一性30 2.1.3 数学命名约定30 2.1.4 数字31 2.1.5 上下文32 2.1.6 函数、参数和变量33 2.1.7 指令和算法34 ...
1.2 源代码表示 1 1.2.1 将拥塞窗口设置为1 1 1.2.2 印刷约定 2 1.3 历史 2 1.4 应用编程接口 3 1.5 程序示例 4 1.6 系统调用和库函数 6 1.7 网络实现概述 6 1.8 描述符 7 1.9 mbuf与输出处理 11 1.9.1 包含插口地址...
1.2 源代码表示 1 1.2.1 将拥塞窗口设置为1 1 1.2.2 印刷约定 2 1.3 历史 2 1.4 应用编程接口 3 1.5 程序示例 4 1.6 系统调用和库函数 6 1.7 网络实现概述 6 1.8 描述符 7 1.9 mbuf与输出处理 11 1.9.1 包含插口地址...
c++黑白棋子交换游戏(基础算法之分治) #include using namespace std; ... move(7); move(1); } else { move(n); move(2*n-1); mv(n-1); } } int main() { cin>>n; init(n); mv(n); }
JPG-C.exe [-m {1, 2, 3}] [-q {1-7}] [-f | -d | -di] source dest -m 表示压缩存储模式 1:直接覆盖, 2:当前路径重命名, 3:另存路径 -q 压缩品质: 1-7 级 默认为 4. (等级越高大小越大) -f 表示压缩单个图片 -...
1. <s:head/>-----在<head></head>里使用,表示头文件结束 2. <s:hidden></s:hidden>-----隐藏值 I: 1. <s:i18n name=""></s:i18n>-----加载资源包到值堆栈 2. <s:include value=""></s:include>-----包含...
1.收集且精读完成后将“阅读进度”改为“复习0次”,表示进入复习曲线, 间隔1天后才会在“第一次复习”中看到! 2.改为”复习1次“,间隔3天后才会在“第二次复习”中看到 版本V2013[4] 更新时间:2013-05-20 1....
1.css的概述 1.问题 HTML属性修饰有一定局限,是不太便捷 2.css的语法规范 1.使用css样式方式 1.内联样式 行内样式 特点:将css样式定义在HTML标记中 语法: 样式声明:用样式属性和值组成(属性:值;) ...
CruiseYoung提供的带有详细书签的电子书籍目录 ... 深入理解Android:卷I(51CTO网站“2011年度最受读者喜爱的原创IT技术图书”) 基本信息 ... 如有一些需要特别说明的地方,则会用下面的格式表示: ...
1.收集且精读完成后将“阅读进度”改为“复习0次”,表示进入复习曲线, 间隔1天后才会在“第一次复习”中看到! 2.改为”复习1次“,间隔3天后才会在“第二次复习”中看到 版本V2013[4] 更新时间:2013-05-20 1....
用JAVA写的一个将正则表达式转换为NFA的代码,基于Thompson算法的思想,递归构建NFA。jar为源码文件。...如正则表达式: c(a|b)NFA为:0-c->1-ep->2-a->3-ep->7 ,0-c->1-ep->4-b->5-ep->7.其中 ep 表示 epsilon
1. 光标不能恢复系统默认的 2. 按Esc键/或右键进行第二次截图时,字体大小不对,颜色板显示不对 3. 一个提示错误,谢 climbfeng@smth # 发行版本: 1.2.0 发行日期: 2011-08-25 + 增加 全面改写‘截图...
离散标记的无向连通图是问题的合适表示,其中样本可以通过各个部分(顶点)及其关系(边)来表示。 图形增强在化学分子分类方面特别成功。 虽然图增强也可以用于回归,但此程序包未实现回归器。 作者 Sebastian ...
超级集版本:表示版本X.YY.ZZzzz符号,表示 0.36.0 0.35.0、0.35.1 0.34.0、0.34.0rc1 最新的0.32.0rc2 0.29.0rc8、0.29.0rc7、0.29.0rc5、0.29.0rc4 0.28.1、0.28.0 后端数据库:MySQL SqlLabs查询异步模式...
1. 光标不能恢复系统默认的 2. 按Esc键/或右键进行第二次截图时,字体大小不对,颜色板显示不对 3. 一个提示错误,谢 climbfeng@smth # 发行版本: 1.2.0 发行日期: 2011-08-25 + 增加 全面改写‘截图...