图的数据结构定义以及两种遍历方法的讨论

简介

    很早以前接触图的定义时，对于它的定义和各种操作有过一种简单的了解。图的结构和通常的其他数据结构不太一样。针对不同的情况我们可以定义不同的样式来处理。这里针对图的基本定义形式和两种常见的遍历方法（深度优先和广度优先）进行讨论。

 

图的结构

    从直观的角度来看，我们常见的图一般是这样的：

或者如下图这样：

    这两种图我们分别称其为无向图和有向图。我们知道，在图里，它主要是由若干个顶点再加上顶点之间关联的边组成。而对于每个顶点来说，它通常和其它所有顶点都可能有关联关系。正因为这些顶点本身不像树或者其他结构那样有特殊的特性，我们可以将他们按照某个顺序进行编号，就像前面图中间那样。有了前面这样的编码我们就方便确定顶点之间的关系了。我们常用的定义图的结构有如下两种：

链表组

    我们可以采用一组链表，每个链表的索引对应一个顶点的编号。比如说索引0对应顶点0这一组。而对应的这个链表里保存的就是所有和顶点0直接相邻的顶点。按照这个定义，我们前面示例中的图分别对应如下的图：

 

    采用这种结构，我们将每个节点和它关联的节点通过链表联系起来了。对于无向图来说，由于关联的关系是相互到两个节点的，比如0和1是相邻的节点，在0节点的关联表里有1,同样，在1节点的关联表里也有0。当然，对于图中间节点关系比较少的情况这是一种空间资源利用比较有效的结构。

 

矩阵

    矩阵结构也是一种比较有意思的表示方式。我们知道，假设一个图中间有n个节点，那么对于任意一个节点来说，它最多和其他n-1个节点有直接关联的关系。所以这所有n个节点的关系构成一个n x n的矩阵。采用这种方式的时候，我们可以假定在一个矩阵m里，如果节点a和b有直接关联关系，我们就定义m[m][n] = 1，否则定义为0。按照这种方式，前面示例对应的矩阵表示形式如下：

 

 

 

    矩阵表示方式对于元素之间关系比较密集的情况比较有效。对于无向图来说，它本身就是一个对称矩阵，我们完全可以只需要使用矩阵的一半空间就可以了。另外，在一些情况下，比如说我们需要表示边的权值，比如a和b之间有一个边，它的值是c，我们可以直接在矩阵中将m[a][b]定义为c。这是一种很紧凑的表示方式。

 

比较和实现

    前面使用链表组和使用矩阵的两种方式在大体上已经能够实现一个图的结构了。在通常情况下，我们还是比较推荐使用链表组的表示方式。因为在一些规模比较大的输入的时候，比如上百万个的时候，如果我们用矩阵，消耗的空间资源太大，有时候显得不可行了。另外，对于有的图来说，比如有并行的边的情况（就是两个节点中间有多条关联的边），使用矩阵的表示形式是没法来区分的。从实现的角度来看，使用矩阵非常简单，这里就不再赘述了。我们主要针对链表组的方式来讨论一下。

    我们来看链表组的实现方式，这里的核心就是我们要创建一组链表。一个直接典型的思路就是定义一个LinkedList<Integer>[]这样的数组。然后在给定节点数量的时候再初始化它。这是一个有意思的问题。虽然我们可以这样定义数组，不过在创建的时候，如果我们用如下的代码LinkedList<Integer>[] lists = new LinkedList<Integer>[number]; 系统编译的时候会报错。错误信息通常如下： "Cannot create a generic array of LinkedList<Integer>.” 这其中主要的原因在于java里面对泛型的支持的不足。所以推荐的方式是使用一个List<LinkedList<Integer>> lists = new ArrayList<LinkedList<Integer>>();。

    在构造好这个大的结构之后，我们再一个个的插入节点到每个节点的关联表中，这样整个的构造过程就结束了。按照这些讨论，我们实现的图代码如下：

import java.util.LinkedList;
import java.util.List;
import java.util.ArrayList;
import java.util.Scanner;
import java.io.FileInputStream;

public class Graph {
    private final int vertices;
    private int edges;
    private List<LinkedList<Integer>> adj;

    public Graph(int vertices) {
        if(vertices < 0) 
            throw new IllegalArgumentException("Number of vertices must be nonnegative");
        this.vertices = vertices;
        this.edges = 0;
        adj = new ArrayList<LinkedList<Integer>>(vertices);
        for(int i = 0; i < vertices; i++) {
            adj.add(new LinkedList<Integer>());
        }
    }
    
    public Graph(Scanner scanner) {
        this(scanner.nextInt());
        int e = scanner.nextInt();
        if(e < 0)
            throw new IllegalArgumentException("Number of edges must be nonnegative");
        for(int i = 0; i < e; i++) {
            int v = scanner.nextInt();
            int w = scanner.nextInt();
            addEdge(v, w);
        }
    }

    public void addEdge(int v, int w) {
        if(v < 0 || v >= vertices)
            throw new IndexOutOfBoundsException();
        if(w < 0 || w >= vertices)
            throw new IndexOutOfBoundsException();
        edges++;
        adj.get(v).add(w);
        adj.get(w).add(v);
    }

    public int getVertices() {
        return vertices;
    }

    public int getEdges() {
        return edges;
    }

    public Iterable<Integer> adj(int v) {
        if(v < 0 || v >= vertices)
            throw new IndexOutOfBoundsException();
        return adj.get(v);
    }

    @Override
    public String toString() {
        StringBuilder s = new StringBuilder();
        String NEWLINE = System.getProperty("line.separator");
        s.append(vertices + " vertices, " + edges + " edges " + NEWLINE);
        for(int v = 0; v < vertices; v++) {
            s.append(v + ": ");
            for(int w : adj.get(v)) {
                s.append(w + " ");
            }
            s.append(NEWLINE);
        }
        return s.toString();
    }

    public static void main(String[] args) throws Exception {
        Scanner s = new Scanner(new FileInputStream(args[0]));
        Graph g = new Graph(s);
        System.out.println(g);
    }
}

    这里定义了两个构造函数，第一个通过传入指定的参数来构造一个链表组，另外一个通过读入一个外部文件，然后再一个个的加入边。还有一个有意思的地方就是addEdge方法，里面指定了增加节点v, w之间的边，对于无向图来说，这里要分别在v的关联表加入w和在w的关联表加入v。 

 

遍历方法

    如果我们考虑图的遍历方法，有时候会难免和其他结构的一些遍历做比较。比如树的遍历。我们会发现他们之间还有不少的相似之处。最常见的两种遍历方式为深度优先遍历和广度优先遍历。

 

深度优先

    我们来看看深度优先遍历的大致过程，每次我们从一个节点开始，首先沿着它关联的某个边到另外一个节点。接着再从这个节点继续遍历下一个节点。每次遍历的时候不能重复原来覆盖过的节点。否则就要返回到原来的节点，再从下一个关联的节点继续原来的过程。这个描述的过程就是一个递归的过程。

    从实现细节来看，既然我们不希望每次从一个节点往后面遍历的时候不要重复覆盖已经访问过的节点，我们需要定义一个数组boolean[] marked，它用来表示对应某个节点是否已经被访问过。另外，如果我们需要求从某个点到另外一个点的路径。我们可以定义一个int[] edgeTo。这个数组里edgeTo[w] = v表示按照遍历方式从v点走到w点。我们后面要查找从某个点到指定的源节点之间的路径时可以通过edgeTo[]数组来回推。详细代码实现如下：

import java.io.FileInputStream;
import java.util.Stack;

public class DepthFirstSearch {
    private boolean[] marked;
    private int count;
    private int[] edgeTo;
    private final int s;

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

    private void dfs(Graph g, int v) {
        marked[v] = true;
        count++;
        for(int w : g.adj(v))
            if(!marked[w]) {
                edgeTo[w] = v;
                dfs(g, w);
            }
    }

    public boolean marked(int w) {
        return hasPathTo(w);
    }

    public boolean hasPathTo(int v) {
        if(v < 0 || v >= marked.length)
            throw new IndexOutOfBoundsException();
        return marked[v];
    }

    public int count() {
        return count;
    }
    public Iterable<Integer> pathTo(int v) {
        if(!hasPathTo(v)) return null;
        Stack<Integer> path = new Stack<Integer>();
        for(int x = v; x != s; x = edgeTo[x])
            path.push(x);
        path.push(s);
        return path;
    }
}

    这部分代码涵盖了几个部分的功能。我们先看整体结构。这和一些图的遍历实现不一样，我们是通过单独定义的一个类来实现深度优先搜索，同时将Graph作为一个引用。在dfs方法里，我们每次遍历到一个节点时就将该节点标识为true。这样最终保证dfs方法退出的条件就是我们所有能遍历到的节点都被标记为true了。       这里还有一个比较有意思的地方是我们定义了一个int count. 它有什么用呢？我们在遍历的时候，每次访问到一个节点，就对该count加一。所以如果我们完整的访问了所有的节点则count的值应该和节点数是一样的。否则就表示这个图不是连通的。这是一种判断图是否为连通的一种方法。

 

广度优先

    求图的广度优先遍历和树的广度优先遍历很相似，我们要用到另外一个结构，就是队列。按照这个思路，我们可以很容易得到如下的实现代码：

private void bfs(Graph g, int s) {
        Queue<Integer> queue = new LinkedList<Integer>();
        marked[s] = true;
        queue.enqueue(s);
        while(q.size() > 0) {
            int v = queue.remove();
            for(int w : g.adj(v))
                if(!marked[w]) {
                    edgeTo[w] = v;
                    marked[w] = true;
                    queue.add(w);
                }
        }
    }

   详细的代码这里就不再分析了。可以参照后面附件里的完整代码。

 

总结

    图的定义和结构的实现细节有一些语言特定的因素影响，这里主要是针对java的实现。这里讨论了图的两种遍历方式，分别为深度优先遍历和广度优先遍历。从表面上看，这只是两种遍历的行为。在不同的问题场景下，他们还有不同的应用。比如说图的深度优先遍历也应用于迷宫问题的解决。而图的广度优先遍历在一些求最短路径的问题上得到应用。这些方法都是解决更深层次问题的基础。 

 

参考材料

Introduction to algorithms

Algorithms

http://stackoverflow.com/questions/217065/cannot-create-an-array-of-linkedlists-in-java