文档章节

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

 大胖和二胖
发布于 2016/11/30 11:55
字数 866
阅读 20
收藏 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]);
                }
            }
        }
    }

 

 

 

 

 

 

 

© 著作权归作者所有

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

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

青蛙要fly
05/04
0
0
[Python图像处理] 一.图像处理基础知识及OpenCV入门函数

版权声明:本文为博主原创文章,转载请注明CSDN博客源地址!共同学习,一起进步~ https://blog.csdn.net/Eastmount/article/details/81748802 该系列文章是讲解Python OpenCV图像处理知识,前...

Eastmount
08/16
0
0
【python数据挖掘课程】十七.社交网络Networkx库分析人物关系(初识篇)

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

Eastmount
2017/11/05
0
0
mybaties源码解析(org.apache.ibatis.type)类型处理器

此模块主要是实现MyBaties数据类型和jdbc中的数据类型的转换 一、TypeHandler接口作为参数转换的基础接口: 1、设定参数函数: void setParameter(PreparedStatement ps, int i, T parameter...

lackiechan
2016/12/12
10
0
[python爬虫] 招聘信息定时系统 (一).BeautifulSoup爬取信息并存储MySQL

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

Eastmount
2017/04/22
0
0

没有更多内容

加载失败,请刷新页面

加载更多

利用cefSharp实现网页自动注册登录的需要注册的一些事项

最近朋友有个需要自动注册登录点击的事,我帮着写了写,好久没写过这东西了,在写的过程中总结了需要注意的一些事项。 一、换IP之后要测试一下速度,我目前用的最简单的测试方法就是20-30秒加...

我退而结网
13分钟前
1
0
Go语言中使用 BoltDB数据库

boltdb 是使用Go语言编写的开源的键值对数据库,Github的地址如下: https://github.com/boltdb/bolt boltdb 存储数据时 key 和 value 都要求是字节数据,此处需要使用到 序列化和反序列化。...

Oo若离oO
13分钟前
1
0
zookeeper分布式锁

//lock 锁 定义分布式锁public interface Lock {//获取锁public void getLock();//释放锁public void unLock();} public abstract class ZookeeperAbstractLock implements Loc......

熊猫你好
21分钟前
0
0
mysql_事务隔离机制

事务隔离机制 事务就是要保证一组数据库操作,要么全部成功,要么全部失败。在mysql中,事务支持是在引擎层实现的。mysql是一个支持多引擎的系统,但并不是所有引擎都支持事务,比如mysql...

grace_233
23分钟前
0
0
不学无数——Java中IO和NIO

JAVA中的I/O和NIO I/O 问题是任何编程语言都无法回避的问题,可以说 I/O 问题是整个人机交互的核心问题,因为 I/O 是机器获取和交换信息的主要渠道。在当今这个数据大爆炸时代,I/O 问题尤其...

不学无数的程序员
29分钟前
0
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部