`
iluoxuan
  • 浏览: 569160 次
  • 性别: Icon_minigender_1
  • 来自: 北京
社区版块
存档分类
最新评论

7: 图-1 图表示

 
阅读更多

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;
    }
}

 

 

 

 

分享到:
评论

相关推荐

    Microsoft SQL Server 2008技术内幕:T-SQL查询(第二卷)

    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 集合论 ...

    Microsoft SQL Server 2005技术内幕: T-SQ程序设计.pdf

    该书解释并比较了SQL Server 2000和SQL Server 2005在数据库开发相关问题上的解决方案,深入讨论了SQL Server 2005中新增的T-SQL编程特性,包含了大量的代码示例、表示例和逻辑难题以帮助数据库开发人员和管理员理解...

    TTY232---480元:RS-232/电流环转换器.PDF

    TTY232的DB-25端还配有跳线子用于选择接收电流环的性质:1-2短接(2-3断开)时接收的电流环有电流表示“1”(无电流表示“0”)、2-3短接(1-2断开)时接收的电流环无电流表示“1”(有电流表示“0”)。TTY232接收...

    TCP/IP详解 卷1:协议--源代码

    上架时间:2000-7-1 出版日期:2000 年4月 页码:423 版次:1-1 所属分类:计算机 &gt; 计算机网络 &gt; 网络协议 &gt; TCP/IP 教材 &gt; 研究生/本科/专科教材 &gt; 工学 &gt; 计算机 教材 &gt; 计算机教材 &gt; 本科/研究生 &gt; 计算机专业...

    数据结构——图的两种实现办法及两种遍历

    图的创建完成,该图的邻接表表示为: 0:1--&gt;1--&gt;2--&gt;NULL 1:2--&gt;0--&gt;3--&gt;4--&gt;NULL 2:3--&gt;0--&gt;5--&gt;6--&gt;NULL 3:4--&gt;1--&gt;7--&gt;NULL 4:5--&gt;7--&gt;1--&gt;NULL 5:6--&gt;2--&...

    Microsoft+SQL+Server+2008技术内幕:T-SQL查询_源代码及附录 中文版

    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 ...

    本资源分为两个压缩包,请注意:TCP-IP详解卷2:实现(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 包含插口地址...

    本资源分为两个压缩包,请注意:TCP-IP详解卷2:实现(2)

    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++代码之黑白棋子交换游戏

    c++黑白棋子交换游戏(基础算法之分治) #include using namespace std; ... move(7); move(1); } else { move(n); move(2*n-1); mv(n-1); } } int main() { cin&gt;&gt;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 表示压缩单个图片 -...

    struts2 标签库 帮助文档

    1. &lt;s:head/&gt;-----在&lt;head&gt;&lt;/head&gt;里使用,表示头文件结束 2. &lt;s:hidden&gt;&lt;/s:hidden&gt;-----隐藏值 I: 1. &lt;s:i18n name=""&gt;&lt;/s:i18n&gt;-----加载资源包到值堆栈 2. &lt;s:include value=""&gt;&lt;/s:include&gt;-----包含...

    针式PinPKM-V201506(免费无使用限制)

    1.收集且精读完成后将“阅读进度”改为“复习0次”,表示进入复习曲线, 间隔1天后才会在“第一次复习”中看到! 2.改为”复习1次“,间隔3天后才会在“第二次复习”中看到 版本V2013[4] 更新时间:2013-05-20 1....

    css入门笔记

    1.css的概述 1.问题 HTML属性修饰有一定局限,是不太便捷 2.css的语法规范 1.使用css样式方式 1.内联样式 行内样式 特点:将css样式定义在HTML标记中 语法: 样式声明:用样式属性和值组成(属性:值;) ...

    深入理解Android:卷I--详细书签版

    CruiseYoung提供的带有详细书签的电子书籍目录 ... 深入理解Android:卷I(51CTO网站“2011年度最受读者喜爱的原创IT技术图书”) 基本信息 ... 如有一些需要特别说明的地方,则会用下面的格式表示:  ...

    PinPKM-V201525(官网发布的最后一个免费无使用限制版本)

    1.收集且精读完成后将“阅读进度”改为“复习0次”,表示进入复习曲线, 间隔1天后才会在“第一次复习”中看到! 2.改为”复习1次“,间隔3天后才会在“第二次复习”中看到 版本V2013[4] 更新时间:2013-05-20 1....

    正则表达式转换为NFA(Regex to NFA).jar

    用JAVA写的一个将正则表达式转换为NFA的代码,基于Thompson算法的思想,递归构建NFA。jar为源码文件。...如正则表达式: c(a|b)NFA为:0-c-&gt;1-ep-&gt;2-a-&gt;3-ep-&gt;7 ,0-c-&gt;1-ep-&gt;4-b-&gt;5-ep-&gt;7.其中 ep 表示 epsilon

    Live Capture1.2.4

    1. 光标不能恢复系统默认的 2. 按Esc键/或右键进行第二次截图时,字体大小不对,颜色板显示不对 3. 一个提示错误,谢 climbfeng@smth # 发行版本: 1.2.0 发行日期: 2011-08-25 + 增加 全面改写‘截图...

    matlabauc代码-gboost-0.1.1:gboost-0.1.1

    离散标记的无向连通图是问题的合适表示,其中样本可以通过各个部分(顶点)及其关系(边)来表示。 图形增强在化学分子分类方面特别成功。 虽然图增强也可以用于回归,但此程序包未实现回归器。 作者 Sebastian ...

    docker-superset:Apache-Superset的Docker映像的存储库。 [Docker镜像:https:hub.docker.comrabhioncbrdocker-superset]

    超级集版本:表示版本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查询异步模式...

    Live Capture

    1. 光标不能恢复系统默认的 2. 按Esc键/或右键进行第二次截图时,字体大小不对,颜色板显示不对 3. 一个提示错误,谢 climbfeng@smth # 发行版本: 1.2.0 发行日期: 2011-08-25 + 增加 全面改写‘截图...

Global site tag (gtag.js) - Google Analytics