数据结构基础温故-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

View Code

  ②表节点Node

View Code

  (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)添加一个顶点

View Code

  就是往集合里边加入新元素;

  (2)添加一条边

  这里需要分为两种情况,一种是添加无向图的边,这时无向图的两个顶点都需要记录边的信息。另一种则是添加有向图的边,这时只需要一条记录;

  ①无向图

View Code

  这里可以看到这两句代码,对应的两个顶点都记录了边的信息。

    // 无向图的两个顶点都需要记录边的信息
    AddDirectedEdge(fromVertex, toVertex);
    AddDirectedEdge(toVertex, fromVertex);

  ②有向图

View Code

  ③如何添加边

  在实现中,无论是无线图还是有向图都是添加的有向边,只不过无向图是添加了两条有向边:

View Code

  (3)打印每个顶点及其邻接点的信息

View Code

  这里判断了是否是有向图,如果是有向图则显示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#语言版)》

作者:周旭龙

出处:http://edisonchou.cnblogs.com

本文版权归作者和博客园共有,欢迎转载,但未经作者同意必须保留此段声明,且在文章页面明显位置给出原文链接。

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏从流域到海域

图(Graph)的常用代码集合

图的相关概念请查阅离散数学图这一章或者数据结构中对图的介绍。代码来自课本。 /*Graph存储结构*/ //邻接矩阵表示法 #define MAX_VERTEX...

41260
来自专栏架构之路

Kosaraju算法、Tarjan算法分析及证明--强连通分量的线性算法

一、背景介绍 强连通分量是有向图中的一个子图,在该子图中,所有的节点都可以沿着某条路径访问其他节点。强连通性是一种非常重要的等价抽象,因为它满足 自反性:顶点V...

44760
来自专栏机器学习与自然语言处理

Lake Counting(POJ-2386)

题目链接: http://poj.org/problem?id=2386 题目大意: 计算出相连的'W'有多少块 所需算法: 深度优先搜索(DFS) 主要思路:...

25670
来自专栏机器学习与自然语言处理

判断有向图是否有圈

1. 拓扑排序 拓扑排序是对有向无圈图的顶点的一种排序:如果存在一条vi到vj的路径,则vj排在vi后面(因为只要满足这个特性就是拓扑序列,所以它不一定是唯一的...

53980
来自专栏尾尾部落

[剑指offer] 跳台阶

一只青蛙一次可以跳上1级台阶,也可以跳上2级。求该青蛙跳上一个n级的台阶总共有多少种跳法(先后次序不同算不同的结果)。

10420
来自专栏向治洪

数据结构之图

基本概念 图(Graph):图(Graph)是一种比线性表和树更为复杂的数据结构。 图结构:是研究数据元素之间的多对多的关系。在这种结构中,任意两个元素之间...

22850
来自专栏数据结构与算法

BZOJ3143: [Hnoi2013]游走(期望DP 高斯消元)

Description 一个无向连通图,顶点从1编号到N,边从1编号到M。  小Z在该图上进行随机游走,初始时小Z在1号顶点,每一步小Z以相等的概率随机选 择当...

50260
来自专栏mathor

LeetCode218. 天际线问题

 如果按照一个矩形一个矩形处理会非常麻烦,我们把这些矩形拆成两个点,一个左上角顶点,一个右上角顶点。将所有顶点按照横坐标进行排序然后开始遍历,遍历时通过一个...

14820
来自专栏zaking's

用js来实现那些数据结构15(图01)

21440
来自专栏算法与数据结构

数据结构 图

1-1 无向连通图至少有一个顶点的度为1 错误: 无向连通图考点: 1. 每条边连接两个顶点,所有顶点的度之和等于边数的2倍 2.记住两个特殊的无相连通图模型:...

48970

扫码关注云+社区

领取腾讯云代金券