参考自文章：https://blog.csdn.net/ntt5667781/article/details/52743342
1、图的存储
在开始各类图算法之前，先将图的结构进行分类。
图的表示，在实际实现过程中，有以下几种基本的方式可以来表示图。
1） 邻接矩阵：对于较小或者中等规模的图的构造较为适用，因为需要V*V大小的空间。
2） 边的数组：使用一个简单的自定义edge类，还有两个变量，分别代表边的两个端点编号，实现简单，但是在求每个点的邻接点的时候实现较为困难。
3） 邻接表数组：较为常用，使用一个以顶点为索引的数组，数组每个元素都是和该顶点相邻的顶点列表，这种数组占空间相对于邻接矩阵少了很多，并且能很好的找到某个给定点的所有邻接点。
按照图中边的方向将图分成有向图和无向图：
1）无向图：图中的边没有方向。
2）有向图：图中的边有方向。
对于有向图和无向图的具体实现表示可以使用前面介绍的三种方法，两种图在表示的时候大部分的实现代码都是一致的。
普通无向图的邻接数组表示方法以及邻接矩阵表示方法的具体实现代码如下：
package graph;
import java.util.*;
public class Graph {
private int V;
private int E;
private List<Integer>[] adj;
private int[][] a;
public Graph(int V){
this.E = 0;
this.V = V;
adj = new ArrayList[V];
a = new int[V][V];
for(int i=0;i<V;i++){
adj[i] = new ArrayList<Integer>();
}
}
//无向图是没有方向的，所以需要在两个定点添加顶点信息
public void addEdge(int v1,int v2){
a[v1][v2] = 1;
a[v2][v1] = 1;
adj[v1].add(v2);
adj[v2].add(v1);
this.E++;
}
public int getV(){
return this.V;
}
public int getE(){
return this.E;
}
//邻接数组返回给定点的所有邻接点
public List<Integer> adj(int i){
return adj[i];
}
//邻接矩阵返回给定点的所有邻接点
public List<Integer> adj1(int i){
List<Integer> list = new ArrayList<Integer>();
for(int j = 0;j<this.V;j++){
if(a[i][j] == 1){
list.add(j);
}
}
return list;
}
public static void main(String[] args){
Graph graph = new Graph(5);
graph.addEdge(0,1);
graph.addEdge(0,3);
graph.addEdge(3,1);
System.out.println(graph.getE());
List<Integer> adj = graph.adj(0);
for(int i=0;i<adj.size();i++){
System.out.print(adj.get(i) + " ");
}
}
}
无权有向图的具体实现代码如下：
package graph;
import java.util.*;
public class DirectedGraph {
private int V; //图中的顶点数目
private int E; //图中的边数目
private List<Integer>[] adj; //邻接数组
private int[][] a; //邻接矩阵
public DirectedGraph(int V) {
this.E = 0;
this.V = V;
adj = new ArrayList[V];
a=new int[V][V];
for (int i = 0; i < V; i++)
adj[i] = new ArrayList<>();
}
//由于无向图中的边是有方向的，所以添加边的时候需要只需要在起始点的邻接列表中添加顶点信息。
public void addEdge(int v1, int v2) {
a[v1][v2]=1;
adj[v1].add(v2);
E++;
}
public int getV() {
return V;
}
public int getE() {
return E;
}
//邻接数组返回给定点的所有邻接点
public List<Integer> adj(int i) {
return adj[i];
}
//邻接矩阵返回给定点的所有邻接点
public List<Integer> adj1(int i){
List<Integer> list=new ArrayList<Integer>();
for(int j=0;j<V;j++){
if(a[i][j] == 1)
list.add(j);
}
return list;
}
public static void main(String[] args){
DirectedGraph graph = new DirectedGraph(5);
graph.addEdge(0,1);
graph.addEdge(0,3);
graph.addEdge(3,1);
System.out.println(graph.getE());
List<Integer> adj = graph.adj1(0);
for(int i=0;i<adj.size();i++){
System.out.print(adj.get(i) + " ");
}
}
}
2、图的遍历算法
2.1 深度优先搜索
介绍两种比较基础的图遍历算法，广度优先搜索和深度优先搜索。
1）深度优先搜索：这是一种典型的递归算法用来搜索图（遍历所有的顶点）；
思想：从图的某个顶点i开始，将顶点i标记为已访问顶点，并将访问顶点i的邻接列表中没有被标记的顶点j，将顶点j标记为已访问，并在访问顶点j的邻接列表中未被标记的顶点k依次深度遍历下去，直到某个点的所有邻接列表中的点都被标记为已访问后，返回上层。重复以上过程直到图中的所有顶点都被标记为已访问。
深度优先遍历和树的先序访问非常类似，尽可能深的去访问节点。深度优先遍历的大致过程（递归版本）：
a）在访问一个节点的时候，将其设置为已访问。
b）递归的访问被标记顶点的邻接列表中没有被标记的所有顶点
（非递归版本）:
图的非递归遍历我们借助栈来实现。
a）如果栈为空，则退出程序，否则，访问栈顶节点，但不弹出栈点节点。
b）如果栈顶节点的所有直接邻接点都已访问过，则弹出栈顶节点，否则，将该栈顶节点的未访问的其中一个邻接点压入栈，同时，标记该邻接点为已访问，继续步骤a。
该算法访问顶点的顺序是和图的表示有关的，而不只是和图的结构或者是算法有关。
深度优先探索是个简单的递归算法(当然借助栈也可以实现非递归的版本)，但是却能有效的处理很多和图有关的任务，比如：
a) 连通性：ex:给定的两个顶点是否联通 or 这个图有几个联通子图。
b) 单点路径：给定一幅图和一个固定的起点，寻找从s到达给定点的路径是否存在，若存在，找出这条路径。
寻找路径：
为了实现这个功能，需要在上面实现的深度优先搜索中中增加实例变量edgeTo[]，它相当于绳索的功能，这个数组可以找到从每个与起始点联通的顶点回到起始点的路径（具体实现的思路非常巧妙： 从边v-w第一次访问w的时候，将edgeTo[w]的值跟新为v来记住这条道路，换句话说，v-w是从s到w的路径上最后一条已知的边，这样搜索结果就是一条以起始点为根结点的树，也就是edgeTo[]是个有父链接表示的树。）
深度优先搜索的递归实现版本和非递归版本
package graph;
import java.util.*;
public class DepthFirstSearch {
//用来记录顶点的标记状态 true表示为已访问，false表示为未被访问。
private boolean[] marked;
private int count;
//用来记录顶点索引所对应的父结点，假设遍历是从s到达的t那么edgeTo[s所对的所用]=t;
private int[] edgeTo;
//起始点
private int s;
private Stack<Integer> stack = new Stack<Integer>();
public DepthFirstSearch(Graph G,int s){
marked = new boolean[G.getV()];
edgeTo = new int[G.getV()];
this.s = s;
stack.push(s);
dfs(G,s);
}
//递归形式实现
public void dfs(Graph G,int s){
marked[s] = true;
count ++;
for(int temp:G.adj(s)){
if(!marked[temp]){
edgeTo[temp] = s;
dfs(G,temp);
}
}
}
//非递归形式实现
public void dfs(Graph G){
while(!stack.isEmpty()){
s = stack.peek();
boolean needPop = true;
marked[s] = true;
count++;
for(int temp:G.adj(s)){
if(!marked[temp]){
needPop = false;
stack.push(temp);
edgeTo[temp]=s;
break;
}
}
if(needPop)
stack.pop();
}
}
public boolean hasPathTo(int v){
return marked[v];
}
//得到到达v的一个路径
public List<Integer> pathTo(int v){
if(!hasPathTo(v))
return null;
List<Integer> list = new ArrayList<Integer>();
list.add(v);
v = edgeTo[v];
while(v!=s) {
list.add(v);
v = edgeTo[v];
}
list.add(s);
Collections.reverse(list);
return list;
}
public int count(){
return count;
}
public static void main(String[] args){
int V = 5;
Graph G=new Graph(V);
G.addEdge(0,1);
G.addEdge(0,2);
G.addEdge(1,3);
G.addEdge(3,4);
int s=0;
DepthFirstSearch dfs=new DepthFirstSearch(G,s);
for(int v=0;v<G.getV();v++){
if(dfs.hasPathTo(v))
for(int x:dfs.pathTo(v))
if(x==s)
System.out.print(x);
else
System.out.print("-"+x);
System.out.println();
}
}
}
DFS其实还可以解决很多在无向图中的基础性问题,比如：
计算图中的连通子图的数量
package graph;
public class ConnectComponent {
private boolean[] marked;
private int[] id;
private int count;
public ConnectComponent(Graph G){
marked = new boolean[G.getV()];
id = new int[G.getV()];
for(int i=0;i<G.getV();i++){
if(!marked[i]){
dfs(G,i);
count++;
}
}
}
public void dfs(Graph G,int s){
marked[s] = true;
id[s] = count;
for(int temp : G.adj(s)){
if(!marked[temp]){
dfs(G,temp);
}
}
}
public boolean connected(int v,int w){
return id[v] == id[w];
}
public int id(int v){
return id[v];
}
public int getCount(){
return count;
}
public static void main(String[] args){
int V = 5;
Graph G=new Graph(V);
G.addEdge(0,1);
G.addEdge(0,2);
G.addEdge(3,4);
int s=0;
ConnectComponent graph = new ConnectComponent(G);
System.out.println(graph.getCount());
System.out.println(graph.connected(0,2));
System.out.println(graph.connected(0,4));
}
}
检测图中是否有环
package graph;
public class CycleDetect {
private boolean[] marked;
private boolean flag;
public CycleDetect(Graph G){
marked = new boolean[G.getV()];
for(int s=0;s<G.getV();s++){
if(!marked[s]){
dfs(G,s,s);
}
}
}
public void dfs(Graph G,int s,int initial){
marked[s] = true;
for(int temp:G.adj(s)){
if(!marked[temp]){
dfs(G,temp,initial);
} else{
if(temp == initial){
flag = true;
return;
}
}
}
}
public boolean hasCycle(){
return flag;
}
}
二分图问题
即能否用两种颜色给这个图进行着色
package graph;
public class IsBiagraph {
private boolean[] marked;
private boolean[] color;
private boolean flag = true;
public IsBiagraph(Graph G){
marked = new boolean[G.getV()];
color = new boolean[G.getV()];
for(int s = 0;s<G.getV();s++){
if(!marked[s]){
dfs(G,s);
}
}
}
public void dfs(Graph G,int s){
marked[s] = true;
for(int temp:G.adj(s)){
if(!marked[temp]){
color[temp] = !color[s];
dfs(G,temp);
}
else{
if(color[temp]==color[s])
flag = false;
}
}
}
public boolean isBiagragh(){
return flag;
}
}
有关二分图的博客参考：https://blog.csdn.net/x_y_q_/article/details/51920683
2.2 广度优先搜索
前面说过，深度优先搜索得到的路径不仅取决于图的结构，还取决于图的表示以及递归调用的性质，但是如果要求最短的路径（给定图G和起始点s寻找给定点v和s间是否存在路径，如果存在，找出最短的路径），那么使用前面的DFS算法并不能解决该问题，所以出现了广度优先搜索BFS来实现这个目的，广度优先搜索也是其他算法的基础。
在程序中，搜索一幅图的时候会遇到有很多条边都需要被遍历的情况，我们会选择其中一条并将其他边留到以后再继续搜索，在DFS中使用栈结构，使用LIFO的规则来描述，从有待搜索的通道中选取最晚遇到的那个通道，然而在BFS算法中，我们希望按照与起点的距离来遍历所有的顶点，使用FIFO（队列）来进行搜索，也就是搜索最先遇到的那个通道。
BFS:使用一个队列来保存所有已经被标记过的但是其邻接点还未被检查过的顶点，现将顶点加入队列中，然后重复下面的操作，直至队列为空：
1）取队列中的下一个顶点v并标记它
2）将与v相邻的所有的未被标记的顶点加入队列中。
广度优先算法
package graph;
import java.util.*;
public class BreadFirstSearch {
private boolean[] marked;
private int[] edgeTo;
//起点
private int s;
public BreadFirstSearch(Graph G,int s){
marked = new boolean[G.getV()];
edgeTo = new int[G.getV()];
this.s = s;
bfs(G,s);
}
public void bfs(Graph G,int s){
Queue<Integer> queue = new LinkedList<Integer>();
marked[s] = true;
queue.offer(s);
while(!queue.isEmpty()){
s = queue.poll();
for(int temp:G.adj(s)){
if(!marked[temp]){
marked[temp] = true;
edgeTo[temp] = s;
queue.offer(temp);
}
}
}
}
public boolean hasPathTo(int v){
return marked[v];
}
public List<Integer> pathTo(int v){
List<Integer> path = new ArrayList<Integer>();
if(!marked[v]) return path;
path.add(v);
v = edgeTo[v];
while(v!=s){
path.add(v);
v = edgeTo[v];
}
path.add(s);
Collections.reverse(path);
return path;
}
}
