图基础知识整理和代码实现
- 介绍图的基本概念和术语。
- 介绍邻接矩阵和邻接表两种图的表示方法。
- 介绍图的广度和深度优先搜索算法。
- 贡献作者自己实现的图通用操作库（Java版）。
1. 概述
1.1 图
所谓的图可定义为G=（V, E）。其中，集合V中的元素称作顶点（vertex）；集合E中的元素称为边（edge），表示顶点（i，j）之间存在某种关系。从计算的需求出发，约定V和E均为有限集，规模分别记为n=|V|和e=|E|。
1.2 无向图、有向图和混合图
若E中各边均无方向，则G称为无向图（undirected graph），例如在描述QQ好友关系的图G中，若小明 i 和小王 j 是好友关系，则他们之间引入一条边（i，j）。反之，若E中含有有向边，则G称为有向图（directed graph）。例如在微博好友关系图中，从顶点 i 指向 j 的有向边，意味着 i 是 j 的粉丝。特别地，若E同时包含有向边和无向边，则G为混合图（mixed graph）。例如在交通图中，有些道路是双行地，另一些是单行地，对应地可分别描述为无向边和有向边。
图1.(a)无向图、(b)混合图和(c)有向图
1.3 度
对于任何边e=(i, j)，称顶点 i 和 j 彼此邻接（adjacent），互为邻居；而它们都与边 e 关联（incident）。在无向图中，与顶点 i 关联地边数，称为 i 地度数（degree），记作deg（i）。以图1(a)为例，顶点{A, B, C, D}地度数分别为{2, 3, 2, 1}。
对于有向边e=(i, j)，e 称作 i 的出边（outgoing edge）、 j 的入边（incoming edge）。 i 的出边总数称作其出度（out-degree），记作outdeg（i）；i 的入边总数称作其入度（in-degree），记作indeg（i）。在图1(c)中，各顶点的出度为{1, 3, 1, 1}，入度为{2, 1, 2, 1}。
1.4 简单图
联接于同一顶点之间的边，称作自环（self-loop）。不含任何自环的图称作简单图（simple graph）。
1.5 通路与环路
所谓通路或者路径（path），就是由m+1个顶点与m条边交替而成的一个序列。图2(a)中的{C, A, B, A, D}，即是从顶点C到顶点D的一条通路，其长度为4。可见，尽管通路上的边必须互异，但顶点却可能重复。沿途顶点互异的通路，称作简单通路，如图2(b)所示，{C, A, D, B}即是从顶点C到B的一条简单通路，其长度为3。
特别地，对于长度m>=1的通路，若起止顶点相同，则称为环路（cycle），其长度等于沿途边的总数。图3(a)中，{C, A, B, D, B, C}即是一条环路，其长度为6。反之，不含任何环路的有向图，称作有向无环图（DAG）。若沿途除开始和结束顶点外所有顶点互异，则称作简单环路（simple cycle），图3(b)中的{C, A, B, C}即是一条简单环路，其长度为3。
特别地，经过图中各边一次且恰好一次的环路，称为欧拉环路（Eulerian tour）——当然，其长度也恰好等于图中边地总数e。图4(a)中的{C, A, B, A, D, C, D, B, C}即是一条欧拉环路，其长度为8。对偶地，经过图中各顶点一次且恰好一次的环路，称为哈密顿环路（Hamiltonlian tour）。图4(b)中，{C, A, D, B, C}即是一条长度为4的哈密顿环路。
图2.通路与简单通路
图3.环路与简单环路
图4.欧拉环路与哈密尔顿环路
总结一下：
通路：由m+1个顶点与m条边交替而成的一个序列，通路上的边必须互异。
简单通路：顶点互异的通路。
环路：起止顶点相同的且长度不小于1的通路。
简单环路：除开始和结束顶点外所有顶点互异的环路。
欧拉环路：经过图中各边一次且恰好一次的环路。
哈密尔顿环路：经过图中各顶点一次且恰好一次的环路。
1.6 带权网络
各边均带有权重（weight）的图，称作带权图（weighted graph）或带权网络（weighted network），有时也简称为网络（network），记作G(V, E, wt())。
2. 图的表示方法
2.1 邻接矩阵
邻接矩阵是图接口的最基本的实现方式，使用方阵A[n][n]表示由n个顶点构成的图，其中每个单元，各自负责描述一对顶点之间可能存在的邻接关系，故此得名。
对于无权图，存在（不存在）从顶点 i 到 j 的边，当且仅当A[i][j]=1(0)。图5(a)和(b)即为无向图和有向图的邻接矩阵实例。这一表示方法，不难推广至带权网络。此时如(c)所示，矩阵各单元可从布尔型改为整型或浮点型，记录所对应表的权重。对于不存在的边，通常统一取值为0或无穷大。
图5.邻接矩阵（空白单元对应的边不存在，其取值统一标注于矩阵最左上角）
2.2 邻接表
以图6(a)所示的无向图为例，只需将如图(b)所示的邻接矩阵，逐行地转化为如图(c)所示地一组列表，即可分别记录各顶点的关联边（或等价地，邻接顶点）。这些列表，也因此称为邻接表（adjacency list）。
图6.以邻接表方式描述和实现图
2.3 两种方式的比较
时间性能
邻矩矩阵优于邻接表
邻接矩阵可以快速判断两个顶点之间是否存在边，可以快速添加边或者删除边。而邻接表在查询某个顶点的边时，需要遍历一整个链表。且对于无向图，如果需要删除一条边，就需要在两个链表上查找并删除。
空间性能
邻接表优于邻矩矩阵
邻接表只存储实际存在的边，非常节省空间。而邻接矩阵通过一个 n∗n 的矩阵存储边的关系，如果顶点之间的边比较少，会比较浪费空间。
3. 两种基本的图遍历算法
3.1 广度优先搜索
广度优先搜索策略可概括为：越早被访问到的顶点，其邻居越优先被选用。
于是，自图中顶点s的BFS搜索，将首先访问顶点s；再依次访问s所有未访问到的邻居；再按后者被访问的先后次序，逐个访问它们的邻居；...；如此不断。在所有已访问到的顶点中，仍有邻居未被访问者，构成所谓的波峰集（frontier）。于是BFS可以等效地理解为：
反复从波峰集中国找到最早被访问到的顶点v，若其邻居均已被访问到，则将其逐出波峰集；否则，随意选出一个尚未访问到的邻居，并将其加入到波峰集中。
图7给出了一个含8个顶点和11条边的有向图，起始于顶点s的BFS搜索过程。请留意观察辅助队列（下方）的演变，顶点状态的变化，边的分类与结果，以及BFS树的生长过程。
图7.广度优先搜索示例
其中，顶点共有三种状态，分别为UNDISCOVERED、DISCOVERED、VISITED，边共有5种状态，分别为UNKNOWN（未知边、TREE（树边）、CROSS（横跨边）、FORWARD（前向跨边）、 BACKWARD（后向跨边）。所有的TREE边构成了BFS树或者BFS森林（当存在多个连通分量时）
3.2 深度优先搜索
深度优先搜索（DFS）选取下一项的策略，可概括为：
优先选取最后一个被访问到的顶点的邻居
于是，以顶点s为基点的DFS搜索，将首先访问顶点s；再从s所有未访问到的邻居种任意选其一，并以之为基点，递归执行DFS搜索。故各顶点被访问到的次序，类似于树的先序遍历；而各顶点被访问完毕的次序，则类似于树的后序遍历。
图8针对含7个顶点和10条边的某有向图，给出了DFS搜索的详细过程。请留意观察顶点时间标签的设置，顶点状态的演变，边的分类和结果，以及DFS树（森林）的生长过程。
图8.深度优先搜索实例
最终结果如图(t)所示，为包含两颗DFS树的DFS森林。可以看出，选不同的起始点，生成的DFS树（森林）可能不同。如本例种，若从D开始搜索，则DFS森林可能如图(u)所示。
图9以时间为横坐标，绘出了图(u)种DFS树内各顶点的活跃期。可以看出，活跃期相互包含的顶点，再DFS树种都是"祖先-后代"的关系（比如B之于C，或者D之于 F），反之亦然。
4 图操作的Java实现
4.1 图的操作接口规范
图的基本操作主要分为边和顶点两类，主要包括查找、增添、删除、判断是否存在、获取顶点（边）的数量。另外，还包括图基本算法，这里只规定了图的广度和深度优先遍历算法，其它算法可以自己另外添加。
package com.whut.DataStructure.graph;
import com.whut.DataStructure.graph.entity.Edge;
import com.whut.DataStructure.graph.entity.Vertex;
/**
* @Auther: 杨赟
* @Date: 2018/10/2 20:25
* @Description: 图的操作接口
*/
public interface Graph<Tv> {
//顶点的操作
int vertexNumber();
boolean exist(Tv vertex);
boolean insert(Tv vertex);
Vertex<Tv> remove(Tv vertex);
Vertex<Tv> find(Tv vertex);
//边的操作
int edgeNumber();
boolean exist(Tv vertex1, Tv vertex2);
boolean insert(Tv vertex1, Tv vertex2, Edge edge);
Edge remove(Tv vertex1, Tv vertex2);
Edge find(Tv vertex1, Tv vertex2);
//图的基本算法
void bfs(Tv vertex, Function<Tv> function);
void dfs(Tv vertex, Function<Tv> function);
}
4.2 顶点和边实体类
顶点类
package com.whut.DataStructure.graph.entity;
/**
* @Auther: 杨赟
* @Date: 2018/10/2 08:45
* @Description: 顶点
*/
public class Vertex<Tv> {
private Tv data; //顶点包含的数据
private int inDegree, outDegree; //入度和出度
private VStatus status;//顶点状态
private int dTime, fTime;//时间标签
private int parent;//父顶点位置
private int priority;//优先级，用于优先级搜索
public Vertex(Tv data) {
this.data = data;
this.inDegree = 0;
this.outDegree = 0;
this.status = VStatus.UNDISCOVERED;
this.dTime = -1;
this.fTime = -1;
this.parent = -1;
this.priority = Integer.MAX_VALUE;
}
public Tv getData() {
return data;
}
public void setData(Tv data) {
this.data = data;
}
public int getInDegree() {
return inDegree;
}
public void setInDegree(int inDegree) {
this.inDegree = inDegree;
}
public int getOutDegree() {
return outDegree;
}
public void setOutDegree(int outDegree) {
this.outDegree = outDegree;
}
public VStatus getStatus() {
return status;
}
public void setStatus(VStatus status) {
this.status = status;
}
public int getdTime() {
return dTime;
}
public void setdTime(int dTime) {
this.dTime = dTime;
}
public int getfTime() {
return fTime;
}
public void setfTime(int fTime) {
this.fTime = fTime;
}
public int getParent() {
return parent;
}
public void setParent(int parent) {
this.parent = parent;
}
public int getPriority() {
return priority;
}
public void setPriority(int priority) {
this.priority = priority;
}
@Override
public String toString() {
return data+"";
}
}
边类
package com.whut.DataStructure.graph.entity;
/**
* @Auther: 杨赟
* @Date: 2018/10/2 08:35
* @Description: 边
*/
public class Edge {
private Object info; //边包含的信息
private int weight; //权重
private EType type; //边的类型
public Edge(int weight) {
this.info = null;
this.weight = weight;
this.type = EType.UNKNOWN;
}
public Edge(int weight,Object info) {
this.info = info;
this.weight = weight;
this.type = EType.UNKNOWN;
}
public Object getInfo() {
return info;
}
public void setInfo(Object info) {
this.info = info;
}
public int getWeight() {
return weight;
}
public void setWeight(int weight) {
this.weight = weight;
}
public EType getType() {
return type;
}
public void setType(EType type) {
this.type = type;
}
}
边的类型枚举类
package com.whut.DataStructure.graph.entity;
/**
* @Auther: 杨赟
* @Date: 2018/10/2 08:30
* @Description: 边的类型
*/
public enum EType {
UNKNOWN, //未知边
TREE, //树边
CROSS, //横跨边
FORWARD, //前向跨边
BACKWARD; //后向跨边
}
顶点的状态枚举类
package com.whut.DataStructure.graph.entity;
/**
* @Auther: 杨赟
* @Date: 2018/10/2 08:33
* @Description: 顶点的状态
*/
public enum VStatus {
UNDISCOVERED, //尚未被发现的顶点
DISCOVERED, //已被发现的顶点
VISITED; //已访问过的顶点
}
4.3 图的邻接矩阵实现
采用邻接矩阵的方式表示并实现图的操作接口，其中邻接矩阵采用二层向量的形式进行实现，优点是可扩展性强，可任意插入和删除顶点和边。
package com.whut.DataStructure.graph;
import com.whut.DataStructure.graph.entity.*;
import java.util.*;
import java.util.concurrent.atomic.AtomicInteger;
/**
* @Auther: 杨赟
* @Date: 2018/10/2 09:01
* @Description: 用邻接矩阵表示图
*/
public class GraphMatrix<Tv> implements Graph<Tv>{
private int n; //当前顶点数量
private int e; //当前边的数量
private Vector<Vertex<Tv>> V; //顶点集合
private Vector<Vector<Edge>> E; //边的集合（邻接矩阵）
private Map<Tv,Integer> hashMap; //顶点的data和顶点在数组中的pos映射表
/**
* 功能描述:重置顶点和边的信息
* @param:
* @return:
* @auther: 杨赟
* @date: 2018/10/2 11:05
*/
private void reset () {
for (int i = 0; i < n; i++) {
Vertex vertex = V.get(i);
vertex.setStatus(VStatus.UNDISCOVERED);
vertex.setdTime(-1);
vertex.setfTime(-1);
vertex.setParent(-1);
vertex.setPriority(Integer.MAX_VALUE);
for (int j = 0; j < n; ++j) {
if(exists(i,j)){
E.get(i).get(j).setType( EType.UNKNOWN);
}
}
}
}
/**
* 功能描述:
* @param: 顶点位置
* @return: 指定顶点的第一个相邻顶点
* @auther: 杨赟
* @date: 2018/10/2 11:06
*/
private int firstNeighbor(int i){
return nextNeighbor(i,n);
}
/**
* 功能描述:
* @param: i 顶点位置
* @param: j 上一个相邻顶点位置
* @return: 顶点i的下一个相邻顶点位置
* @auther: 杨赟
* @date: 2018/10/2 11:07
*/
private int nextNeighbor(int i, int j){
while ((-1<j)&&(!exists(i,--j)));
return j;
}
/**
* 功能描述:是否存在顶点i到顶点j的有向边
* @param: i 起始顶点位置
* @param: j 结束顶点位置
* @return: 是否存在
* @auther: 杨赟
* @date: 2018/10/2 11:08
*/
private boolean exists(int i, int j){
return (0<=i) && (i<n) && (0<=j) && (j<n) && E.get(i).get(j)!=null;
}
private int inDegree(int i){
return V.get(i).getInDegree();
}
private int outDegree(int i){
return V.get(i).getOutDegree();
}
private VStatus status(int i){
return V.get(i).getStatus();
}
private int dTime(int i){
return V.get(i).getdTime();
}
private int fTime(int i){
return V.get(i).getfTime();
}
private int parent(int i){
return V.get(i).getParent();
}
private void setParent(int i,int parent){
V.get(i).setParent(parent);
}
private int priority(int i){
return V.get(i).getPriority();
}
private void setPriority(int i,int priority){
V.get(i).setPriority(priority);
}
private int weight(int i, int j){
return E.get(i).get(j).getWeight();
}
private EType type(int i, int j){
return E.get(i).get(j).getType();
}
private Object info(int i, int j){
return E.get(i).get(j).getInfo();
}
public GraphMatrix() {
n = 0;e = 0;
V = new Vector<Vertex<Tv>>();
E = new Vector<Vector<Edge>>();
hashMap = new HashMap<Tv, Integer>();
}
@Override
public int vertexNumber() {
return n;
}
@Override
public boolean exist(Tv vertex) {
return hashMap.containsKey(vertex);
}
@Override
public boolean insert(Tv vertex) {
if(hashMap.containsKey(vertex)) return false;
for(int j = 0; j < n; j++) E.get(j).add(null); n++;
Vector<Edge> vector = new Vector<Edge>();
for(int j = 0; j < n; j++) vector.add(null); E.add(vector);
V.add(new Vertex<Tv>(vertex));
hashMap.put(vertex,n-1);
return true;
}
@Override
public Vertex<Tv> remove(Tv vertex) {
Integer i = hashMap.get(vertex);
if(i == null) return null;
//删除第i行
for(int j = 0; j < n; j++){
if(exists(i,j)) V.get(j).setInDegree(V.get(j).getInDegree()-1);//顶点j的入度减1
}
int i1 = i; E.remove(i1); n--;
//删除顶点
Vertex<Tv> vector = V.get(i); V.remove(i1);
//删除第i列
for(int j = 0; j < n; j++){
if(exists(j,i)) V.get(j).setOutDegree(V.get(j).getOutDegree()-1);//顶点j的入度减1
E.get(j).remove(i1); //删除所有j->i的边
}
//重置hashMap
for(int j = 0; j < n; j++){
hashMap.put(V.get(j).getData(),j);
}
return vector;
}
@Override
public Vertex<Tv> find(Tv vertex) {
Integer i = hashMap.get(vertex);
if(i == null) return null;
return V.get(i);
}
@Override
public int edgeNumber() {
return e;
}
@Override
public boolean exist(Tv vertex1, Tv vertex2) {
return find(vertex1,vertex1) != null;
}
@Override
public boolean insert(Tv vertex1, Tv vertex2, Edge edge) {
Integer i = hashMap.get(vertex1);
Integer j = hashMap.get(vertex2);
if(i==null || j==null) return false;
if(!exists(i,j)) {
E.get(i).set(j,edge); ++e;
V.get(i).setOutDegree(V.get(i).getOutDegree()+1);
V.get(j).setInDegree(V.get(j).getInDegree()+1);
}
return true;
}
@Override
public Edge remove(Tv vertex1, Tv vertex2) {
Integer i = hashMap.get(vertex1);
Integer j = hashMap.get(vertex2);
if(i==null || j==null || !exists(i,j)) return null;
Edge edge = E.get(i).get(j);
E.get(i).set(j,null); --e;
V.get(i).setOutDegree(V.get(i).getOutDegree()-1);
V.get(j).setInDegree(V.get(j).getInDegree()-1);
return edge;
}
@Override
public Edge find(Tv vertex1, Tv vertex2) {
Integer i = hashMap.get(vertex1);
Integer j = hashMap.get(vertex2);
if(i==null || j==null || !exists(i,j)) return null;
return E.get(i).get(j);
}
@Override
public void bfs(Tv vertex, Function<Tv> function) {
Integer i = hashMap.get(vertex);
if(i == null) return;
reset();
AtomicInteger clock = new AtomicInteger(0);
int v = i;
do {
if(status(v) == VStatus.UNDISCOVERED) BFS(v,clock,function);
}while (i != (v=(++v%n)));
}
private void BFS(int i, AtomicInteger clock,Function<Tv> function) {
Queue<Integer> queue = new LinkedList<Integer>();
function.discover(V.get(i));
V.get(i).setStatus(VStatus.DISCOVERED);
queue.add(i);
while (!queue.isEmpty()){
i = queue.poll();//取出对首顶点v
V.get(i).setdTime(clock.addAndGet(1));//v顶点的时钟加1
for (int u = firstNeighbor(i); -1 < u; u = nextNeighbor(i, u)){
if(status(u) == VStatus.UNDISCOVERED) {
Vertex<Tv> vertex = V.get(u);
function.discover(vertex);
vertex.setStatus(VStatus.DISCOVERED);
queue.add(u);
E.get(i).get(u).setType(EType.TREE);
vertex.setParent(i);
}else {
E.get(i).get(u).setType(EType.CROSS);
}
}
function.visit(V.get(i));
V.get(i).setStatus(VStatus.VISITED);
}
}
@Override
public void dfs(Tv data, Function<Tv> function){
Integer i = hashMap.get(data);
if(i == null) return;
reset();
AtomicInteger clock = new AtomicInteger(0);
int v = i; List<Vertex<Tv>> list = new ArrayList<Vertex<Tv>>();
do {
if(status(v) == VStatus.UNDISCOVERED) DFS(v,clock,function);
}while (i != (v=(++v%n)));
}
private void DFS(int i, AtomicInteger clock, Function<Tv> function) {
Vertex<Tv> vertex = V.get(i);
vertex.setdTime(clock.addAndGet(1));
function.discover(vertex);//发现顶点
vertex.setStatus(VStatus.DISCOVERED);
for(int j = firstNeighbor(i); -1 < j; j=nextNeighbor(i,j)){
if(status(j) == VStatus.UNDISCOVERED){
E.get(i).get(j).setType(EType.TREE);
V.get(j).setParent(i);
DFS(j,clock,function);
}else if(status(j) == VStatus.DISCOVERED){
E.get(i).get(j).setType(EType.BACKWARD);
}else {
E.get(i).get(j).setType(dTime(i)<dTime(j)?EType.FORWARD:EType.CROSS);
}
}
function.visit(vertex);
vertex.setStatus(VStatus.VISITED);
vertex.setfTime(clock.addAndGet(1));
}
其中Function<Tv> 类型是一个接口，其中定义了两个方法，分别为发现顶点时的操作和访问完毕后对顶点的操作，我们使用该库时，自己实现这两个方法。Function<Tv>的定义如下：
package com.whut.DataStructure.graph;
import com.whut.DataStructure.graph.entity.Vertex;
/**
* @Auther: 杨赟
* @Date: 2018/10/2 21:15
* @Description: 双连通域分解算法(bcc)结果
*/
public interface Function<Tv> {
void discover(Vertex<Tv> vertex);
void visit(Vertex<Tv> vertex);
}
4.4 测试
采用3.1和3.2的两个例子对代码进行测试。测试类如下
package com.whut.DataStructure.graph;
import com.whut.DataStructure.graph.entity.Edge;
import com.whut.DataStructure.graph.entity.Vertex;
import java.util.List;
/**
* @Auther: 杨赟
* @Date: 2018/10/2 11:37
* @Description:
*/
public class Test {
private static void bfsTest(String start) {
GraphMatrix<String> graphMatrix = new GraphMatrix<String>();
graphMatrix.insert("S");
graphMatrix.insert("G");
graphMatrix.insert("F");
graphMatrix.insert("E");
graphMatrix.insert("D");
graphMatrix.insert("C");
graphMatrix.insert("B");
graphMatrix.insert("A");
graphMatrix.insert("S","A",new Edge(1,1));
graphMatrix.insert("S","C",new Edge(1,2));
graphMatrix.insert("S","D",new Edge(1,3));
graphMatrix.insert("A","C",new Edge(1,4));
graphMatrix.insert("A","E",new Edge(1,5));
graphMatrix.insert("C","B",new Edge(1,6));
graphMatrix.insert("D","B",new Edge(1,7));
graphMatrix.insert("E","F",new Edge(1,8));
graphMatrix.insert("E","G",new Edge(1,9));
graphMatrix.insert("G","F",new Edge(1,10));
graphMatrix.insert("G","B",new Edge(1,11));
System.out.print("广度优先遍历结果:");
graphMatrix.bfs(start, new Operation<String>() {
@Override
public void discover(Vertex<String> vertex) {
System.out.print(" "+vertex.getData());
}
@Override
public void visit(Vertex<String> vertex) {
}
});
System.out.println("");
}
private static void dfsTest(String start) {
GraphMatrix<String> graphMatrix = new GraphMatrix<String>();
graphMatrix.insert("G");
graphMatrix.insert("F");
graphMatrix.insert("D");
graphMatrix.insert("E");
graphMatrix.insert("C");
graphMatrix.insert("B");
graphMatrix.insert("A");
graphMatrix.insert("A","B",new Edge(1,1));
graphMatrix.insert("A","F",new Edge(1,2));
graphMatrix.insert("A","C",new Edge(1,3));
graphMatrix.insert("B","C",new Edge(1,4));
graphMatrix.insert("F","G",new Edge(1,5));
graphMatrix.insert("G","C",new Edge(1,6));
graphMatrix.insert("D","A",new Edge(1,7));
graphMatrix.insert("D","E",new Edge(1,8));
graphMatrix.insert("E","F",new Edge(1,9));
graphMatrix.insert("G","A",new Edge(1,10));
System.out.print("深度优先遍历结果:");
graphMatrix.dfs(start, new Operation<String>() {
@Override
public void discover(Vertex<String> vertex) {
System.out.print(" "+vertex.getData());
}
@Override
public void visit(Vertex<String> vertex) {
}
});
System.out.println("");
}
public static void main(String[] args) {
bfsTest("S");
dfsTest("A");
dfsTest("D");
}
}
如图9所示，代码运行结果与预期相符。
图9.运行结果
