Java数据结构：图
2020-07-21 本文已影响0人
Patarw
一、为什么要有图
- 线性表局限于一个直接前驱和一个直接后继的关系
- 树也只能有一个直接前驱也就是父节点
- 当我们需要表示多对多的关系时，就需要用到图这种数据结构
基本介绍
- 图是一种数据结构，其中结点可以具有零个或多个相邻元素。两个结点之间的连接称为边(edge)； 结点也可以称为顶点(vertex)。
- 路径: 比如从 D -> C 的路径有
- D->B->C
- D->A->B->C
-
1.无向图： 顶点之间的连接没有方向，比如A-B,
即可以是 A-> B 也可以 B->A .
-
2.有向图： 顶点之间的连接有方向，比如A-B,
只能是 A-> B 不能是 B->A .
- 3.带权图：这种边带权值的图也叫网
二、图的表示方式
图的表示方式有两种：二维数组表示（邻接矩阵）；链表表示（邻接表）。
- 1.邻接矩阵表示：邻接矩阵是表示图形中顶点之间相邻关系的矩阵
- 2.邻接表表示：邻接矩阵需要为每个顶点都分配n个边的空间，其实有很多边都是不存在,会造成空间的一定损失.而邻接表的实现只关心存在的边，不关心不存在的边。因此没有空间浪费，邻接表由数组+链表组成。
-
代码实现邻接矩阵：
以这个图为例
public class ArrayQueue {
private ArrayList<String> vertexList; //存储顶点集合
private int[][] edgs; //存储对应邻接矩阵
private int numOfEdgs; //表示边的数目
private boolean[] isVisited; //记录某个节点是否被访问
public static void main(String[] args) {
int n = 5;
String VertexValue[] = {"A","B","C","D","E"};
ArrayQueue a = new ArrayQueue(n);
for(String val : VertexValue) {
a.insertVertex(val);
}
//A-B A-C B-C B-D B-E
a.insertEdge(0, 1, 1);
a.insertEdge(0, 2, 1);
a.insertEdge(1, 2, 1);
a.insertEdge(1, 3, 1);
a.insertEdge(1, 4, 1);
a.print();
a.dfs();
}
//构造器,初始化实例
public ArrayQueue(int n) {
edgs = new int[n][n];
vertexList = new ArrayList<>(n);
numOfEdgs = 0;
isVisited = new boolean[n];
}
//插入节点
public void insertVertex(String vertex) {
vertexList.add(vertex);
}
//添加边
public void insertEdge(int v1,int v2,int weight) {
edgs[v1][v2] = weight;
edgs[v2][v1] = weight;
numOfEdgs++;
}
//返回节点个数
public int getNumOfVertex() {
return vertexList.size();
}
//得到边的数目
public int getNumOfEdgs() {
return numOfEdgs;
}
//返回i下表对应的数据
public String getValueByIndex(int i) {
return vertexList.get(i);
}
//返回v1，v2的权值
public int getWeight(int v1,int v2) {
return edgs[v1][v2];
}
//打印图
public void print() {
for(int[] a : edgs) {
for(int i = 0;i < a.length;i++) {
System.out.print(a[i] + " ");
}
System.out.println();
}
}
}
- 打印结果如图：
三、图的遍历方式
- 所谓图的遍历，即是对结点的访问。一个图有那么多个结点，如何遍历这些结点，需要特定策略，一般有两种访问策略: (1)深度优先遍历 (2)广度优先遍历
1、图的深度优先遍历 DFS (Depth First Search)
- 二叉树的前序、中序、后序遍历，本质上也可以认为是深度优先遍历。
- 假设你去参观景点，把每个节点看作为一个景点，那么怎么规划参观路线呢？
- DFS就相当于是一头扎到底的玩法。我们选择一条支路，尽可能不断地深入，如果遇到死路就往回退，回退过程中如果遇到没探索过的支路，就进入该支路继续深入。（这里看出来DFS肯定要用到递归回溯）
- 在图中，我们首先选择景点1的这条路，继续深入到景点4、景点5、景点3、景点6，发现后面没有其他景点了（景点旁边的数字代表探索次序）：
- 于是，我们退回到景点1，然后探索景点7，景点8，又走到了死胡同。于是，退回到景点7，探索景点10：
- 按照这个思路，我们再退回到景点1，探索景点9,最后再退回到景点0，后续依次探索景点2，终于玩遍了整个游乐场：
- 代码实现
//得到下一个邻接节点的下标
public int getFirstNeighbor(int index) {
for(int j = 0;j < vertexList.size();j++) {
if(edgs[index][j] > 0) {
return j;
}
}
return -1;
}
//获取下一位
public int getNextNeighbor(int v1,int v2) {
for(int j = v2 + 1;j < vertexList.size();j++) {
if(edgs[v1][j] > 0) {
return j;
}
}
return -1;
}
//深度优先遍历算法
public void dfs(boolean[] isVisited,int i) {
//首先访问该节点
System.out.print(getValueByIndex(i) + "->");
isVisited[i] = true; //设置节点为已访问
int w = getFirstNeighbor(i);
while(w != -1) {
if(!isVisited[w]) {
dfs(isVisited,w);
}
w = getNextNeighbor(i,w);
}
}
//对dfs进行一个重载，遍历我们所有的节点，并进行dfs
public void dfs() {
//遍历所有节点，进行dfs[回溯]
for(int i = 0;i < getNumOfVertex();i++) {
if(!isVisited[i]) {
dfs(isVisited,i);
}
}
}
2、图的广度优先遍历 BFS (Broad First Search)
二叉树的层次遍历，本质上也可以认为是深度优先遍历。
- 在图中，我们首先探索景点0的相邻景点1、2、3、4
- 接着，我们探索与景点0相隔一层的景点7、9、5、6：
- 最后，我们探索与景点0相隔两层的景点8、10：
- 代码实现:
//广度优先遍历算法
public void bfs(boolean[] isVisited,int i) {
int u = 0;
int w = 0;
LinkedList q = new LinkedList(); //用链表模拟队列
System.out.print(getValueByIndex(i) + "=>");
isVisited[i] = true;
q.addLast(i);
while(!q.isEmpty()) {
u = (Integer)q.removeFirst();
w = getFirstNeighbor(u);
while(w != -1) {
if(!isVisited[w]) {
System.out.print(getValueByIndex(w) + "=>");
isVisited[w] = true;
q.addLast(w);
}
w = getNextNeighbor(u,w);
}
}
}
五、图的深度优先VS 广度优先
- 深度优先遍历顺序为 1->2->4->8->5->3->6->7
- 广度优先算法的遍历顺序为：1->2->3->4->5->6->7->8
