数据结构(十九) -- 图

作者: 峰峰小 | 来源:发表于2016-11-07 00:49 被阅读252次

一，概述

弥诺陶洛斯（Minotaur）是希腊神话中半人半牛的怪物，它藏身于一个精心设计的迷宫之中。这个迷宫的结构极其复杂，一般人一旦进入其中，都休想走出来。不过，在公主阿里阿德涅（Ariadne）的帮助下，古希腊英雄特修斯（Theseus）还是想出了一个走出迷宫的方法。特修斯带上一团线去闯迷宫，在入口处，他将绳线的一头绑在门上。然后，他不断查找迷宫的各个角落，而绳线的另一头则始终抓在他的手里，跟随他穿梭于蜿蜒曲折的迷宫之中。借助如此简单的工具，特修斯不仅终于找到了怪物并将其杀死，而且还带着公主轻松地走出了迷宫。

特修斯之所以能够成功，关键在于他借助绳线来掌握迷宫内各个通道之间的联接关系，而在很多的问题中，掌握类似的信息都是至关重要的。通常，这类信息所反映的都是一组对象之间的二元关系，比如城市交通图中联接于不同点之间的街道，或 Internet 中联接于两个 IP 之间的路由等。

在某种程度上，我们前面所讨论过的树结构也可以携带和表示这种二元关系，只不过树结构中的这类关系仅限于父、子节点之间。然而在一般情况下，我们所需要的二元关系往往是定义在任意一对对象之间。实际上，这样的二元关系恰恰正是图论（Graph theory ）

** 图（Graph）可以表示为 G = (V, E)：**

其中集合 V 中的对象称作顶点（Vertex）；
而集合 E 中的每一元素都对应于 V 中某一对顶点⎯⎯说明这两个顶点之间存在某种关系⎯⎯称作边（Edge）。

这里还约定 V 和 E 都是有限集，通常记 n = |V|、m = |E|。

二，无向图、混合图及有向图

图中的边可以是没有方向的，也可以是有方向的。

如果边 e = (u, v)所对应的顶点 u 和 v 不是对等的，或者存在某种次序，就称 e 为有向边（Directed edge）。

如果 u 和 v 的次序无所谓，e 就是一条无向边（Undirected edge）。

注意：无向边(u, v)也可以记作(v, u)，而有向边(u, v)和(v, u)则是不同的两条边。

（a）无向图（b）混合图（c）有向图

顶点v的关联边的总数，称为v的度数（Degree），记作deg(v)。以（a）为例，有deg(a) = deg(c) = 3。

v 出边总数称作v的出度（Out-degree），记作outdeg(v)；
v入边总数称作v的入度（In-degree），记作indeg(v)。
以（c）为例，有outdeg(a) = indeg(a) = outdeg(c) = indeg(c) =3。

图中所含的边并不见得能构成一个集合（Set），准确地说它们构成了一个复集（Multiset）⎯⎯其中允许出现重复的元素。

比如，若在某对顶点之间有多条无向边，或者两条有向边的起点和终点
完全一样，就属于这种情况。这类重复的边也称作平行边（Parallel e dges）或多重边（Multiple edges）。例如，要是用顶点表示城市，用边表示城市之间的飞机航线，则有可能在某一对城市之间存在多条航线；如果用顶点表示演员，则某两位演员合演过的影片很有可能不止一部。

无论是无向图还是有向图，还有另一种特殊情况：与某条边关联的是同一个顶点（如上图中的顶点a）⎯⎯这样的边称作** 自环（Self-loop）**。

不含上述特殊边的图，称作简单图（Simple graph）。对简单图而言，其中的边必然构成一个集合，而且每条边只能联接于不同的顶点之间。本文我们讨论的图都限于简单图。

三，通路、环路及可达分量

通路——所谓图中的一条通路或路径（Path），就是由（不一定互异的）m+1 个顶点与 m 条边交替构成的一个序列ρ = {v 0 , e 1 , v 1 , e 2 , v 2 , …, e m , v m }，m ≥ 0，而且 e i = (v i-1 , v i )，1 ≤ i ≤ m。

环路—— 长度 m ≥ 1 的路径，若第一个顶点与最后一个顶点相同，则称之为环路（Cycle）。

可达分量——对于指定的顶点 s，从 s 可达的所有顶点所组成的集合，称作 s 在 G 中对应的可达分量，记作 V r (G, s)。

四，树、森林和连通图

无向图 G = (V, E)：

若 G 中不含任何环路，则称之为森林（Forest）。

连通的森林称作树（Tree）。

不难看出，森林中的每一连通分量都是一棵树，反之亦然。

设 G 为由 n 个顶点与 m 条边组成一幅无向图：

（1）若 G 是连通的，则 m ≥ n-1；

（2）若 G 是一棵树，则 m = n-1；

（3）若 G 是森林，则 m ≤ n-1。

五，图 ADT

（这里以有向图为例介绍图结构及其算法）
作为一种抽象数据类型，有向图必须支持以下操作：

操作方法	功能描述
vNumber()	返回顶点集 V 的规模
eNumber()	返回边集 E 的规模
vertices()	返回所有顶点的迭代器
vPositions()	返回所有顶点位置的迭代器
edges()	返回所有边的迭代器
ePositions()	返回所有边位置的迭代器
areAdjacent(u, v)	判断顶点 u 和 v 是否相邻
remove(v)	将顶点 v 从顶点集中删除，并返回之
insert(v)	在顶点集 V 中插入新顶点 v，并返回其位置
insert(e)	在边集 E 中插入新边 e，并返回其位置

六，图的实现

** 基于邻接矩阵（Adjacency matrix）的图的实现 **

图 ADT 有多种实现方式，其中最直接的就是基于邻接矩阵（Adjacency matrix）的实现。

若图 G 中包含 n 个顶点，我们就使用一个 n×n 的方阵 A，并使每一顶点都分别对应于某一行（列）。

既然图所描述的是这些顶点各自对应的元素之间的二元关系，故可以很自然地将任意一对元素 u 和 v 之间可能存在二元关系与矩阵 A 中对应的单元 A[u, v]对应起来：
1 或 true 表示存在关系，0 或 false 表示不存在关系。

这一矩阵中的各个单元分别描述了一对元素之间可能存在的邻接关系，故此得名。

以上基于邻接矩阵的实现方法直观易懂、思路简明，而且能够高效地实现图的大多数 ADT 操作。

但是矩阵结构是静态的，通常都是事先估计一个较大的整数 N，然后创建一个 N×N 的矩阵。

然而，图的规模往往都是动态变化的，因此如果 N 不是足够大，极有可能出现因空间“不足”而无法加入新顶点的情况⎯⎯而实际上，此时系统并非没有更多空间可以提供。为了降低这种情况发生的概率，必须选用足够大的 N，而如此一来，单元闲置的程度也将加剧。

** 邻接表 **

由上面的分析可知，邻接矩阵的空间效率之所以低，是因为其中大量的单元所对应的边有可能并未在图中出现，这也是静态向量结构普遍的不足。

既然如此，为什么不将向量改进为列表呢？实际上，按照这一思路的确可以导出图结构的另一种表示与实现形式——邻接表（Adjacency list）。

基于列表实现的顶点与边的结构：

** 具体由以下3个接口和对应的3个类实现：**

（有向）图的顶点结构接口：

package dsa.Graph;

import dsa.Iterator.Iterator;
import other.Position;

public interface Vertex {

    /*
     * （有向）图的顶点结构接口
     */
    // 常量
    final static int UNDISCOVERED = 0;// 尚未被发现的顶点
    final static int DISCOVERED = 1;// 已被发现的顶点
    final static int VISITED = 2;// 已访问过的顶点
    // 返回当前顶点的信息

    public Object getInfo();

    // 将当前顶点的信息更新为x，并返回原先的信息
    public Object setInfo(Object x);

    // 返回当前顶点的出、入度
    public int outDeg();

    public int inDeg();

    // 返回当前顶点所有关联边、关联边位置的迭代器
    public Iterator inEdges();

    public Iterator inEdgePositions();

    public Iterator outEdges();

    public Iterator outEdgePositions();

    // 取当前顶点在所属的图的顶点集V中的位置
    public Position getVPosInV();

    // 读取、设置顶点的状态（DFS + BFS）
    public int getStatus();

    public int setStatus(int s);

    // 读取、设置顶点的时间标签（DFS）
    public int getDStamp();

    public int setDStamp(int s);

    public int getFStamp();

    public int setFStamp(int s);

    // 读取、设置顶点至起点的最短距离（BFS或BestFS）
    public int getDistance();

    public int setDistance(int s);

    // 读取、设置顶点在的DFS、BFS、BestFS或MST树中的父亲
    public Vertex getBFSParent();

    public Vertex setBFSParent(Vertex s);
}

（有向）图的边结构接口

package dsa.Graph;

import other.Position;

public interface Edge {

    /*
     * （有向）图的边结构接口
     */
    // 常量
    final static int UNKNOWN = 0;// 未知边
    final static int TREE = 1;// 树边
    final static int CROSS = 2;// 横跨边
    final static int FORWARD = 3;// 前向跨边
    final static int BACKWARD = 4;// 后向跨边
    // 返回当前边的信息（对于带权图，也就是各边的权重）

    public Object getInfo();

    // 将当前边的信息更新为x，并返回原先的信息
    public Object setInfo(Object x);

    // 取当前边在所属的图的边集E中的位置
    public Position getEPosInE();

    // 取v[i]在顶点集V中的位置（i=0或1，分别对应于起点、终点）
    public Position getVPosInV(int i);

    // 当前边在其两个端点的关联边集I(v[i])中的位置
    public Position getEPosInI(int i);

    // 读取、设置边的类别（针对遍历）
    public int getType();

    public int setType(int t);
}

（有向）图结构接口

package dsa.Graph;

import dsa.Iterator.Iterator;
import other.Position;

public interface Graph {

    /*
     * （有向）图结构接口 
     */

    // 取图中顶点、边的数目
    public int vNumber();

    public int eNumber();

    // 取图中所有顶点、顶点位置的迭代器
    public Iterator vertices();

    public Iterator vPositions();

    // 返回图中所有边、边位置的迭代器
    public Iterator edges();

    public Iterator ePositions();

    // 检测是否有某条边从顶点u指向v
    public boolean areAdjacent(Vertex u, Vertex v);

    // 取从顶点u指向v的边，若不存在，则返回null
    public Edge edgeFromTo(Vertex u, Vertex v);

    // 将顶点v从顶点集中删除，并返回之
    public Vertex remove(Vertex v);

    // 将边e从边集中删除，并返回之
    public Edge remove(Edge e);

    // 在顶点集V中插入新顶点v，并返回其位置
    public Position insert(Vertex v);

    // 在边集E中插入新边e，并返回其位置
    public Position insert(Edge e);
}

基于邻接边表实现图的顶点结构

package dsa.Graph;

import dsa.Iterator.Iterator;
import dsa.List.List;
import dsa.List.List_DLNode;
import other.Position;

public class Vertex_List implements Vertex {

    /*
     * 基于邻接边表实现图的顶点结构
     */

    // 变量
    protected Object info;// 当前顶点中存放的数据元素
    protected Position vPosInV;// 当前顶点在所属的图的顶点表V中的位置
    protected List outEdges;// 关联边表：存放以当前顶点为尾的所有边（的位置）
    protected List inEdges;// 关联边表：存放以当前顶点为头的所有边（的位置）
    protected int status;// （在遍历图等操作过程中）顶点的状态
    protected int dStamp;// 时间标签：DFS过程中该顶点被发现时的时刻
    protected int fStamp;// 时间标签：DFS过程中该顶点被访问结束时的时刻
    protected int distance;// 到指定起点的距离：BFS、Dijkstra等算法所确定该顶点到起点的距离
    protected Vertex bfsParent;// 在最短距离树（BFS或BestFS）中的父亲
    // 构造方法：在图G中引入一个属性为x的新顶点

    public Vertex_List(Graph G, Object x) {
        info = x;// 数据元素
        vPosInV = G.insert(this);// 当前顶点在所属的图的顶点表V中的位置
        outEdges = new List_DLNode();// 出边表
        inEdges = new List_DLNode();// 入边表
        status = UNDISCOVERED;
        dStamp = fStamp = Integer.MAX_VALUE;
        distance = Integer.MAX_VALUE;
        bfsParent = null;
    }

    // 返回当前顶点的信息
    public Object getInfo() {
        return info;
    }

    // 将当前顶点的信息更新为x，并返回原先的信息
    public Object setInfo(Object x) {
        Object e = info;
        info = x;
        return e;
    }

    // 返回当前顶点的出、入度
    public int outDeg() {
        return outEdges.getSize();
    }

    public int inDeg() {
        return inEdges.getSize();
    }

    // 返回当前顶点所有关联边、关联边位置的迭代器
    public Iterator inEdges() {
        return inEdges.elements();
    }

    public Iterator inEdgePositions() {
        return inEdges.positions();
    }

    public Iterator outEdges() {
        return outEdges.elements();
    }

    public Iterator outEdgePositions() {
        return outEdges.positions();
    }

    // 取当前顶点在所属的图的顶点集V中的位置
    public Position getVPosInV() {
        return vPosInV;
    }

    // 读取、设置顶点的状态（DFS + BFS）
    public int getStatus() {
        return status;
    }

    public int setStatus(int s) {
        int ss = status;
        status = s;
        return ss;
    }

    // 读取、设置顶点的时间标签（DFS）
    public int getDStamp() {
        return dStamp;
    }

    public int setDStamp(int s) {
        int ss = dStamp;
        dStamp = s;
        return ss;
    }

    public int getFStamp() {
        return fStamp;
    }

    public int setFStamp(int s) {
        int ss = fStamp;
        fStamp = s;
        return ss;
    }

    // 读取、设置顶点至起点的最短距离（BFS）
    public int getDistance() {
        return distance;
    }

    public int setDistance(int s) {
        int ss = distance;
        distance = s;
        return ss;
    }

    // 读取、设置顶点在的DFS、BFS、BestFS或MST树中的父亲
    public Vertex getBFSParent() {
        return bfsParent;
    }

    public Vertex setBFSParent(Vertex s) {
        Vertex ss = bfsParent;
        bfsParent = s;
        return ss;
    }
}

基于邻接边表实现图的边结构

package dsa.Graph;

import dsa.Deque.DLNode;
import other.Position;

public class Edge_List implements Edge {

    /*
     * 基于邻接边表实现图的边结构
     */

    // 变量
    protected Object info;// 当前边中存放的数据元素
    protected Position ePosInE;// 当前边在所属的图的边表中的位置
    protected Position vPosInV[];// 当前边两个端点在顶点表中的位置
    protected Position ePosInI[];// 当前边在其两个端点的关联边表中的位置
    // 约定：第0（1）个顶点分别为尾（头）顶点
    // 禁止头、尾顶点相同的边
    protected int type;// （经过遍历之后）边被归入的类别
    // 构造方法：在图G中，生成一条从顶点u到v的新边（假定该边尚不存在）

    public Edge_List(Graph G, Vertex_List u, Vertex_List v, Object x) {
        info = x;// 数据元素
        ePosInE = G.insert(this);// 当前边在所属的图的边表中的位置
        vPosInV = new DLNode[2];// 当前边两个端点在顶点表中的位置
        vPosInV[0] = u.getVPosInV();
        vPosInV[1] = v.getVPosInV();
        ePosInI = new DLNode[2];// 当前边在其两个端点的关联边表中的位置
        ePosInI[0] = u.outEdges.insertLast(this);// 当前边加入u的邻接（出）边表
        ePosInI[1] = v.inEdges.insertLast(this);// 当前边加入v的邻接（入）边表
        type = UNKNOWN;
    }

    // 返回当前边的信息
    public Object getInfo() {
        return info;
    }

    // 将当前边的信息更新为x，并返回原先的信息
    public Object setInfo(Object x) {
        Object e = info;
        info = x;
        return e;
    }

    // 取当前边在所属的图的边集E中的位置
    public Position getEPosInE() {
        return ePosInE;
    }

    // 取v[i]在顶点集V中的位置（i=0或1，分别对应于起点、终点）
    public Position getVPosInV(int i) {
        return vPosInV[i];
    }

    // 当前边在其两个端点的关联边集I(v[i])中的位置
    public Position getEPosInI(int i) {
        return ePosInI[i];
    }

    // 读取、设置边的类别（针对遍历）
    public int getType() {
        return type;
    }

    public int setType(int t) {
        int tt = type;
        type = t;
        return tt;
    }
}

基于邻接边表实现图结构

package dsa.Graph;

import dsa.Iterator.Iterator;
import dsa.List.List;
import dsa.List.List_DLNode;
import other.Position;

public class Graph_List implements Graph {
    /*
     * 基于邻接边表实现图结构
     */
    // 变量
    protected List E;// 容器：存放图中所有边
    protected List V;// 容器：存放图中所有顶点
    // 构造方法

    public Graph_List() {
        E = new List_DLNode();
        V = new List_DLNode();
    }

    // 取图的边表、顶点表
    protected List getE() {
        return E;
    }

    protected List getV() {
        return V;
    }

    // 取图中顶点、边的数目
    public int vNumber() {
        return V.getSize();
    }

    public int eNumber() {
        return E.getSize();
    }

    // 取图中所有顶点、顶点位置的迭代器
    public Iterator vertices() {
        return V.elements();
    }

    public Iterator vPositions() {
        return V.positions();
    }

    // 返回图中所有边、边位置的迭代器
    public Iterator edges() {
        return E.elements();
    }

    public Iterator ePositions() {
        return E.positions();
    }

    // 检测是否有某条边从顶点u指向v
    public boolean areAdjacent(Vertex u, Vertex v) {
        return (null != edgeFromTo(u, v));
    }

    // 取从顶点u指向v的边，若不存在，则返回null
    public Edge edgeFromTo(Vertex u, Vertex v) {
        for (Iterator it = u.outEdges(); it.hasNext();) {// 逐一检查
            Edge e = (Edge) it.getNext();// 以u为尾的每一条边e
            if (v == e.getVPosInV(1).getElem())// 若e是(u, v)，则
                return e;// 返回该边
        }
        return null;// 若不存在这样的(u, v)，则返回null
    }

    // 将顶点v从顶点集中删除，并返回之
    public Vertex remove(Vertex v) {
        while (0 < v.outDeg())// 将以v为尾的所有边
            remove((Edge) (((Vertex_List) v).outEdges.first()).getElem());// 逐一删除
        while (0 < v.inDeg())// 将以v为头的所有边
            remove((Edge) (((Vertex_List) v).inEdges.first()).getElem());// 逐一删除
        return (Vertex) V.remove(v.getVPosInV());// 在顶点表中删除v
    }

    // 将边e从边集中删除，并返回之
    public Edge remove(Edge e) {
        ((Vertex_List) e.getVPosInV(0).getElem()).outEdges.remove(e.getEPosInI(0));// 从起点的出边表中删除e
        ((Vertex_List) e.getVPosInV(1).getElem()).inEdges.remove(e.getEPosInI(1));// 从终点的入边表中删除e
        return (Edge) E.remove(e.getEPosInE());// 从边表中删除e
    }

    // 在顶点集V中插入新顶点v，并返回其位置
    public Position insert(Vertex v) {
        return V.insertLast(v);
    }

    // 在边集E中插入新边e，并返回其位置
    public Position insert(Edge e) {
        return E.insertLast(e);
    }
}

这里主要涉及三个算法，具体分析如下：

判断任意一对顶点是否相邻

算法：areAdjacent(u, v)
输入：一对顶点u和v
输出：判断是否有某条边从顶点u指向v
{
取顶点u的出边迭代器it;
通过it逐一检查u的每一条出边e;
一旦e的终点为v，则报告true;
若e的所有出边都已检查过，则返回false;
}

删除边

算法：RemoveEdge(e)
输入：边e = (u, v)
输出：将边e从边集E中删除
{
从起点u的出边邻接表中删除e;
从终点v的入边邻接表中删除e;
从边表E中删除e;
}

删除顶点

算法：removeVertex(v)
输入：顶点v
输出：将顶点v从顶点集V中删除
{
扫描v的出边邻接表，（调用removeEdge()算法）将所有边逐一删除;
扫描v的入边邻接表，（调用removeEdge()算法）将所有边逐一删除;
在顶点表V中删除v;
}

数据结构(十九) -- 图

一，概述

二，无向图、混合图及有向图

三，通路、环路及可达分量

四，树、森林和连通图

五，图 ADT

六，图的实现

相关文章

网友评论

延伸阅读

深度阅读

栏目导航

热点阅读