文章目录
前言1.什么是图？2.图如何表示？3.如何创建一个邻接表一、深度优先搜索（Depth First Search）二、广度优先搜索（Breadth First Search）三、寻找路径四、测试前言
1.什么是图？
图（graph）是由一些点（vertex）和这些点之间的连线（edge）所组成的；其中，点通常称为顶点（vertex），而点到点之间的连线通常称之为边或者弧（edge）。通常记为G=（V,E）。
大概张这样：
2.图如何表示？
图的表示有两种方式：
邻接矩阵
邻接表
如何合理的使用这两种存储方式：
设 顶点个数 V、边的个数 E
那么从空间复杂度来说：邻接矩阵为O(V^2)、邻接表为O(V+E)
从上面两个空间复杂度可以得出：
对于边较少的图，明显采用邻接表较为合理。
3.如何创建一个邻接表
从上面的存储图可以得知，邻接表都是通过每个顶点，后面连接相关联的边信息。
Vertex.java
package com.kiger.graph;/*** @ClassName Vertex* @Description 邻接表的顶点* 该类借鉴于一种Bag的数据结构* @Author zk_kiger* @Date /11/12 22:30* @Version 1.0*/public class Vertex<T> {// 存储顶点数据private T data;// 下一条边信息private Edge first;// 该顶点连顶点数private int size;public Vertex() {}// 使用链表的头插法将边结点的信息插入顶点后面public void add(Edge item) {if (first == null) {first = item;} else {item.setNext(first);first = item;}size++;}// 获得下标为index的元素public int get(int index) {if (index >= size)return 0;Edge cur = first;while (index != 0) {cur = cur.getNext();--index;}return cur.getVertexIndex();}// 获取元素个数public int size() {return size;}// 判断是否为空public boolean isEmpty() {return (first == null);}public T getData() {return data;}public void setData(T data) {this.data = data;}public Edge getFirst() {return first;}public void setFirst(Edge first) {this.first = first;}@Overridepublic String toString() {return "Vertex{" +"data=" + data +", first=" + first +", size=" + size +'}';}}
Edge.java
package com.kiger.graph;/*** @ClassName Edge* @Description 边结点* @Author zk_kiger* @Date /11/12 22:32* @Version 1.0*/public class Edge {// 存在边的顶点下标private int vertexIndex;// 与顶点之间的权值private int weight;// 相连的下一个边private Edge next;public Edge() {}public Edge(int vertexIndex, Edge next) {this.vertexIndex = vertexIndex;this.next = next;}public Edge(int vertexIndex, int weight, Edge next) {this.vertexIndex = vertexIndex;this.weight = weight;this.next = next;}public int getVertexIndex() {return vertexIndex;}public void setVertexIndex(int vertexIndex) {this.vertexIndex = vertexIndex;}public int getWeight() {return weight;}public void setWeight(int weight) {this.weight = weight;}public Edge getNext() {return next;}public void setNext(Edge next) {this.next = next;}}
为了操作方便预先创建了下面图：
Graph.java
package com.kiger.graph;import java.util.Scanner;/*** @ClassName Graph* @Description 无向图* @Author zk_kiger* @Date /11/13 22:22* @Version 1.0*/public class Graph{private int V; // 顶点数目private int E; // 边的数目private Vertex<Integer>[] adj; // 邻接表private Graph(int V) {this.V = V;this.E = 0;// 实例化邻接表adj = new Vertex[V];for (int i = 0; i < V; i++) {adj[i] = new Vertex<>();adj[i].setData(i);}}public Graph(Scanner input) {// 读取V并初始化图/*this(input.nextInt());int E = input.nextInt();for (int i = 0; i < E; i++) {int v = input.nextInt();int w = input.nextInt();addEdge(v, w);}*/this(6);int E = 8;int a[][] = {{0, 5},{2, 4},{2, 3},{1, 2},{0, 1},{0, 4},{3, 5},{0, 2}};for (int i = 0; i < a.length; i++) {addEdge(a[i][0], a[i][1]);}}private void addEdge(int v, int w) {// 将w添加到v的链表中adj[v].add(new Edge(w, null));adj[w].add(new Edge(v, null));E++;}// 获得某个顶点的链表public Vertex getVertex(int v) {return adj[v];}public int getV() {return V;}public void setV(int v) {V = v;}public int getE() {return E;}public void setE(int e) {E = e;}}
一、深度优先搜索（Depth First Search）
图的深度优先算法有点类似于树的前序遍历，首先图中的顶点均未被访问，确定某一顶点，从该顶点出发，依次访问未被访问的邻接点，直到某个邻接点没有未被访问邻接点时，则回溯父节点（此处我们将先被访问的节点当做后被访问节点的父节点，例如对于节点A、B，访问顺序是A ->B，则称A为B的父节点），找到父节点未被访问的子节点；如此类推，直到所有的顶点都被访问到。
DepthFirstSearch.java
package com.kiger.graph;/*** @ClassName DepthFirstSearch* @Description 深度优先搜索* @Author zk_kiger* @Date /11/13 22:41* @Version 1.0*/public class DepthFirstSearch {private boolean[] marked;public DepthFirstSearch() {}public void dfs(Graph G, int v) {// 初始化标记数组marked = new boolean[G.getV()];dfs_(G, v);}private void dfs_(Graph G, int v) {marked[v] = true;System.out.print(v + " ");Vertex vertex = G.getVertex(v);for (int i = 0; i < vertex.size(); i++) {int next = vertex.get(i);if (!marked[next])dfs_(G, next);}}}
二、广度优先搜索（Breadth First Search）
从图中的某个顶点出发，访问它所有的未被访问邻接点，然后分别从这些邻接点出发访问它的邻接点。说白了就是一层一层的访问，“浅尝辄止”！
注意，广度优先搜索的存储方式一般是以队列的方式存储。
可以尝试使用优先队列广度优先搜索的方法实现一下Dijkstra算法。
BreadthFirstSearch.java
package com.kiger.graph;import java.util.ArrayDeque;/*** @ClassName BreadthFirstPaths* @Description 广度优先搜索* @Author zk_kiger* @Date /11/15 21:00* @Version 1.0*/public class BreadthFirstSearch {private boolean[] marked;public BreadthFirstSearch() {}// 从顶点v开始广搜public void bfs(Graph G, int v) {marked = new boolean[G.getV()];ArrayDeque<Integer> queue = new ArrayDeque<>();marked[v] = true;queue.add(v);while (!queue.isEmpty()) {int curVertex = queue.remove();System.out.print(curVertex + " ");Vertex vertex = G.getVertex(curVertex);for (int i = 0; i < vertex.size(); i++) {int nextVertex = vertex.get(i);if (!marked[nextVertex]) {marked[nextVertex] = true;queue.add(nextVertex);}}}}}
三、寻找路径
如何通过搜索将S点到V点的路径输出？
我们可以使用一个数组edgeTo[]，存储当前顶点的父结点，之后通过反遍历获得路径。
Paths.java
package com.kiger.graph;import java.awt.*;import java.util.ArrayDeque;import java.util.Stack;/*** @ClassName Paths* @Description 寻找路径* @Author zk_kiger* @Date /11/15 20:32* @Version 1.0*/public class Paths {private boolean[] marked;private int[] edgeTo;// 记录下标顶点上一次访问的最后一个顶点 - 用于后面的路径寻找private final int s;// 起点public Paths(Graph G, int s) {marked = new boolean[G.getV()];edgeTo = new int[G.getV()];this.s = s;}// 广搜记录起点s开始的路径到数组edgeTopublic void bfs(Graph G) {bfs(G, s);}private void bfs(Graph G, int v) {ArrayDeque<Integer> queue = new ArrayDeque<>();marked[v] = true;queue.add(v);while (!queue.isEmpty()) {int curVertex = queue.remove();Vertex vertex = G.getVertex(curVertex);for (int i = 0; i < vertex.size(); i++) {int nextVertex = vertex.get(i);if (!marked[nextVertex]) {// !!! 存储上一个顶点idedgeTo[nextVertex] = curVertex;marked[nextVertex] = true;queue.add(nextVertex);}}}}// 深搜记录起点s开始的路径到数组edgeTopublic void dfs(Graph G) {dfs(G, s);}private void dfs(Graph G, int v) {marked[v] = true;Vertex vertex = G.getVertex(v);for (int i = 0; i < vertex.size(); i++) {int next = vertex.get(i);if (!marked[next]) {// !!! 存储上一个顶点idedgeTo[next] = v;dfs(G, next);}}}// 是否存在从s到v的路径public boolean hasPathTo(int v) {return marked[v];}// s到v的路径，如果不存在则返回null// 返回一个栈path便于遍历public Iterable<Integer> pathTo(int v) {if (!hasPathTo(v))return null;Stack<Integer> path = new Stack<>();for (int i = v; i != s ; i = edgeTo[i]) {path.push(i);}path.push(s);return path;}}
四、测试
RunTest.java
package com.kiger.graph;import java.util.Scanner;/*** @ClassName RunTest* @Description* @Author zk_kiger* @Date /11/14 10:59* @Version 1.0*/public class RunTest {public static void main(String[] args) {Graph G = new Graph(new Scanner(System.in));DepthFirstSearch depthFirstSearch = new DepthFirstSearch();BreadthFirstSearch breadthFirstSearch = new BreadthFirstSearch();Paths paths = new Paths(G, 0);System.out.println("从顶点 0 深搜路径如下：");depthFirstSearch.dfs(G, 0);System.out.println();System.out.println("从顶点 0 广搜路径如下：");breadthFirstSearch.bfs(G, 0);System.out.println();System.out.println("使用深搜输出顶点 0 到顶点 5 的路径：");paths.dfs(G);Iterable<Integer> path = paths.pathTo(5);for (Integer v :path) {System.out.print(v + " ");}System.out.println();System.out.println("使用广搜输出顶点 0 到顶点 5 的路径：");paths.bfs(G);Iterable<Integer> path_ = paths.pathTo(5);for (Integer v :path_) {System.out.print(v + " ");}}}
测试结果：
