无向图

微信公众号:Vegout 如有问题或建议,请公众号留言

概念轰炸

  • 是由一组顶点和一组能够将两个顶点连接的组成的
  • x-y表示x到y的一条
  • 一条连接一个顶点和其自身的边称为自环
  • 连接同一对顶点的两条边称为平行边
  • 含有平行边的图称为多重图
  • 某个顶点的度数即为依附于它的边的总数
  • 当两个顶点通过一条边相连时,我们称这两个顶点是相邻的,并称这条边依附于这两个顶点
  • 子图是由一幅图的所有边的一个子集(以及它们所依附的所有顶点)组成的图
  • 如果从任何一个顶点都存在一条路径到达另一个任意顶点,我们称这幅图为连通图
  • 一幅非连通的图由若干连通的部分组成,它们都是它的极大连通子图
  • 二分图是一种能够将所有结点分为两部分的图,也就是说图中每条边连接的两个顶点属于不同的部分

无向图的表示

今天的主角是无向图,顾名思义,无向图就是边没有方向的图。每当一个概念拿到程序中,总是需要抽象出一个数据结构来表示这个概念。那么,图怎么表示呢?表示图的这个数据结构叫做邻接表

这个邻接表表示的就是下面这个图

首先,邻接表使用了一个数组来存放各个顶点,各个顶点又都指向了一个链表,链表里存放了与这个顶点相邻的顶点。1与2、5相邻,于是数组下标为1的元素指向的链表结点中含有2和5,同样数组下标为2和5的元素指向的链表中也一定含有1。当我们对一个图进行操作的时候,其实就是对这个邻接表进行操作。同时我们也可以看到,如果要访问与顶点3相邻的顶点,我们势必会先访问到2,然后是5,最后是9。但是对与顶点3来说,和它相邻的任何一个顶点低位都是相同的,但这个先后顺序却是确定的。所以构造这个图的时候,也就是构造这个邻接表的时候就已经决定了我们操作图中结点时的某些顺序。

对与领接表数组中的元素,本身是一个链表,为了方便操作,我们用一个Bag类来实现这个链表。

public class Bag<Item> implements Iterable<Item>{
    private Node first;
    private class Node{
        Item item;
        Node next;
    }
    public void add(Item item){
        Node oldfirst = first;
        first = new Node();
        first.item=item;
        first.next=oldfirst;
    }
    public Iterator<Item> iterator(){
        return new ListIterator();
    }
    private class ListIterator implements Iterator<Item>{
        private Node current = first;
        public boolean hasNext(){
            return current!=null;
        }
        public Item next(){
            Item item = current.item;
            current=current.next;
            return item;
        }
    }
}

从而我们就可以用这个Bag来构造我们的无向图

public class Graph {
    private final 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 Graph(In in){
        this(in.readInt());
        this.E=in.readInt();
        for (int i=0;i<V;i++){
            int w = in.readInt();
            int v = in.readInt();

        }

    }
    public int V(){
        return V;
    }
    public int E(){
        return E;
    }
    public void addEdge(int v,int w){
        adj[v].add(w);
        adj[w].add(v);
        E++;
    }
    public Iterable<Integer> adj(int v){
        return adj[v];
    }
}

今天主要说一下图的两种搜索方法,深度优先搜索和广度优先搜索。

深度优先搜索(递归)

深度优先搜索就是:一条路走到黑,装了南墙就返回,再找一条路往黑了走。还以上边的图为例,我们从1开始进行深度优先搜索,首先他会先访问1,然后访问1的相邻顶点,于是找到了2(为什么不是5?因为构造邻接表时,2排在了5前边),然后再去找2的相邻顶点,当它开始访问2的相邻顶点的时候,1的相邻顶点其实还没有访问完,这就体现了深度优先,访问过程是一直深入的,直到碰了南墙才会返回。这里的碰了南墙其实就是访问的顶点已经被访问过。

public class DeepFirstSearch {
    private boolean[] marked;
    private int count;//被访问过的结点的个数
    public DeepFirstSearch(Graph g,int s){
        marked = new boolean[g.V()];
        dfs(g,s);
    }
    private void dfs(Graph g,int s){
        marked[s] = true;
        count++;
        for (int v:g.adj(s)
             ) {
            if (!marked[v])dfs(g,v);
        }
    }
    public boolean marked(int v){
        return marked[v];
    }
    public int count(){
        return count;
    }
}

marked这个boolean数组用来记录哪些顶点被访问过,以完成撞南墙检测。深度优先搜索可以用来解决单点路径问题。如:从1到9是否存在一条路径?如果有,找出这条路径。 其实我们只需要改动一点点上边的代码就可以解决这个问题

public class DeepFirstPath {
    private final int s;
    private boolean[] marked;
    private int[] edgeTo;
    public DeepFirstPath(Graph g,int s){
        this.s=s;
        marked = new boolean[g.V()];
        edgeTo = new int[g.V()];

    }
    private void dfs(Graph g,int v){
        marked[v] = true;
        for (int w :
                g.adj(v)) {
            if (!marked[v]){
                edgeTo[w] = v;
                dfs(g,w);
            }
        }
    }
    public boolean hasPathTo(int v){
        return marked[v];
    }
    public Iterable<Integer> pathTo(int v){
        if (!hasPathTo(v))return null;
        Stack<Integer> path = new Stack<>();
        for (int i = v;i!=s;i=edgeTo[i]){
            path.push(i);
        }
        path.push(s);
        return path;
    }
}

我们只是加了一个Int数组edgeTo,这个数组记录了路径的信息。edgeTo[2]=1,表示1-2是第一次访问2时经过的边。通过edgeTo这个数组我们就可以还原出一个路径。除此之外,深度优先搜索还可以找出图中的所有连通分量。

public class CC {
    private boolean[] marked;
    private int[] id;
    private int count;
    public CC(Graph graph){
        marked = new boolean[graph.V()];
        id = new int[graph.V()];
        for (int s = 0;s> graph.V();s++){
            if (!marked[s]){
                dfs(graph,s);
                count++;
            }
        }

    }
    public void dfs(Graph g,int v){
        marked[v] = true;
        id[v] = count;
        for (int w :
                g.adj(v)) {
            if (!marked[w]) dfs(g, w);
        }
    }
    public boolean connected(int v,int w){
        return id[v]==id[w];
    }
    public int id(int v){
        return id[v];
    }
    public int count(){
        return count;
    }
}

在原来一篇文中我们通过union-find算法寻找了连通分量,今天这个深度优先算法一样可以用来寻找连通分量。其中的id数组起到的就是这个作用,如若x和y两个顶点属于一个连通分量,那么id[x]=id[y]。

广度优先搜索

刚才说到深度优先搜索可以找到两个顶点之间的一个路径,但当两个顶点之间有多个路径的时候,我们需要找出最短的那一条时,深度优先搜索就束手无策了。此刻只能我们广度优先搜索出来亮亮相了。广度优先搜索会先搜索最近的顶点(也就是邻接表中的顶点),然后再去搜索最近的顶点的相邻顶点,就像是一个扩散的过程。所以第一次访问到的顶点所经过的边构成的路径一定是最短的路径。广度优先搜索的实现没有使用递归,而是用了一个队列来保存已经被访问过但其领接表还没有被访问的顶点。然后重复以下两步:①取队列中的下一个顶点并标记为已访问。②将和这个顶点相邻的所有未访问的顶点加入队列

public class BreadthFirstPaths {
    private boolean[] marked;
    private final int s;
    private int[] edgeTo;
    public BreadthFirstPaths(Graph g,int s){
        this.s=s;
        marked = new boolean[g.V()];
        edgeTo = new int[g.V()];
    }
    private void bfs(Graph g,int v){
        Queue<Integer> queue = new LinkedBlockingQueue<Integer>();
        marked[v]=true;
        queue.add(v);
        while (!queue.isEmpty()){
            int w = queue.remove();
            for (int ss :
                    g.adj(w)) {
                if (!marked[ss]) {
                edgeTo[ss]=w;
                queue.add(ss);
                }
        }
    }
    }
    public boolean hasPathTo(int v){
        return marked[v];
    }
    public Iterable<Integer> pathTo(int v){
        if (!marked[v]) return null;
        Stack<Integer> path = new Stack<>();
        for (int i=v;i!=s;i=edgeTo[i]){
            path.push(i);
        }
        path.push(s);
        return path;
    }

}

本文分享自微信公众号 - Vegout(t10244201)

原文出处及转载信息见文内详细说明,如有侵权,请联系 yunjia_community@tencent.com 删除。

原始发表时间:2018-09-15

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • Java I/O 概览

    Java IO是Java语言支持输入输出的API,Java IO主要关注文件,网络流,内部存储器缓冲区等的输入和输出。但是,Java IO不包括网络通信套接字的...

    搬砖俱乐部
  • 初识I/O | I/O系列(一)

    I/O设备,包括磁盘、键盘、显示器、各种网络传输设备、及各种驱动程序等。计算机系统参与I/O的外设大体分为三类:

    搬砖俱乐部
  • [WPF自定义控件库]使用WindowChrome自定义RibbonWindow

    自定义Window有可能是设计或功能上的要求,可以是非必要的,而自定义RibbonWindow则不一样:

    dino.c
  • 搜索与回溯算法模板及其应用

    为了求得问题的解,先选择某一种可能情况向前探索,在探索的过程中,一旦发现原来的选择是错误的,就退回一步重新选择,继续向前探索,如此反复进行,直至得到解或证明无解...

    echobingo
  • Activiti工作流引擎数据库表

    Acitiviti数据库中表的命名都是以ACT_开头的。第二部分是一个两个字符用例表的标识。此用例大体与服务API是匹配的。

    秋白
  • 《Spring实战》摘录 - 20

    问题:#11.2.1-4 | Hibernate的JPA适配器支持多种数据库,可以通过其database属性配置使用哪个数据库

    用户1335799
  • 应用层体系结构与协议

    应用层是开放系统的最高层,是直接为应用进程提供服务的,作用是在实现多个系统应用进程互相通信的同时,完成一系列业务处理所需的服务。我们平时使用的应用程序就在这一层...

    搬砖俱乐部
  • 10 行Python 代码,实现 AI 目标检测技术,真给力!

    看完了代码,下面容我们聊聊目标检测背后的技术背景,并解读这10行Python代码的由来和实现原理。

    一墨编程学习
  • 观察者模式(浅谈监听器工作原理)

    从某种角度来说,我们总是处于两种生活状态:观察者与被观察者。当处于观察者状态时,被观察的对象会向我们发出某种信息,使我们产生某种心理活动或行为状态的改变。当我们...

    秋白
  • 强化学习笔记-Python/OpenAI/TensorFlow/ROS-程序指令

    版权声明:本文为zhangrelay原创文章,有错请轻拍,转载请注明,谢谢... https://...

    zhangrelay

扫码关注云+社区

领取腾讯云代金券