Java用邻接矩阵存储图的示例代码
目录
- 一、点睛
- 1.无向图的邻接矩阵
- 2.有向图的邻接矩阵
- 3.网的邻接矩阵
- 二、算法步骤
- 三、实现
- 四、测试
一、点睛 邻接矩阵通常采用一个一维数组存储图中节点的信息,采用一个二维数组存储图中节点之间的邻接关系。
邻接矩阵可以用来表示无向图、有向图和网。
1.无向图的邻接矩阵
在无向图中,若从节点 Vi 到节点 Vj 有边,则邻接矩阵 M[i][j] = M[j][i ]= 1,否则 M[i][j] = 0。
无向图的邻接矩阵的特定如下。
a 无向图的邻接矩阵是对称矩阵,并且是唯一的。
b 第 I 行或第 i 列非零的个数正好是第 i 个节点的度。
2.有向图的邻接矩阵
在有向图中,若从节点 Vi 到节点 Vj 有边,则邻接矩阵 M[i][j]=1,否则 M[i][j]=0 。
有向图的邻接矩阵的特定如下。
a 有向图的邻接矩阵不一定是对称的。
b 第 i 行非零元素的个数正好是第 i 个节点的出度,第 i 列非零元素的个数正好是第 i 个节点的入度。
3.网的邻接矩阵
【Java用邻接矩阵存储图的示例代码】网是带权图,需要存储边的权值,则邻接矩阵表示为:M[i][j] = Wij,其他情况为无穷大。
二、算法步骤 1 输入节点数和边数。
2 依次输入节点信息,将其存储到节点数组 Vex[] 中。
3 初始化邻接矩阵,如果是图,则将其初始化为0,如果是网,则将其初始化为无穷大。
4 依次输入每条边依附的两个节点,如果是网,则还需要输入该边的权值。
- 如果是无向图,则输入a,b,查询节点a、b在节点数组 Vex[] 中的存储下标 i、j,让 Edge[i][j]=Edge[j][i]=1。
- 如果是有向图,则输入a,b,查询节点a、b在节点数组 Vex[] 中的存储下标 i、j,让 Edge[i][j]=1。
- 如果是无向网,则输入a,b,w,查询节点a、b在节点数组 Vex[] 中的存储下标 i、j,让 Edge[i][j]=Edge[j][i]=w。
- 如果是有向网,则输入a,b,w,查询节点a、b在节点数组 Vex[] 中的存储下标 i、j,让 Edge[i][j]=w。
三、实现
package graph; import java.util.Scanner; public class CreateAMGraph {static final int MaxVnum = 100; // 顶点数最大值 static int locatevex(AMGraph G, char x) {for (int i = 0; i < G.vexnum; i++) // 查找顶点信息的下标if (x == G.Vex[i])return i; return -1; // 没找到} static void CreateAMGraph(AMGraph G) {Scanner scanner = new Scanner(System.in); int i, j; char u, v; System.out.println("请输入顶点数:"); G.vexnum = scanner.nextInt(); System.out.println("请输入边数:"); G.edgenum = scanner.nextInt(); System.out.println("请输入顶点信息:"); // 输入顶点信息,存入顶点信息数组for (int k = 0; k < G.vexnum; k++) {G.Vex[k] = scanner.next().charAt(0); }//初始化邻接矩阵所有值为0,如果是网,则初始化邻接矩阵为无穷大for (int m = 0; m < G.vexnum; m++)for (int n = 0; n < G.vexnum; n++)G.Edge[m][n] = 0; System.out.println("请输入每条边依附的两个顶点:"); while (G.edgenum-- > 0) {u = scanner.next().charAt(0); v = scanner.next().charAt(0); i = locatevex(G, u); // 查找顶点 u 的存储下标j = locatevex(G, v); // 查找顶点 v 的存储下标if (i != -1 && j != -1)G.Edge[i][j] = G.Edge[j][i] = 1; //邻接矩阵储置1else {System.out.println("输入顶点信息错!请重新输入!"); G.edgenum++; // 本次输入不算}}} static void print(AMGraph G) { // 输出邻接矩阵System.out.println("图的邻接矩阵为:"); for (int i = 0; i < G.vexnum; i++) {for (int j = 0; j < G.vexnum; j++)System.out.print(G.Edge[i][j] + "\t"); System.out.println(); }} public static void main(String[] args) {AMGraph G = new AMGraph(); CreateAMGraph(G); print(G); }} class AMGraph {char Vex[] = new char[CreateAMGraph.MaxVnum]; int Edge[][] = new int[CreateAMGraph.MaxVnum][CreateAMGraph.MaxVnum]; int vexnum; // 顶点数int edgenum; // 边数}
四、测试 绿色为输入,白色为输出。
文章图片
到此这篇关于Java用邻接矩阵存储图的示例代码的文章就介绍到这了,更多相关Java邻接矩阵存储图内容请搜索脚本之家以前的文章或继续浏览下面的相关文章希望大家以后多多支持脚本之家!
推荐阅读
- Java|Java easyExcel的复杂表头多级表头导入
- Java用邻接表存储图的示例代码
- 专业课|数据库原理与应用实验-数据库定义实验
- 走进Boost [Boost 使用入门]
- java|使用堆内内存HeapByteBuffer的注意事项
- Java|java集合之ArrayList详解
- java常用的容器_java常用集合容器详解
- Java|第十二篇(Java集合详解、ArrayList、Vector、LinkedList、Queue、PriorityQueue、Deque、HashSet、TreeSet)
- 计算机基础|【数据结构】Java容器——ArrayList、LinkedList、HashMap(红黑树)等结构的分析
- java|java常用集合详解