Java数据结构之图的领接矩阵详解_java（有向图的领接矩阵）
2022-03-01
目录
- 1.图的领接矩阵（Adjacency Matrix）存储结构
- 2.图的接口类
- 3.图的类型，用枚举类表示
- 4.图的领接矩阵描述
- 测试类
- 结果
1.图的领接矩阵（Adjacency Matrix）存储结构
图的领接矩阵（Adjacency Matrix）存储方式是用两个数组来表示图。一个一位数组存储图中顶点信息，一个二维数组（称为领接矩阵）存储图中的边或弧的信息。
举例
无向图
无向图的领接矩阵的第i行或第i列的非零元素个数正好是第i个顶点的度。
有向图
有向图的领接矩阵的第i行的非零元素个数正好是第i个顶点的出度，第i列的非零元素个数正好是第i个顶点的入度。
带权值的网图
2.图的接口类
3.图的类型，用枚举类表示
public enum GraphKind {
UDG,DG,UDN,DN;//无向图、有向图、无向网、有向网
}
4.图的领接矩阵描述
对于一个具有n个顶点的图G，可以将图G的领接矩阵存储在一个二维数组中.
package Graph;
/*
图的领接矩阵描述类
*/
import java.util.Scanner;
public class MyGraph implements IGraph {
public final static int INFINITY = Integer.MAX_VALUE;
private GraphKind kind; //图的标志
private int vexNum, arcNum; //图当前顶点和边数
private Object[] vexs; //顶点
private int[][] arcs; //邻接矩阵
public MyGraph() { //空参构造
this(null, 0, 0, null, null);
}
public MyGraph(GraphKind kind, int vexNum, int arcNum, Object[] vexs, int[][] arcs) { // 实参构造
this.kind = kind;
this.vexNum = vexNum;
this.arcNum = arcNum;
this.vexs = vexs;
this.arcs = arcs;
}
@Override
public void createGraph() { //创建新图
Scanner sc = new Scanner(System.in);
System.out.println("请输入图的类型：");
GraphKind kind = GraphKind.valueOf(sc.next());
switch (kind) {
case UDG:
createUDG();
return;
case DG:
createDG();
return;
case UDN:
createUDG();
return;
case DN:
createDN();
return;
}
}
private void createUDG() { //创建无向图
Scanner sc = new Scanner(System.in);
System.out.println("请输入图的顶点数、图的边数：");
vexNum = sc.nextInt();
arcNum = sc.nextInt();
vexs = new Object[vexNum];
System.out.println("请分别输入图的各个顶点");
for (int v = 0; v < vexNum; v++) //构造顶点函数
vexs[v] = sc.next();
arcs = new int[vexNum][vexNum];
for (int v = 0; v < vexNum; v++)
for (int u = 0; u < vexNum; u++)
arcs[v][u] = INFINITY; //初始化领接矩阵
System.out.println("请输入各个边的两个顶点及其权值：");
for (int k = 0; k < arcNum; k++) {
int v = locateVex(sc.next());
int u = locateVex(sc.next());
arcs[v][u] = arcs[v][u] = sc.nextInt();
}
}
private void createDG() { //创建有向图
}
;
private void createUDN() { //创建无向网
}
private void createDN() { //创建有向网
Scanner sc = new Scanner(System.in);
System.out.println("请输入图的顶点数、图的边数：");
vexNum = sc.nextInt();
arcNum = sc.nextInt();
vexs = new Object[vexNum];
System.out.println("请分别输入图的各个顶点");
for (int v = 0; v < vexNum; v++) //构造顶点函数
vexs[v] = sc.next();
arcs = new int[vexNum][vexNum];
for (int v = 0; v < vexNum; v++)
for (int u = 0; u < vexNum; u++)
arcs[v][u] = INFINITY; //初始化领接矩阵
System.out.println("请输入各个边的两个顶点及其权值：");
for (int k = 0; k < arcNum; k++) {
int v = locateVex(sc.next());
int u = locateVex(sc.next());
arcs[v][u] = sc.nextInt();
}
}
@Override
public int getVexNum() {
return vexNum; //返回顶点数
}
@Override
public int getArcNum() {
return arcNum; //返回边数
}
@Override //返回v的第一个领接点，若v没有领接点返回-1;
public Object getVex(int v) throws Exception {
if (v < 0 && v >= vexNum)
throw new Exception("第" + v + "个顶点不存在！");
return vexs[v];
<0v<vexNum
}
@Override
public int locateVex(Object vex) { //顶点定位法
for (int v = 0; v < vexNum; v++)
if (vexs[v].equals(vex))
return v;
return 0;
}
@Override
public int firstAdjVex(int v) throws Exception { //查找第一个领接点
if (v < 0 && v >= vexNum)
throw new Exception("第" + v + "个顶点不存在！");
for (int j = 0; j < vexNum; j++)
if (arcs[v][j] != 0 && arcs[v][j] < INFINITY)
return j;
return -1;
}
@Override
public int nextAdjvex(int v, int w) { //查找下一个领接点
return 0;
}
public GraphKind getKind(){ //返回图标类型
return kind;
}
public int[][] getArcs() { //返回邻接矩阵的值
return arcs;
}
//返回顶点
public Object[] getVexs() {
return vexs;
}
}
测试类
public static void main(String[] args) throws Exception {
MyGraph M=new MyGraph(); //创建图空间
M.createGraph();
System.out.println("创建无向网的顶点个数为："+M.getVexNum());
System.out.println("创建无向网的边个数为："+M.getArcNum());
System.out.println("请输入要查找顶点的值：");
Scanner sc=new Scanner(System.in);
Object top=sc.next();
System.out.println("要查找顶点"+top+"的值为："+ M.locateVex(top));
System.out.println("请输入要查找顶点的索引：");
int x= sc.nextInt();
System.out.println("要查找位置"+x+"处的顶点值为："+M.getVex(x) );
System.out.println("请输入邻接点的顶点的位置：");
int n= sc.nextInt();
System.out.println("要查找位置"+n+"处的顶点值为："+M.firstAdjVex(n) );
}
}
结果
