1. 为什么要有图
- 前面我们学了线性表和树
- 线性表局限于一个直接前驱和一个直接后继的关系
- 树也只能有一个直接前驱也就是父节点
- 当我们需要 表示多对多的关系时, 这里我们就用到了 图
2. 基本介绍
图是一种 数据结构,其中结点可以具有零个或多个相邻元素。两个结点之间的连接称为边。 结点也可以称为顶点。
2.1 图的基本概念
顶点(vertex)
边(edge)
路径
无向图(下图)
有向图
带权图
3. 图的表示方式
图的表示方式有两种:
3.1 邻接矩阵
邻接矩阵是表示图形中顶点之间相邻关系的矩阵,对于 n 个顶点的图而言,矩阵是的 row 和 col 表示的是 1….n个点。
3.2 邻接表
- 邻接矩阵需要为每个顶点都分配 n 个边的空间,其实有很多边都是不存在,会造成空间的一定损失
- 邻接表的实现只关心存在的边,不关心不存在的边。因此没有空间浪费,邻接表由数组+链表组成。
4. 图的快速入门
属性:
private ArrayList<String> vertexList;
储存顶点的集合
private int[][] edges;
储存图对应的 邻结矩阵
private int numOfEdges;
表示边的数目
方法:
public void insertVertex(String vertex);
插入节点的方法
public void insertEdge(int v1,int v2,int weight);
插入边的方法
public int getNumOfVertex();
返回节点的个数
public int getNumOfEdges();
返回边的条数
public String getValueByIndex(int i);
返回节点 i 下标对应的数据 0–>A
public int getWeight(int v1,int v2);
返回v1
和v2
的权值
public void showGraph();
显示图对应的矩阵
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118
| public class Graph {
private ArrayList<String> vertexList; private int[][] edges; private int numOfEdges;
public Graph(int n){ edges = new int[n][n]; vertexList = new ArrayList<String>(n); numOfEdges = 0; }
public void insertVertex(String vertex) { vertexList.add(vertex); }
public void insertEdge(int v1,int v2,int weight) { edges[v1][v2] = weight; edges[v2][v1] = weight; numOfEdges++; }
public int getNumOfVertex() { return vertexList.size(); }
public int getNumOfEdges() { return numOfEdges; }
public String getValueByIndex(int i) { return vertexList.get(i); }
public int getWeight(int v1,int v2) { return edges[v1][v2]; }
public void showGraph() { for(int[] link: edges) { System.out.println(Arrays.toString(link)); } } public static void main(String[] args) { int n = 5; String[] vertexs = {"A","B","C","D","E"}; Graph graph = new Graph(n); for(String vertex: vertexs) { graph.insertVertex(vertex); } graph.insertEdge(0, 1, 1); graph.insertEdge(0, 2, 1); graph.insertEdge(1, 2, 1); graph.insertEdge(1, 3, 1); graph.insertEdge(1, 4, 1); graph.showGraph(); }
}
|
5. 图的遍历☆☆
所谓图的遍历,即是对结点的访问。一个图有那么多个结点,如何遍历这些结点,需要特定策略,一般有两种访问策略:
深度优先遍历
广度优先遍历
5.1 深度优先遍历算法
图的深度优先搜索(Depth First Search)
深度优先遍历,从初始访问结点出发,初始访问结点可能有多个邻接结点,深度优先遍历的策略就是首先访问第一个邻接结点,然后再以这个被访问的邻接结点作为初始结点,访问它的第一个邻接结点, 可以这样理解:每次都在访问完当前结点后首先访问当前结点的第一个邻接结点。
- 我们可以看到,这样的访问策略是优先往纵向挖掘深入,而不是对一个结点的所有邻接结点进行横向访问。
- 显然,深度优先搜索是一个递归的过程
深度优先遍历算法步骤
- 访问初始结点 v,并标记结点 v 为已访问。
- 查找结点 v 的第一个邻接结点 w。
- 若 w 存在,则继续执行 4,如果 w 不存在,则回到第 1 步,将从 v 的下一个结点继续。
- 若 w 未被访问,对 w 进行深度优先遍历递归(即把 w 当做另一个 v,然后进行步骤 123)。
- 查找结点 v 的 w 邻接结点的下一个邻接结点,转到步骤 3。
代码实现
public int getFirstNeighbor(int index);
如果存在就返回相应的下标,否则返回-1
public int getNextNeighbor(int v1,int v2);
根据前一个邻接结点的下标来获取下一个邻接结点
private void dfs(boolean[] isVisited,int i);
深度优先遍历算法
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76
|
public int getFirstNeighbor(int index) { for (int i = 0; i < vertexList.size(); i++) { if(edges[index][i]>0) { return i; } } return -1; }
public int getNextNeighbor(int v1,int v2) {
for (int i = v2+1; i < vertexList.size(); i++) { if(edges[v1][i]>0) { return i; } } return -1; }
private 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); } }
public void dfs() { isVisited = new boolean[vertexList.size()]; for (int i = 0; i < getNumOfVertex(); i++) { if(!isVisited[i]) { dfs(isVisited,i); } } }
|
5.2 广度优先遍历算法
图的广度优先搜索(Broad First Search)
类似于一个 分层搜索的过程,广度优先遍历需要使用一个队列以保持访问过的结点的顺序,以便按这个顺序来访问这些结点的邻接结点
广度优先遍历算法步骤
- 访问初始结点 v 并标记结点 v 为已访问。
- 结点 v 入队列
- 当队列非空时,继续执行,否则算法结束。
- 出队列,取得队头结点 u。
- 查找结点 u 的第一个邻接结点 w。
- 若结点 u 的邻接结点 w 不存在,则转到步骤 3;否则循环执行以下三个步骤:
- 若结点 w 尚未被访问,则访问结点 w 并标记为已访问。
- 结点 w 入队列
- 查找结点 u 的继 w 邻接结点后的下一个邻接结点 w,转到步骤 6。
代码实现
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60
|
public void bfs(boolean[] isVisited,int i) { int u; int w; LinkedList queues = new LinkedList(); System.out.print(getValueByIndex(i)+"-->"); isVisited[i] = true; queues.addLast(i); while(!queues.isEmpty()) { u = (Integer)queues.removeFirst(); w = getFirstNeighbor(u); while(w != -1) { if(!isVisited[w]) { System.out.print(getValueByIndex(w)+"-->"); isVisited[w] = true; queues.addLast(w); } w = getNextNeighbor(u, w); } }
}
public void bfs() { isVisited = new boolean[vertexList.size()]; for (int i = 0; i < getNumOfVertex(); i++) { if(!isVisited[i]) { bfs(isVisited,i); } } }
|
5.3 深度优先 VS 广度优先
☆