文档章节

图的基础知识(二、存储)

 大胖和二胖
发布于 2016/11/30 11:55
字数 866
阅读 15
收藏 2

图需要存储的信息有以下这些

1、顶点信息

2、边或弧的信息,如果有权,也需要表示出来

3、顶点个数、边(弧)的个数

 

邻接矩阵及其实现

顶点数据存储:

一维数组

边(弧)信息存储

邻接矩阵

图中n个顶点之间相邻关系的n阶矩阵(即二维数组a[n][n])

下面举例说明

无向图邻接矩阵,中间斜着的一条线上的0,代表的意义是同一顶点,其余部分,1代表2顶点之间有边,0代表无边。

无向网邻接矩阵,中间斜着的一条线上的0,代表的意义是同一顶点,其余部分,用一个大于所有边的权值的值来表示没有没有边,具体的值表示边上的权值。

有向图邻接矩阵,有几个特点,不一定对称,行方向上的非0元素的个数意味着该顶点的出度,列方向上的非0元素的个数意味着该顶点的入度。

 

邻接矩阵法的优点:

容易实现图的操作,如:求某顶点的度、判断顶点之间是否有边(弧)、找顶点的邻接点

邻接矩阵法的缺点:

n个顶点,需要n*n个单元存储边(弧),空间效率为O(n2),

对于稀疏图的话,尤其浪费空间

 

图的java定义,图当中顶点类型为int,然后有4个顶点,6条边(弧),该定义既可以表示有向图,也可以表示无向图,同时也可以表示有整形权的网。

public class Graph {
    int vn;
    int en;
    int[] vex;
    int[][] arc;
    
    public static void main(String[] args){
        Graph graph = new Graph();
        graph.vn = 10;
        graph.en = 20;
        graph.vex = new int[graph.vn];
        graph.arc = new int[graph.vn][graph.vn];
    }
}

 

建图运算,我们设置了1,2,3,4一共四个顶点,然后,在所有不同顶点之间画上了边,其实这里我们就是做了一个完全图(至于是有向还是无向,全看你怎么理解和使用了)

        for (int i = 1; i <= 4; i ++){
            graph.vex[i - 1] = i;
        }

        for (int i = 1; i <= 4; i ++){
            for (int j = 1; j <= 4; j ++) {
                graph.arc[i - 1][j - 1] = i == j ? 0 : 1;
            }
        }

 

邻接表及其实现

是顺序与链接相结合的图的存储方式

所有顶点组成一个数组,为每个顶点建立一个单向链表

下面还是举例说明

无向图邻接表

无向网邻接表,增加了每一条边的权值信息

有向图邻接表

邻接表的优点:

空间效率高;容易寻找顶点的邻接点

邻接表的缺点:

对于有向图而言,查询顶点的出度很容易,但是要查询入度,就需要遍历整个表。

 

邻接表的java定义,这里我们跟前面的概念部分有所不同,不过问题不大,需要注意的是,如果是网的存储的话,这样的做法就不行了,可能需要针对边,再做一个类。

public class GraphWithLink {
    Vex[] vex;
    List<Vex> arc = new LinkedList<Vex>();
    int vn;
    int en;
}

public class Vex {
    int i;
}

建图运算,我们还是建一个4个顶点的完全图

    public static void main(String[] args){
        GraphWithLink graph = new GraphWithLink();
        graph.vn = 4;
        graph.en = 6;
        graph.vex = new Vex[graph.vn];
        for (int i = 1; i <= 4; i ++){
            Vex vex = new Vex();
            vex.i = i;
            graph.vex[i - 1] = vex;
        }

        for (int i = 1; i <= 4; i++) {
            graph.arc.add(graph.vex[i - 1]);
            for (int j = 1; j <= 4; j++) {
                if (i != j){
                    graph.arc.add(graph.vex[j - 1]);
                }
            }
        }
    }

 

 

 

 

 

 

 

© 著作权归作者所有

共有 人打赏支持
粉丝 21
博文 69
码字总数 50842
作品 0
沈阳
架构师
Android技能树 — 树基础知识小结(一)

前言: 现在安卓面试,对于数据结构的问题也越来越多了,也经常看到别人发的面试题都是问什么红黑树,二叉树查找等,所以我们虽然不会马上就会各种难的面试题,但起码树的基础知识还是要会的...

青蛙要fly
05/04
0
0
【python数据挖掘课程】十七.社交网络Networkx库分析人物关系(初识篇)

这是《Python数据挖掘课程》系列文章,也是我大数据金融学院上课的部分内容。本章主要讲述复杂网络或社交网络基础知识,通过Networkx扩展包绘制人物关系,并分析了班级学生的关系学院信息。本...

Eastmount
2017/11/05
0
0
[python爬虫] 招聘信息定时系统 (一).BeautifulSoup爬取信息并存储MySQL

这系列文章主要讲述,如何通过Python爬取招聘信息,且爬取的日期为当前天的,同时将爬取的内容保存到数据库中,然后制作定时系统每天执行爬取,最后是Python调用相关库发送短信到手机。 最近...

Eastmount
2017/04/22
0
0
【python数据挖掘课程】十五.Matplotlib调用imshow()函数绘制热图

前面系列文章讲过数据挖掘的各种知识,最近在研究人类时空动力学分析和幂率定律,发现在人类兴趣转移模型中,可以通过热图(斑图)来进行描述的兴趣转移,如下图所示。下一篇文章将简单普及人...

Eastmount
2017/06/20
0
0
系统的学习大数据分布式计算spark技术

我们在学习一门技术的时候一定要以系统的思维去学习,这样的话,不仅对你的提高有很大的帮助,也可以让你高效的使用这个技术。 对于学习spark,当然也是要以系统的思维去全面的学习。这篇博客...

tangweiqun
2017/09/24
0
0

没有更多内容

加载失败,请刷新页面

加载更多

下一页

【七】组合Action

本章描述了常用定义Action的方法。 自定义action builders 我们在action一章已经看过如何声明一个action——有request parameter、无request parameter、有body parser等等。你可以在 asynch...

Landas
25分钟前
0
0
Spring Boot实战之基础回顾

本文作者: 吴伟祥 本文链接: https://wuweixiang.cn/2018/08/21/Spring-Boot实战之基础回顾/ 版权声明: 本博客所有文章除特别声明外均为原创,采用CC BY-NC-SA 4.0 许可协议。转载请在文章开...

吴伟祥
25分钟前
0
0
OAuth认证开发

提示: 以下测试是基于项目安装成功,初始化数据库(initial_db.ddl, oauth.ddl, initial_data.ddl)后的测试, 也可在页面上点击"client_details"菜单里进行测试 方式1:基于浏览器 (grant_type=...

舒文joven
33分钟前
1
0
第二章-对象及变量的并发访问-第二篇

锁对象的改变 请阅读如下代码 public class MainClass { private String lock = "123"; public void printStringB() { try { synchronized (lock) { ......

简心
37分钟前
0
0
日志中记录代理IP以及真实客户端、apache只记录指定URI的日志

apache 日志中记录代理IP以及真实客户端 默认情况下log日志格式为: LogFormat "%h %l %u %t "%r" %>s %b "%{Referer}i" "%{User-Agent}i"" combined 其中%h 是记录访问者的IP,如果在web的前...

李超小牛子
46分钟前
0
0

没有更多内容

加载失败,请刷新页面

加载更多

下一页

返回顶部
顶部