图结构基本知识

1. 相关概念

• 图G(V,E) ：一种数据结构，可表示“多对多”关系，由顶点集V和边集E组成；
• 顶点(vertex) ：
• 边 (edge)：一幅点对（v,w），v,w∈V，边也称为弧；
• 邻接：点v，w邻接，当且仅当边(v,w)∈E；
• 路径 ：由一个顶点序列v₁，v₂，…,v_n组成，路径长为n-1；
• 有向图 ：边是单向的，点对有序；
• 无向图 ：边是双向的图，点对无序；
• 带权图：不同边具有不同的权值的图；
• 连通：无向图的一个顶点到其他任何顶点都存在一条路径，则称其为连通的；
• 强连通：有向图的一个顶点到其他任何顶点都存在一条路径；
• 弱连通：有向图本身不是强连通的，但是其边不考虑方向的无向图是连通的；
• 完全图：每一对顶点间都存在边；

2. 图的表示方式

• 邻接矩阵：使用二维数组实现，数组中每个元素表示图中两顶点之间是否有边，或者表示边的权值，适用于稠密图，对于稀疏图而言此表示方法过于浪费空间；

package com.northsmile.graph;import java.util.ArrayList;
import java.util.Arrays;/*** Author:NorthSmile* Create:2023/4/18 9:17* 使用邻接矩阵表示图（无向图）*/
public class Graph {// 存储边及其权值int[][] edges;// 存储顶点ArrayList<String> vertexes;// 记录边的数目int edgeNums;public Graph(int n){edges=new int[n][n];vertexes=new ArrayList<>(n);edgeNums=0;}/*** 插入顶点* @param vertex*/public void insertVertex(String vertex){vertexes.add(vertex);}/*** 插入边* @param v1 边的一个顶点对应下标* @param v2 边的另一个顶点对应下标* @param w 边对应权值，默认为1*/public void insertEdge(int v1,int v2,int w){edges[v1][v2]=w;edges[v2][v1]=w;edgeNums++;}/*** 获取顶点数量* @return*/public int getVertexesNum(){return vertexes.size();}/*** 获取边的数目* @return*/public int getEdgesNum(){return edgeNums;}/*** 获取指定下标对应的顶点的值* @param v* @return*/public String getValByIndex(int v){return vertexes.get(v);}/*** 获取指定边的权值* @param v1* @param v2* @return*/public int getWeightOfEdge(int v1,int v2){return edges[v1][v2];}/*** 显示表示图的邻接矩阵*/public void showGraph(){for (int[] edge:edges){System.out.println(Arrays.toString(edge));}}
}

package com.northsmile.graph;/*** Author:NorthSmile* Create:2023/4/18 9:18*/
public class GraphDemo {public static void main(String[] args) {int n=5;String[] vertexes={"A","B","C","D","E"};Graph graph = new Graph(n);// 插入顶点for (String vertex:vertexes){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();}
}

• 邻接表：使用数组+链表的方式实现，适用于稀疏图表示，是图的标准表示方法，对于每个顶点，将其所有邻接点使用一个表存放；
  

package com.northsmile.graph;import java.util.ArrayList;
import java.util.HashMap;/*** Author:NorthSmile* Create:2023/4/18 11:12* 使用邻接表表示图（有向图）*/
public class GraphByAdjacenceList {// 邻接表HashMap<String,Vertex> list;int vertexNums;int edgeNums;public GraphByAdjacenceList(int n){list=new HashMap<>();vertexNums=n;edgeNums=0;}/*** 插入顶点* @param vertex*/public void insertVertex(String vertex){list.put(vertex,new Vertex(vertexNums));}/*** 插入边* @param v 顶点* @param w 邻接点*/public void insertEdge(String v,String w){Vertex vertex = list.get(v);vertex.table.add(w);edgeNums++;}/*** 获取顶点数量* @return*/public int getVertexesNum(){return list.size();}/*** 获取边的数目* @return*/public int getEdgesNum(){return edgeNums;}/*** 显示表示图的邻接表*/public void showGraph(){for (String vertex:list.keySet()){System.out.println(vertex+":"+list.get(vertex).table);}}/*** 顶点类*/class Vertex{ArrayList<String> table;public Vertex(int n){table=new ArrayList<>(n/2);}}
}

package com.northsmile.graph;/*** Author:NorthSmile* Create:2023/4/18 9:18*/
public class GraphDemo {public static void main(String[] args) {// 2.邻接表int n=5;String[] vertexes={"A","B","C","D","E"};GraphByAdjacenceList graph = new GraphByAdjacenceList(n);// 插入顶点for (String vertex:vertexes){graph.insertVertex(vertex);}// 插入边graph.insertEdge("A","B");graph.insertEdge("A","C");graph.insertEdge("B","C");graph.insertEdge("B","D");graph.insertEdge("B","E");graph.showGraph();}
}

3. 图的遍历

3.1 深度优先遍历（DFS）

• 类似树的先序遍历，先访问当前顶点，再依次以其邻接点为新的起点，进行深度优先遍历；
• 与树的遍历不同，图在深度优先遍历时，当前顶点的邻接点可能已经访问过，所以无需再进行访问；
• 为了实现顶点的唯一遍历，在代码实现时需要提供一个标记数组，表示对应顶点是否已经访问过；
• 代码实现以递归方式进行；
  
  

    /*** 深度优先遍历：类似树的先序遍历* @param v 以当前点开始遍历* @param visited 标记节点是否访问过*/public void dfs(int v,boolean[] visited){System.out.print(vertexes.get(v)+"->");// 遍历当前顶点的邻接点for (int i=0;i<vertexes.size();i++){// 说明v、i之间存在边if (edges[v][i]!=0&&!visited[i]){visited[i]=true;dfs(i,visited);}}}public void dfs(){// 标记顶点是否已经访问过boolean[] visited=new boolean[vertexes.size()];// 以每个顶点开始进行DFS，实现图的完整遍历for (int i=0;i<vertexes.size();i++){if (!visited[i]){visited[i]=true;dfs(i,visited);}}}

3.2 广度优先遍历（BFS）

• 类似树的层序遍历，先访问当前顶点，再依次访问其邻接点，然后分别以其邻接点为新的起点，继续进行广度优先遍历；
• 与树的遍历不同，图在深度优先遍历时，当前顶点的邻接点可能已经访问过，所以无需再进行访问；
• 为了实现顶点的唯一遍历，在代码实现时需要提供一个标记数组，表示对应顶点是否已经访问过；
• 代码实现借助队列实现；
  

    /*** 广度优先遍历：类似树的层次遍历* @param v 以当前点开始遍历* @param visited 标记节点是否访问过*/public void bfs(int v,boolean[] visited){ArrayDeque<Integer> queue=new ArrayDeque<>();queue.offer(v);visited[v]=true;while (!queue.isEmpty()){Integer cur = queue.poll();System.out.print(vertexes.get(cur)+"->");// 遍历当前顶点的邻接点for (int i=0;i<vertexes.size();i++){// 说明v、i之间存在边if (edges[cur][i]!=0&&!visited[i]){visited[i]=true;queue.offer(i);}}}}public void bfs(){// 标记顶点是否已经访问过boolean[] visited=new boolean[vertexes.size()];// 以每个顶点开始进行BFS，实现图的完整遍历for (int i=0;i<vertexes.size();i++){if (!visited[i]){bfs(i,visited);}}}

资料来源：尚硅谷