本文将带你重温“图”这一数据结构的基础概念，以及使用Java实现“图”的数据结构和遍历算法（DFS、BFS）

1. 概览

1.1 定义

主要有以下两种定义。

二元组的定义：

图G是一个有序二元组(V,E)，其中V称为顶集(Vertices Set)，E称为边集(Edges set)，E与V不相交。它们亦可写成V(G)和E(G)。E的元素都是二元组，用(x,y)表示，其中x,y∈V。

三元组的定义：

图G是指一个三元组(V,E,I)，其中V称为顶集，E称为边集，E与V不相交；I称为关联函数，I将E中的每一个元素映射到 。如果e被映射到(u,v)，那么称边e连接顶点u,v，而u,v则称作e的端点，u,v此时关于e相邻。同时，若两条边i,j有一个公共顶点u，则称i,j关于u相邻。

1.2 分类

• 无向图：图是有一组顶点和一组能够将两个顶点相连的边组成的。可能概念有点模糊，但是可以根下面的有向图相比较就特别简单了。
• 有向图：由一组顶点和一组有方向的边组成，每条有方向的边都连接着有序的一对顶点

1.3 术语

• 相邻：如果两个顶点通过一条边相连， 则称这两个顶点是相邻的，并称这条边依附于这两个顶点
• 度数：某个顶点的度数即为依附于它的边的总数。
• 子图：一幅图的所有边的一个子集以及他们所依附的所有顶点组成的图。
• 路径：由边顺序链接的一系列顶点。
• 简单路径：一条没有重复顶点的路径。
• 环：一条至少包含一条边且起点和终点相同的路径。
• 简单环：除了第一个顶点和最后一个顶点之外，其余顶点不重复出现的环。
• 连通图：任意两个顶点之间互通。一副非连通的图由诺干个连通的部分组成。
• 图的密度：已连接的顶点对占所有可能被连接的顶点对的比例。
• 平行边：连接同一对顶点的两条边称为平行边。
• 二分图：图中的每一条边所连接的两个顶点都分别属于不同的部分

1.4 图的表示方法

邻接矩阵

下图一眼就可以看懂，如果结点a与结点b之间相连接，则A(a,b) = A(b,a) = 1，否则为0

邻接表

在邻接表表示法中，第一列代表的为结点，如0,1,2……，而后面的则代表为结点与其他结点相连接的结点。（例如0结点后面为1,4结点，则代表0结点与1结点和4结点相连接【在这里我们可以发现，第5行的4结点的后面同样有1结点】）

关联矩阵

2. Java实现

邻接矩阵 和 邻接表 两种各有优缺点：

如果我们需要处理顶点V的邻接顶点，我们使用邻接表只需要deg(v)步操作（deg:图论中点连出的边数）。而在邻接矩阵中，我们需要进行|V|步操作。但是在当我们需要插入或者删除一个邻接与v的节点的时候，我们需要对邻接表进行调整，而对于邻接矩阵，只需要进行0和1的变换即可。

邻接矩阵的空间复杂度是O(V*V)，而邻接表的复杂度为O(V+E)，V为顶点数，E为边数。

​ 在这里我们可以再想一下，在最稠密的情况下（每一个结点都与其他结点相连接），邻接矩阵的空间复杂度会远远的 小于邻接表（n!和n^2不在一个数量级）。

如果出现平行边了，我们只能够使用邻接表去表示。

说了这么多，在下面的数据结构中，除非特殊说明，我们选择使用邻接表来进行数据储存。我们可以上代码了。

图的Java实现

public class Graph {
    // 顶点数量
    int V;
    // 边的数量
    int E;
    // 邻接表
    List[] adj;

    // 构造一个含有V个顶点的图，但是不含边
    Graph(int V) {
        adj = new ArrayList[V];
        for (int i = 0; i < V; i++) {
            adj[i] = new ArrayList<Integer>();
        }
        this.V = V;
    }

    // 在图中添加一条边v-w
    void addEdge(int v, int w) {
		// 无向图实现
	    adj[v].add(w);
	    adj[w].add(v);
	    this.E ++;
	}

    // 获得与v相邻的所有顶点
    Iterable<Integer> adj(int v) {
		return adj[v];
	}

    // 与结点s相连通的所有结点
	Iterable<Integer> search(int s) {
    	DepthFirstSearch dfs = new DepthFirstSearch(this,s);
    	List list = new ArrayList(dfs.getCount());
    	for (int i=0;i<this.V();i++) {
    	    if (dfs.getMarked(i)){
    	        list.add(i);
    	    }
    	}
    	return list;
	}

    // 是否存在S结点到V结点的路径
	boolean hasPathTo(int s,int v);

    // 找出s到v结点的路径
	Iterable<Integer> pathTo(int s,int v);
}

搜索算法 - 深度优先搜索

我们可以通过adj函数得到结点的相邻结点，需要一个标志mark，这个标志代表着这个结点是否已经被访问过。

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

    public DepthFirstSearch(UndirGraph graph,int s){
        marked = new boolean[graph.V()];
        dfs(graph,s);
    }

    private void dfs(UndirGraph graph, int s) {
        marked[s] = true;
        count++;
        for (int v:graph.adj(s)){
            if (!marked[v]){
                dfs(graph,v);
            }
        }
    }

    public boolean getMarked(int w) {
        return marked[w];
    }

    public int getCount() {
        return count;
    }
}

搜索算法 - 广度优先搜索

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

    public BreadthFirstSearch(Graph graph,int s) {
        this.s = s;
        this.marked = new boolean[graph.V()];
        this.edgeTo = new int[graph.V()];
        bfs(graph,s);
    }

    private void bfs(Graph graph, int s) {
        Queue<Integer> queue = new LinkedList<>();
        marked[s] = true;
        // 将s加入队列中
        queue.offer(s);
        while(!queue.isEmpty()){
            // 从队列中删除结点
            int v = queue.poll();
            for (int w: graph.adj(v)) {
                if (!marked[w]){
                    edgeTo[w] = v;
                    marked[w] = true;
                    queue.offer(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;
    }
}