数据结构 JAVA描述（六） 图的创建 （邻接矩阵+邻接表）

时间：2025-02-17 10:27:52

图的抽象数据类型描述

IGraph

package Graph;

/**
 * @description 图的抽象数据类型描述
 *  
 * @date  2015年12月30日
 */
public interface IGraph {

    void createGraph();
    /**
     * @description 返回图中顶点数 
     * @date  2015年12月30日
     */
    int getVexNum();  

    /**
     * @description 返回图中边数 
     * @date  2015年12月30日
     */
    int getArcNum() ;

    /**
     * @throws Exception 
     * @description 给定位置v，返回其对应的顶点值 
     * @date  2015年12月30日
     */
    Object getVex(int v) throws Exception;  

    /**
     * @description 给定顶点的值vex，返回其在图中的位置  
     * @date  2015年12月30日
     */
    int locateVex(Object vex);

    /**
     * @throws Exception 
     * @description 返回v的第一个邻接点  
     * @date  2015年12月30日
     */
    int firstAdjVex(int v) throws Exception;

    /**
     * @throws Exception 
     * @description 返回v相对于w的下一个邻接点  
     * @date  2015年12月30日
     */
    int nextAdjVex(int v, int w) throws Exception;
}

图的邻接矩阵的描述

GraphKind

package Graph;

/**
 * @description 图的类型 
 * 
 * @author liuquan
 * @date  2015年12月30日
 */
public enum GraphKind {
    UDG, // 无向图（UnDirected Graph）
    DG, // 有向图（Directed Graph）
    UDN, //无向网（UnDirected Network）
    DN, //有向网（Directed Network）
}

MGraph 

package Graph;

import ;

/**
 * @description 图的邻接矩阵的描述 
 *  
 * @date  2015年12月30日
 */
public class MGraph implements IGraph{
    public final static int INFINITY = Integer.MAX_VALUE;
    private GraphKind kind; // 图的种类标志
    private int vexNum, arcNum; // 图的当前顶点数和边数
    private Object[] vexs; // 顶点
    private int[][] arcs;  // 邻接矩阵

    public MGraph(){
        this(null, 0, 0, null, null);
    }


    public MGraph(GraphKind kind, int vexNumi, int arcNum, Object[] vexs, int[][] arcs) { 
        this.kind = kind;
        this.vexNum = vexNumi;
        this.arcNum = arcNum;
        this.vexs = vexs;
        this.arcs = arcs;
    }


    /**
     * @description 图的创建算法 图的类型共有4种 
     *  
     * @date  2015年12月30日
     */
    public void createGraph() {
        Scanner sc = new Scanner();
        ("请输入图的类型：（UDG、DG、UDN、DN）");
        GraphKind kind = (());
        switch (kind) {
        case UDG:
            createUDG();
            break;
        case DG:
            createDG();
            break;
        case UDN:
            createUDN();
            break;
        case DN:
            createDN();
            break;
        default:
            break;
        }
    }


    /**
     * @description 创建有向网
     *  
     * @date  2015年12月30日
     */
    private void createDN() {
        Scanner sc = new Scanner();
        ("请分别输出图的顶点数、图的边数：");
        vexNum = ();
        arcNum = ();
        vexs = new Object[vexNum];
        ("请分别输出图的各个顶点：");
        for(int v = 0; v < vexNum; v++){
            vexs[v] = ();
        }
        arcs = new int[vexNum][vexNum];
        // 初始化邻接矩阵
        for(int v = 0; v < vexNum; v++){
            for(int u = 0; u < vexNum; u++){
                arcs[v][u] = INFINITY;
            }
        }
        ("请输入各个边的两个顶点及其权值");
        for(int k = 0; k < arcNum; k++){
            int v = locateVex(());
            int u = locateVex(());
            arcs[v][u] = ();
        }
    }


    /**
     * @description 创建无向网 
     *  
     * @date  2015年12月30日
     */
    private void createUDN() { 
        Scanner sc = new Scanner();
        ("请分别输出图的顶点数、图的边数：");
        vexNum = ();
        arcNum = ();
        vexs = new Object[vexNum];
        ("请分别输出图的各个顶点：");
        for(int v = 0; v < vexNum; v++){
            vexs[v] = ();
        }
        arcs = new int[vexNum][vexNum];
        // 初始化邻接矩阵
        for(int v = 0; v < vexNum; v++){
            for(int u = 0; u < vexNum; u++){
                arcs[v][u] = INFINITY;
            }
        }
        ("请输入各个边的两个顶点及其权值");
        for(int k = 0; k < arcNum; k++){
            int v = locateVex(());
            int u = locateVex(());
            arcs[v][u] = arcs[u][v] = ();
        }
    }


    /**
     * @description 创建有向图 
     *  
     * @date  2015年12月30日
     */ 
    private void createDG() {
        // 略 
    }


    /**
     * @description 创建无向图 
     *  
     * @date  2015年12月30日
     */
    private void createUDG() {
        // 略
    }


    public int getVexNum() { 
        return vexNum;
    }

    public int getArcNum() {  
        return arcNum;
    }

    /**
     * @description 根据顶点在数组中的位置返回顶点  
     * @date  2015年12月30日
     */
    public Object getVex(int v) throws Exception {        
        if(v < 0 && v >= vexNum)
            throw new Exception("第" + v + "个顶点不存在");
        return vexs[v];
    }

    /**
     * @description 顶点定位 根据顶点名返回其在数组中的位置  
     * @date  2015年12月30日
     */ 
    public int locateVex(Object vex) {  
        for(int v = 0; v < vexNum; v++){
            if(vexs[v].equals(vex))
                return v;
        }
        return -1;
    }

    /**
     * @description 查找第一个邻接点   
     * @date  2015年12月30日
     */
    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;
    }

    /**
     * @description 查找下一个邻接点，已知顶点v以及一个邻接点w，返回v相对于w的下一个邻接点 
     * @date  2015年12月30日
     */
    public int nextAdjVex(int v, int w) throws Exception { 
        if(v < 0 && v >= vexNum)
            throw new Exception("第" + v + "个顶点不存在");

        for(int j = w + 1; j < vexNum; j++){
            if(arcs[v][j] != 0 && arcs[v][j] < INFINITY){
                return j;
            }
        }
        return -1; 
    }   

    public void display(){
        for(int i = 0; i < vexNum; i++){
            for(int j = 0; j< vexNum; j++){
                if(arcs[i][j] == INFINITY) 
                    ("+ "); 
                else
                    (arcs[i][j] + " ");
            }
            ();
        }
    } 

}

构造一个具有n个顶点和e条边的网的时间复杂度是O（n² + en），其中邻接矩阵的初始化耗费了O（n²）的时间。

图的邻接表的描述

ALGraph

package Graph;
import ;

/**
 * @description 邻接表顶点结点结构
 *  
 * @date 2015年12月30日
 */
class VNode {

    private Object data; // 顶点信息

    private ArcNode firstArc; // 指向第一条依附于该顶点的弧

    public VNode() {
        this(null, null);
    }

    public VNode(Object data) {
        this(data, null);
    }

    public VNode(Object data, ArcNode firstArc) {
        this.data = data;
        this.firstArc = firstArc;
    }

    public Object getData() {
        return data;
    }

    public void setData(Object data) {
        this.data = data;
    }

    public ArcNode getFirstArc() {
        return firstArc;
    }

    public void setFirstArc(ArcNode firstArc) {
        this.firstArc = firstArc;
    }
}

/**
 * @description 邻接表 边（弧）的结点类
 *  
 * @date 2015年12月30日
 */
class ArcNode {

    private int adjVex; // 该弧所指向的顶点位置

    private int value; // 边的权值

    private ArcNode nextArc; // 指向下一条弧

    public ArcNode() {
        this(-1, 0, null);
    }

    public ArcNode(int adjVex) {
        this(adjVex, 0, null);
    }

    public ArcNode(int adjVex, int value) {
        this(adjVex, value, null);
    }

    public ArcNode(int adjVex, int value, ArcNode nextArc) {
        this.adjVex = adjVex;
        this.value = value;
        this.nextArc = nextArc;
    }

    public int getAdjVex() {
        return adjVex;
    }

    public void setAdjVex(int adjVex) {
        this.adjVex = adjVex;
    }

    public int getValue() {
        return value;
    }

    public void setValue(int value) {
        this.value = value;
    }

    public ArcNode getNextArc() {
        return nextArc;
    }

    public void setNextArc(ArcNode nextArc) {
        this.nextArc = nextArc;
    }
}

/**
 * @description 图的邻接表的描述 
 *  
 * @date  2015年12月30日
 */
public class ALGraph implements IGraph{ 

    private GraphKind kind; // 图的种类标志

    private int vexNum, arcNum; // 图的当前顶点数和边数

    private VNode[] vexs; // 顶点  

    public ALGraph(){
        this(null, 0, 0, null);
    }   


    public GraphKind getKind() {
        return kind;
    }

    public VNode[] getVexs() {
        return vexs;
    }


    public ALGraph(GraphKind kind, int vexNum, int arcNum, VNode[] vexs) {
        this.kind = kind;
        this.vexNum = vexNum;
        this.arcNum = arcNum;
        this.vexs = vexs;
    }

    /**
     * @description 图的创建算法 图的类型共有4种 
     *  
     * @date  2015年12月30日
     */
    public void createGraph() {
        Scanner sc = new Scanner();
        ("请输入图的类型：（UDG、DG、UDN、DN）");
        GraphKind kind = (());
        switch (kind) {
        case UDG:
            createUDG();
            break;
        case DG:
            createDG();
            break;
        case UDN:
            createUDN();
            break;
        case DN:
            createDN();
            break;
        default:
            break;
        }
    }

    /**
     * @description 创建有向网
     *  
     * @date  2015年12月30日
     */
    private void createDN() {
        Scanner sc = new Scanner();
        ("请分别输出图的顶点数、图的边数：");
        vexNum = ();
        arcNum = ();
        vexs = new VNode[vexNum];
        ("请分别输出图的各个顶点：");
        for(int v = 0; v < vexNum; v++){
            vexs[v] = new VNode(());
        } 
        ("请输入各个边的两个顶点及其权值");
        for(int k = 0; k < arcNum; k++){
            int v = locateVex(()); //弧尾 指出的点
            int u = locateVex(()); //弧头 被指入的点
            int value = ();
            addArc(v, u, value);
        }
    }


    /**
     * @description 创建无向网 
     *  
     * @date  2015年12月30日
     */
    private void createUDN() { 
        Scanner sc = new Scanner();
        ("请分别输出图的顶点数、图的边数：");
        vexNum = ();
        arcNum = ();
        vexs = new VNode[vexNum];
        ("请分别输出图的各个顶点：");
        for(int v = 0; v < vexNum; v++){
            vexs[v] = new VNode(());
        } 
        ("请输入各个边的两个顶点及其权值");
        for(int k = 0; k < arcNum; k++){
            int v = locateVex(()); //弧尾 指出的点
            int u = locateVex(()); //弧头 被指入的点
            int value = ();
            addArc(v, u, value);
            addArc(u, v, value);
        }
    }


    /**
     * @description 在位置v、u顶点之间，添加一条弧，其权值为value  
     * @date  2015年12月30日
     */
    private void addArc(int v, int u, int value) {
        ArcNode arc = new ArcNode(u,value);
        (vexs[v].getFirstArc());
        vexs[v].setFirstArc(arc); 
    }


    /**
     * @description 创建有向图 
     *  
     * @date  2015年12月30日
     */ 
    private void createDG() {
        // 略 
    }


    /**
     * @description 创建无向图 
     *  
     * @date  2015年12月30日
     */
    private void createUDG() {
        // 略
    }

    public int getVexNum() {
        return vexNum;
    }

    public int getArcNum() { 
        return arcNum;
    }

    /**
     * @description 根据顶点在数组中的位置返回顶点  
     * @date  2015年12月30日
     */
    public Object getVex(int v) throws Exception {        
        if(v < 0 && v >= vexNum)
            throw new Exception("第" + v + "个顶点不存在");
        return vexs[v].getData();
    }

    /**
     * @description 顶点定位 根据顶点名返回其在数组中的位置  
     * @date  2015年12月30日
     */ 
    public int locateVex(Object vex) {  
        for(int v = 0; v < vexNum; v++){
            if(vexs[v].getData().equals(vex))
                return v;
        }
        return -1;
    } 

    /**
     * @description 查找第一个邻接点  若没有邻接点则返回-1 
     * @date  2015年12月30日
     */
    public int firstAdjVex(int v) throws Exception { 
        if(v < 0 && v >= vexNum)
            throw new Exception("第" + v + "个顶点不存在");

        VNode vex = vexs[v]; 
        if(() != null)
            return ().getAdjVex();
        else 
            return -1; 
    }

    /**
     * @description 查找v的相对于w位置的邻接点的下一个邻接点，如 v-a-b-w-c（a,b,w,c都是v的邻接点）,那么返回的就是c 
     * @date  2015年12月30日
     */
    public int nextAdjVex(int v, int w) throws Exception { 
        if(v < 0 && v >= vexNum)
            throw new Exception("第" + v + "个顶点不存在");

        VNode vex = vexs[v];
        ArcNode arcvw = null;
        for(ArcNode arc = (); arc != null; arc = ()){
            if(() == w){
                arcvw = arc;
                break;
            }
        }
        if(arcvw != null && () != null)
            return ().getAdjVex();
        else
            return -1;
    }   

    public void display() throws Exception{
        for(int i = 0; i < vexNum; i++){
            VNode vex = vexs[i];
            (());
            for(ArcNode arc = (); arc != null; arc = ()){
                ("->" + getVex(()) +  ());
            }
            ();
        }
    }
}

构造一个具有n个顶点和e条边的网的时间复杂度是O（en）

相关文章