概叙

科普文：算法和数据结构系列【算法和数据结构概叙】-CSDN博客

这些数据结构在计算机科学和软件工程中有着广泛的应用，它们各自具有不同的特点和适用场景，选择合适的数据结构对于解决特定问题至关重要。

1. 数组：一种线性数据结构，元素按顺序存储。（已梳理）

2. 链表：一种线性数据结构，元素通过指针链接。（已梳理）

科普文：算法和数据结构系列【数据结构：数组和链表】-CSDN博客

科普文：算法和数据结构系列【数据结构：链表扩展之跳表Skip List原理、应用即java实现跳表】-CSDN博客

科普文：算法和数据结构系列【数据结构：链表扩展之有序链表（Sorted Linked List）和LRU缓存链表（LRU Cache Linked List）‌原理、应用即java实现】-CSDN博客

3. 栈：一种后进先出（LIFO）的数据结构。（已梳理）

4. 队列：一种先进先出（FIFO）的数据结构。（已梳理）

科普文：算法和数据结构系列【线性数据结构：栈和队列的原理、应用、以及java实现】-CSDN博客

5. 树：一种层次结构的数据结构，如二叉树、红黑树等。（已梳理）

6. 堆（树）：一种特殊的树形数据结构。堆通常被实现为完全二叉树，并满足堆性质：即子结点的键值或索引总是小于（或大于）它的父结点。如：最大堆、最小堆。（已梳理）

科普文：算法和数据结构系列【非线性数据结构：树Tree和堆Heap的原理、应用、以及java实现】-CSDN博客

7. 图：一种表示实体及其关系的数据结构。（已梳理）

8. 哈希表：一种通过键值对存储数据的数据结构。（已梳理）

科普文：算法和数据结构系列【非线性数据结构：哈希表和位图的原理、应用、以及java实现】-CSDN博客

‌图（Graph）

图是一个二元组G=(V(G),E(G))。其中V(G)是非空集，称为点集，对于V中的每个元素，我们称其为顶点或节点，简称点；E(G)为V(G)各节点之间边的集合，称为边集。

常用G=(V,E)表示图。

• 定义：图由顶点（Vertex）和边（Edge）组成，用于表示实体之间的连接关系。
• 基本术语：包括顶点、边、路径、度、入度、出度等。
• 分类：无向图、有向图、完全图、加权图、稀疏图、稠密图等。

图（Graph）是由顶点的有穷非空集合和顶点之间边的集合组成，通常表示为G(V,E)，其中G表示一个图，V是图G中顶点的集合，E是图G中边的集合。

图是一种较线性表和树更加复杂的数据结构，在图形结构中，结点之间的关系可以是任意的，图中任意两个数据元素之间都可能相关‌。

‌图的原理‌

图的原理基于顶点集合和边集合的定义。

顶点代表图中的实体或对象，而边则表示这些实体或对象之间的关系。

图可以是无向的，即边没有方向；也可以是有向的，即边具有方向性。

此外，图还可以是加权的，即每条边都关联有一个权重值，用于表示边上的某种度量‌1（如距离、成本等）。

图的存储方式主要有两种：邻接矩阵和邻接表。邻接矩阵是一个二维数组，用于表示图中各顶点间的连接情况；而邻接表则通过链表或数组等数据结构来存储每个顶点的相邻顶点信息‌。

图的结构

上面的定义可能较为抽象，我们也可以从另一个角度来理解图，即图的内部结构，图由哪些要素组成的——点与边。

简单来说图就是由若干个点以及连接两点的边构成的图形，而上面的定义也只是在说所有的点和所有的边组成图，这样是不是就很容易理解了。

​

其中点可以代表某种事物，而边可表示两个事物之间的关系，这样我们就可以把一些实际问题转为图，然后使用软件解决问题。

图数据结构

图数据结构主要有以下几种表示方法：

1. ‌邻接矩阵（Adjacency Matrix）‌：

   • 邻接矩阵是一个二维数组，其中行和列代表图中的顶点，数组中的元素值表示顶点之间是否存在边以及边的权重（对于加权图）。
   • 无向图的邻接矩阵是对称的，而有向图的邻接矩阵可能不是对称的。
   • 邻接矩阵的缺点是对于边数相对顶点较少的图（稀疏图），会浪费大量的存储空间。

2. ‌邻接表（Adjacency List）‌：

   • 邻接表是一个数组，其中每个元素是一个链表，链表中的节点表示与该顶点相邻的所有顶点。
   • 邻接表相对于邻接矩阵来说，更加节省存储空间，特别是对于稀疏图。
   • 邻接表可以方便地添加或删除边，但判断两个顶点之间是否存在边可能需要遍历链表。

3. ‌十字链表（Cross Linked List）‌：

   • 十字链表是有向图的一种链式存储结构，它将邻接表和逆邻接表整合在一起，便于同时获取顶点的出度和入度。
   • 在十字链表中，每个顶点都对应一个结点，每条弧也对应一个结点。

4. ‌邻接多重表（Adjacency Multilist）‌：

   • 邻接多重表主要用于无向图的存储，以边为中心进行存储。
   • 在邻接多重表中，同一条边只由一个结点表示，这样便于对边的操作。

5. ‌边集数组（Edge Set Array）‌：

   • 边集数组是由两个一维数组组成，一个数组用于存储顶点信息，另一个数组用于存储边的信息（包括起点、终点和权值）。
   • 边集数组可以方便地存储和访问边的信息，但不适用于需要频繁查询顶点邻接信息的情况。

每种表示方法都有其优缺点，选择哪种方法取决于具体问题的需求以及图的特性（如顶点数、边数、是否有向、是否加权等）。在实际应用中，应根据具体情况选择合适的图表示方法以提高算法的效率和性能。

图的分类

我们可以根据边是否有方向，是否带权，简单的将图分类为无向图、有向图、带权图，当然还有其他类型的图，现阶段我们就不过多介绍了，容易把自己搞晕。

（1）无向图

无向图顾名思义就是边没有方向，即两个点之间没有方向，没有顺序之分，这样的边叫作无向边，也简称边。其中点也叫作端点。

​

（2）有向图

有向图则指边有方向，也就代表边所连接的两点有顺序之分，其中一个为起点，则另一个则为终点，而这样的边就叫作有向边或弧。起点和终点也叫端点。

其中同一个点既可以是起点，也可以是终点。

​

对于任何图，与一个点关联的所有边数称为该点的度。而对于有向图来说，以一个点为起点的边数称为该的点出度，以一个点为终点的边数称为该点的入度。

如上图点A的出度为3，入度1。

（3）带权图

带权图指每个边都带有一个权重，代表边连接的两点关系的强弱、远近。同时权只是代表边的权重，并不代表边的方向，因此无论无边图还是有边图都可以是带权图。

​

（4）图的示例

1. ‌无向图示例‌：

   假设有一个无向图G，其顶点集合V={A, B, C, D}，边集合E={(A, B), (B, C), (C, D), (D, A)}。这个图可以表示为：​

   其中，每条边都是无向的，表示两个顶点之间存在连接关系。

2. ‌有向图示例‌：

   假设有一个有向图G，其顶点集合V={A, B, C, D}，边集合E={<A, B>, <B, C>, <C, D>}。这个图可以表示为：A -> B -> C -> D

   其中，每条边都是有向的，表示顶点之间的连接关系具有方向性。

3. ‌加权图示例‌：

   假设有一个加权图G，其顶点集合V={A, B, C, D}，边集合E={(A, B, 5), (B, C, 3), (C, D, 2), (D, A, 7)}。这个图可以表示为：A - 5 -> B - 3 -> C - 2 -> D - 7 -> A

   其中，每条边都有一个权重值，表示两个顶点之间关系的某种度量（如距离、成本等）。

4. ‌社交网络图示例‌：

   在社交网络中，图可以用来表示用户之间的关系。假设有一个社交网络图G，其顶点集合V={用户1, 用户2, 用户3, 用户4}，边集合E={(用户1, 用户2), (用户1, 用户3), (用户2, 用户3), (用户3, 用户4)}。这个图可以表示为：

   其中，每个顶点代表一个用户，每条边代表两个用户之间的好友关系。

5. ‌地铁路线图示例‌：

   地铁路线图也可以用图来表示。假设有一个地铁路线图G，其顶点集合V={站点A, 站点B, 站点C, 站点D}，边集合E={(站点A, 站点B), (站点B, 站点C), (站点C, 站点D)}。这个图可以表示为：站点A - 站点B - 站点C - 站点D

   其中，每个顶点代表一个地铁站点，每条边代表两个站点之间的地铁线路。

这些示例展示了图在数据结构中的多种应用场景，包括表示对象之间的连接关系、有向关系、加权关系等。在实际应用中，图可以用于解决各种复杂的问题，如路径查找、网络流、最短路径等。

图的存储方式

了解了图的基本知识以后，带来了一个新的问题，这么复杂的结构我们要怎么存储下来呢？

下面我们就来介绍几种常用的存储方式邻接矩阵、邻接表、逆邻接表、十字链表。

1、邻接矩阵

邻接矩阵就是用一个二维数组来存储任意两点之间的关系，其中行列索引表示点，而行列索引所在的位置的值表示两点关系，其中两点关系可以用以下数值表示：

（1）0：表示两点之间没有边；

（2）1：表示两点之间有边；

（3）权值：表示两点之间边的权值；

如果图存在n个点，则可以用n x n的二维数组来表示图，下面我们来看看常见图的表示方式。

（1）无向图

对于无向图，如果点A与点B有边，则[A,B]与[B,A]都为1，否则都为0，因此无向图的邻接矩阵是对称的，如下图：

​

（2）有向图

对于有向图，则可以通过把行索引当作边的起点，把列当作边的终点，来表示方向，比如[A,B]为1，而[B,A]为0，如下图：

​

对于有向图，我们可以发现关于点的度有以下特性：

点的出度就是第i行元素之和；

点的入度就是第i列元素之和；

点的度就是第i行元素之和 + 第i列元素之和；

（3）带权图

对于带权图，本质上和无向图与有向图相同，只是存储的值有所差别，如果两点之间有边则直接存权值，如果两点之间无边则存一个特殊值（如0、无穷），如果可以保证权值中不存在0,可以用0，否则要选一个其他特殊值，如下图：

​

邻接矩阵优点：

（1）简单直观：实现简单，易于理解，尤其适合小型图。

（2）快速查找：便于判断两点之间是否有边，以及各点的度。

邻接矩阵缺点：

（1）空间浪费：空间复杂度高为O(n^2)，对于稀疏图，许多元素为零，造成空间浪费。

（2）不易扩展：不便于插入和删除点，需要更新整个矩阵，时间复杂度高为O(n)。

2、邻接表

对于邻接矩阵空间浪费以及不易扩展的问题，发展出了另一种链式存储方式——「邻接表」。

邻接表的存储思想和前面章节介绍的散列的链式存储很像。首先我们用一个数组存储所有的点，而每个点元素又作为单链表头，其后继节点则存储与头节点相邻的点元素。

（1）无向图

如下图，图中所有点都存储在数组中，而与其相邻的点存储在其后面的链表中。

点A相邻的点为点B和点C;

点C相邻的点为点A、点D和点E；

点D相邻的点为点C；

​

（2）有向图

与无向图不同的是有向图链表中存储的不是所有相邻的点，而是存储有方向的点，即以数组中的点为起的终点元素。

点A为起点的终点为点B和点C；

点B为起点的终点为点E；

点D为起点的终点不存在；

​

通过上图可以发现，邻接表对于有向图可以很直观的表示出某个点的出度，但是对于入度获取就很麻烦。

（3）带权图

带权图与无向图和有向图相比，只需要在元素中多加一个权重属性即可。

邻接表优点：

（1）节省空间：时间复杂度相对较低为O(m+n)，m为点数量，n为边数量，对于稀疏图存储效率更高；

（2）操作灵活：插入和删除点操作方便，时间复杂度为O(1)；

（3）出度易取：对于有向图获取某个点的出度非常方便，只需要找到这个点所在的数组元素位置，然后获取其链表中的元素个数即可；

邻接表缺点：

（1）不便查找：判断两点之间是否有边的时间复杂度为O(V), 其中V 是该点的相邻点数量；

（2）入度难算：对于有向图点的入度的计算难度较大，时间复杂度为 O(E)，其中E是图中的边的数量；

3、逆邻接表

逆邻接表从名字上就可以看出来和邻接表是逆的关系，这个逆就体现在入度和出度上。我们知道邻接表计算出度容易，计算入度难，而逆邻接表恰恰相反是计算入度容易，计算出度难。

如下图数组中存储点元素，而链表中存储的是以数组中的点为终点的起点元素。

点A为终点的起点不存在；

点B为终点的起点为点A；

点D为终点的起点为点A和点E；

​

与邻接表差异在于在存储的方向正好相反，所以入度和出度计算难度正好相反，而其他则完全一样。

4、十字链表

邻接表出度计算容易，逆邻接表入度计算容易，那么有没有一种结构同时计算出度入度都容易呢？答案就是十字链表。

十字链表是邻接表和逆邻接表的结合体，每个点的边通过双向链表存储，同时记录了边的出度和入度。

下面我们详细讲解一下十字链表是怎么得到的。

（1）合并逆邻接表与邻接表

如下图我们之间把逆邻接表和邻接表拼接到一起，得到一个伪十字链表。

​

之所以称这个结合体为伪十字链表，是因为它虽然同时存储了边的两个方向，解决了出度入度计算问题，但是也引发了新的问题——存储效率低。

从上图不难看出链表中存在严重的重复存储的问题。要解决这个问题，我们先梳理一下我们得到的伪十字链表结构。

（2）链表由存点改存边

首先数组存储所有点，左侧链表存储起点元素集合，右侧链表存储终点元素集合；然后我们想为什么需要两条链表呢？因为一条链表就代表一个方向；

那第一步我们是否可以先解决方向的问题呢？而目前的结构节点只有一个点的信息，显然没有方向性，因此我们需要把链表节点改造成包含两个点的结构即起点和终点，这也意味着链表由原来存储点元素变为存储边元素。

原来点A出度链表存储点B和点C，现在改为存储[A->B]边和[A->C]边。

原来点B入度链表存储点A，现在改为存储[A->B]边。

如下图：

​

（3）删除重复元素

到这里就有条件解决重复的元素的问题了，比如上面链表中有两个[A->B]边，如果我们想把点B入度链表中[A->B]边删除，那么我们必须要有一个途径使得点B的入度链表可以和点A的出度链表中[A->B]边链接上。

首先数组元素结构应该至少包含：数据域|入边头节点指针|出边头节点指针；

然后链表节点元素结构应该至少包含：边起点下标|边终点下标|下一个入边节点指针域|下一个出边节点指针域；

下面我们进行去除重复元素，首先表里下出度链表结构，移除现有入度链表，其中入度链表中的元素指向到出度链表中，最后结果如下图：

​

如上图红色实线箭头表示出度链表，而彩色虚线箭头表示入度链表。

点A为终点的边不存在，点A为起点的边为 [A->B]边和[A->C]边；

点B为终点的边为[A->B]边（即红色1号虚线），点B为起点的边为 [B->E]边；

点C为终点的边为[A->C]边（即绿色2号虚线）和[E->C]边（即绿色3号虚线）,点C为起点的边为[C->D]边；

十字链表总结

优点：

（1）高效存储，适合复杂的有向图，支持快速遍历；

（2）快速计算出度入度；

缺点：

（1）实现复杂，维护难度高；

注：测试方法代码以及示例源码都已经上传至代码库，有兴趣的可以看看。https://gitee.com/hugogoos/Planner

图的遍历（算法）

在图的基本功能中有个很重要的功能——遍历，遍历顾名思义就是把图上所有的点都访问一遍，具体来说就是从一个连通的图中某一个点出发，沿着边访问所有的点，并且每个点只能访问一遍。

下面我们介绍两种常见的遍历方式：深度优先遍历（DFS）和广度优先遍历（BFS）。

1、深度优先遍历

如果我们把边当作路，深度优先遍历就是路一直往下走，直到没路了再返回走其他路。其实优点像树的先序遍历从根节点沿着子节点一直向下直到叶子节点再调头。

下面我们梳理一下深度优先遍历大致分为以下几个步骤：

（1）从图中任意一个点A出发，并访问点；

（2）找出点A的第一个未被访问的邻接点，并访问该点；

（3）以该点为新的点，重复步骤（2），直至新的邻接点没有未被访问的邻接点；

（4）返回前一个点并依次访问前一个点为未被访问的其他邻接点，并访问该点；

（5）重复步骤（3）和（4），直至所有点都被访问过；

​

如上图演示了从点A出发进行深度优先遍历过程，其中红色虚线表示前进路线，蓝色虚线表示回退路线。最后输出：A->B->E->F->C->G->D。

2、广度优先遍历

如果说深度优先遍历是找到一条路一直走到底，那么广度优先遍历就是先把所有的路走一步再说。其实优点像树的层次遍历从根节点出发先遍历其子节点然后再遍历其孙子节点直至遍历完所有节点。

下面我们梳理一下广度优先遍历大致分为以下几个步骤：

（1）从图中任意一点A出发，并访问点A；

（2）依次访问点A所有未被访问的邻接点，访问完邻接点后，然后按邻接点顺序把邻接点作为新的出发执行步骤（1）；

（3）重复步骤（1）和（2）直至所有点都被访问到。

​

如上图演示了从点A出发进行广度优先遍历过程，其中红色虚线表示前进路线。最后输出：A->B->C->D->E->F->G。

‌图的优缺点‌

‌优点‌：表达能力强，能够描述复杂的关系和结构；简洁直观，易于理解和可视化；丰富的算法，适用于多种实际问题。

• 图能够直观地表示实体之间的关系，具有强大的表达能力。
• 图结构灵活，可以表示复杂的网络结构，如社交网络、交通网络等。
• 通过图的遍历算法，可以高效地搜索图中的路径、环等结构。

‌缺点‌：计算复杂度高，特别是在处理大规模图时；数据表示限制，不能直接表示其他属性；难以处理动态变化。

• 对于大规模的图，存储和处理的开销可能较大。
• 图的遍历算法可能涉及复杂的递归或迭代过程，实现起来可能较为困难。

‌图的应用场景‌

图在多个领域都有广泛的应用，包括但不限于：

• ‌社交网络分析‌：利用图来表示用户之间的关系，分析社交网络的拓扑结构、影响力传播等。
• ‌交通网络优化‌：将交通网络表示为图，通过算法来优化路线规划、减少拥堵等。
• ‌推荐系统‌：利用图来表示用户与物品之间的关系，通过图算法来推荐用户可能感兴趣的物品。
• ‌搜索引擎‌：利用图来表示网页之间的链接关系，通过PageRank等算法来评估网页的重要性。
• 网络路由和通信：优化数据包传输路径，提高网络效率。
• 项目管理：优化任务依赖和调度，确保项目按时完成。
• 生物信息学：研究分子结构、基因网络等。

‌图的注意事项‌

• 在使用图时，需要根据具体的应用场景选择合适的存储方式和遍历算法。
• 对于大规模的图，需要考虑存储和处理的效率问题，可能需要采用分布式存储和并行处理等技术。
• 在处理图时，需要注意图的连通性、环等特性，以避免出现错误或无效的结果。
• 对于加权图，需要确保权重值的合理性和有效性，以反映实体之间的真实关系‌。
• 明确图的目的和受众，选择合适的图表类型。
• 确保数据的准确性和完整性，避免误导。
• 设计简洁明了，避免过度装饰，使用清晰的标签和刻度。
• 添加适当的标题和注释，增强图表的可读性。
• 绘制完成后，进行反复检查和验证。

图的java实现包括两种遍历

package com.zxx.study.algorithm.datastruct.DataStructures.graph;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.LinkedList;

public class Graph {

	private ArrayList<String> vertexList; //存储顶点集合
	private int[][] edges; //存储图对应的邻结矩阵
	private int numOfEdges; //表示边的数目
	//定义给数组boolean[], 记录某个结点是否被访问
	private boolean[] isVisited;
	
	public static void main(String[] args) {
		//测试一把图是否创建ok
		int n = 8;  //结点的个数
		//String Vertexs[] = {"A", "B", "C", "D", "E"};
		String Vertexs[] = {"1", "2", "3", "4", "5", "6", "7", "8"};
		
		//创建图对象
		Graph graph = new Graph(n);
		//循环的添加顶点
		for(String vertex: Vertexs) {
			graph.insertVertex(vertex);
		}
		
		//添加边
		//A-B A-C B-C B-D B-E 
//		graph.insertEdge(0, 1, 1); // A-B
//		graph.insertEdge(0, 2, 1); // 
//		graph.insertEdge(1, 2, 1); // 
//		graph.insertEdge(1, 3, 1); // 
//		graph.insertEdge(1, 4, 1); // 
		
		//更新边的关系
		graph.insertEdge(0, 1, 1);
		graph.insertEdge(0, 2, 1);
		graph.insertEdge(1, 3, 1);
		graph.insertEdge(1, 4, 1);
		graph.insertEdge(3, 7, 1);
		graph.insertEdge(4, 7, 1);
		graph.insertEdge(2, 5, 1);
		graph.insertEdge(2, 6, 1);
		graph.insertEdge(5, 6, 1);

		
		
		//显示一把邻结矩阵
		graph.showGraph();
		
		//测试一把，我们的dfs遍历是否ok
		System.out.println("深度遍历");
		graph.dfs(); // A->B->C->D->E [1->2->4->8->5->3->6->7]
		System.out.println();
		System.out.println("广度优先!");
		graph.bfs(); // A->B->C->D-E [1->2->3->4->5->6->7->8]
		
	}
	
	//构造器
	public Graph(int n) {
		//初始化矩阵和vertexList
		edges = new int[n][n];
		vertexList = new ArrayList<String>(n);
		numOfEdges = 0;
		
	}
	
	//得到第一个邻接结点的下标 w 
	/**
	 * 
	 * @param index 
	 * @return 如果存在就返回对应的下标，否则返回-1
	 */
	public int getFirstNeighbor(int index) {
		for(int j = 0; j < vertexList.size(); j++) {
			if(edges[index][j] > 0) {
				return j;
			}
		}
		return -1;
	}
	//根据前一个邻接结点的下标来获取下一个邻接结点
	public int getNextNeighbor(int v1, int v2) {
		for(int j = v2 + 1; j < vertexList.size(); j++) {
			if(edges[v1][j] > 0) {
				return j;
			}
		}
		return -1;
	}
	
	//深度优先遍历算法
	//i 第一次就是 0
	private void dfs(boolean[] isVisited, int i) {
		//首先我们访问该结点,输出
		System.out.print(getValueByIndex(i) + "->");
		//将结点设置为已经访问
		isVisited[i] = true;
		//查找结点i的第一个邻接结点w
		int w = getFirstNeighbor(i);
		while(w != -1) {//说明有
			if(!isVisited[w]) {
				dfs(isVisited, w);
			}
			//如果w结点已经被访问过
			w = getNextNeighbor(i, w);
		}
		
	}
	
	//对dfs 进行一个重载, 遍历我们所有的结点，并进行 dfs
	public void dfs() {
		isVisited = new boolean[vertexList.size()];
		//遍历所有的结点，进行dfs[回溯]
		for(int i = 0; i < getNumOfVertex(); i++) {
			if(!isVisited[i]) {
				dfs(isVisited, i);
			}
		}
	}
	
	//对一个结点进行广度优先遍历的方法
	private void bfs(boolean[] isVisited, int i) {
		int u ; // 表示队列的头结点对应下标
		int w ; // 邻接结点w
		//队列，记录结点访问的顺序
		LinkedList queue = new LinkedList();
		//访问结点，输出结点信息
		System.out.print(getValueByIndex(i) + "=>");
		//标记为已访问
		isVisited[i] = true;
		//将结点加入队列
		queue.addLast(i);
		
		while( !queue.isEmpty()) {
			//取出队列的头结点下标
			u = (Integer)queue.removeFirst();
			//得到第一个邻接结点的下标 w 
			w = getFirstNeighbor(u);
			while(w != -1) {//找到
				//是否访问过
				if(!isVisited[w]) {
					System.out.print(getValueByIndex(w) + "=>");
					//标记已经访问
					isVisited[w] = true;
					//入队
					queue.addLast(w);
				}
				//以u为前驱点，找w后面的下一个邻结点
				w = getNextNeighbor(u, w); //体现出我们的广度优先
			}
		}
		
	} 
	
	//遍历所有的结点，都进行广度优先搜索
	public void bfs() {
		isVisited = new boolean[vertexList.size()];
		for(int i = 0; i < getNumOfVertex(); i++) {
			if(!isVisited[i]) {
				bfs(isVisited, i);
			}
		}
	}
	
	//图中常用的方法
	//返回结点的个数
	public int getNumOfVertex() {
		return vertexList.size();
	}
	//显示图对应的矩阵
	public void showGraph() {
		for(int[] link : edges) {
			System.err.println(Arrays.toString(link));
		}
	}
	//得到边的数目
	public int getNumOfEdges() {
		return numOfEdges;
	}
	//返回结点i(下标)对应的数据 0->"A" 1->"B" 2->"C"
	public String getValueByIndex(int i) {
		return vertexList.get(i);
	}
	//返回v1和v2的权值
	public int getWeight(int v1, int v2) {
		return edges[v1][v2];
	}
	//插入结点
	public void insertVertex(String vertex) {
		vertexList.add(vertex);
	}
	//添加边
	/**
	 * 
	 * @param v1 表示点的下标即使第几个顶点  "A"-"B" "A"->0 "B"->1
	 * @param v2 第二个顶点对应的下标
	 * @param weight 表示 
	 */
	public void insertEdge(int v1, int v2, int weight) {
		edges[v1][v2] = weight;
		edges[v2][v1] = weight;
		numOfEdges++;
	}
}

运行结果：