多平台统一管理软件接口,如何实现多平台统一管理软件接口
339
2022-09-11
Java数据结构之图的领接矩阵详解
目录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();
NHeRkRkanE 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 } @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) ); } } 结果 以上就是Java数据结构之图的领接矩阵详解的详细内容,更多关于Java数据结构资料请关注我们其它相关文章!
}
@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) );
}
}
结果
以上就是Java数据结构之图的领接矩阵详解的详细内容,更多关于Java数据结构资料请关注我们其它相关文章!
版权声明:本文内容由网络用户投稿,版权归原作者所有,本站不拥有其著作权,亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容,请联系我们jiasou666@gmail.com 处理,核实后本网站将在24小时内删除侵权内容。
发表评论
暂时没有评论,来抢沙发吧~