数据结构–图（一）(图的存储结构)

Myth丶恋晨 2022-06-05 11:23 230阅读 0赞

### （一）图的抽象数据类型 ###

> 数据类型是指一个类型和定义在这个类型上的操作集合（如整型和加减乘除等操作），抽象数据类型是指一个逻辑概念上的类型和这个类型上的操作集合。

数据集合：由节点集合和边集合组成。  
操作集合：初始化、插入/删除节点/边、寻找邻接节点

### （二）图的存储结构 ###

图要存储的信息包括：节点信息+描述节点间关系的边的信息  
节点信息的描述实际是一个线性表的存储问题  
边信息描述实际是一个（n\*n）矩阵在计算机内的存储问题  
按照边的存储方式，分为图的存储分为**邻接矩阵**存储和**邻接表**存储

#### 邻接矩阵存储 ####

节点采用一维数组存储；边信息的邻接矩阵采用二维数组存储。

> 邻接矩阵存储适用于稠密矩阵

#### 邻接表存储 ####

图的一种链式存储结构  
图中顶点采用一维数组存储，顶点数组中的数据元素除了存储节点信息，还要存储该顶点的第一个邻接点的指针，便于查找该顶点的边信息。即，每个顶点由data域、adj域两部分组成，data域存储节点信息，adj域存储该顶点的邻接顶点链表的头指针。  
图中边采用链表存储。对图中每个顶点vi建立一个单链表，第i个单链表中的各个结点表示依附于顶点vi的边。每个结点由vex域、wei域、以及next域组成，vex域存储与起始顶点vi相连的邻接顶点vj在顶点数组中的下标序号；wei域存储两个顶点之间边的权值；next存储下一个邻接结点的指针域。

> 邻接表存储结构适用于稀疏图

### （三）邻接矩阵图类设计 ###

public class AdjMWGraph{
        static final int maxWeight=10000;//图中边权值的最大值，用于表示无穷
    
        private SeqList nodes;//存储节点的顺序表
        private int[][] edge;//存储边权值的二维数组
        private int numOfEdge;//存储图中边的个数
    
        public AdjMWGraph(int numOfNode){//numOfNode表示节点数
            nodes=new SeqList(numOfNode);//为节点和边分配空间并初始化
            edge=new int[numOfNode][numOfNode];
            for(int i=0;i<numOfNode;i++){
                for(int j=0;j<numOfNode;j++){
                    if(i==j)
                        edge[i][j]=0;
                    else
                        edge[i][j]=maxWeight;
                }
            }
            numOfEdge=0;        
        }
    
        public int getNumOfNode(){return nodes.size();  }
        public int getNumOfEdge(){return numOfEdge;}
        public int getWeight(int v1,int v2){ return edge[v1][v2];}
    
        public void insetNode(Object node){
            nodes.insert(nodes.size,node);//在节点顺序表的末尾加入节点
        }
        public void insertEdge(int v1,int v2,int weight){
            edge[v1][v2]=weight;//无向图插入一条边要更新邻接矩阵的两个值
            edge[v1][v2]=weight;
            numOfEdge++;
        }
        //…………
    }