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

133 阅读 0 评论 88 点赞

我是靠谱客的博主俊秀白羊，最近开发中收集的这篇文章主要介绍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) );
    }
}