文章目录
- 图
- 图的存储
- 图的搜索（无向无权图）
- 代码演示
图
图中包含 顶点、边、度，无向图，有向图，无权图，带权图，其中 度表示一个顶点包含多少条边，有出度和入度。
图的存储
- 邻接矩阵
代码
/**
* 图的存储结构
*/
public class Graph {
// 存储顶点
private ArrayList<String> vertextList;
// 需要一个二维数组，存储邻接矩阵
private int[][] edges;
// 边的个数
private int numofEdges;
// 顶点是否已经访问
private static boolean[] isVisited;
// n: 边数
public Graph(int n) {
vertextList = new ArrayList<>();
isVisited = new boolean[n];
edges = new int[n][n];
numofEdges = 0;
}
// 如何添加顶点
public void insertVertex(String vertex) {
vertextList.add(vertex);
}
/**
* @param e1
* @param e2
* @param weight 边的权值，0代表无边，1代表有边
*/
public void insertEdges(int e1, int e2, int weight) {
edges[e1][e2] = weight;
edges[e2][e1] = weight;
numofEdges++;
}
// 返回节点的个数
public int getNumofVertex() {
return vertextList.size();
}
// 返回边的个数
public int getNumofEdges() {
return numofEdges;
}
// 获取临界矩阵对应下标的值
public int getWeight(int e1, int e2) {
return edges[e1][e2];
}
public String getValueByIndex(int index) {
return vertextList.get(index);
}
// 显示矩阵
public void showGraph() {
for (int[] e : edges) {
System.out.println(Arrays.toString(e));
}
}
// 获取第一个邻接点的下标
public int getFirstNeighbor(int index) {
for (int i = 0; i < vertextList.size(); i++) {
if (edges[index][i] > 0) {
return i;
}
}
return -1;
}
// 通过前一个邻接节点的下标获取下一个邻接节点
public int getNextNeighbor(int e1, int e2) {
for (int i = e2 + 1; i < vertextList.size(); i++) {
if (edges[e1][i] > 0) {
return i;
}
}
return -1;
}
相当于一个二维数组，当存储无向图时，两点相连标1，当存储有向图时，横向的是起始点指向相应的点标1。优点是简单高效，缺点是浪费空间
- 邻接表存储
无向图是将每个点相连的点用链表存储，无向图邻接表中元素的边是途中边的2倍。
有向图是将每个点指向的点列出来，有向图邻接表中元素的边与图中的边数相同。
图的搜索（无向无权图）
- 广度优先搜索（使用队列）
过程：
- 初始状态，将原定点放入队列
- 取出堆首节点（搜索数据），将这个堆首的后继未访问过的顶点放入队列
- 重复2步骤
- 最终取出所有的对首节点即为搜索数据
代码
// 广度优先遍历
public void bfs(boolean[] ifVisited, int index) {
// 获得头节点
int headIndex;
// 邻接点w
int w;
// 用队列模拟操作
LinkedList<Integer> linkedList = new LinkedList<>();
// 输出当前节点
System.out.print(getValueByIndex(index) + "->");
// 节点访问，进行标记
isVisited[index] = true;
// 队列中存入下标
linkedList.add(index);
// 当队列非空，就继续执行，负责结束。
while (!linkedList.isEmpty()) {
// 获取头节点下标
headIndex = linkedList.removeFirst();
// 获取邻接点下标
w = getFirstNeighbor(headIndex);
while (w > 0) {
// 若邻接点w存在，访问邻接点，并标记已访问，节点w入队列
while (!isVisited[w]) {
System.out.print(getValueByIndex(w) + "->");
isVisited[w] = true;
linkedList.add(w);
}
// 下一个邻接节点要出来
w = getNextNeighbor(headIndex, w);
}
}
}
public void bfs() {
isVisited = new boolean[getNumofVertex()];
for (int i = 0; i < getNumofVertex(); i++) {
if (!isVisited[i]) {
bfs(isVisited, i);
}
}
}
- 深度优先搜索（使用栈）
过程：
- 初始状态，将原定点放入栈中
- 取出栈顶元素（搜索栈），将这个栈顶的后继未访问过的顶点放入栈
- 重复2步骤
- 最终取出所有的栈顶元素即为搜索数据
代码
// 深度优先遍历
public void dfs(boolean[] isVisited, int index) {
System.out.print(getValueByIndex(index) + "->");
// 如果为true，表示当前节点已经访问
isVisited[index] = true;
// 获取邻接点的下标
int w = getFirstNeighbor(index);
while (w != -1) {
if (!isVisited[w]) {
dfs(isVisited, w);
}
w = getNextNeighbor(index, w);
}
}
// 深度遍历时需要回溯
public void dfs() {
for (int i = 0; i < getNumofVertex(); i++) {
if (!isVisited[i]) {
dfs(isVisited, i);
}
}
}
代码演示
import java.util.*;
/**
* 图的存储结构
*/
public class Graph {
// 存储顶点
private ArrayList<String> vertextList;
// 需要一个二维数组，存储邻接矩阵
private int[][] edges;
// 边的个数
private int numofEdges;
// 顶点是否已经访问
private static boolean[] isVisited;
// n: 边数
public Graph(int n) {
vertextList = new ArrayList<>();
isVisited = new boolean[n];
edges = new int[n][n];
numofEdges = 0;
}
// 如何添加顶点
public void insertVertex(String vertex) {
vertextList.add(vertex);
}
/**
* @param e1
* @param e2
* @param weight 边的权值，0代表无边，1代表有边
*/
public void insertEdges(int e1, int e2, int weight) {
edges[e1][e2] = weight;
edges[e2][e1] = weight;
numofEdges++;
}
// 返回节点的个数
public int getNumofVertex() {
return vertextList.size();
}
// 返回边的个数
public int getNumofEdges() {
return numofEdges;
}
// 获取临界矩阵对应下标的值
public int getWeight(int e1, int e2) {
return edges[e1][e2];
}
public String getValueByIndex(int index) {
return vertextList.get(index);
}
// 显示矩阵
public void showGraph() {
for (int[] e : edges) {
System.out.println(Arrays.toString(e));
}
}
// 获取第一个邻接点的下标
public int getFirstNeighbor(int index) {
for (int i = 0; i < vertextList.size(); i++) {
if (edges[index][i] > 0) {
return i;
}
}
return -1;
}
// 通过前一个邻接节点的下标获取下一个邻接节点
public int getNextNeighbor(int e1, int e2) {
for (int i = e2 + 1; i < vertextList.size(); i++) {
if (edges[e1][i] > 0) {
return i;
}
}
return -1;
}
// 深度优先遍历
public void dfs(boolean[] isVisited, int index) {
System.out.print(getValueByIndex(index) + "->");
// 如果为true，表示当前节点已经访问
isVisited[index] = true;
// 获取邻接点的下标
int w = getFirstNeighbor(index);
while (w != -1) {
if (!isVisited[w]) {
dfs(isVisited, w);
}
w = getNextNeighbor(index, w);
}
}
// 深度遍历时需要回溯
public void dfs() {
for (int i = 0; i < getNumofVertex(); i++) {
if (!isVisited[i]) {
dfs(isVisited, i);
}
}
}
// 广度优先遍历
public void bfs(boolean[] ifVisited, int index) {
// 获得头节点
int headIndex;
// 邻接点w
int w;
// 用队列模拟操作
LinkedList<Integer> linkedList = new LinkedList<>();
// 输出当前节点
System.out.print(getValueByIndex(index) + "->");
// 节点访问，进行标记
isVisited[index] = true;
// 队列中存入下标
linkedList.add(index);
// 当队列非空，就继续执行，负责结束。
while (!linkedList.isEmpty()) {
// 获取头节点下标
headIndex = linkedList.removeFirst();
// 获取邻接点下标
w = getFirstNeighbor(headIndex);
while (w > 0) {
// 若邻接点w存在，访问邻接点，并标记已访问，节点w入队列
while (!isVisited[w]) {
System.out.print(getValueByIndex(w) + "->");
isVisited[w] = true;
linkedList.add(w);
}
// 下一个邻接节点要出来
w = getNextNeighbor(headIndex, w);
}
}
}
public void bfs() {
isVisited = new boolean[getNumofVertex()];
for (int i = 0; i < getNumofVertex(); i++) {
if (!isVisited[i]) {
bfs(isVisited, i);
}
}
}
public static void main(String[] args) {
int n = 4;
Graph graph = new Graph(n);
// 添加顶点
graph.insertVertex("A");
graph.insertVertex("B");
graph.insertVertex("C");
graph.insertVertex("D");
// 添加边
graph.insertEdges(1, 0, 1);
graph.insertEdges(1, 3, 1);
graph.insertEdges(3, 0, 1);
graph.insertEdges(3, 2, 1);
graph.showGraph();
System.out.println("深度优先遍历");
graph.dfs();
System.out.println("\n广度优先遍历");
graph.bfs();
}
}
