Java实现无向图的示例详解

目录
  • 基本概念
    • 图的定义
    • 无向图的定义
  • 无向图的 API
  • 无向图的实现方式
    • 邻接矩阵
    • 边的数组
    • 邻接表数组
  • 无向图的遍历
    • 深度优先搜索
    • 广度优先搜索
  • 后记

基本概念

图的定义

一个图是由点集V={vi} 和 VV 中元素的无序对的一个集合E={ek} 所构成的二元组,记为G=(V,E),V中的元素vi叫做顶点,E中的元素 ek叫做边。

对于V中的两个点 u,v,如果边(u,v) 属于E,则称 u,v两点相邻,u,v称为边(u,v)的端点。

我们可以用m(G)=|E| 表示图G中的边数,用n(G)=|V|表示图G中的顶点个数。

无向图的定义

对于E中的任意一条边(vi,vj),如果边(vi,vj) 端点无序,则它是无向边,此时图G称为无向图。无向图是最简单的图模型,下图显示了同一幅无向图,顶点使用圆圈表示,边则是顶点之间的连线,没有箭头(图片来自于《算法第四版》):

无向图的 API

对于一幅无向图,我们关心图的顶点数、边数、每个顶点的相邻顶点和边的添加操作,所以接口如下所示:

package com.zhiyiyo.graph;

/**
 * 无向图
 */
public interface Graph {
    /**
     * 返回图中的顶点数
     */
    int V();

    /**
     * 返回图中的边数
     */
    int E();

    /**
     * 向图中添加一条边
     * @param v 顶点 v
     * @param w 顶点 w
     */
    void addEdge(int v, int w);

    /**
     * 返回所有相邻顶点
     * @param v 顶点 v
     * @return 所有相邻顶点
     */
    Iterable<Integer> adj(int v);
}

无向图的实现方式

邻接矩阵

用矩阵表示图对研究图的性质及应用常常是比较方便的,对于各种图有各种矩阵表示方式,比如权矩阵和邻接矩阵,这里我们只关注邻接矩阵。它的定义为:

对于图G=(V,E),|V|=n,构造一个矩阵 A=(aij)n×n,其中:

则称矩阵A为图G的邻接矩阵。

由定义可知,我们可以使用一个二维的布尔数组 A 来实现邻接矩阵,当 A[i][j] = true 时说明顶点 i 和 j 相邻。

对于 n个顶点的图 G,邻接矩阵需要消耗的空间为 n2个布尔值的大小,对于稀疏图来说会造成很大的浪费,当顶点数很大时所消耗的空间会是个天文数字。同时当图比较特殊,存在自环以及平行边时,邻接矩阵的表示方式是无能为力的。《算法》中给出了存在这两种情况的图:

边的数组

对于无向图,我们可以实现一个类 Edge,里面只用两个实例变量用来存储两个顶点 u和 v,接着在一个数组里面保存所有 Edge 即可。这样做有一个很大的问题,就是在获取顶点 v的所有相邻顶点时必须遍历整个数组才能得到,时间复杂度是O(|E|),由于获取相邻顶点是很常用的操作,所以这种表示方式也不太行。

邻接表数组

如果我们把顶点表示为一个整数,取值范围为0∼|V|−1,那么就可以用一个长度为|V| 的数组的索引表示每一个顶点,然后将每一个数组元素设置为一个链表,上面挂载着索引所代表的的顶点相邻的其他顶点。图一所示的无向图可以用下图所示的邻接表数组表示出来:

使用邻接表实现无向图的代码如下所示,由于邻接表数组中的每个链表都会保存与顶点相邻的顶点,所以将边添加到图中时需要对数组中的两个链表进行添加节点的操作:

package com.zhiyiyo.graph;

import com.zhiyiyo.collection.stack.LinkStack;

/**
 * 使用邻接表实现的无向图
 */
public class LinkGraph implements Graph {
    private final int V;
    private int E;
    private LinkStack<Integer>[] adj;

    public LinkGraph(int V) {
        this.V = V;
        adj = (LinkStack<Integer>[]) new LinkStack[V];
        for (int i = 0; i < V; i++) {
            adj[i] = new LinkStack<>();
        }
    }

    @Override
    public int V() {
        return V;
    }

    @Override
    public int E() {
        return E;
    }

    @Override
    public void addEdge(int v, int w) {
        adj[v].push(w);
        adj[w].push(v);
        E++;
    }

    @Override
    public Iterable<Integer> adj(int v) {
        return adj[v];
    }
}

这里用到的栈代码如下所示,栈的实现不是这篇博客的重点,所以这里不做过多解释:

package com.zhiyiyo.collection.stack;

import java.util.EmptyStackException;
import java.util.Iterator;

/**
 * 使用链表实现的堆栈
 */
public class LinkStack<T> {
    private int N;
    private Node first;

    public void push(T item) {
        first = new Node(item, first);
        N++;
    }

    public T pop() throws EmptyStackException {
        if (N == 0) {
            throw new EmptyStackException();
        }

        T item = first.item;
        first = first.next;
        N--;
        return item;
    }

    public int size() {
        return N;
    }

    public boolean isEmpty() {
        return N == 0;
    }

    public Iterator<T> iterator() {
        return new ReverseIterator();
    }

    private class Node {
        T item;
        Node next;

        public Node() {
        }

        public Node(T item, Node next) {
            this.item = item;
            this.next = next;
        }
    }

    private class ReverseIterator implements Iterator<T> {
        private Node node = first;

        @Override
        public boolean hasNext() {
            return node != null;
        }

        @Override
        public T next() {
            T item = node.item;
            node = node.next;
            return item;
        }

        @Override
        public void remove() {
        }
    }
}

无向图的遍历

给定下面一幅图,现在要求找到每个顶点到顶点 0 的路径,该如何实现?或者简单点,给定顶点 0 和 4,要求判断从顶点 0 开始走,能否到达顶点 4,该如何实现?这就要用到两种图的遍历方式:深度优先搜索和广度优先搜索。

在介绍这两种遍历方式之前,先给出解决上述问题需要实现的 API:

package com.zhiyiyo.graph;

public interface Search {
    /**
     * 起点 s 和 顶点 v 之间是否连通
     * @param v 顶点 v
     * @return 是否连通
     */
    boolean connected(int v);

    /**
     * 返回与顶点 s 相连通的顶点个数(包括 s)
     */
    int count();

    /**
     * 是否存在从起点 s 到顶点 v 的路径
     * @param v 顶点 v
     * @return 是否存在路径
     */
    boolean hasPathTo(int v);

    /**
     * 从起点 s 到顶点 v 的路径,不存在则返回 null
     * @param v 顶点 v
     * @return 路径
     */
    Iterable<Integer> pathTo(int v);
}

深度优先搜索

深度优先搜索的思想类似树的先序遍历。我们从顶点 0 开始,将它的相邻顶点 2、1、5 加到栈中。接着弹出栈顶的顶点 2,将它相邻的顶点 0、1、3、4 添加到栈中,但是写到这你就会发现一个问题:顶点 0 和 1明明已经在栈中了,如果还把他们加到栈中,那这个栈岂不是永远不会变回空。所以还需要维护一个数组 boolean[] marked,当我们将一个顶点 i 添加到栈中时,就将 marked[i] 置为 true,这样下次要想将顶点 加入栈中时,就得先检查一个 marked[i] 是否为 true,如果为 true 就不用再添加了。重复栈顶节点的弹出和节点相邻节点的入栈操作,直到栈为空,我们就完成了顶点 0 可达的所有顶点的遍历。

为了记录每个顶点到顶点 0 的路径,我们还需要一个数组 int[] edgeTo。每当我们访问到顶点 u 并将其一个相邻顶点 i 压入栈中时,就将 edgeTo[i] 设置为 u,说明要想从顶点i 到达顶点 0,需要先回退顶点 u,接着再从顶点 edgeTo[u] 处获取下一步要回退的顶点直至找到顶点 0。

package com.zhiyiyo.graph;

import com.zhiyiyo.collection.stack.LinkStack;
import com.zhiyiyo.collection.stack.Stack;

public class DepthFirstSearch implements Search {
    private boolean[] marked;
    private int[] edgeTo;
    private Graph graph;
    private int s;
    private int N;

    public DepthFirstSearch(Graph graph, int s) {
        this.graph = graph;
        this.s = s;
        marked = new boolean[graph.V()];
        edgeTo = new int[graph.V()];
        dfs();
    }

    /**
     * 递归实现的深度优先搜索
     *
     * @param v 顶点 v
     */
    private void dfs(int v) {
        marked[v] = true;
        N++;
        for (int i : graph.adj(v)) {
            if (!marked[i]) {
                edgeTo[i] = v;
                dfs(i);
            }
        }
    }

    /**
     * 堆栈实现的深度优先搜索
     */
    private void dfs() {
        Stack<Integer> vertexes = new LinkStack<>();
        vertexes.push(s);
        marked[s] = true;

        while (!vertexes.isEmpty()) {
            Integer v = vertexes.pop();
            N++;

            // 将所有相邻顶点加到堆栈中
            for (Integer i : graph.adj(v)) {
                if (!marked[i]) {
                    edgeTo[i] = v;
                    marked[i] = true;
                    vertexes.push(i);
                }
            }
        }
    }

    @Override
    public boolean connected(int v) {
        return marked[v];
    }

    @Override
    public int count() {
        return N;
    }

    @Override
    public boolean hasPathTo(int v) {
        return connected(v);
    }

    @Override
    public Iterable<Integer> pathTo(int v) {
        if (!hasPathTo(v)) return null;
        Stack<Integer> path = new LinkStack<>();

        int vertex = v;
        while (vertex != s) {
            path.push(vertex);
            vertex = edgeTo[vertex];
        }

        path.push(s);
        return path;
    }
}

广度优先搜索

广度优先搜索的思想类似树的层序遍历。与深度优先搜索不同,从顶点 0 出发,广度优先搜索会先处理完所有与顶点 0 相邻的顶点 2、1、5 后,才会接着处理顶点 2、1、5 的相邻顶点。这个搜索过程就是一圈一圈往外扩展、越走越远的过程,所以可以用来获取顶点 0 到其他节点的最短路径。只要将深度优先搜索中的堆换成队列,就能实现广度优先搜索:

package com.zhiyiyo.graph;

import com.zhiyiyo.collection.queue.LinkQueue;

public class BreadthFirstSearch implements Search {
    private boolean[] marked;
    private int[] edgeTo;
    private Graph graph;
    private int s;
    private int N;

    public BreadthFirstSearch(Graph graph, int s) {
        this.graph = graph;
        this.s = s;
        marked = new boolean[graph.V()];
        edgeTo = new int[graph.V()];
        bfs();
    }

    private void bfs() {
        LinkQueue<Integer> queue = new LinkQueue<>();
        marked[s] = true;
        queue.enqueue(s);

        while (!queue.isEmpty()) {
            int v = queue.dequeue();
            N++;

            for (Integer i : graph.adj(v)) {
                if (!marked[i]) {
                    edgeTo[i] = v;
                    marked[i] = true;
                    queue.enqueue(i);
                }
            }
        }
    }
}

队列的实现代码如下:

package com.zhiyiyo.collection.queue;

import java.util.EmptyStackException;

public class LinkQueue<T> {
    private int N;
    private Node first;
    private Node last;

    public void enqueue(T item) {
        Node node = new Node(item, null);
        if (++N == 1) {
            first = node;
        } else {
            last.next = node;
        }
        last = node;
    }

    public T dequeue() throws EmptyStackException {
        if (N == 0) {
            throw new EmptyStackException();
        }

        T item = first.item;
        first = first.next;
        if (--N == 0) {
            last = null;
        }
        return item;
    }

    public int size() {
        return N;
    }

    public boolean isEmpty() {
        return N == 0;
    }

    private class Node {
        T item;
        Node next;

        public Node() {
        }

        public Node(T item, Node next) {
            this.item = item;
            this.next = next;
        }
    }
}

后记

这样就简要介绍完了无向图的实现及遍历方式,对于无向图的更多操作,比如寻找环和判断是否为二分图可以参见《算法第四版》,以上~~

到此这篇关于Java实现无向图的示例详解的文章就介绍到这了,更多相关Java无向图内容请搜索我们以前的文章或继续浏览下面的相关文章希望大家以后多多支持我们!

(0)

相关推荐

  • 带你了解Java数据结构和算法之无权无向图

    目录 1.图的定义 ①.邻接: ②.路径: ③.连通图和非连通图: ④.有向图和无向图: ⑤.有权图和无权图: 2.在程序中表示图 ①.顶点: ②.边: 3.搜索 ①.深度优先搜索(DFS) ②.广度优先搜索(BFS) ③.程序实现 4.最小生成树 5.总结 1.图的定义 我们知道,前面讨论的数据结构都有一个框架,而这个框架是由相应的算法实现的,比如二叉树搜索树,左子树上所有结点的值均小于它的根结点的值,右子树所有结点的值均大于它的根节点的值,类似这种形状使得它容易搜索数据和插入数据,树的边表示

  • 邻接表无向图的Java语言实现完整源码

    邻接表无向图的介绍 邻接表无向图是指通过邻接表表示的无向图. 上面的图G1包含了"A,B,C,D,E,F,G"共7个顶点,而且包含了"(A,C),(A,D),(A,F),(B,C),(C,D),(E,G),(F,G)"共7条边. 上图右边的矩阵是G1在内存中的邻接表示意图.每一个顶点都包含一条链表,该链表记录了"该顶点的邻接点的序号".例如,第2个顶点(顶点C)包含的链表所包含的节点的数据分别是"0,1,3":而这"

  • java搜索无向图中两点之间所有路径的算法

    参考 java查找无向连通图中两点间所有路径的算法,对代码进行了部分修改,并编写了测试用例. 算法要求: 1. 在一个无向连通图中求出两个给定点之间的所有路径: 2. 在所得路径上不能含有环路或重复的点: 算法思想描述: 1. 整理节点间的关系,为每个节点建立一个集合,该集合中保存所有与该节点直接相连的节点(不包括该节点自身): 2. 定义两点一个为起始节点,另一个为终点,求解两者之间的所有路径的问题可以被分解为如下所述的子问题:对每一 个与起始节点直接相连的节点,求解它到终点的所有路径(路径上

  • java编程无向图结构的存储及DFS操作代码详解

    图的概念 图是算法中是树的拓展,树是从上向下的数据结构,结点都有一个父结点(根结点除外),从上向下排列.而图没有了父子结点的概念,图中的结点都是平等关系,结果更加复杂. 无向图                                                       有向图 图G=(V,E),其中V代表顶点Vertex,E代表边edge,一条边就是一个定点对(u,v),其中(u,v)∈V. 这两天遇到一个关于图的算法,在网上找了很久没有找到java版的关于数据结构中图的存储及其

  • Java实现无向图的示例详解

    目录 基本概念 图的定义 无向图的定义 无向图的 API 无向图的实现方式 邻接矩阵 边的数组 邻接表数组 无向图的遍历 深度优先搜索 广度优先搜索 后记 基本概念 图的定义 一个图是由点集V={vi} 和 VV 中元素的无序对的一个集合E={ek} 所构成的二元组,记为G=(V,E),V中的元素vi叫做顶点,E中的元素 ek叫做边. 对于V中的两个点 u,v,如果边(u,v) 属于E,则称 u,v两点相邻,u,v称为边(u,v)的端点. 我们可以用m(G)=|E| 表示图G中的边数,用n(G)

  • Java反射框架Reflections示例详解

    MAVEN 坐标 <dependency> <groupId>org.reflections</groupId> <artifactId>reflections</artifactId> <version>0.9.10</version> </dependency> Reflections 的作用 Reflections通过扫描classpath,索引元数据,并且允许在运行时查询这些元数据. 获取某个类型的所有

  • Java设计模式之单例模式示例详解

    目录 0.概述 1.饿汉式 1.1 饿汉式单例实现 1.2 破坏单例的几种情况 1.3 预防单例的破坏 2.枚举饿汉式 2.1 枚举单例实现 2.2 破坏单例 3.懒汉式 4.双检锁懒汉式 5.内部类懒汉式 6.JDK中单例的体现 0.概述 为什么要使用单例模式? 在我们的系统中,有一些对象其实我们只需要一个,比如说:线程池.缓存.对话框.注册表.日志对象.充当打印机.显卡等设备驱动程序的对象.事实上,这一类对象只能有一个实例,如果制造出多个实例就可能会导致一些问题的产生,比如:程序的行为异常.

  • java基础之注解示例详解

    目录 定义 作用 注解与注释的区别 JDK内置的标准注解 自定义注解 @Target 属性 定义 注解也叫原数据,它是JDK1.5及之后版本引入的一个特性,它可以声明在类.方法.变量等前面,用来对这些元素进行说明. 作用 生成文档:通过代码里标识的注解生成doc文档[生成doc文档] 代码分析:通过代码里标识的注解对代码进行分析[反射] 编译检查:通过代码里标识的注解让编译器能够实现基本的编译检查[Override] 注解与注释的区别 注解是给编译器看的,注释是给程序员看的. JDK内置的标准注

  • Java代理模式的示例详解

    目录 定义 案例 需求 方案:静态代理模式 总结 定义 代理模式(Proxy Parttern) 为一个对象提供一个替身,来控制这个对象的访问,即通过代理对象来访问目标对象,这样做的话好处是可以在目标对象实现的基础上,进行额外的功能的扩展. 案例 需求 苹果公司通过苹果代理商来卖手机 方案:静态代理模式 定义抽象接口类,该类在代理模式中扮演的是一个抽象功能的角色,该案例中就是把出售手机抽象为了一个接口 /** * 售卖手机的接口(代理模式--抽象角色) * @author:liyajie * @

  • Java动态代理的示例详解

    目录 定义 分类 案例 需求 方案一:jdk动态代理 方案二:cglib动态代理 分析 总结 定义 动态代理指的是,代理类和目标类的关系在程序运行的时候确定的,客户通过代理类来调用目标对象的方法,是在程序运行时根据需要动态的创建目标类的代理对象. 分类 jdk动态代理 cglib动态代理 案例 需求 苹果公司通过苹果代理商来卖手机 方案一:jdk动态代理 定义抽象接口 /** * 售卖手机的接口(代理模式--抽象角色) * @author:liyajie * @createTime:2022/2

  • Java Stream流语法示例详解

    目录 如何使用Stream? Stream的操作分类 1.创建流 2.操作流 1)过滤 2)映射 3)匹配 4)组合 3.转换流 如何使用Stream? 聚合操作是Java 8针对集合类,使编程更为便利的方式,可以与Lambda表达式一起使用,达到更加简洁的目的. 前面例子中,对聚合操作的使用可以归结为3个部分: 1)  创建Stream:通过stream()方法,取得集合对象的数据集. 2)  Intermediate:通过一系列中间(Intermediate)方法,对数据集进行过滤.检索等数

  • Java HttpClient用法的示例详解

    目录 1.导入依赖 2.使用工具类 3.扩展 1.导入依赖 <dependency> <groupId>org.apache.httpcomponents</groupId> <artifactId>httpclient</artifactId> <version>4.5.3</version> </dependency> <dependency> <groupId>com.alibab

  • Java实现FutureTask的示例详解

    目录 前言 FutureTask 自己实现FutureTask 工具准备 FutureTask设计与实现 总结 前言 在并发编程当中我们最常见的需求就是启动一个线程执行一个函数去完成我们的需求,而在这种需求当中,我们常常需要函数有返回值.比如我们需要同一个非常大的数组当中数据的和,让每一个线程求某一个区间内部的和,最终将这些和加起来,那么每个线程都需要返回对应区间的和.而在Java当中给我们提供了这种机制,去实现这一个效果——FutureTask. FutureTask 在自己写FutureTa

  • Go&java算法之最大数示例详解

    目录 最大数 方法一:排序(java) 方法一:排序(go) 最大数 给定一组非负整数 nums,重新排列每个数的顺序(每个数不可拆分)使之组成一个最大的整数. 注意:输出结果可能非常大,所以你需要返回一个字符串而不是整数. 示例 1: 输入:nums = [10,2] 输出:"210" 示例 2: 输入:nums = [3,30,34,5,9] 输出:"9534330" 提示: 1 <= nums.length <= 100 0 <= nums[

随机推荐