吴江企业网站建设,手机网站模版 优帮云,建设网站需要多久到账,投资交易网站开发目录
一、图的两种存储方式
1.邻接矩阵
2.邻接表 生活中处处有图Graph的影子#xff0c;例如交通图#xff0c;地图#xff0c;电路图等#xff0c;形象的表示点与点之间的联系。
首先简单介绍一下图的概念和类型#xff1a; 图的的定义#xff1a;图是由一组顶点和一…目录
一、图的两种存储方式
1.邻接矩阵
2.邻接表 生活中处处有图Graph的影子例如交通图地图电路图等形象的表示点与点之间的联系。
首先简单介绍一下图的概念和类型 图的的定义图是由一组顶点和一组能够将两个顶点相连的边组成的 图的类型 顶点之间的连接方向无方向--无向图 有方向--有向图 边上是否有权值有--带权图 无--无权图 以下分别是无向无权、有向无权、无向有权、有向有权图 一、图的两种存储方式
1.邻接矩阵
存储原理邻接矩阵是一种用数组来表示图的方法其中矩阵的行和列表示图中的顶点矩阵元素表示顶点之间是否有边相连。具体来说如果顶点v和顶点u之间有边则矩阵的第u行第v列的元素为1否则为0。带权值则为权值没有相连的为0。
优点 结构简单易于理解和实现。 对于稠密图邻接矩阵的空间利用率较高。 可以方便地计算出图中节点的度即与该节点相邻的节点的数量。
缺点 对于稀疏图邻接矩阵可能占用大量空间。 访问相邻节点的速度较慢需要进行遍历操作。
示例下图的邻接矩阵存储 代码实现
import java.util.Arrays;//邻接矩阵
public class Graph01 {char[] val;//顶点数据int[][] edges;//二维数组记录边Vertex[] vertices;//顶点类数组int N;//表大小public Graph01(char[] arr) {this.N arr.length;//初始化顶点数据this.val Arrays.copyOf(arr, arr.length);this.edges new int[this.N][this.N];this.vertices new Vertex[this.N];for (int i 0; i this.N; i) {this.vertices[i] new Vertex(arr[i]);}}private class Vertex {Character val;public Vertex(Character val) {this.val val;}}//打印邻接矩阵public void show() {System.out.format(%5c, 32);for (int i 0; i this.N; i) {System.out.format(%5c, this.val[i]);}System.out.println();for (int i 0; i this.N; i) {System.out.format(%5c, this.val[i]);for (int j 0; j this.N; j) {System.out.format(%5d, this.edges[i][j]);}System.out.println();}}public static void main(String[] args) {char[] arr {A, E, F, G, H, P};Graph01 graph01 new Graph01(arr);// 构建边集int[][] edges graph01.edges;edges[0][1] 5;edges[0][2] 4;edges[0][3] 2;edges[1][0] 5;edges[1][3] 1;edges[1][4] 3;edges[2][0] 4;edges[3][0] 2;edges[3][1] 1;edges[3][4] 2;edges[3][5] 4;edges[4][1] 3;edges[4][3] 2;edges[4][5] 3;edges[5][3] 4;edges[5][4] 3;// 调用打印方法graph01.show();}
}打印结果 2.邻接表
存储原理
邻接表中的每个节点都对应一个链表链表中的每个元素都是一个顶点或节点表示与当前节点相邻的节点。这种方式在处理稀疏图即边的数量远小于顶点的数量时效率较高。
优点 存储空间开销较小适用于稀疏图。 查找速度快可以直接通过索引访问相邻节点。 可动态添加、删除节点和边。
缺点 存储结构相对复杂不利于处理大规模数据。 空间利用率不高对于稠密图可能存在大量未使用的节点和边。
代码实现
import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;//邻接表
public class Graph02 {char[] val;//顶点数据ListInteger[] edgesList;//边连接Vertex[] vertices;int N;//表大小public Graph02(char[] arr){this.N arr.length;this.val Arrays.copyOf(arr,arr.length);this.edgesList new List[this.N];this.vertices new Vertex[this.N];for (int i 0; i this.N; i) {this.vertices[i] new Vertex(arr[i]);this.edgesList[i] new ArrayList();}}private class Vertex{Character val;public Vertex(Character val){this.val val;}}public void show(){//打印邻接矩阵for (int i 0; i this.N; i) {System.out.format(%-3c,this.val[i]);ListInteger list this.edgesList[i];list.stream().forEach(item-{System.out.format(%d--,item);});System.out.println();}}public static void main(String[] args) {char[] arr {A, E, F, G, H, P};Graph02 graph02 new Graph02(arr);// 构建边集ListInteger[] edges graph02.edgesList;edges[0].add(1);edges[0].add(2);edges[0].add(3);edges[1].add(0);edges[1].add(3);edges[1].add(4);edges[2].add(0);edges[3].add(0);edges[3].add(1);edges[3].add(4);edges[3].add(5);edges[4].add(1);edges[4].add(3);edges[4].add(5);edges[5].add(3);edges[5].add(4);// 调用打印方法graph02.show();}
}打印结果
