图的基本概念与图的表示

内容较基础，从简记录。

图的一些概念

有向图，无向图，有权图，无权图，简单图(无自环边和平行边)，多重图，稠密图，稀疏图(一般|E|<|V||logV|时称)；
顶点的度，入度，出度，边的权值；
子图，连通图，强联通图，弱连通图，连通分量，强连通分量，弱连通分量；
路径，简单路径，回路，简单回路，距离，欧拉路径，哈密顿路径，欧拉回路，哈密顿回路；
生成树，生成森林，最小生成树。
......
更多图相关的概念将在后续笔记介绍具体图论算法时给出。

图的表示概述

图的表示最基本的有邻接矩阵和邻接表。
邻接矩阵：适用于稠密图
邻接表：适用于稀疏图

图的表示时空复杂度分析

(以无向无权图为例)
要做的一点说明是，邻接表方式中所谓"表"只是邻接顶点的组织形式，可以使用普通链表，也可以使用红黑树，哈希表。
各种图的表示对算法的影响如下：

上面列举的图的操作是图论领域很多经典算法的基础，所以选择适合的数据结构研究图论问题是必要的。
在邻接表的各种实现中，虽然哈希表性能最优，但是顶点之间的顺序性失去了，这在一些图论算法的调试和模拟中非常不方便，而红黑树可以保持节点间的顺序，且红黑树相比哈希表只是在部分操作多了一个logV数量级，还是可以接受的，故本文及以后的图论问题讨论邻接表都采用红黑树数据结构。当然如果在竞赛和刷题中追求效率可以用哈希表。

邻接矩阵表示(基于无向无权图)

/*Ice_spring 2020/3/26*/
import java.io.File;
import java.io.IOException;
import java.util.ArrayList;
import java.util.Scanner;
// 图的邻接矩阵表示，无向无权图
public class AdjMatrix {
    private int V; // 顶点数
    private int E; // 边数
    private int[][] adj; // 邻接矩阵

    public AdjMatrix(String filename){
        File file = new File(filename);
        try(Scanner scanner = new Scanner(file)){

            V = scanner.nextInt();
            if(V < 0) throw new IllegalArgumentException("V must be a non-neg number!");
            adj = new int[V][V];

            E = scanner.nextInt();
            if(E < 0) throw new IllegalArgumentException("E must be a non-neg number!");
            for(int i=0; i < E; i ++){
                int a = scanner.nextInt();
                validateVertex(a);
                int b = scanner.nextInt();
                validateVertex(b);
                // 本代码只处理简单图
                if(a == b) throw new IllegalArgumentException("检测到self-loop边！");
                if(adj[a][b] == 1) throw new IllegalArgumentException("Parallel Edges are detected!");
                adj[a][b] = 1;
                adj[b][a] = 1;
            }
        }
        catch(IOException e){
            e.printStackTrace();//打印异常信息
        }
    }
    private void validateVertex(int v){
        // 判断顶点v是否合法
        if(v < 0 ||v >= V)
            throw new IllegalArgumentException("vertex " + v + "is invalid!");
    }
    public int V(){ // 返回顶点数
        return V;
    }
    public int E(){
        return E;
    }
    public boolean hasEdge(int v, int w){
        // 顶点 v 到 w 是存在边
        validateVertex(v);
        validateVertex(w);
        return adj[v][w] == 1;
    }
    public ArrayList<Integer> adj(int v){
        // 返回和顶点 v 相邻的顶点
        validateVertex(v);
        ArrayList<Integer> res = new ArrayList<>();
        for(int i = 0; i < V; i ++)
            if(adj[v][i] == 1)
                res.add(i);
        return res;
    }
    public int degree(int v){
        // 返回节点 v 的度，即与该顶点相邻的顶点个数
        return adj(v).size(); // adj 函数
    }
    @Override
    public String toString(){
        StringBuilder sb = new StringBuilder();
        sb.append(String.format("V = %d, E = %d\n",V, E));
        for(int i = 0; i < V; i ++){
            for(int j = 0; j < V; j ++){
                sb.append(String.format("%d ", adj[i][j]));
            }
            sb.append('\n');
        }
        return sb.toString();
    }
    public static void main(String args[]){
        AdjMatrix adjMatrix = new AdjMatrix("g.txt");
        System.out.println(adjMatrix);
    }
}

邻接表表示(基于无向无权图，表数据结构使用红黑树)

/*Ice_spring 2020/3/26*/
import java.io.File;
import java.io.IOException;
import java.util.ArrayList;
import java.util.LinkedList;
import java.util.Scanner;
import java.util.TreeSet;

// 图的邻接表表示，无向无权图
public class AdjSet {
    private int V; // 顶点数
    private int E; // 边数
    private TreeSet<Integer>[] adj; // 邻接矩阵

    public AdjSet(String filename){
        File file = new File(filename);
        try(Scanner scanner = new Scanner(file)){

            V = scanner.nextInt();
            if(V < 0) throw new IllegalArgumentException("V must be a non-neg number!");
            adj = new TreeSet[V];

            for(int i = 0; i < V; i ++)
                adj[i] = new TreeSet<>();
            E = scanner.nextInt();
            if(E < 0) throw new IllegalArgumentException("E must be a non-neg number!");
            for(int i=0; i < E; i ++){
                int a = scanner.nextInt();
                validateVertex(a);
                int b = scanner.nextInt();
                validateVertex(b);
                // 本代码只处理简单图
                if(a == b) throw new IllegalArgumentException("检测到self-loop边！");
                if(adj[a].contains(b)) throw new IllegalArgumentException("Parallel Edges are detected!");
                adj[a].add(b);
                adj[b].add(a);
            }
        }
        catch(IOException e){
            e.printStackTrace();//打印异常信息
        }
    }
    private void validateVertex(int v){
        // 判断顶点v是否合法
        if(v < 0 ||v >= V)
            throw new IllegalArgumentException("vertex " + v + "is invalid!");
    }
    public int V(){ // 返回顶点数
        return V;
    }
    public int E(){
        return E;
    }
    public boolean hasEdge(int v, int w){
        // 顶点 v 到 w 是存在边
        validateVertex(v);
        validateVertex(w);
        return adj[v].contains(w);
    }
    public Iterable<Integer> adj(int v){
        // 返回值可以是TreeSet，不过用 Iterable 接口更能体现面向对象
        // 返回和顶点 v 相邻的所有顶点
        validateVertex(v);
        return adj[v];
    }
    public int degree(int v){
        // 返回节点 v 的度，即与该顶点相邻的顶点个数
        validateVertex(v);
        return adj[v].size(); //
    }
    @Override
    public String toString(){
        StringBuilder sb = new StringBuilder();
        sb.append(String.format("V = %d, E = %d\n",V, E));
        for(int v = 0; v < V; v ++){
            // 编程好习惯 i,j,k 作索引, v,w 作顶点
            sb.append(String.format("%d : ", v));

            for(int w: adj[v])
                sb.append(String.format("%d ", w));

            sb.append('\n');
        }
        return sb.toString();
    }
    public static void main(String args[]){
        AdjSet adjList = new AdjSet("g.txt");
        System.out.println(adjList);
    }
}

最后，在上面的时空复杂度分析中可以看到，综合来看，相比于邻接矩阵邻接表(红黑树)性能是更好的，所以以后对图论各个算法的实现均采用邻接表(红黑树)，这样更多的注意力可以集中在算法本身。