基础知识

点：顶点、邻接节点
边：有向边、无向边、加权边
度：入度、出度、无向边的度
环：环、自环（glist[i]中有i）
连通性：连通图、不连通

有向图

顶点类

class Vertex {
   int id;
   List<Vertex> neighbors;
   // Vertex[] neighbors;
}

邻接表

// int值表示 顶点id
// 嵌套int列表
List<List<Integer>> glist;
// int列表数组
List<Integer>[] glist;
// 顶点列表
List<Vertex> glist;

邻接表有两个层级：

外层 - 顶点列表

用一个列表存储顶点

内层 - 邻居列表

每个顶点对应个邻居列表

邻接矩阵

// boolean 方阵
boolean [][] gmtx = new [n][n];

每一个有向边都是矩阵的元素
可以快速判断两个点是否邻接，但是费空间；

入度、出度

指向当前节点的箭头数、从当前节点指出的箭头数

有向加权图

邻接表：

顶点类实现

class Vertex {
	int id;
	int val;
	Vertex [] neighbors;
}
List<Vertex> glist;

直接存储：

// int数组的列表的数组
List<int[]>[] glist;
// int数组的列表的列表
List<List<int[]>> glist;

邻接矩阵：

int [][] gmtx = new [n][n];

无向图（双向图）

所有边的两边节点，都变成互相指向

图的遍历

系统栈 dfs 或者队列 bfs

图中包含不连通子图时的遍历思路：

// 遍历非连通图
for(int v = 0; v < g.length; v++){
	dfs[g, v];
	// if(!vst[v]) dfs(g, v);
}

题目

DAG所有可能的路径

时间 1ms，击败100%

class Solution {
	List<Integer> res;
	List<List<Integer>> ans;
	public List<List<Integer>> allPathsSourceTarget(int[][] graph) {
		res = new ArrayList<>();
		ans = new ArrayList<>();
		dfs(graph, 0);
		return ans;
	}
	public void dfs(int [][] graph, int vid){
		res.add(vid);
		if(vid == graph.length - 1)
			ans.add(new ArrayList<>(res));
		for(int v : graph[vid])
			dfs(graph, v);
		res.remove(res.size() - 1);
	}
}

判断二分图

dfs解法

class Solution {
    // 记录 当前图 是否是 二分图
    private boolean isBip = true;
    private boolean [] clr;
    private boolean [] vst;
    public boolean isBipartite(int[][] graph) {
        clr = new boolean[graph.length];
        vst = new boolean[graph.length];
        // dfs(graph, 0);
        for(int i = 0; i < graph.length; i++){
            dfs(graph, i);
        }
        return isBip;
    }
    private void dfs(int [][] graph, int vid){
        // 已经判定不是二分图，不进行递归
        if(!isBip) return;
        vst[vid] = true;
        for(int v : graph[vid]){
            if(!vst[v]){
                // dfs(graph, v);
                clr[v] = !clr[vid];
                dfs(graph, v);
            } else {
                if(clr[v] == clr[vid]){
                    isBip = false;
                    return;
                }
            }
        }
    }
}

bfs解法

class Solution {
    // 记录 当前图 是否是 二分图
    private boolean isBip = true;
    private boolean [] clr;
    private boolean [] vst;
    public boolean isBipartite(int[][] graph) {
        clr = new boolean[graph.length];
        vst = new boolean[graph.length];
        // dfs(graph, 0);
        for(int v = 0; v < graph.length; v++){
            // if(!vst[v]) dfs(graph, v);
            // bfs(graph, v);
            if(!vst[v]) bfs(graph, v);
        }
        return isBip;
    }
    private void bfs(int [][] graph, int vid){
        Deque<Integer> dq = new ArrayDeque<>();
        dq.offer(vid);
        while(!dq.isEmpty() && isBip){
            int v = dq.poll();
            vst[v] = true;
            for(int w : graph[v]){
                // dq.offer(w);
                if(!vst[w]){
                    clr[w] = !clr[v];
                    dq.offer(w);
                } else {
                    if(clr[w] == clr[v])
                        isBip = false;
                }
            }
        }
    }