图 - Java实现无向带权图的邻接矩阵表示法
1.图
1.1 图的介绍
- 图(Graph),是一种复杂的非线性表结构
- 图中的元素我们就叫做顶点(vertex)
- 图中的一个顶点可以与任意其他顶点建立连接关系。我们把这种建立的关系叫做边(edge),跟顶点相连接的边的条数叫做度(degree)
- 这是一个无向带权图:
1.2 邻接矩阵的介绍
|
A |
B |
C |
D |
E |
F |
A |
0 |
1 |
1 |
1 |
0 |
0 |
B |
1 |
0 |
0 |
1 |
0 |
0 |
C |
1 |
0 |
0 |
0 |
1 |
1 |
D |
1 |
1 |
0 |
0 |
1 |
1 |
E |
0 |
0 |
1 |
1 |
0 |
1 |
F |
0 |
0 |
1 |
1 |
1 |
0 |
-
带权图:数组中就存储相应的权重
|
1 |
2 |
3 |
4 |
1 |
0 |
5 |
3 |
0 |
2 |
0 |
0 |
1 |
6 |
3 |
3 |
2 |
0 |
1 |
4 |
0 |
6 |
1 |
0 |
2.Java实现无向带权图邻接矩阵表示法的常见功能
package com.lagou;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
/**
* @author 云梦归遥
* @date 2022/5/20 12:30
* @description 无向带权图 - 邻接矩阵法
*/
public class NoDirectionWeightTuMethod {
private List<Object> nodeList; // 存储所有节点的集合
private int[][] adjacencyMatrix; // 邻接矩阵
private int edge; // 边的数量
public NoDirectionWeightTuMethod(int num){
nodeList = new ArrayList<>(num);
adjacencyMatrix = new int[num][num];
edge = 0;
}
// 添加节点
public NoDirectionWeightTuMethod insert(Object node){
nodeList.add(node);
return this;
}
// 查找节点
public String select(Object node){
StringBuilder stringBuilder = new StringBuilder();
stringBuilder.append("【" + node + "】= ");
int index = nodeList.indexOf(node); // 获取索引
if (index >= 0){
// 节点存在
for (int i = 0; i < adjacencyMatrix.length; i++){
if (adjacencyMatrix[index][i] > 0){
stringBuilder.append("【<" + node + ", " + nodeList.get(i) + "> - weight: " + adjacencyMatrix[index][i] + "】 => ");
}
}
} else {
stringBuilder.append("null");
}
String result = stringBuilder.toString();
result = result.substring(0, result.lastIndexOf(" => "));
return result;
}
// 获取节点的个数
public int getNodeNum(){
return nodeList.size();
}
// 添加边(权重)
public NoDirectionWeightTuMethod addEdge(Object object1, Object object2, int weight){
if (nodeList.contains(object1) && nodeList.contains(object2)){
int index1 = nodeList.indexOf(object1);
int index2 = nodeList.indexOf(object2);
adjacencyMatrix[index1][index2] = weight;
adjacencyMatrix[index2][index1] = weight;
}
return this;
}
// 获取权重
public int getWeight(Object object1, Object object2){
int result = Integer.MAX_VALUE; // 默认 int 最大值
if (nodeList.contains(object1) && nodeList.contains(object2)){
int index1 = nodeList.indexOf(object1);
int index2 = nodeList.indexOf(object2);
result = adjacencyMatrix[index1][index2];
}
return result;
}
// 判断边是否存在
public boolean hasEdge(Object object1, Object object2){
boolean result = false;
if (nodeList.contains(object1) && nodeList.contains(object2)){
int index1 = nodeList.indexOf(object1);
int index2 = nodeList.indexOf(object2);
if (adjacencyMatrix[index1][index2] > 0){
result = true;
}
}
return result;
}
// 获取边的数量
public int getEdgeNum(Object object){
int num = Integer.MAX_VALUE;
if (nodeList.contains(object)){
num = 0;
int index = nodeList.indexOf(object);
for (int i = 0; i < adjacencyMatrix.length; i++){
if (adjacencyMatrix[index][i] > 0){
num++;
}
}
}
return num;
}
// 获取 邻接矩阵
public String getAdjacencyMatrix(){
StringBuilder stringBuilder = new StringBuilder();
stringBuilder.append(" " + Arrays.toString(nodeList.toArray()) + "\n");
for (int i = 0; i < adjacencyMatrix.length; i++){
stringBuilder.append(nodeList.get(i) + " " + Arrays.toString(adjacencyMatrix[i]) + "\n");
}
return stringBuilder.toString();
}
}
进行测试
package com.lagou.test;
import com.lagou.NoDirectionWeightTuMethod;
/**
* @author 云梦归遥
* @date 2022/5/20 13:05
* @description
*/
public class NoDirectionWeightTuMethodTest {
public static void main(String[] args) {
NoDirectionWeightTuMethod weightTuMethod = new NoDirectionWeightTuMethod(5);
weightTuMethod.insert("A").insert("B").insert("C").insert("D").insert("E"); // 链式调用
weightTuMethod
.addEdge("A", "B", 3) // 链式调用
.addEdge("A", "D", 1)
.addEdge("A", "E", 5)
.addEdge("B", "C", 2)
.addEdge("D", "E", 7)
.addEdge("C", "D", 3);
System.out.println("是否存在边:" + weightTuMethod.hasEdge("A", "D"));
System.out.println("边的权重:" + weightTuMethod.getWeight("A", "D"));
System.out.println("边的数量:" + weightTuMethod.getEdgeNum("A"));
System.out.println("A 的所有关系:" + weightTuMethod.select("A"));
System.out.println("图中节点个数:" + weightTuMethod.getNodeNum());
System.out.println("整个图的邻接矩阵:");
System.out.println(weightTuMethod.getAdjacencyMatrix());
}
}
3.总结
- 无向带权图的邻接矩阵表示法主要是通过二维数组来实现的
- 每个行与列的交点存储的值其实是对应边上的权重