图论（上）无权图

图论Graph theory 基础

研究由点和边组成的数学模型
graph theory

应用&＃xff1a;
交通运输
社交网络
互联网
工作安排
脑区活动
程序状态执行

图的分类

default

图的连通性

default

简单图(Simple Graph)

simple graph

图的表示

邻接表适合表示稀疏图(Sparse Graph)
邻接矩阵适合表示稠密图(Dense Graph)

邻接矩阵

表示无向图
default
表示有向图
default

邻接表

表示无向图
default

表示有向图
default

图的实现

邻接矩阵

public class DenseGraph {private int n;// 节点数private int m;// 边数private boolean directed;//是否为有向图private boolean[][] g;// 图的具体数据public DenseGraph(int n, boolean directed) {this.n &＃61; n;this.m &＃61; 0;this.directed &＃61; directed;g &＃61; new boolean[n][n];}public int getNodesCount() {return n;}public int getEdgesCount(){return m;}public void addEdge(int v, int w) {if (v <0 || v >&＃61; n || w <0 || w >&＃61; n) {return;} if (hasEdge(v, w)) {return;}g[v][w] &＃61; true;if (!directed) {g[w][v] &＃61; true;}m&＃43;&＃43;;}public boolean hasEdge(int v, int w) {if (v <0 || v >&＃61; n || w <0 || w >&＃61; n) {return false;} return g[v][w];} }

邻接表

public class SparseGraph {private int n, m;private boolean directed;private List> g;public SparseGraph(int n, boolean) {if (n <0) {return;}this.n &＃61; n;this.m &＃61; 0;this.directed &＃61; directed;g &＃61; (ArrayList[])new ArrayList[n];}public int getNodesCount() {return n;}public int getEdgesCount() {return m;}public boolean hasEdge(int v, int w) {if (v <0 || v >&＃61; n || w <0 || w >&＃61; n) {return false;}int n &＃61; g[v].size();for (int i &＃61; 0; i &＃61; n || w <0 || w >&＃61; n) {return;}//如果不允许平行边&＃xff0c;需要加这样的判断if (hasEdge(v, w)) {return;}//如果允许平行边&＃xff0c;注释掉上述判断g[v].add(w);if (v !&＃61; w && !directed) {g[w].add(v);}m&＃43;&＃43;;} } 遍历边

返回一个节点的所有邻边

对于稀疏图来说

返回当前行即可

public Iterable adj(int v) {if (v <0 || v >&＃61; n) {return new ArrayList();}return g[v];}

对于稠密图来说

需要遍历一下&＃xff0c;代码如下&＃xff1a;

public Iterable adj(int v) {List res &＃61; new ArrayList<>();if (v <0 || v >&＃61; n) {return res;}for (int i &＃61; 0; i

边的遍历对图的遍历至关重要&＃xff01;

 阶段重构 抽象一个图的接口
 public interface Graph {public int getNodesCount();public int getEdgesCount();public void addEdge(int v, int w);public boolean hasEdge(int v, int w);public Iterable adj(int v);
} 
将DenseGraph和SparseGraph修改为实现Graph接口
 图的遍历 深度优先遍历
 从一个节点开始&＃xff0c;不断向下&＃xff0c;直到无法进行为止&＃xff0c;由于图可能有环&＃xff0c;因此需要记录遍历过程中的点。
 求一个图的联通分量
 以求一个图的联通分量来展示图的深度优先遍历
     //求无权图的联通分量public class Component {private Graph g;private boolean[] visited;// 记录dfs的过程中节点是否被访问private int ccount;// 记录联通分量个数private int[] id;// 每个节点所对应的联通分量标记public Component(Graph g) {this.g &＃61; g;int n &＃61; g.getNodesCount();visited &＃61; new boolean[n];id &＃61; new int[n];ccount &＃61; 0;//初始化for (int i &＃61; 0; i &＃61; n || w <0 || w >&＃61; n) {return false;}return id[v] &＃61;&＃61; id[w];}} 
求两点的路径
 public class Path {private Graph g;private boolean[] visited;private int s;private int[] from;public Path(Graph g, int s) {this.g &＃61; g;this.s &＃61; s;int n &＃61; g.getNodesCount();visited &＃61; new boolean[n];from &＃61; new int[n];for (int i &＃61; 0; i &＃61; g.getNodesCount()) {return false;}return visited[w];}public List path(int w) {List res &＃61; new ArrayList<>();if (w <0 || w >&＃61; g.getNodesCount()) {return res;}Stack s &＃61; new Stack<>();int p &＃61; w;while (p !&＃61; -1) {s.push(p);p &＃61; from[p];}while (!s.isEmpty()) {res.add(s.pop());}return res;}
} 
深度遍历复杂度
稀疏图O(V&＃43;E)
稠密图O(V^2)
深度优先遍历对有向图依旧有效
 广度优先遍历
 又称为层序遍历&＃xff0c;以两点间的最短路径为例
 public class ShortestPath {private Graph g;private int s;private boolean[] visited;private int[] from;private int[] order;public ShortestPath(Graph g, int s) {this.g &＃61; g;this.s &＃61; s;int n &＃61; g.getNodesCount();from &＃61; new int[n];visited &＃61; new boolean[n];order &＃61; new int[n];for (int i &＃61; 0; i  queue &＃61; new LinkedList<>();queue.offer(s);visited[s] &＃61; true;order[s] &＃61; 0;while (!queue.isEmpty()) {int v &＃61; queue.poll();for (int i : g.adj()) {if (!visited[i]) {queue.offer(i);visited[i] &＃61; true;from[i] &＃61; v;order[i] &＃61; order[v] &＃43; 1;}}}}public boolean hasPath(int w) {if (w <0 || w >&＃61; g.getNodesCount()) {return false;}return visited[w];}public List path(int w) {List res &＃61; new ArrayList<>();if (w <0 || w >&＃61; g.getNodesCount()) {return res;}Stack s &＃61; new Stack<>();int p &＃61; w;while (p !&＃61; -1) {s.push(p);p &＃61; from[p];}while (!s.isEmpty()) {res.add(s.pop());}return res;}public int length(int w) {if (w <0 || w >&＃61; g.getNodesCount()) {return -1;}return order[w];}
}