LearnJava
  • Summary
    • Introduction
    • MyResume
  • 开发
    • 小程序
      • 小程序开发问题总结
      • 小程序bug
    • 环境搭建
      • Linux搭建git服务器
      • Linux切换JDK版本
      • Mac搭建http服务器
      • Ubuntu搭建C++开发环境
      • ProtoBuffer安装
      • Ubuntu开启Telnet
      • Linux搭建邮件服务器
    • 遇到的问题
      • Mac下eclipse问题
      • Mac下Github问题
      • Markdown解决方案实例
      • Spring问题
  • 编程语言
    • C++
      • C&C++框架汇总
      • C++Primer课后习题记录
      • C++疑问
      • C++与java的异同
      • C++内存模型
      • C++知识点
      • Make和Cmake
    • GO
      • Go语言简介
      • Go语言知识点
    • XML
      • XML知识点
  • 技术学习
    • JavaIO
      • AIO通信
      • IO和NIO
      • 阻塞式IO通信
      • 非阻塞式IO通信
    • 计算机网络
      • CDN
      • HTTPS协议入门
      • HTTP_POST请求的数据格式
      • HTTP错误码和出现场景
      • HTTP协议入门
      • TCP/IP协议入门
      • Wireshark抓包
      • 域名解析过程
    • 计算机原理
      • 整型计算
      • GPU
      • Swap内存
    • 架构学习
      • 分布式锁
      • 分布式系统的CAP理论
      • IaaS,PaaS,SaaS的区别
      • Web框架
      • 康威定律
      • 秒杀系统设计
      • 数据异构
      • 微服务架构入门
      • 协程
      • MQ推拉模式对比
      • UML图
      • 缓存穿透击穿和雪崩
    • 前端学习
      • 安装使用VUE
      • 搭建VUE项目
    • 大数据
      • Hadoop之HBASE
      • Hadoop之HDFS
      • Hadoop之MapReduce
      • Hadoop简介
    • 数据结构
      • 二叉树
      • 图
      • 跳表
      • Bitmap
    • 算法
      • 排序算法
        • 插入排序
        • 归并排序
        • 计数排序
        • 快速排序
        • 冒泡排序
        • 选择排序
      • Hash算法
      • MD5介绍
      • 一致性Hash算法
      • 数字全排列
      • MD5介绍
      • 储水量
      • 最大子序列
    • Java多线程
      • AQS原理
      • AtomicInteger原理
      • Condition
      • Fork/Join框架
      • happens-before
      • Java锁优化
      • Java线程池
      • Java中的阻塞队列
      • Java实现线程的三种方式
      • Lock
      • Lock的种类
      • ThreadLocal
      • 线程状态及其转换
    • Java设计模式
      • Builder模式
      • 代理模式
      • 工厂和抽象工厂模式
      • 观察者模式
      • 设计模式概述
      • 职责链模式
      • 装饰者模式
      • Java实现单例的5种方式
    • Java学习
      • Java拓展学习
        • JavaSPI
      • Java序列化
      • Java异常
      • Java注解
      • 学习UML图
      • Java的Lambda表达式
      • Java集合之ArrayList
      • Java集合之HashMap
      • Java集合之LinkedList
      • List⤅&Set的操作和遍历
      • JavaP反编译命令
      • Servlet学习
    • JVM学习
      • 分层编译
      • Java进程内存占用
      • JVM参数
      • JVM常用工具
      • JVM的内存模型
      • 垃圾回收机制
      • 看懂gc日志
      • 类加载机制和双亲委派模型
      • 类的反射
      • 自己动手编译OPENJDK
      • ASM字节码增强技术
      • CodeCache
      • GC耗时案例
      • JVM性能调优
    • Linux学习
      • gdb调试定位
      • Linux常用命令
      • Linux工具
      • Linux进程通信的方式
      • Linux文件系统结构
      • Linux系统知识点
      • Linux小技巧
      • Shell学习
      • Vim常用命令
    • Java设计模式
      • 设计模式概述
      • 代理模式
      • 装饰者模式
    • Mysql
      • InnoDB介绍
      • Mac_mysql问题
      • mysql之group_concat函数
      • mysql事务
      • Mysql优化
      • Mysql实用命令
      • mysql慢查询
      • mysql文件
      • mysql视图
      • mysql锁
      • mysql索引
      • mysql约束
      • 存储过程和触发器
      • mysql常用语法
    • Spring
      • SpringCloud
        • 搭建Jenkins自动部署
        • SpringCloud介绍
        • SpringCloudBus
        • SpringCloudConfig
        • SpringCloudEureka
        • SpringCloudFeign
        • SpringCloudHystrix
        • SpringCloudRibbon
        • SpringCloudSleuth
        • SpringCloudStream
        • SpringCloudZuul
      • FactoryBean理解
      • MyBatis入门介绍
      • rose框架学习
      • SpringMVC的启动流程
      • SpringBean的生命周期
      • SpringBoot入门
      • Spring入门AOP和IOC
      • SpringMVC入门笔记
      • SpringMVC集成Log4j2
      • web.xml详解
    • web中间件学习
      • Redis
        • Redis入门
        • Redis持久化
        • Redis的数据类型
        • Redis特性
      • Gremlin入门
      • Elasticsearch安装使用
      • HugeGraph入门
      • jetty介绍
      • Kafka介绍使用
      • Maven安装配置
      • Netty介绍使用
      • Netty的编解码
      • Maven的pom介绍
      • Nginx介绍
      • Nginx配置详解
      • ProtocolBuffers学习笔记
      • Resin学习
      • RESTful入门
      • RocketMQ入门
      • RPC入门
      • Thrift介绍
      • Tomcat常用配置
      • Tomcat学习
      • Tomcat实现
      • zookeeper入门
      • Zookerper选举原理
  • 文档读后感
    • 除了写代码你还会干什么
  • 效率提升
    • Java诊断工具Arthas
    • Mac下安装多版本java
    • Mac下显示git分支
    • Mac中Clion快捷键
    • Mac中Eclipse快捷键
    • MacShell常用快捷键
    • PlantUML入门
    • Windows与Linux服务器传文件
    • Sublime技巧
    • 搜索引擎检索技巧
  • 总结
    • 2017工作总结
Powered by GitBook
On this page
  • 1. 简介
  • 2. 相关概念
  • 3. 图的存储
  • 4. 代码实例

Was this helpful?

  1. 技术学习
  2. 数据结构

图

Previous二叉树Next跳表

Last updated 4 years ago

Was this helpful?

1. 简介

图结构也是一种非线性数据结构。生活中有很多图结构的例子,比如通信网络、交通网络、人际关系网络等都可以归结为图结构。图结构的每个节点可以互相关联,比树结构更加复杂

下图就是一个简单的图结构:

2. 相关概念

  • 1.有向图

  • 2. 无向图

  • 3. 顶点的度:连接顶点的边的数量称为该顶点的度。在有向图中又分为入度和出度。

  • 4. 邻接顶点:指一条边的两个顶点。在有向图中分为入边邻接顶点和出边邻接顶点。

  • 5. 无向完全图:每两个顶点之间就有一条边。

  • 6. 有向完全图:每两个顶点之间存在方向相反的两条边。对于一个N个节点的有向完全图,边数为N(N-1),是无向完全图的两倍。

  • 7. 子图:类似子集合,子图的顶点和边都是原图的。

  • 8. 路径:两个顶点之间的连线,可以有多条,每条长度可能不一样。路径又可以分为三种形式:

    • 简单路径:一条路径上的顶点不重复出现;

    • 环:路径的第一个顶点和最后一个顶点相同叫做环,有时也成回路;

    • 简单回路:路径的第一个顶点和最后一个顶点相同,其余顶点不重复的叫做简单回路。

  • 9. 连通、连通图和连通分量:

    • 如果两个顶点之间有路径,那么这两个顶点是连通的;

    • 无向图中任意两个顶点都是连通的,称为连通图;

    • 无向图中极大连通子图称为连通分量。

    连通图的连通分量有且仅有一个,就是它本身。

  • 10. 强连通图和强连通分量:

    • 如果两个顶点之间有路径,那么这两个顶点是连通的,注意,因为有向,有时可能是Vi -> Vj是连通的,Vj -> Vi不是连通的;

    • 如果有向图中任意两个顶点都是连通的,那么就是强连通图;

    • 有向图的最大强连通子图称为该图的强连通分量。

    强连通图的强连通分量有且仅有一个,就是它本身。

  • 11. 权:在边上表示的数值,这个数值就是该边的权。无向图中加入权值称为无向带权图,有向图中加入权值称为有向带权图。权在生活中可以表示交通图中道路的长度,人际关系中代表亲密度等。

  • 12. 网(network):即边上带有权值的图的另一个名称,网与实际应用更为贴切。

3. 图的存储

在实际应用中,通常使用数组来单独保存顶点信息,然后采用二维数组保存顶点之间的关系。这种保存顶点之间关系的数组称为邻接矩阵。

char[] Vertex = new char[MaxNum];  //保存顶点信息
int[][] EdgeWeight = new int[MaxNum][MaxNum];  //保存边

这张无向图的边就可以这样表示

Vertex[0] = 1;
Vertex[1] = 2;
Vertex[2] = 3;
Vertex[3] = 4;
Vertex[5] = 5;

边通过EdgeWeight二维数组表示,有边的话存1,没有的话存0。比如1和2之间的表可以表示为:

//数组下角标从0开始的
EdgeWeight[0][1] = 1;
EdgeWeight[1][0] = 1;

这个图的邻接矩阵:

0

1

1

0

1

1

0

0

1

0

1

0

0

0

1

0

1

0

0

1

1

0

1

1

0

因为是无向图,所以左下和右上是对称的,有向图就不是了。

4. 代码实例

接下来用一个代码实例来看下树的结构初始化,清空以及输出遍历操作:

package com.wangjun.datastructure;

public class GraphTest {
    private final int MaxNum = 5; // 最大顶点数

    public static void main(String[] args) {
        GraphTest gt = new GraphTest();
        GraphMatrix gm = gt.new GraphMatrix();
        gt.createGraph(gm);
        gt.outGraph(gm);
        gt.deepTraGraph(gm);
    }


    // 定义邻接矩阵结构
    class GraphMatrix {
        char[] Vertex = new char[MaxNum]; // 保存顶点信息,数字或者字母
        int GType; // 类型,0:无向图,1:有向图
        int vertexNum; // 顶点的数量
        int EdgeNum; // 边的数量
        int[][] EdgeWeight = new int[MaxNum][MaxNum]; // 保存边的权
        int[] isTrav = new int[MaxNum]; // 遍历标志
    }

    // 创建邻接矩阵图
    // 这里创建手动创建一个5节点的图,对应上面的图
    public void createGraph(GraphMatrix gm) {
        gm.Vertex[0] = '1';
        gm.Vertex[1] = '2';
        gm.Vertex[2] = '3';
        gm.Vertex[3] = '4';
        gm.Vertex[4] = '5';

        gm.GType = 0;
        gm.vertexNum = 5;
        gm.EdgeNum = 6;
        gm.EdgeWeight[0][1] = 1;
        gm.EdgeWeight[1][0] = 1;
        gm.EdgeWeight[0][2] = 1;
        gm.EdgeWeight[2][0] = 1;
        gm.EdgeWeight[0][4] = 1;
        gm.EdgeWeight[4][0] = 1;
        gm.EdgeWeight[2][4] = 1;
        gm.EdgeWeight[4][2] = 1;
        gm.EdgeWeight[1][3] = 1;
        gm.EdgeWeight[3][1] = 1;
        gm.EdgeWeight[3][4] = 1;
        gm.EdgeWeight[4][3] = 1;
    }

    // 清空图
    public void clearGraph(GraphMatrix gm) {
        for (int i = 0; i < MaxNum; i++) {
            for (int j = 0; i < MaxNum; j++) {
                gm.EdgeWeight[i][j] = 0;
            }
        }
    }

    // 显示图,即显示邻接矩阵
    public void outGraph(GraphMatrix gm) {
        // 输出顶点信息
        System.out.println("顶点:");
        for (int i = 0; i < MaxNum; i++) {
            System.out.print(gm.Vertex[i] + "  ");
        }
        System.out.println();
        // 输出边的信息
        System.out.println("边:");
        for (int i = 0; i < MaxNum; i++) {
            for (int j = 0; j < MaxNum; j++) {
                System.out.print(gm.EdgeWeight[i][j] + "  ");
            }
            System.out.println();
        }
    }

    /*
     * 遍历图,即逐个访问图的顶点,使用isTrav数组标志该节点是否被遍历过 
     * 常用的遍历图方法:广度优先遍历法和深度优先遍历法 此函数以深度优先遍历法为例
     * 深度遍历法类似于树的先序遍历,具体执行过程如下: 
     * 1)从isTrav数组中选择一个未被访问的顶点Vi,将其标记为1,表示已访问过
     * 2)从Vi的一个未被访问过的邻接点出发进行深度优先遍历 
     * 3)重复步骤2),直至图中所有和Vi有路径相通的顶点都被访问过
     * 4)重复步骤1)至3)的操作,直至图中所有的顶点都被访问过 
     * 深度优先遍历法是一个递归过程
     */
    public void deepTraGraph(GraphMatrix gm) {
        // 清除顶点访问标志
        for (int i = 0; i < gm.vertexNum; i++) {
            gm.isTrav[i] = 0;
        }
        System.out.println("深度优先遍历节点:");
        for (int i = 0; i < gm.vertexNum; i++) {
            // 若该节点未遍历
            if (gm.isTrav[i] == 0) {
                deepTraOne(gm, i);// 调用函数遍历
            }
        }
    }

    //深度遍历的执行函数
    public void deepTraOne(GraphMatrix gm, int n) {
        // 从第n个节点开始,深度遍历图
        gm.isTrav[n] = 1;
        // 输出节点数据
        System.out.println("node:" + gm.Vertex[n] + "  ");

        // 添加处理节点的操作
        for (int i = 0; i < gm.vertexNum; i++) {
            if (gm.EdgeWeight[n][i] != 0 && gm.isTrav[i] == 0) {
                deepTraOne(gm, i);// 递归进行遍历
            }
        }
    }

}