数据结构基础温故-5.图（上）：图的基本概念
前面几篇已经介绍了线性表和树两类数据结构，线性表中的元素是“一对一”的关系，树中的元素是“一对多”的关系，本章所述的图结构中的元素则是“多对多”的关系。图（Graph）是一种复杂的非线性结构，在图结构中，每个元素都可以有零个或多个前驱，也可以有零个或多个后继，也就是说，元素之间的关系是任意的。现实生活中的很多事物都可以抽象为图，例如世界各地接入Internet的计算机通过网线连接在一起，各个城市和城市之间的铁轨等等。
一、图的基本概念
1.1 多对多的复杂关系
现实中人与人之间关系非常复杂，比如我认识的朋友，可能他们之间也互相认识，这不是简单的一对一、一对多，研究人际关系很自然会考虑多对多的情况。图是一种较线性表和树更加复杂的数据结构。在图形结构中，结点之间的关系可以是任意的，图中任意两个数据元素之间都可能相关。
定义：图（Graph）是由顶点的有穷非空集合和顶点之间边的集合组成，通常表示为：G(V,E)，其中，G表示一个图，V是图G中顶点的集合，E是图G中边的集合。
在图中需要注意的是：
（1）线性表中我们把数据元素叫元素，树中将数据元素叫结点，在图中数据元素，我们则称之为顶点（Vertex）。
（2）线性表可以没有元素，称为空表；树中可以没有节点，称为空树；但是，在图中不允许没有顶点（有穷非空性）。
（3）线性表中的各元素是线性关系，树中的各元素是层次关系，而图中各顶点的关系是用边来表示（边集可以为空）。
1.2 纷繁冗多的术语
图的基本术语有很多，本文只挑选几个特别重要的来说明，其余的请阅读相关教材。
（1）无向图
如果图中任意两个顶点之间的边都是无向边（简而言之就是没有方向的边），则称该图为无向图（Undirected graphs）。
（2）有向图
如果图中任意两个顶点之间的边都是有向边（简而言之就是有方向的边），则称该图为有向图（Directed graphs）。
（3）完全图
①无向完全图：在无向图中，如果任意两个顶点之间都存在边，则称该图为无向完全图。（含有n个顶点的无向完全图有(n×(n-1))/2条边）如下图所示：
②有向完全图：在有向图中，如果任意两个顶点之间都存在方向互为相反的两条弧，则称该图为有向完全图。（含有n个顶点的有向完全图有n×(n-1)条边）如下图所示：
PS：当一个图接近完全图时，则称它为稠密图（Dense Graph），而当一个图含有较少的边时，则称它为稀疏图（Spare Graph）。
（4）顶点的度
顶点Vi的度（Degree）是指在图中与Vi相关联的边的条数。对于有向图来说，有入度（In-degree）和出度（Out-degree）之分，有向图顶点的度等于该顶点的入度和出度之和。
（5）邻接
①若无向图中的两个顶点V1和V2存在一条边(V1,V2)，则称顶点V1和V2邻接（Adjacent）；
②若有向图中存在一条边<V3,V2>，则称顶点V3与顶点V2邻接，且是V3邻接到V2或V2邻接直V3；
PS：无向图中的边使用小括号“()”表示，而有向图中的边使用尖括号“<>”表示。
（6）路径
在无向图中，若从顶点Vi出发有一组边可到达顶点Vj，则称顶点Vi到顶点Vj的顶点序列为从顶点Vi到顶点Vj的路径（Path）。
（7）连通
若从Vi到Vj有路径可通，则称顶点Vi和顶点Vj是连通（Connected）的。
（8）权
有些图的边或弧具有与它相关的数字，这种与图的边或弧相关的数叫做权（Weight）。
二、图的存储结构
图的存储结构除了要存储图中的各个顶点本身的信息之外，还要存储顶点与顶点之间的关系，因此，图的结构也比较复杂。常用的图的存储结构有邻接矩阵和邻接表等。
2.1 邻接矩阵表示法
图的邻接矩阵（Adjacency Matrix）存储方式是用两个数组来表示图。一个一维数组存储图中顶点信息，一个二维数组（称为邻接矩阵）存储图中的边或弧的信息。
（1）无向图：
我们可以设置两个数组，顶点数组为vertex[4]={v0,v1,v2,v3}，边数组arc[4][4]为上图右边这样的一个矩阵。对于矩阵的主对角线的值，即arc[0][0]、arc[1][1]、arc[2][2]、arc[3][3]，全为0是因为不存在顶点的边。
（2）有向图：
我们再来看一个有向图样例，如下图所示的左边。顶点数组为vertex[4]={v0,v1,v2,v3}，弧数组arc[4][4]为下图右边这样的一个矩阵。主对角线上数值依然为0。但因为是有向图，所以此矩阵并不对称，比如由v1到v0有弧，得到arc[1][0]=1，而v到v没有弧，因此arc[0][1]=0。
不足：由于存在n个顶点的图需要n*n个数组元素进行存储，当图为稀疏图时，使用邻接矩阵存储方法将会出现大量0元素，这会造成极大的空间浪费。这时，可以考虑使用邻接表表示法来存储图中的数据。
2.2 邻接表表示法
首先，回忆我们在线性表时谈到，顺序存储结构就存在预先分配内存可能造成存储空间浪费的问题，于是引出了链式存储的结构。同样的，我们也可以考虑对边或弧使用链式存储的方式来避免空间浪费的问题。
邻接表由表头节点和表节点两部分组成，图中每个顶点均对应一个存储在数组中的表头节点。如果这个表头节点所对应的顶点存在邻接节点，则把邻接节点依次存放于表头节点所指向的单向链表中。
（1）无向图：下图所示的就是一个无向图的邻接表结构。
从上图中我们知道，顶点表的各个结点由data和firstedge两个域表示，data是数据域，存储顶点的信息，firstedge是指针域，指向边表的第一个结点，即此顶点的第一个邻接点。边表结点由adjvex和next两个域组成。adjvex是邻接点域，存储某顶点的邻接点在顶点表中的下标，next则存储指向边表中下一个结点的指针。例如：v1顶点与v0、v2互为邻接点，则在v1的边表中，adjvex分别为v0的0和v2的2。
PS：对于无向图来说，使用邻接表进行存储也会出现数据冗余的现象。例如上图中，顶点V0所指向的链表中存在一个指向顶点V3的同事，顶点V3所指向的链表中也会存在一个指向V0的顶点。
（2）有向图：若是有向图，邻接表结构是类似的，但要注意的是有向图由于有方向的。因此，有向图的邻接表分为出边表和入边表（又称逆邻接表），出边表的表节点存放的是从表头节点出发的有向边所指的尾节点；入边表的表节点存放的则是指向表头节点的某个顶点，如下图所示。
（3）带权图：对于带权值的网图，可以在边表结点定义中再增加一个weight的数据域，存储权值信息即可，如下图所示。
三、图的模拟实现
PS：由于邻接矩阵容易造成空间资源的浪费，因此这里只考虑使用邻接表来实现。
3.1 总体设计结构
（1）链表节点定义
①表头节点Vertex
/// <summary> /// 嵌套类：存放于数组中的表头节点 /// </summary> /// <typeparam name="TValue"></typeparam> protected class Vertex<TValue> { public TValue data; // 数据 public Node firstEdge; // 邻接点链表头指针 public bool isVisited; // 访问标志：遍历时使用 public Vertex() { this.data = default(TValue); } public Vertex(TValue value) { this.data = value; } }
②表节点Node
/// <summary> /// 嵌套类：链表中的表节点 /// </summary> protected class Node { public Vertex<T> adjvex; // 邻接点域 public Node next; // 下一个邻接点指针域 public Node() { this.adjvex = null; } public Node(Vertex<T> value) { this.adjvex = value; } }
（2）邻接表总体定义
public class MyAdjacencyList<T> where T : class { private List<Vertex<T>> items; // 图的顶点集合 public MyAdjacencyList() : this(10) { } public MyAdjacencyList(int capacity) { this.items = new List<Vertex<T>>(capacity); } #region 基本方法：为图中添加顶点、添加有向与无向边 #endregion #region 辅助方法：图中是否包含某个元素、查找指定顶点、初始化visited标志 #endregion #region 嵌套类：表头节点与表节点定义 #endregion }
首先，我们使用了一个动态集合List来代替数组存储Vertex的集合，默认容量为10，且不需要数组存储空间不够的情况，简化了操作。其次，我们要定义一些基本方法，如添加顶点、添加边。还要定义一些辅助方法，如判断是否包含某个元素等（详见完整代码文件）。最后，我们再实现图的一些遍历算法，如深度优先遍历与广度优先遍历（本篇不作介绍，下一篇再介绍）。
3.2 基本方法实现
（1）添加一个顶点
/// <summary> /// 添加一个顶点 /// </summary> /// <param name="item">顶点元素data</param> public void AddVertex(T item) { if (Contains(item)) { throw new ArgumentException("添加了重复的顶点！"); } Vertex<T> newVertex = new Vertex<T>(item); items.Add(newVertex); }
就是往集合里边加入新元素；
（2）添加一条边
这里需要分为两种情况，一种是添加无向图的边，这时无向图的两个顶点都需要记录边的信息。另一种则是添加有向图的边，这时只需要一条记录；
①无向图
/// <summary> /// 添加一条无向边 /// </summary> /// <param name="from">头顶点data</param> /// <param name="to">尾顶点data</param> /// <param name="weight">权值</param> public void AddEdge(T from, T to) { Vertex<T> fromVertex = Find(from); if (fromVertex == null) { throw new ArgumentException("头顶点不存在！"); } Vertex<T> toVertex = Find(to); if (toVertex == null) { throw new ArgumentException("尾顶点不存在！"); } // 无向图的两个顶点都需要记录边的信息 AddDirectedEdge(fromVertex, toVertex); AddDirectedEdge(toVertex, fromVertex); }
这里可以看到这两句代码，对应的两个顶点都记录了边的信息。
// 无向图的两个顶点都需要记录边的信息 AddDirectedEdge(fromVertex, toVertex); AddDirectedEdge(toVertex, fromVertex);
②有向图
/// <summary> /// 添加一条有向边 /// </summary> /// <param name="from">头结点data</param> /// <param name="to">尾节点data</param> public void AddDirectedEdge(T from, T to) { Vertex<T> fromVertex = Find(from); if (fromVertex == null) { throw new ArgumentException("头顶点不存在！"); } Vertex<T> toVertex = Find(to); if (toVertex == null) { throw new ArgumentException("尾顶点不存在！"); } AddDirectedEdge(fromVertex, toVertex); }
③如何添加边
在实现中，无论是无线图还是有向图都是添加的有向边，只不过无向图是添加了两条有向边：
/// <summary> /// 添加一条有向边 /// </summary> /// <param name="fromVertex">头顶点</param> /// <param name="toVertex">尾顶点</param> private void AddDirectedEdge(Vertex<T> fromVertex, Vertex<T> toVertex) { if (fromVertex.firstEdge == null) { fromVertex.firstEdge = new Node(toVertex); } else { Node temp = null; Node node = fromVertex.firstEdge; do { // 检查是否添加了重复边 if (node.adjvex.data.Equals(toVertex.data)) { throw new ArgumentException("添加了重复的边！"); } temp = node; node = node.next; } while (node != null); Node newNode = new Node(toVertex); temp.next = newNode; } }
（3）打印每个顶点及其邻接点的信息
/// <summary> /// 打印打印每个顶点和它的邻接点 /// </summary> /// <param name="isDirectedGraph">是否是有向图</param> public string GetGraphInfo(bool isDirectedGraph = false) { StringBuilder sb = new StringBuilder(); foreach (Vertex<T> v in items) { sb.Append(v.data.ToString() + ":"); if (v.firstEdge != null) { Node temp = v.firstEdge; while (temp != null) { if (isDirectedGraph) { sb.Append(v.data.ToString() + "→" + temp.adjvex.data.ToString() + " "); } else { sb.Append(temp.adjvex.data.ToString()); } temp = temp.next; } } sb.Append("\r\n"); } return sb.ToString(); }
这里判断了是否是有向图，如果是有向图则显示A→B的形式，如果是无向图则显示A：B的形式。
3.3 基本功能测试
这里我们对基本功能做一下测试，分为无向图和有向图，首先插入顶点及对应边，然后打印顶点及其邻接表的信息，要构造的无向图与有向图如上面两张图所示，测试代码如下所示：
static void MyAdjacencyListTest() { Console.WriteLine("------------无向图------------"); MyAdjacencyList<string> adjList = new MyAdjacencyList<string>(); // 添加顶点 adjList.AddVertex("A"); adjList.AddVertex("B"); adjList.AddVertex("C"); adjList.AddVertex("D"); //adjList.AddVertex("D"); // 会报异常：添加了重复的节点 // 添加无向边 adjList.AddEdge("A", "B"); adjList.AddEdge("A", "C"); adjList.AddEdge("A", "D"); adjList.AddEdge("B", "D"); //adjList.AddEdge("B", "D"); // 会报异常：添加了重复的边 Console.Write(adjList.GetGraphInfo()); Console.WriteLine("------------有向图------------"); MyAdjacencyList<string> dirAdjList = new MyAdjacencyList<string>(); // 添加顶点 dirAdjList.AddVertex("A"); dirAdjList.AddVertex("B"); dirAdjList.AddVertex("C"); dirAdjList.AddVertex("D"); // 添加有向边 dirAdjList.AddDirectedEdge("A", "B"); dirAdjList.AddDirectedEdge("A", "C"); dirAdjList.AddDirectedEdge("A", "D"); dirAdjList.AddDirectedEdge("B", "D"); Console.Write(dirAdjList.GetGraphInfo(true)); }
运行结果如下图所示：
附件下载
本篇实现的图的邻接表结构：code.datastructure.graph
参考资料
（1）程杰，《大话数据结构》
（2）陈广，《数据结构（C#语言描述）》
（3）段恩泽，《数据结构（C#语言版）》
