【图（1）】：用邻接矩阵和邻接表实现图

大家好，欢迎来到IT知识分享网。

目录

一、图的基本概念

二、图的存储结构

1.邻接矩阵

2.邻接表

一、图的基本概念

注意：概念性的文字不列出太多，记不住也不便于理解

图（Graph）是由节点（Node）和边（Edge）组成的数据结构。图可以用来表示对象之间的关系，其中节点表示对象，边表示对象之间的连接或关联。

图的基本概念包括以下几个要素：

1. 节点：也称为顶点（Vertex），表示图中的对象。节点可以具有属性或标签，用于描述对象的特征。
2. 边：也称为弧（Arc）或连接（Link），表示节点之间的关系或连接。边可以是有向的（从一个节点指向另一个节点）或无向的（没有方向）。
3. 权重：边可以带有权重（Weight），表示节点之间的某种度量或距离。权重可以表示关系的强度、路径的长度等。
4. 邻接：两个节点之间存在一条边，则它们被称为邻接（Adjacent）节点。如果图是有向的，那么邻接节点分为入度邻接节点和出度邻接节点。无向图某顶点的度=入度=出度，有向图某顶点的度=入度+出度。
5. 路径：路径（Path）是由边连接的节点序列，表示从一个节点到另一个节点的通路。路径的长度可以通过边的数量或权重之和来衡量。
6. 连通性：图中的节点通过边相互连接，如果任意两个节点之间都存在路径，那么图被称为连通图。如果图中存在不连通的部分，则称为非连通图。
7. 图的类型：根据边的属性和连接方式，图可以分为有向图（Directed Graph）和无向图（Undirected Graph）。有向图的边具有方向性，无向图的边没有方向。此外，还有其他特殊类型的图，如加权图、带环图等。

不带权值的图：

带权值的图：

二、图的存储结构

1.邻接矩阵

用邻接矩阵存储图的优点是能够快速知道两个顶点是否连通，缺陷是如果顶点比较多，边比较少时，矩阵中存储了大量的0成为系数矩阵，比较浪费空间，并且要求两个节点之间的路径不是很好求。

下面看代码实现（基于无向图G1）

• printGraph方法用于打印邻接矩阵；
• 顶点用HashMap存储 顶点-下标 的键值对，使获取下标的时间复杂度达到O（1）；
• addEdge方法表示v1指向v2。

//邻接矩阵 public class GraphByMatrix { private char[] arrayV; //存放顶点 private int[][] matrix; //存放权值或者边 private boolean isDirect; //是否是有向图 private HashMap<Character, Integer> indexMap; //定位顶点对应的下标 public GraphByMatrix(int size, boolean isDirect) { arrayV = new char[size]; matrix = new int[size][size]; this.isDirect = isDirect; indexMap = new HashMap<>(); } / * 初始化 * * @param array 顶点集合 */ public void initArrayV(char[] array) { for (int i = 0; i < array.length; i++) { arrayV[i] = array[i]; indexMap.put(array[i], i); } } / * 给两个顶点的边添加权重 * * @param v1 顶点1 * @param v2 顶点2 * @param weight 权值 */ public void addEdge(char v1, char v2, int weight) { int index1 = getIndexOfV(v1); int index2 = getIndexOfV(v2); if (index1 == -1 || index2 == -1) { throw new RuntimeException("v1或v2顶点不存在"); } matrix[index1][index2] = weight; //无向图则对称位置也设置权重 if (!isDirect) { matrix[index2][index1] = weight; } } //获取该顶点对应的下标 private int getIndexOfV(char v) { Integer index = indexMap.get(v); return index == null ? -1 : index;//hashMap定位 } / * 获取顶点的度 * * @param v * @return */ public int getDevOfV(char v) { //1.获取顶点在arrayV的下标 int index = getIndexOfV(v); //2.计算该顶点的出度 int count = 0; for (int i = 0; i < arrayV.length; i++) { if (matrix[index][i] != 0) { count++; } } //3.如果是有向图，还需要计算顶点的入度 if (isDirect) { for (int i = 0; i < arrayV.length; i++) { if (matrix[i][index] != 0) { count++; } } } return count; } public void printGraph() { System.out.print(" "); for (char c : arrayV) { System.out.print(c + " "); } System.out.println(); for (int i = 0; i < matrix.length; i++) { System.out.print(arrayV[i] + " "); for (int j = 0; j < matrix[i].length; j++) { System.out.print(matrix[i][j] + " "); } System.out.println(); } } }

代码测试：

 public static void main(String[] args) { GraphByMatrix graphByMatrix = new GraphByMatrix(4, false); char[] array = {'A', 'B', 'C', 'D'}; graphByMatrix.initArrayV(array); graphByMatrix.addEdge('A', 'B', 1); graphByMatrix.addEdge('A', 'D', 1); graphByMatrix.addEdge('B', 'A', 1); graphByMatrix.addEdge('B', 'C', 1); graphByMatrix.addEdge('C', 'B', 1); graphByMatrix.addEdge('C', 'D', 1); graphByMatrix.addEdge('D', 'A', 1); graphByMatrix.addEdge('D', 'C', 1); graphByMatrix.printGraph(); System.out.println("顶点A的度：" + graphByMatrix.getDevOfV('A')); }

假设无向图（第二参数为false）                              假设有向图（第二参数为true）

2.邻接表

2. 有向图邻接表存储

import java.util.ArrayList; import java.util.HashMap; //邻接表 public class GraphByTable { static class Node { public int src; //起点坐标 public int dest; //终点坐标 public int weight; //权重 public Node next; public Node(int src, int dest, int weight) { this.src = src; this.dest = dest; this.weight = weight; } } private ArrayList<Node> edgeList; //保存所有的顶点 private char[] arrayV; //顶点数组 private boolean isDirect; //是否是有向图 private HashMap<Character, Integer> indexMap; //快速定位顶点下标 public GraphByTable(int size, boolean isDirect) { arrayV = new char[size]; this.isDirect = isDirect; indexMap = new HashMap<>(); edgeList = new ArrayList<>(size); //给list添加元素，否则list初始为空 for (int i = 0; i < size; i++) { edgeList.add(null); } } public void initArrayV(char[] array) { for (int i = 0; i < array.length; i++) { arrayV[i] = array[i]; indexMap.put(array[i], i); } } / * 给两个顶点的边添加权重 * * @param v1 顶点1 * @param v2 顶点2 * @param weight 权值 */ public void addEdge(char v1, char v2, int weight) { //1.找出两个顶点在数组中的位置 int src = getIndexOfV(v1); int dest = getIndexOfV(v2); addEdgeChild(src, dest, weight); //连通 //2.如果是无向图，反方向连通 if (!isDirect) { addEdgeChild(dest, src, weight); } } private void addEdgeChild(int src, int dest, int weight) { //获取顶点集合中链表的头节点 Node cur = edgeList.get(src); while (cur != null) { //如果当前节点的dest就是要连通的dest，说明已经连通过了 if (cur.dest == dest) { return; } cur = cur.next; } //走到这说明顶点还没连通过，进行头插 Node node = new Node(src, dest, weight); node.next = edgeList.get(src); edgeList.set(src, node); } private int getIndexOfV(char v) { return indexMap.get(v); } / * 获取顶点的度 * * @param v * @return */ public int getDevOfV(char v) { //1.获取顶点的下标，得到链表 int index = getIndexOfV(v); Node cur = edgeList.get(index); //2.计算出度(无向图的度就是出度) int count = 0; while (cur != null) { count++; cur = cur.next; } //3.如果是有向图，还要计算顶点的入度 if (isDirect) { for (int i = 0; i < edgeList.size(); i++) { //出度的链表不能计算进去 if (i != index) { cur = edgeList.get(i); while (cur != null) { //cur的dest为当前顶点下标，就是当前顶点的入度 if (cur.dest == index) { count++; } cur = cur.next; } } } } return count; } public void printGraph() { for (int i = 0; i < edgeList.size(); i++) { System.out.print(arrayV[i] + " -> "); Node cur = edgeList.get(i); while (cur != null) { System.out.print(cur.dest + " -> "); cur = cur.next; } System.out.println(); } } public static void main(String[] args) { GraphByTable graphByTable = new GraphByTable(4, true); char[] array = {'A', 'B', 'C', 'D'}; graphByTable.initArrayV(array); graphByTable.addEdge('A', 'B', 1); graphByTable.addEdge('A', 'D', 1); graphByTable.addEdge('B', 'A', 1); graphByTable.addEdge('B', 'C', 1); graphByTable.addEdge('C', 'B', 1); graphByTable.addEdge('C', 'D', 1); graphByTable.addEdge('D', 'A', 1); graphByTable.addEdge('D', 'C', 1); graphByTable.printGraph(); System.out.println(graphByTable.getDevOfV('A')); } }