目录
基础知识
- 点：顶点、邻接节点
- 边：有向边、无向边、加权边
- 度：入度、出度、无向边的度
- 环：环、自环（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;
}
}
}
}