今天我们就来学习“数据结构入门系列”中最后一个数据结构“图”。图是很常用的数据结构,比如计算机网络、社交网络、谷歌地图都需要用到此数据结构,掌握图的知识可以完善我们的数据结构知识体系,也能帮助我们解决算法中更为复杂的问题。

简单来说,图是一种用来表示相连数据的数据结构,类似我们的社交网络,图中有很多的节点,每个节点代表一个数据,每个节点可以和其他节点相连。其中每个节点叫做顶点(vertice),连接顶点之间的线叫做相连线(edge)。下图就是一个用来表示社交网络的图数据结构:

在此图中,我们含有5个顶点和6条相连线,每个顶点包含了人名,而连接线代表相连人名之间是朋友关系。如果我们要更正式地表示图,那么图就可以用一对(V,E)集合来表示,其中V是一堆顶点的集合,而E是一堆相连线的集合,请看下图:

在此图中:V = {a, b, c, d, e},E = {ab, ac, bd, cd, de}

上面提到的图是无向图,而常见的图有以下三种:

  1. 无向图(Undirected Graph):在无向图中,每个顶点和其他顶点通过相连线连接。
  2. 有向图(Directed Graph):有向图中的相连线是有方向的。
  3. 权重图(Weighted Graph):在权重图中,每条相连线有各自的权重。

下图是有向图:

此图可以用来表示用户之间相互关注的情况,如果Mark指向Alice,则代表Mark关注了Alice。下图是权重图:

此图可以用来表示两个好友之间的亲密程度,数值越高代表越亲密。可见不同的图可以用来表示不同的关系,而有向图是最常见的图,我们接下来就用Java实现有向图。

有向图的实现(Directed Graph)

有向图的实现有两种,一种是用矩阵(Matrix)的形式来实现,另一种是用链表(List)的形式来实现。

如果我们使用矩阵来实现有向图,来看一个例子:

每行代表相应的顶点,如果M[i][j] = 1,那么就代表顶点 i 连向 j,如果是0,则表达顶点间没有联系。用矩阵的方式来实现图的优势很明显,我们可以很快地判断两个顶点之间是否相连,可是用矩阵实现的空间复杂度很高,我们需要O(V^2)来记录所有的数据,不管顶点之间是否有相连线。为了解决空间复杂度的问题,我们可以使用链表的方式来实现图:

在链表实现中,我们实际上使用了储存链表的数组来表示图,图的左侧用数组来实现,代表我们的所有顶点,而每个顶点含有一个链表,链表上储存了该顶点指向的顶点。以下是Java的实现代码:

public class ListGraph {

    ArrayList<ArrayList<Integer>> graphs;

    public ListGraph(int v) {
        graphs = new ArrayList<>(v);
        for (int i = 0; i < v; i++) {
            graphs.add(new ArrayList<>());
        }
    }

    public void addEdge(int start, int end) {
        graphs.get(start).add(end);
    }

    public void removeEdge(int start, int end) {
        graphs.get(start).remove((Integer)end);
    }
}

有向图的实现很简单,我们直接使用Java中的ArrayList来代表左侧的数组和数组上的链表,其中两个重要方法addEdge和removeEdge直接使用ArrayList自带的方法add和remove即可。使用链表的形式来实现图,我们可以只记录有用的数据,省下了很多空间。了解完图的链表实现,我们来了解一下如何遍历图:

图的遍历(Graph Traversal)

遍历图有两种常见的方式,一种是深度优先搜索(Depth-first Search),另一种是宽度优先搜索(Breadth-first search)。首先我们来学习深度优先搜索:

深度优先搜索(Depth-First Search)

图的深度优先和树的前序遍历(Pre-order Traversal)有点类似。在深度优先遍历中,我们假设初始状态所有顶点都没被访问,然后从每一顶点v出发,先访问该顶点,然后依次从它的各个未被访问的邻接点出发,深度优先遍历图,直到图中所有和v相通的顶点都被访问到。若遍历完后,还有其他顶点没被访问到,则另选一个未被访问的顶点作为起始点,重复上述过程,直到所有顶点都被访问完为止。

下面以“有向图”为例,来对深度优先搜索进行演示:

对于上面的图,我们从顶点A开始搜索:

以下是具体的遍历步骤:

  1. 访问A
  2. 访问B(在访问A之后,接下来应该访问的是A出发的另一个顶点,既顶点B)
  3. 访问C(在访问B之后,接下来访问的是从B出发的另一个顶点,既C,E,F。在此图中,我们按照字母排序顺序访问,因此先访问C。)
  4. 访问E(接下来访问与C连接的另一个顶点E。)
  5. 访问D(接下来访问从E出发的顶点B和D,因为B已被访问过,所以访问顶点D。)
  6. 访问F(接下来回溯“访问A的另一个连接顶点F”)
  7. 访问G

因此访问顺序是:A -> B -> C -> E -> D -> F -> G。

在图的深度优先搜索中,我们尽可能先遍历一个顶点可以达到的最深处,其中可能会出现的问题就是会有循环出现,所以我们需要一个数组来记录哪些节点已经被访问过。以下是Java的回溯实现代码:

public class GraphTraversal {

    ListGraph graph;
    boolean[] visited;

    public GraphTraversal(ListGraph listGraph) {
        this.graph = listGraph;
        visited = new boolean[listGraph.graphs.size()];
    }

    public void DFSTraversal(int v) {
        if(visited[v]) return;
        visited[v] = true;
        System.out.print(v + " -> ");
        Iterator<Integer> neighbors = graph.graphs.get(v).listIterator();
        while (neighbors.hasNext()) {
            int nextNode = neighbors.next();
            if (!visited[nextNode]) {
                DFSTraversal(nextNode);
            }
        }
    }
    
    public void DFS() {
        for (int i = 0; i < graph.graphs.size(); i++) {
            if (!visited[i]) {
                DFSTraversal(i);
            }
        }
    }
}

广度优先搜索(Breadth-First Search)

广度优先搜索算法也叫做“宽度优先搜索”或“横向优先搜索”,其方法是从图中的某一顶点v出发,在访问了v之后依次访问v的各个没有访问到的邻接点,然后分别从这些邻接点出发依次访问他们的邻接点,使得先被访问的顶点的邻接点先与后被访问顶点的邻接点被访问,直到图中所有已被访问的顶点的邻接点都被访问到。如果此时图中尚有顶点未被访问,则需要另选一个未曾被访问到的顶点作为新的起始点,重复上述过程,直至图中所有顶点都被访问到为止。换句话说,广度优先搜索遍历图的过程是以v为起点,由近至远,依次访问和v有路径相通且路径长度为1,2,…的顶点。

下面以“有向图”为例,对广度优先搜索进行演示:

以下是访问步骤:

  1. 访问A
  2. 访问B
  3. 依次访问C,E,F(在B被访问之后,接下来访问B的邻接点,既C,E,F。)
  4. 依次访问D,G(在访问完C,E,F之后,再依次访问他们出发的另一个顶点。还是按照C,E,F的顺序访问,C的已经全部访问过了,那么就只剩下E,E;先访问E的邻接点D,再访问F的邻接点G。

访问顺序是:A -> B -> C -> E -> F -> D -> G。

在实现中,我们需要使用queue来储存接下来要遍历的顶点(每层的邻接点),在Java中我们通过Deque来实现Queue,以下是代码:

public void BFSTraversal(int v) {
    Deque<Integer> queue = new ArrayDeque<>();
    visited[v] = true;
    queue.offerFirst(v);
    while (queue.size() != 0) {
        Integer cur = queue.pollFirst();
        System.out.print(cur + " -> ");
        Iterator<Integer> neighbors = graph.graphs.get(cur).listIterator();
        while (neighbors.hasNext()) {
            int nextNode = neighbors.next();
            if (!visited[nextNode]) {
                visited[nextNode] = true;
                queue.offerLast(nextNode);
            }
        }
    }
}

public void BFS() {
    for (int i = 0; i < graph.graphs.size(); i++) {
        if (!visited[i]) {
            BFSTraversal(i);
        }
    }
}

以上就是图的两种遍历方法:深度优先遍历和广度优先遍历。简单来说,深度优先遍历就是选择一条路径走到头再回来,而广度深度优先就是将最近的邻接点先访问完,再向更远的顶点延伸。

Leetcode相关题目和源代码

Leetcode题目

GitHub源代码