一、图的概念
- 图：图是由一组顶点和一组能够将两个顶点相连的边组成的
- 顶点：用一张符号表来为顶点的名字和0到V-1的整数值建立一一对应的关系，顶点可以表示一个城市，一个网页等
- 边：两个顶点之间的连接关系
- 邻接：两个顶点通过一条边相连，说明两个节点邻接，这条边依附于这两个顶点
- 子图：由一幅图的所有边的一个子集（包括它们所依附的所有顶点）组成的图
- 路径：由边顺序连接的一系列顶点，路径的长度为其所包含的边数
- 连通图：从任意一个顶点都存在一条路径到达另一个任意顶点的图
- 非连通图：一般由若干个连通的部分组成，他们都是其极大连通子图
- 无环图：不包含环的图
- 生成树森林：所有连通子图的生成树的集合
- 自环：一条连接一个顶点和其自身的边
- 平行边：连接同一对顶点的两条边
- 环：一条至少含有一条边且起点和终点相同的路径
- 无向图：边仅仅连接两个顶点，没有其他含义
- 有向图：边不仅连接两个顶点，并且具有方向
- 度：某个顶点的度数依附于他的边的总数
二、图的表示
- 要表示一幅图，只需要表示清楚以下两部分内容即可：图中所有的顶点+所有连接顶点的边
- 邻接矩阵：使用一个V*V的二维数组int[V][V] adj,把索引的值看做是顶点；如果顶点v和顶点w相连，我们只需要将adj[v][w]和adj[w][v]的值设置为1,否则设置为 0 。邻接矩阵这种存储方式的空间复杂度是V^2的，如果我们处理的问题规模比较大的话，内存空间极有可能不够用。
- 邻接表：使用一个大小为V的数组 Queue[V] adj，把索引看做是顶点；每个索引处adj[v]存储了一个队列，该队列中存储的是所有与该顶点相邻的其他顶点
- 创建图的表示类
package 图;
import java.util.LinkedList;
import java.util.Queue;
public class Graph1 {
private int V; //顶点数
private int E;//边数
private Queue<Integer>[] adj;//邻接表
public Graph1(int V) {
this.V = V;
this.E = 0;
this.adj = new Queue[V];
for (int i = 0; i < V; i++) {
adj[i] = new LinkedList<Integer>();
}
}
//获取顶点数
public int getV() {
return V;
}
//获取边数
public int getE() {
return E;
}
//向图中添加一条边 v-w
public void addEdge(int v, int w) {
/*
在无向图中，边是没有方向的，所以该边既可以说是从v到w的边，
又可以说是从w到v的边，因此，需要让w出现在v的邻接表中，并且还要让v出现在w的邻接表中
*/
adj[v].offer(w);
adj[w].offer(v);
E++;
}
//向图中添加一条边 v-w，方法重载
public void addEdge(int... Edges){
if(Edges.length%2==0){
for (int i = 0; i <Edges.length ; i+=2) {
addEdge(Edges[i],Edges[i+1]);
}
}else throw new IllegalStateException("顶点数必须为2的整数倍");
}
// 获取和V相邻的所有节点
public Queue<Integer> adj(int V) {
return adj[V];
}
// 打印节点
@Override
public String toString() {
StringBuilder s = new StringBuilder("(" + V + " vertices, " + E + " edges)\n");
for (int v = 0; v < V; v++) {
s.append(v).append(": ");
for (int w : this.adj(v)) {
s.append(w).append(" ");
}
s.append("\n");
}
return s.toString();
}
public static void main(String[] args) {
Graph1 g = new Graph1(13);
g.addEdge(0,1,0,2,0,6,0,5,3,5,3,4,4,5,6,4,7,8,9,10,9,11,9,12,11,12);
System.out.println(g); //构建图
}
}
三、深度优先搜索
深度优先搜索：要搜索一幅图，只需要一个递归方法来遍历所有顶点。在访问其中一个节点时将它标记为已访问，并递归的访问它的所有没有被标记过的邻居顶点。
在搜索时，如果遇到一个结点既有子结点，又有兄弟结点，那么先找子结点，然后找兄弟结点。常用于连通分量的判断
package 图;
import java.util.Stack;
public class DepthFirstPaths {
private Graph1 graph;
private int s;//起点
private int[] edgeTo;//从起点到一个顶点的已知路径上的最后一个顶点
private boolean[] visited;//标记已访问过的顶点
public DepthFirstPaths(Graph1 graph, int s) {
this.graph = graph;
this.s = s;
this.edgeTo=new int[graph.getV()];
visited=new boolean[graph.getV()];
dfs(graph,s);
}
// 深度优先搜索
public void dfs(Graph1 graph, int s) {
visited[s]=true;
for (Integer v : graph.adj(s)) {
if(!visited[v]){
edgeTo[v]=s;
dfs(graph,v);
}
}
}
// 是否存在路径
public boolean hasPathTo(int v){
return visited[v];
}
// 存在起点到终点的路径
public Iterable<Integer> pathTo(int v){
if(!hasPathTo(v))return null;
Stack<Integer> path=new Stack<>();
for (int x = v; x!=s ; x=edgeTo[x]) {
path.push(x);
}
path.push(s);
return path;
}
public static void main(String[] args) {
//准备Graph对象
Graph1 G = new Graph1(13);
G.addEdge(0,1);
G.addEdge(0,2);
G.addEdge(0,6);
G.addEdge(0,5);
G.addEdge(5,3);
G.addEdge(5,4);
G.addEdge(3,4);
G.addEdge(4,6);
G.addEdge(7,8);
G.addEdge(9,11);
G.addEdge(9,10);
G.addEdge(9,12);
G.addEdge(11,12);
System.out.println(G);
System.out.println("----------");
DepthFirstPaths paths = new DepthFirstPaths(G, 0);
Iterable<Integer> iterable = paths.pathTo(3);
for (Integer integer : iterable) {
System.out.print(integer+"--");
}
}
}
四、广度优先搜索
广度优先搜索：求单点最短路径常用的经典方法，可以用于求间隔的度数。
在搜索时，如果遇到一个结点既有子结点，又有兄弟结点，那么先找兄弟结点，然后找子结点。
package 图;
import java.util.LinkedList;
import java.util.Queue;
import java.util.Stack;
public class BreadthFirstPaths {
private Graph1 graph;
private int s;//起点
private int[] edgeTo;//从起点到一个顶点的已知路径上的最后一个顶点
private boolean[] visited;//标记已访问过的顶点
public BreadthFirstPaths(Graph1 graph, int s) {
this.graph = graph;
this.s = s;
this.edgeTo=new int[graph.getV()];
visited=new boolean[graph.getV()];
bfs(graph,s);
}
// 广度优先搜索，找到的一定是最短的路径，但并不一定是唯一的最短路径
public void bfs(Graph1 graph, int s) {
Queue<Integer> queue = new LinkedList<>();
visited[s]=true; //标记起点
queue.offer(s); //加入队列
while (!queue.isEmpty()){
Integer w = queue.poll(); //取出邻接的一个顶点
for (Integer v : graph.adj(w)) { //获取该顶点的邻接节点
if(!visited[v]){//如果没有被访问，就标记边，并入队
edgeTo[v]=w;
visited[v]=true;
queue.offer(v);
}
}
}
}
// 是否存在路径
public boolean hasPathTo(int v){
return visited[v];
}
// 存在起点到终点的路径
public Iterable<Integer> pathTo(int v){
if(!hasPathTo(v))return null;
Stack<Integer> path=new Stack<>();
for (int x = v; x!=s ; x=edgeTo[x]) {
path.push(x);
}
path.push(s);
return path;
} public static void main(String[] args) {
//准备Graph对象
Graph1 G = new Graph1(13);
G.addEdge(0,1);
G.addEdge(0,2);
G.addEdge(0,6);
G.addEdge(0,5);
G.addEdge(5,3);
G.addEdge(5,4);
G.addEdge(3,4);
G.addEdge(4,6);
G.addEdge(7,8);
G.addEdge(9,11);
G.addEdge(9,10);
G.addEdge(9,12);
G.addEdge(11,12);
System.out.println(G);
System.out.println("----------");
BreadthFirstPaths paths = new BreadthFirstPaths(G, 0);
Iterable<Integer> iterable = paths.pathTo(4);
for (Integer integer : iterable) {
System.out.print(integer+"--");
}
}
}