前言
由于图的结构比较复杂，任意两个顶点之间都可能存在关系（边），无法通过存储位置表示这种任意的逻辑关系，所以，图无法采用顺序存储结构。这一点同其他数据结构（如线性表、树）不同。
因为图中的顶点具有相对概念，没有固定的位置，且顶点和顶点之间通过添加和删除边，维持着不同的关系。考虑图的定义，图是由顶点和边组成的。所以，分别考虑如何存储顶点和边。图常用的存储结构有邻接矩阵、邻接表、十字链表和邻接多重表。那么对于一般情况下该怎么存储图的数据结构呢？这里我们主要分两个章节详细介绍两种常用的图存储结构 — 邻接矩阵、邻接表
图的类型&存储结构的介绍
图的类型主要有4种：无向图、有向图、无向网和有向网。
可以用枚举表示为：
public enum GraphKind{ UDG, //无向图(UnDirected Graph) DG, //有向图(Directed Graph) UDN, //无向网(UnDirected Network) DN, //有向网(Directed Network) }
图有多种存储结构，每种存储结构都能表示上面的4种的类型。图的存储结构除了存储图中各个顶点的信息外，还需要存储与顶点相关的边的信息。
常见图的存储结构：
邻接矩阵
邻接表
邻接多重表
十字链表
邻接矩阵
— 无向图、有向图的邻接矩阵定义
逻辑结构分为两部分：V和E集合，其中，V是顶点，E是边。因此，用一个一维数组存放图中所有顶点数据；用一个二维数组存放顶点间关系（边或弧）的数据，这个二维数组称为邻接矩阵。邻接矩阵又分为有向图邻接矩阵和无向图邻接矩阵。
图的邻接矩阵：用来表示顶点之间相邻关系的矩阵。
图G=(V, E)具有n(n >= 1)个顶点,顶点的顺序依次为{v0,v1,...,vn-1}
设图A=（V，E）有n个顶点，则关于顶点数据的一维数组为：
则图G的邻接矩阵A是一个n阶方阵，定义如下：
特点1：无向图 的邻接矩阵一定是对称 的，而 有向图 的邻接矩阵不一定对称。
因此，用 对无向图而言，邻接矩阵一定是对称的，而且主对角线一定为零，副对角线不一定为0，有向图则不一定如此。
邻接矩阵来表示一个具有n个顶点的有向图时需要n^2个单元来存储邻接矩阵；对有n个顶点的无向图则只需存入上（下）三角阵中剔除了左上右下对角线上的0元素后剩余的元素压缩存储，故只需1+2+...+(n-1)=n(n-1)/2个单元。
特点2：无向图邻接矩阵的 第i行（或第i列）非零元素的个数 正好是第i个顶点的度。
度（Degree）：一个顶点的度是指与该顶点相关联的边的条数，顶点v的度记作d(v)”
无向图，没有方向，所有两个顶点连线必定是相互的。因此行或列的非零元素个数必定一样。则找顶点的度时，看行或列都可以。
特点3：
有向图顶点的度【行表示出度，列表示入度】
顶点v的入边数目是该顶点的入度，记为ID(v);
顶点v的出边数目是该顶点的出度，记为OD(v);
顶点v的度等于它的入度和出度之和，即D(v)=ID(v)+OD(v)
有向图邻接矩阵中第i行非零元素的个数为第i个顶点的出度，第i列非零元素的个数为第i个顶点的入度，第i个顶点的度为第i行与第i列非零元素个数之和。
特点4：用邻接矩阵表示图，很容易看出确定图中任意两个顶点是否有边相连。
无向图的邻接矩阵是对称的，一般可以采用压缩存储。
— 网的邻接矩阵的定义
网(network)：带权的图
图与网的区别：
1. 权值：网里面对应的边是有权值的，用以表示边的某种属性比如距离等。而图的边是没有权值的
2. 表示零元素的形式不同：不管是无向图还是有向图表示零元素时，都用0代替表示；而在网中，表示零元素则是用无穷大∞ 表示。
无向网的邻接矩阵：
有向网的邻接矩阵 ：
邻接矩阵：类的描述
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 void createGraph(){} //创建图 private void createUDG() {} //创建无向图 private void createDG() {} //创建有向图 private void createUDN() {} //创建无向网 private void createDN() {} //创建有向网 public int getVexNum() { //返回定点数 return vexNum; } public int getArcNum() { //返回边数 return arcNum; } // 给定顶点的值vex，返回其在图中的位置，如果图中不包含此顶点，则返回-1 public int locateVex(Object vex) {} // 返回v表示结点的值，0 <= v <= vexNum public Object getVex(int v) throws Exception {} // 返回v的第一个邻接点，若v没有邻接点则返回-1。其中 0 <= v <= vexNum public int firstAdjVex(int v) throws Exception {} // 返回v相对于w的下一个邻接点，若w是v的最后一个邻接点，则返回-1。其中 0 <= v,w <= vexNum public int nextAdjVex(int v, int w) throws Exception {} }
邻接矩阵：基本操作
1）创建图
// 创建图 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: createUDN(); // 构建无向网 return; case DN: createDN(); // 构建有向网 return; } }
2）创建无向网
- 输入图的顶点、边及权值构造无向图，步骤：
- 输入顶点数或边数
- 根据图的顶点数构建邻接矩阵
- 根据图的边数，确定输入边的数目
- 根据输入每条边的顶点再邻接矩阵相应位置保存每条边的权值。
- 代码
private void createUDN() { //初始化变量 Scanner sc = new Scanner(System.in); System.out.println("请分别输入图的顶点数、图的边数:"); vexNum = sc.nextInt();//顶点数n arcNum = sc.nextInt();//边数e //输入图中各顶点 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[u][v] = sc.nextInt(); //权值, 对称 } }
3）创建有向网
// 构建有向网 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(); //仅设置顶点v-->顶点u，不是对称的，只需要设置一个 } }
4）顶点定位
- 根据顶点信息vex，取得其在顶点数组中的位置，若图中无此顶点，则返回-1。
- 代码：
// 根据顶点信息vex，取得其在顶点数组中的位置，若图中无此顶点，则返回-1。 public int locateVex(Object vex) { // 遍历顶点数组 for (int v = 0; v < vexNum; v++) if (vexs[v].equals(vex)) return v; return -1; }
- 时间复杂度：O(n)
5）查询第一个邻接点
步骤：
- 判断v的合法性
- 顶点v的索引号，对应邻接矩阵的第v行，遍历第v行，查找是否有非0、非无穷大值的元素
- 代码：
// 已知图中的一个顶点v，返回v的第一个邻接点，如果v没有连接点，则返回-1，其中0 <= v < vexNum 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; }
- 时间复杂度：O(n)
6）查找下一个邻接点
步骤：
- 判断v的合法性
- 从邻接矩阵第v行第w+1列开始遍历查找是否有非0、非无穷大值的元素
- 代码：
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; }
- 时间复杂度：O(n)
