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数据结构之图的领接矩阵详解的详细内容，更多关于java数据结构资料请关注其它相关文章！