Java数据结构之图的领接矩阵详解

网友投稿 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小时内删除侵权内容。

上一篇:深信服SSL远程接入与深信服行为审计同步登陆用户信息(深信服数据库审计系统)
下一篇:【逗老师带你学IT】Windows Server NPS服务构建基于AD域控的radius认证(IT好学么)
相关文章

 发表评论

暂时没有评论,来抢沙发吧~