Java数据结构图的领接矩阵举例分析

本篇内容介绍了“Java数据结构图的领接矩阵举例分析”的有关知识，在实际案例的操作过程中，不少人都会遇到这样的困境，接下来就让小编带领大家学习一下如何处理这些情况吧！希望大家仔细阅读，能够学有所成！

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) );    }}

“Java数据结构图的领接矩阵举例分析”的内容就介绍到这里了，感谢大家的阅读。如果想了解更多行业相关的知识可以关注编程网网站，小编将为大家输出更多高质量的实用文章！