大话数据结构_大话数据结构pdf - CSDN
大话数据结构 订阅
《大话数据结构》是2011年清华大学出版社出版的图书,作者是程杰 。本书以一个计算机教师教学为场景,讲解数据结构和相关算法的知识。 [1-2] 展开全文
《大话数据结构》是2011年清华大学出版社出版的图书,作者是程杰 。本书以一个计算机教师教学为场景,讲解数据结构和相关算法的知识。 [1-2]
信息
作    者
程杰
定    价
59.00
字    数
662000
装    帧
平装
书    名
大话数据结构
出版时间
2011-6-1
开    本
16开
出版社
清华大学出版社
ISBN
9787302255659
页    数
439
大话数据结构编辑推荐
超级畅销书《大话设计模式》作者的新作!用户群更为广泛,写作风格一如既往,技术沉淀更加深厚,势必掀起全民数据结构的热潮!
收起全文
精华内容
参与话题
  • 大话数据结构》是一本关于数据结构和算法的自学读物,全书模拟上 课场景,让一个说话有趣的老师来和同学们交流数据结构知识。它不板 着脸灌输,它期望和读者做朋友,在每每的会心一笑中,只是融入了读 者脑海,...
  • 大话数据结构 扫描 超清版 这本书写的非常有意思,看起来很带劲。 本书为超级畅销书《大话设计模式》作者程杰潜心三年推出的扛鼎之作!以一个计算机教师教学为场景,讲解数据结构和相关算法的知识。通篇以一种趣味...
  • 书本下载链接:链接:https://pan.baidu.com/s/1jgVnbBZoLgA8pshpxbapOQ 密码...虽说数据结构以美国人Mark Allen Weiss 写的《数据结构与算法分析——C语言实现》最好,但是我发现他的书让人很不容易理解,可能我们...

    书本下载链接:链接:https://pan.baidu.com/s/1jgVnbBZoLgA8pshpxbapOQ 密码:577l

    配套程序链接:https://pan.baidu.com/s/1HYka42KngWT2el7T0HO7LA 密码:i6hw

    虽说数据结构以美国人Mark Allen Weiss 写的《数据结构与算法分析——C语言实现》最好,但是我发现他的书让人很不容易理解,可能我们和外人们写作、理解的方式不一样。
    因此对于新手入门还是推荐——《大话数据结构》这本书
    在这里插入图片描述
    下面是书本下载链接:链接:https://pan.baidu.com/s/1jgVnbBZoLgA8pshpxbapOQ 密码:577l

    配套程序链接:https://pan.baidu.com/s/1HYka42KngWT2el7T0HO7LA 密码:i6hw

    展开全文
  • 大话数据结构.zip

    2020-06-05 23:32:11
    学习数据结构必备
  • 大话数据结构》适合学过一门编程语言的各类读者,包括在读的大中专计算机专业学生、想转行做开发的非专业人员、欲考计算机研究生的应届或在职人员,以及工作后需要补学或温习数据结构和算法的程序员等。
  • 数据域:存储数据元素信息的域 指针域:存储直接后继位置域 开始结点: 是指链表中的第一个结点,它没有直接前驱 头指针:链表中第一个结点的存储位置叫做头指针一个单链表可以由其头指针唯一确定,一般用其头指针....

    第3章 线性表

    3.2 线性表的定义

    A B C…

    B直接前驱元素: A

    B直接后驱元素:C

    3.6线性表的链式存储结构

    3.6.2线性表链式存储结构定义(P57)

    • 结点(node)
      • 数据域:存储数据元素信息的域
      • 指针域:存储直接后继位置域

    img

    • 开始结点: 是指链表中的第一个结点,它没有直接前驱
    • 头指针:链表中第一个结点的存储位置叫做头指针一个单链表可以由其头指针唯一确定,一般用其头指针来命名单链表
    • 头结点:是在链表的开始结点之前附加的一个结点

    3.14双向链表

    双向链表是在单链表的每个结点中,再设置一个指向其前驱结点的指针域

    双向链表的插入和删除:

    插入:
    s -> prior = p;
    s -> next = p -> next;
    p -> next -> prior = s;
    p -> next = s;
    
    删除:
    p -> prior -> next = p -> next;
    p -> next -> prior = p ->prior;
    free(p);
    

    3.15 总结回顾

    线性表

    • 顺序存储结构
    • 链式存储结构
      • 单链表
      • 静态链表
      • 循环链表
      • 双向链表

    第4章 栈和队列

    • 栈是限定仅在表尾进行插入和删除操作的线性表
    • 队列是只允许在一端进行插入操作,而在另一段进行删除操作的线性表

    4.2 栈的定义

    • 栈顶(top)
    • 栈底(bottom)
    • 空栈
    • 后进先出(LIFO结构),栈的两种操作–Push和Pop

    栈的插入操作称为入栈,反之称为出栈.

    img

    4.3 栈的抽象数据类型

    栈的一些基本操作:

    ADT 栈(stack)
    Data
    	同线性表.元素具有相同的类型,相邻元素具有前驱和后继关系
    Operation
    	InitStack(*S)
    	DestroyStack(*S)
    	ClearStack(*S)
    	StackEmpty(*S)判断堆栈是否为空,返回值是ture和false
    	GetTop(*S)
    	Push(*S, e)插入e值
    	POp(*S, *e)删除栈顶元素并用e返回其值
    	StackLength(S)
    

    4.4 栈的顺序存储结构及实现(P93)

    利用下标为0的数组一端作为栈的栈底

    判断空栈的条件是top=-1

    **销毁一个栈: **释放内存

    **清空一个栈: **只改变地址

    4.5两栈共享空间

    两栈共享空间结构:使用数组同时实现两个栈,即栈1和栈2;栈1为空时,栈1的栈顶指针指向-1;栈2为空时,栈2 的栈顶指针指向MAXSIZE;栈1和栈2添加元素时,都会向数据中间靠拢,当栈1的指针+1等于栈2的指针的时候,栈满。img

    img

    img

    img

    img

    4.6 栈的链式存储结构及实现

    img

    栈顶指针和单链表的头指针合二为一.

    4.9 栈的应用–四则运算表达式求值

    9+(3-1)*3+10/2 这是中缀表达式

    9 3 1 - 3 * + 10 2 / + 这是后缀表达式

    栈的四则运算最主要的就是让中缀表达式转换为后缀表达式,然后再进行一些其他的操作.

    4.10 队列的定义

    队列是只允许在一端进行插入操作,在另一端进行删除操作的线性表

    • 先进先出
    • 队尾: 允许插入的一端
    • 队头: 允许删除的一端

    img

    4.12 循环队列

    如何判断队列是否已满?利用下面共指来判断
    (rearfront+QueneSize)%QueneSize==front (rear-front+QueneSize) \% QueneSize == front

    第5章 串

    串是由零个或者多个字符组成的有限序列,又名叫字符串.

    5.2 串的定义

    串是由零个或者多个字符组成的有限序列,又名叫字符串

    一般记作:
    s="a1a2a3......an" s = "a1a2a3......an"
    所谓序列,是指相邻的字符串之间具有前驱和后继的关系

    5.4 串的抽象数据类型

    ADT 串 (String)
    
    Data
    	串中的元素仅由一个字符组成,相邻元素具有前驱和后继关系.
    	
    Operation
    StrAssign (&T, chars)
    	初始条件:chars是字符串常量。
    	操作结果:生成一个其值等于chars的串T。
    StrCopy (&T, S)
    	初始条件:串S存在。
    	操作结果:由串S复制得串T。
    StrEmpty(S)
    	初始条件:串S存在。
    	操作结果:若S为空串,则返回TRUE,否则返回FALSE。 
    StrCompare(S, T)
    	初始条件:串S和T存在。
    	操作结果:若S>T,则返回值>0;若S=T,则返回值=0;若S < T,则返回值 < 0。
    StrLength(S)
    	初始条件:串S存在。
    	操作结果:返回S的元素个数,称为串的长度。
    ClearString (&S)
    	初始条件:串S存在。
    	操作结果:将S清为空串。
    Concat (&T, S1, S2)
    	初始条件:串S1和S2存在。
    	操作结果:用T返回由S1和S2联接而成的新串。
    SubString(&Sub, S, pos, len)
    	初始条件:串S存在,1≤pos≤StrLength(S)且0≤len≤StrLength(S)-pos+1
    	操作结果:用Sub返回串S的第pos个字符长度为len的子串。
    Index(S, T, pos)
    	初始条件:串S和T存在,T是非空串,1≤pos≤StrLength(S)。
    	操作结果:若主串S中存在和串T值相同的子串,则返回它在主串S中第pos个字符之后第一次出现的位置;否则函数值为0。
    Replace (&S, T, V)
    	初始条件:串S, T和V存在,T是非空串。
    	操作结果:用V替换主串S中出现的所有与T相等的不重叠的子串。
    StrInsert (&S, pos, T)
    	初始条件:串S和T存在, 1≤pos≤StrLength(S)+1。
    	操作结果:在串S的第pos个字符之前插入串T。
    StrDelete (&S, pos, len)
    	初始条件:串S存在, 1≤pos≤StrLength(S)-len+1。
    	操作结果:从串S中删除第pos个字符起长度为len的子串。
    DestroyString (&S)
    	初始条件:串S存在。
    	操作结果:串S被销毁。
    
    endADT
    

    5.6 KMP模式匹配算法

    问题描述

    给定一个主串S及一个模式串P,判断模式串是否为主串的子串;若是,返回匹配的第一个元素的位置(序号从1开始),否则返回0;如S=“abcd”,P=“bcd”,则返回2;S=“abcd”,P=“acb”,返回0。

    KMP算法

    https://blog.csdn.net/qq_37969433/article/details/82947411

    朴素算法理解简单,但两个串都有依次遍历,时间复杂度为O(n*m),效率不高。由此有了KMP算法。
    一般的,在一次匹配中,我们是不知道主串的内容的,而模式串是我们自己定义的。
    朴素算法中,P的第j位失配,默认的把P串后移一位。
    但在前一轮的比较中,我们已经知道了P的前(j-1)位与S中间对应的某(j-1)个元素已经匹配成功了。这就意味着,在一轮的尝试匹配中,我们get到了主串的部分内容,我们能否利用这些内容,让P多移几位(我认为这就是KMP算法最根本的东西),减少遍历的趟数呢?

    第6章 树

    6.2 树的定义

    树是n个结点的有限集合.n=0时称为空树.在任意一棵非空树中:

    • 有且仅有一个特定的称为根(Root)的结点;
    • 当n>1时,其余结点可以分为m个互不相交的有限集T1,T2…Tm,其中每一个集合本身又是一课树,并且称为根的子树(SubTree)

    img

    • 度: 结点拥有的子树的个数称为结点的度(Degree),度为0的结点称为叶节点或者终端结点.度不为0的结点称为非终端结点或者分支结点

    img

    • 树的度是树的各个结点度的最大值
    • 深度或高度: 树中结点的最大层次称为树的深度或高度

    img

    • 有序树和无序树
    • 森林是m棵互不相交的树的集合

    6.4 树的存储结构(P155)

    • 双亲表示法
    • 孩子表示法
    • 孩子兄弟表示法

    http://data.biancheng.net/view/30.html

    6.4.1 双亲表示法

    img

    双亲表示法

    6.4.2 孩子表示法

    将树中的每个结点的孩子结点排列成一个线性表,用链表存储起来。对于含有 n 个结点的树来说,就会有 n 个单链表,将 n 个单链表的头指针存储在一个线性表中,这样的表示方法就是孩子表示法。

    img

    孩子表示法

    使用孩子表示法存储的树结构,正好和双亲表示法相反,适用于查找某结点的孩子结点,不适用于查找其父结点。可以将两种表示方法合二为一,存储效果如图 :

    img

    孩子双亲表示法
    #define TElemType int
    #define Tree_Size 100
    //孩子表示法
    typedef struct CTNode{
        int child;//链表中每个结点存储的不是数据本身,而是数据在数组中存储的位置下标
        struct CTNode * next;
    }*ChildPtr;
    typedef struct {
        TElemType data;//结点的数据类型
        ChildPtr firstchild;//孩子链表的头指针
    }CTBox;
    typedef struct{
        CTBox nodes[Tree_Size];//存储结点的数组
        int n,r;//结点数量和树根的位置
    }CTree;
    

    6.4.3 孩子兄弟表示法

    任意一棵树, 他的结点的第一个孩子如果存在就是唯一的, 他的右兄弟如果存在也是唯一的.因此我们设置两个指针,分别指向该结点的第一个孩子和此节点的右兄弟

    img

    data firstchild rightsib
    数据域 孩子域 兄弟域

    上下两个表格一个意思

    img

    这个表示方法就是把一个复杂的树变成了二叉树

    6.5 二叉树的定义

    https://www.jianshu.com/p/bf73c8d50dc2

    二叉树(Binary Tree)是n(n>=0)个结点的有限集合,该集合或者为空集(称为空二叉树), 或者由一个根节点和两棵互不相交的,分别称为根节点的左子树和右子树的二叉树组成

    img

    二叉树

    二叉树的特点:

    • 每个结点最多有两颗子树,所以二叉树中不存在度大于2的结点。
    • 左子树和右子树是有顺序的,次序不能任意颠倒。
    • 即使树中某结点只有一棵子树,也要区分它是左子树还是右子树。

    6.5.2特殊二叉树

    斜树: 所有的结点都只有左子树的二叉树叫左斜树。所有结点都是只有右子树的二叉树叫右斜树。这两者统称为斜树。

    img

    左斜树

    img

    右斜树

    满二叉树: 在一棵二叉树中。如果所有分支结点都存在左子树和右子树,并且所有叶子都在同一层上,这样的二叉树称为满二叉树

    • 叶子只能出现在最下一层。出现在其它层就不可能达成平衡
    • 非叶子结点的度一定是2
    • 在同样深度的二叉树中,满二叉树的结点个数最多,叶子数最多.并且叶子都处于同一层

    img

    满二叉树

    完全二叉树: 对一颗具有n个结点的二叉树按层编号,如果编号为i(1<=i<=n)的结点与同样深度的满二叉树中编号为i的结点在二叉树中位置完全相同,则这棵二叉树称为完全二叉树

    img

    完全二叉树

    特点:

    1)叶子结点只能出现在最下层和次下层。
    2)最下层的叶子结点集中在树的左部。
    3)倒数第二层若存在叶子结点,一定在右部连续位置。
    4)如果结点度为1,则该结点只有左孩子,即没有右子树。
    5)同样结点数目的二叉树,完全二叉树深度最小。
    :满二叉树一定是完全二叉树,但反过来不一定成立。

    6.5.3 其他重要二叉树

    1.二叉排序树
    二叉排序树,又叫二叉查找树,它或者是一棵空树;或者是具有以下性质的二叉树:

    1. 若它的左子树不空,则左子树上所有节点的值均小于它的根节点的值;
    2. 若它的右子树不空,则右子树上所有节点的值均大于它的根节点的值;
    3. 它的所有结点的左右子树也分别为二叉排序树。
      在这里插入图片描述

    2.平衡二叉树

    (AVL)平衡二叉树是一种二叉排序树,其中每个结点的左子树和右子树的高度差至多等于1。它是一种高度平衡的二叉排序树。意思是说,要么它是一棵空树,要么它的左子树和右子树都是平衡二叉树,且左子树和右子树的深度之差的绝对值不超过1。

    平衡二叉树是一种二叉排序树。也就是二叉排序树包含了平衡二叉排序树,其次它要满足后面的约束条件,就是每个结点的左子树和右子树的高度差不超过1
    在这里插入图片描述

    6.6 二叉树的性质

    https://blog.csdn.net/why_still_confused/article/details/51532222

    6.7 二叉树的存储结构

    6.7.2 二叉链表

    链表每个结点包含一个数据域和两个指针域:

    mark

    其中data是数据域,lchild和rchild都是指针域,分别指向左孩子和右孩子。

    mark

    /*二叉树的二叉链表结点结构定义*/
    typedef struct BiNode
    {
        char data;    /*结点数据*/
        struct BiNode *lchild, *rchild; /*左右孩子指针*/
    }BiNode,*BiTree;
    

    6.8 遍历二叉树

    二叉树的遍历是指从根节点出发,按照某种次序依次访问二叉树中的所有结点, 使得每个结点被访问一次且仅被访问一次。

    https://blog.csdn.net/gatieme/article/details/51163010(二叉树建立和遍历的C++代码实现)

    1. 前序遍历

    根结点 —> 左子树 —> 右子树

    2. 中序遍历

    左子树 —> 根节点 —> 右子树

    3. 后续遍历

    左子树 —> 右子树—> 根节点

    4. 层序遍历

    从根节点开始访问,从上而下逐层遍历,在同一层中,按照从左到右的顺序对结点逐个访问

    6.10 线索二叉树

    为什么存在线索二叉树:

    二叉树是一种非线性结构,遍历二叉树几乎都是通过递归或者用栈辅助实现非递归的遍历。用二叉树作为存储结构时,取到一个节点,只能获取节点的左孩子和右孩子,不能直接得到节点的任一遍历序列的前驱或者后继。为了保存这种在遍历中需要的信息,我们利用二叉树中指向左右子树的空指针来存放节点的前驱和后继信息

    img

    6.10.1 线索二叉树原理

    n个节点的二叉树中含有n+1个空指针域。利用二叉树中的空指针域来存放在某种遍历次序下的前驱和后继,这种指针叫“线索”。这种加上了线索的二叉树称为线索二叉树。

    img

    线索二叉树节点
    • ltag为0时指向左孩子,为1时指向该节点的前驱
    • rtag为0时指向右孩子, 为1时指向该节点的后继

    img

    6.11 树,森林与二叉树的转换

    https://blog.csdn.net/linraise/article/details/11745559

    1. 将树转换成二叉树:
    (1)加线。就是在所有兄弟结点之间加一条连线;
    (2)抹线。就是对树中的每个结点,只保留他与第一个孩子结点之间的连线,删除它与其它孩子结点之间的连线;
    (3)旋转。就是以树的根结点为轴心,将整棵树顺时针旋转一定角度,使之结构层次分明。

    img

    2. 森林转换为二叉树

    森林是由若干棵树组成,可以将森林中的每棵树的根结点看作是兄弟,由于每棵树都可以转换为二叉树,所以森林也可以转换为二叉树。

    将森林转换为二叉树的步骤是:
    (1)先把每棵树转换为二叉树;
    (2)第一棵二叉树不动,从第二棵二叉树开始,依次把后一棵二叉树的根结点作为前一棵二叉树的根结点的右孩子结点,用线连接起来。当所有的二叉树连接起来后得到的二叉树就是由森林转换得到的二叉树。
    img

    3. 二叉树转化为森林

    二叉树转换为树是树转换为二叉树的逆过程,其步骤是:
    (1)若某结点的左孩子结点存在,将左孩子结点的右孩子结点、右孩子结点的右孩子结点……都作为该结点的孩子结点,将该结点与这些右孩子结点用线连接起来;
    (2)删除原二叉树中所有结点与其右孩子结点的连线;
    (3)整理(1)和(2)两步得到的树,使之结构层次分明。
    img

    4. 二叉树转换为森林

    二叉树转换为森林比较简单,其步骤如下:
    (1)先把每个结点与右孩子结点的连线删除,得到分离的二叉树;
    (2)把分离后的每棵二叉树转换为树;
    (3)整理第(2)步得到的树,使之规范,这样得到森林。

    根据树与二叉树的转换关系以及二叉树的遍历定义可以推知,树的先序遍历与其转换的相应的二叉树的先序遍历的结果序列相同;树的后序遍历与其转换的二叉树的中序遍历的结果序列相同;树的层序遍历与其转换的二叉树的后序遍历的结果序列相同。由森林与二叉树的转换关系以及森林与二叉树的遍历定义可知,森林的先序遍历和中序遍历与所转换得到的二叉树的先序遍历和中序遍历的结果序列相同。

    6.12 哈夫曼树及其应用

    6.12.2 哈夫曼树定义与原理(P203)

    构建哈夫曼树的步骤:

    原始节点

    构建Huffman树的步骤

    哈夫曼编码:

    Huffman编码

    第7章 图

    https://baozouai.com/2019/03/08/%E5%A4%A7%E8%AF%9D%E6%95%B0%E6%8D%AE%E7%BB%93%E6%9E%84-%E7%AC%AC%E4%B8%83%E7%AB%A0%20%20%E5%9B%BE/

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

    7.2 图的定义

    • 无向图:若顶点Vi到Vj之间的边没有方向,则称这条边为无向边(Edge),用序偶对(Vi,Vj)表示。如果图的任意两个顶点之间的边都是无向边,则称该图是无向图。

      img

      上述无向图G1来说,G1=(V1, {E1}),其中顶点集合V1={A,B,C,D};边集合E1={(A,B),(B,C),(C,D),(D,A),(A,C)};

    • 有向图:若从顶点Vi到Vj的边是有方向的,则成这条边为有向边,也称为弧(Arc)。用有序对(Vi,Vj)标示,Vi称为弧尾,Vj称为弧头。如果任意两条边之间都是有向的,则称该图为有向图。

      [外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-aEpVicYr-1573180530985)(https://baozou.gitbooks.io/-data-structure/content/assets/152import.png)]

      有向图G2中,G2=(V2,{E2}),顶点集合(A,B,C,D),弧集合E2={<A,D>,<B,A>,<C,A>,<B,C>}.

    • 无向完全图:在一个无向图中,任意两个顶点之间都存在边,则称该图为无向完全图。含有n个顶点的无向完全图有 n(n+1)/2 n*(n+1)/2 条边

    [外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-YzB97B8u-1573180530986)(https://baozou.gitbooks.io/-data-structure/content/assets/155import.png)]

    • 有向完全图:在有向图中,如果任意两个顶点之间都存在方向互为相反的两条弧,则称该图为有向完全图。含有n个顶点的有向完全图有n×(n−1)条边

    [外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-8L4L0N2g-1573180530986)(https://baozou.gitbooks.io/-data-structure/content/assets/157import.png)]

    • 有很少条边或弧的图称为稀疏图,反之称为稠密图。稀疏和稠密是模糊的概念,是相对而言的
    • 有些图的边或弧具有与它相关的数字,这种与图的边或弧相关的数叫做权(Weight)。这些权可以表示从一个顶点到另一个顶点的距离或耗费。这种带权的图通常称为网(Network)
    • 假设有两个图G*=(V,{E})G*′=(V′,{E′}),如果V′⊆VE′⊆E*,则称G′为G的子图(Sub-graph)

    [外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-UOuSOE7Z-1573180530987)(https://baozou.gitbooks.io/-data-structure/content/assets/160import.png)]

    7.2.2 图的顶点和边的关系

    7.4 图的存储结构

    7.4.1 邻接矩阵

    图的邻接矩阵存储方式是用两个数组来表示图。一个一维数组存储图中顶点信息,一个二位数组(称为邻接矩阵)存储图中的边或弧的信息。

    设图G有n个顶点,则邻接矩阵是一个n*n的方阵,定义为:

    img

    • 无向图的邻接矩阵

    img

    • 有向图的邻接矩阵

    img

    • 网图的邻接表

      设图G是网图,有n个顶点,则邻接矩阵是一个n*n的方阵,定义为:

    img

    img

    7.4.2 邻接表

    数组与邻接表相结合的存储方法称为邻接表

    • 无相图的邻接表

      img

    • 有向图的邻接表

      img

    • 网图(带权值)的邻接表

      img

    7.4.3 十字链表

    十字链表 = 邻接表 + 逆邻接表

    7.4.4 邻接多重表

    针对无向图(存储空间压缩时用)

    7.4.5 边集数组

    边集数组是由两个一维数组构成。一个是存储顶点的信息;另一个是存储边的信息,这个边数组每个数据元素由一条边的起点下标(begin)、终点下标(end)和权(weight)组成

    begin是存储起点下标,end是存储终点下标,weight是存储权值

    [外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-zrNe533V-1573180530987)(https://baozou.gitbooks.io/-data-structure/content/assets/import.png23)]

    边集数组关注的是边的集合,在边集数组中要查找一个顶点的度需要扫描整个边数组,效率并不高。因此它更适合对边依次进行处理的操作,而不适合对顶点相关的操作

    7.5 图的遍历

    定义:从图的某一顶点出发访遍图中的其余顶点,且使每一个顶点仅被访问一次,这一过程就叫做图的遍历

    7.5.1 深度优先遍历(P239)

    从图中某个顶点v出发,访问此顶点,然后从v的未被访问的邻接点出发深度优先遍历图,直至图中所有和v有路径相通的顶点都被访问到,以上说的只是连通图,对于非连通图,只需要对它的连通分量分别进行深度优先遍历,即在先前一个顶点进行一次深度优先遍历后,若图中尚有顶点未被访问,则另选图中一个未曾被访问的顶点作为起始点,重复上述过程,直至图中所有顶点都被访问到位置

    7.5.2 广度优先算法(P242)

    [外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-fDuS4knY-1573180530987)(https://baozou.gitbooks.io/-data-structure/content/assets/import.png24)]

    图的深度优先遍历和广度优先遍历算法在时间复杂度上一样,不同之处仅在于对顶点的访问次序不同深度优先算法更适合目标比较明确的。以找到目标为主要目的的情况,而广度优先更适合在不断扩大遍历范围时找到相对最优解的情况

    7.6 最小生成树(B站上的王卓老师讲原理讲的比较好)

    生成树的特点:

    1. 生成树的顶点个数和图的顶点个数相同
    2. 生成数是图的极小联通子图,去掉一条边则非联通
    3. 一个有n个顶点的联通图的生成树有n-1条边
    4. 在生成树中再加一条边必然形成回路
    5. 生成树中任意两个顶点之间的路径是唯一的

    最小成本,就是n个顶点,用n-1条边把一个连通图连接起来,并且使得权值的和最小

    最小生成树:把构造联通网的最小代价生成树称为最小生成树。最小生成树不唯一,但是最小生成树的权值和一定唯一。

    7.6.1 普利姆(prim)算法

    https://www.bilibili.com/video/av36885391/?spm_id_from=333.788.videocard.0(B站)

    [外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-DQVfGhpK-1573180530987)(https://baozou.gitbooks.io/-data-structure/content/assets/import.png25)]

    算法实现(C++)
    #include <iostream>
    #define MAXINT 6
    
    using namespace std;
    
    //声明一个二维数组,C[i][j]存储的是点i到点j的边的权值,如果不可达,则用1000表示
    //借此二维数组来表示一个连通带权图
    int c[MAXINT][MAXINT]={{1000,6,1,5,1000,1000},{6,1000,5,1000,3,1000},{1,5,1000,5,6,4},{5,1000,5,1000,1000,2},{1000,3,6,1000,1000,6},{1000,1000,4,2,6,1000}};
    void Prim(int n)
    {
        int lowcost[MAXINT];//存储S中到达对应的其它各点的最小权值分别是多少
        int closest[MAXINT];//closest[]数组保存的是未在S中的点所到达S中包含的最近的点是哪一个,如:closest[i]=1表示i最靠近的S中的点是1
        bool s[MAXINT];//bool型变量的S数组表示i是否已经包括在S中
        int i,k;
        s[0]=true;//从第一个结点开始寻找,扩展
        for(i=1;i<=n;i++)//简单初始化
        {
            lowcost[i]=c[0][i];
            closest[i]=0;//现在所有的点对应的已经在S中的最近的点是1
            s[i]=false;
        }
        cout<<"0->";
        for(i=0;i<n;i++)
        {
            int min=1000;//最小值,设大一点的值,后面用来记录lowcost数组中的最小值
            int j=1;
            for(k=1;k<=n;k++)//寻找lowcost中的最小值
            {
                if((lowcost[k]<min)&&(!s[k]))
                {
                    min=lowcost[k];j=k;
                }
            }
            cout<<j<<" "<<"->";
            s[j]=true;//添加点j到集合S中
            for(k=1;k<=n;k++)//因为新加入了j点,所以要查找新加入的j点到未在S中的点K中的权值是不是可以因此更小
            {
                if((c[j][k]<lowcost[k])&&(!s[k])){lowcost[k]=c[j][k];closest[k]=j;}
            }
        }
    
    }
    int main()
    {
        
        //输入初始化数组
    
        cout<<"请输入初始权值数组:"<<endl;
        for(int i=0;i<MAXINT;i++)
        {
            for(int j=0;j<MAXINT;j++)
            {
            //    cout<<"please enter c["<<i<<"]["<<j<<"]:";
            //    cin>>c[i][j];
                cout<<c[i][j]<<"\t";
            //    cout<<endl;
            }
            cout<<endl;
        }
        
        Prim(MAXINT-1);
        return 0;
    }
    

    7.6.2 克鲁斯卡尔(Kruskal)算法

    https://www.bilibili.com/video/av36885495/?spm_id_from=333.788.videocard.0(B站)

    本质就是一种贪心算法

    算法思想:

    • 设联通网N=(V,E)令最小生成树初始状态为只有n个顶点而无边的非联通图T=(V,{}),每个顶点自成一个连通分量.
    • 在E中选取代价最小的边,若该边依附的顶点落在T中的不同联通分量上(即:不能形成环),则将此边加入到T中,否则,舍去此边,选取一条代价最小的边.
    • 以此类推,直到T中所有顶点都在同一个联通分量上为止.

    两种算法的比较


    算法名 Prime算法 Kruskal算法
    算法思想 选择点 选择边
    时间复杂度 O(n^2) O(eloge)
    适应范围 稠密图 稀疏图

    7.7 最短路径

    最短路径:指两个顶点之间经过边上的权值之和最少的路径,并称第一个顶点是源点, 最后一个顶点是终点.

    要解决的两类问题:

    • 两点之间的最短路径(单源最短路径(Dijkstra算法))
    • 某源点到其他各个点的最短路径(所有顶点之间的最短路径(Floyd算法))

    7.7.1 Dijkstra算法

    单源最短路径

    https://www.bilibili.com/video/av36886088/?spm_id_from=333.788.videocard.0(B站)

    按路径长度递增次序产生最短路径

    7.7.2 Floyd算法

    https://www.bilibili.com/video/av36886554/?spm_id_from=333.788.videocard.0(B站)

    所有顶点之间的最短路径

    算法思想:

    • 逐个顶点试探
    • 从Vi到Vj的所有可能存在的路径中
    • 选出一条长度最短的路径

    7.8 拓扑排序

    https://www.bilibili.com/video/av36886991/?spm_id_from=333.788.videocard.0(B站)

    1.AOV

    用一个有向图表示一个工程的各子工程及其相互制约的关系,其中以顶点表示活动,弧表示活动之间的优先制约关系,称这种有向图为顶点表示活动的网,简称AOV网.

    2.AOE

    用一个有向图表示一个工程的各子工程及其相互制约的关系,以弧表示活动,以顶点表示活动的开始或结束时间,称这种有向图为边表示活动的网,简称AOE网.

    3.AOV网的特点:

    • 若从i到j有一条有向路径,则i是j的前驱;j是i的后继
    • 若<i, j>是网中的有向边, 则i是j的直接前驱, j是i的直接后继
    • AOV网中不允许有回路, 因为如果有回路存在,表明某项活动是以自己为先决条件,显然这是荒谬的.
    • 如何判断AOV网中是否存在回路?

    img

    4.什么是拓扑排序?:

    在AOV网没有回路的前提下,我们将全部活动排列成一个线性序列,使得若AOV网中有弧<i, j>存在, 则在这个序列中, i一定排在j的前面, 具有这种性质的线性序列称为拓扑有序序列, 相应的拓扑有序排序的算法称为拓扑排序.

    5.拓扑排序的方法

    一个拓扑序列并不唯一

    上述拓扑序列也可以是C9, C10, C11, C6, C1, C12, C4, C2, C3, C5, C7, C8

    6.拓扑排序的一个重要应用

    检测AOV网中是否存在环

    对有向图构造其顶点的拓扑有序序列, 若网中所有顶点都在他的拓扑有序序列中,则该AOV网必定不存在环.

    7.9 关键路径

    https://www.bilibili.com/video/av36907591/?spm_id_from=trigger_reload(B站)

    1.AOE

    用一个有向图表示一个工程的各子工程及其相互制约的关系,以弧表示活动,以顶点表示活动的开始或结束时间,称这种有向图为边表示活动的网,简称AOE网.

    2.关键路径

    把工程计划表示为边表示的活动的网络, 即AOE网, 用顶点表示事件, 弧表示活动, 弧的权表示活动持续时间

    事件表示在他之前的活动已经完成, 在他之后的活动可以开始
    ~~在这里插入图片描述~~
    在这里插入图片描述
    在这里插入图片描述在这里插入图片描述
    在这里插入图片描述
    在这里插入图片描述
    在这里插入图片描述

    展开全文
  • 一个数据元素可以由若干个数据项组成,数据项是数据不可分割的最小单位数据对象数据对象:是性质相同的数据元素的集合,是数据的子集数据结构不同数据元素之间不是独立的,而是存在特定的关系,我们将这些

    数据

    数据:是描述客观事物的符号,是计算机中可以操作的对象,是能被计算机识别,并输入给计算机处理的符号集合

    数据元素

    数据元素:是组成数据的、有一定意义的基本单位,在计算机中通常作为整体处理,也被称为记录

    数据项

    数据项:一个数据元素可以由若干个数据项组成,数据项是数据不可分割的最小单位

    数据对象

    数据对象:是性质相同的数据元素的集合,是数据的子集

    数据结构

    不同数据元素之间不是独立的,而是存在特定的关系,我们将这些关系称为结构

    数据结构:是相互之间存在一种或多种特定关系的数据元素的集合

    数据结构

    逻辑结构

    逻辑结构:是指数据对象中数据元素之间的相互关系

    集合结构

    集合结构:集合结构中的数据元素除了同属于一个集合外,它们之间没有其他关系。各个数据元素是”平等”的,类似于数学中的集合

    线性结构

    线性结构:线性结构中的数据元素之间是一对一的关系

    树形结构

    树形结构:树形结构中的数据元素之间存在一种一对多的层次关系

    图形结构

    图形结构:图形结构的数据元素是多对多的关系

    物理结构

    物理结构(存储结构):是指数据的逻辑结构在计算机中的存储形式

    顺序存储结构

    顺序存储结构:是把数据元素存放在地址连续的存储单元里,其数据间的逻辑关系和物理关系是一致的

    链式存储结构

    链式存储结构:是把数据元素存放在任意的存储单元里,这组存储单元可以是连续的,也可以是不连续的,数据元素的存储关系并不能反映其逻辑关系,因此需要用一个指针存放数据元素的地址,这样通过地址就可以找到相关数据元素的位置

    数据类型

    数据类型:是指一组性质相同的值的集合及定义在此集合上的一些操作的总称

    在C语言中,按照取值的不同,数据类型可以分为两类

    原子类型

    是不可以再分解的基本类型,包括整型、字符型等

    结构类型

    由若干个类型组合而成,是可以再分解的,例如整型数组

    抽象数据类型

    抽象数据类型(Abstract Data Type, ADT):是指一个数学模型及定义在该模型上的一组操作,如”整数”类型->整型

    抽象数据类型体现了程序设计中问题分解、抽象和信息隐藏的特性

    算法

    算法是解决特定问题求解步骤的描述,在计算机中表现为指令的有限序列,并且每条指令表示一个或多个操作

    算法的特性

    算法具有五个基本特性:输入、输出、有穷性、确定性和可行性

    • 算法具有零个或多个输入
    • 算法至少有一个或多个输出
    • 算法在执行有限的步骤后,自动结束而不会出现无限循环,并且每一个步骤在可接受的时间内完成
    • 算法的每一步骤都具有确定的含义,不会出现二义性
    • 算法的每一步都必须是可行的,也就是说,每一步都能够通过执行有限次数完成

    正确性

    正确性:算法的正确性是指算法至少应该具有输入、输出和加工处理无歧义性、能正确反映问题的需求、能够得到问题的正确答案

    正确性大体分为以下四个层次:

    • 算法程序没有语法错误
    • 算法程序对于合法的输入数据能够产生满足要求的输出结果
    • 算法程序对于非法的输入数据能够产生满足规格说明的结果(一般情况下,将此作为判断一个算法是否正确的标准)
    • 算法程序对于精心选择的,甚至刁难的测试数据都有满足要求的输出结果

    可读性

    可读性:算法设计的另一个目的是为了便于阅读、理解和交流

    健壮性

    健壮性:当输入数据不合法时,算法也能做出相关处理,而不是产生异常或莫名其妙的结果

    时间效率高和存储量低

    设计算法应该尽量满足时间效率高和存储量低的需求

    算法效率的度量方法

    • 事后统计方法

      这种方法主要是通过设计好的测试程序和数据,利用计算机计时器对不同算法编制的程序的运行时间进行比较,从而确定算法效率的高低

      缺陷较大,不予采纳

    • 事前分析估算方法

      在计算机程序编制前,依据统计方法对算法进行估算

      一个程序的运行时间,依赖于算法的好坏和问题的输入规模

      在分析程序的运行时间时,最重要的是把程序看成是独立于程序设计语言的算法或一系列步骤

    函数的渐近增长

    函数的渐近增长:给定两个函数f(n)和g(n),如果存在一个整数N,使得对于所有的n > N,f(n)总是比g(n)大,那么,我们说f(n)的增长渐近快于g(n)

    判断一个算法的效率时,函数中的常数和其他次要项常常可以忽略,而更应该关注主项(最高阶项)的阶数

    算法时间复杂度

    定义

    在进行算法分析时,语句总是执行次数T(n)是关于问题模型n的函数,进而分析T(n)随n的变化情况并确定T(n)的数量级,算法的时间复杂度,也就是算法的时间量度,记作:T(n)=O(f(n))。它表示随问题规模n的增大,算法执行时间的增长率和f(n)的增长率相同,称作算法的渐近时间复杂度,简称为时间复杂度,其中f(n)是问题规模n的某个函数

    一般情况下,随着n的增大,T(n)增长最慢的算法为最优算法

    • 常数阶:O(1)

      不管n为多少,执行的次数都是恒定的,不会随着n的变大而发生变化,其时间复杂度为O(1)

    • 线性阶:O(n)

      循环结构中的代码需要执行n次,其时间复杂度为O(n)

      for(i = 0; i < n; i++){
      
      }
      
    • 对数阶:O(logn)

      有多少个2相乘后大于n,则会退出循环

      2^x=n
      int count = 1;
      while(count < n){
          count = count * 2;
      }
      
    • 平方阶

      两层循环嵌套

      int i,j;
      for(i = 0; i < n; j++){
          for(j = i; j < n; j++){
      
          }
      }
      

    常见的时间复杂度

    <img shuju_001>

    算法空间复杂度

    算法的空间复杂度通过计算算法所需的存储空间实现,算法空间复杂度的计算公式记作:S(n)=O(f(n)),其中,n为问题的规模,f(n)为语句关于n所占存储空间的函数

    当不用限定词地使用”复杂度”时,通常都是指时间复杂度

    线性表

    定义

    线性表(List):零个或多个数据元素的有限序列

    除第一个元素外,每一个元素有且只有一个直接前驱元素,除了最后一个元素外,每一个元素有且只有一个直接后继元素,数据元素之间的关系是一对一的关系

    在较复杂的线性表中,一个数据元素可以由若干个数据项组成

    线性表的顺序存储结构

    线性表的顺序存储结构,指的是用一段地址连续的存储单元一次存储线性表的数据元素

    顺序存储方式

    在内存中占据一定的内存空间,然后把相同数据类型的数据元素依次存放在这块空地中

    属性:

    • 存储空间的起始位置:数组data,它的存储位置就是存储空间的存储位置
    • 线性表的最大存储容量:数组长度MaxSize
    • 线性表的当前长度:length

    存储器中的每个存储单元都有自己的编号,这个编号称为地址

    对于每个线性表位置的存入或者取出数据,对于计算机来说都是相等的时间(LOC(ai)=LOC(a1)+(i1)c),也就是一个常数,因此它的时间复杂度为O(1)

    顺序存储结构的插入与删除

    插入:

    • 如果插入位置不合理,抛出异常
    • 如果线性表长度大于等于数组长度,则抛出异常或动态增加容量
    • 从最后一个元素开始向前遍历到第i个位置,分别将它们都向后移动一个位置
    • 将要插入元素填入位置i处
    • 表长加1

    删除:

    • 如果删除位置不合理,抛出异常
    • 取出删除元素
    • 从删除元素位置开始遍历到最后一个元素位置,分别将它们都向前移动一个位置
    • 表长度减1

    插入或删除时,平均移动次数和最中间的那个元素移动次数相等,为(n-1)/2

    插入和删除时,时间复杂度为O(n)

    线性表顺序存储结构的优缺点

    优点:

    • 无须为表示表中元素之间的逻辑关系而增加额外的存储空间
    • 可以快速地存取表中任一位置的元素

    缺点:

    • 插入和删除操作需要移动大量元素
    • 当线性表长度变化较大时,难以确定存储空间的容量
    • 造成存储空间的”碎片”

    线性表的链式存储结构

    线性表的链式存储结构的特点是用一组任意的存储单元存储线性表的数据元素,这组存储单元可以是连续的,也可以是不连续的,这就意味着,这些数据元素可以存在内存未被占用的任意位置

    链式结构中,除了要存储数据元素信息外,还要存储它的后继元素的存储地址

    <img shuju_002>

    链表中第一个结点的存储位置叫做头指针,之后的每一个结点,其实就是上一个的后继指针指向的位置,最后一个结点的指针为null

    为了更加方便地对链表进行操作,有时会在单链表的第一个结点前附设一个结点,称为头结点,头结点的数据域可以不存储任何信息,也可以存储如线性表的长度等附加信息,头结点的指针域存储指向第一个结点的指针

    头指针与头结点的异同:

    • 头指针是指链表指向第一个结点的指针,若链表有头结点,则是指向头结点的指针
    • 头指针具有标识作用,所以常用头指针冠以链表的名字
    • 无论链表是否为空,头指针均不为空,头指针是链表的必要元素
    • 头结点是为了操作的统一和方便而设立的,放在第一元素的结点之前,其数据域一般无意义(也可存放链表的长度)
    • 有了头结点,对在第一元素结点前插入结点和删除第一结点,其操作与其它结点的操作就统一了
    • 头结点不一定是链表必须要素

    单链表的读取

    单链表中查找某一个元素,必须要从头开始找

    获得链表第i个数据的算法思路:

    • 声明一个结点p指向链表第一个结点,初始化j从1开始
    • 当j<i时,就遍历链表,让p的指针向后移动,不断指向下一结点,j累加1,
    • 若到链表末尾p为空,则说明第i个元素不存在
    • 否则查找成功,返回结点p的数据

    时间复杂度为O(n)

    单链表的插入与删除

    <img shuju_003>

    在ai和ai+1之间插入一个数据,只需要

    s->next=p->next;
    p->next=s;
    

    单链表第i个数据插入结点的算法思路:

    • 声明一结点p指向链表第一个结点,初始化j从1开始
    • 当j<i时,就遍历链表,让p的指针向后移动,不断指向下一结点,j累加1
    • 若到链表末尾p为空,则说明第i个元素不存在
    • 否则查找成功,在系统中生成一个空结点s
    • 将数据元素e赋值给s->data
    • 单链表的插入标准语句s->next=p->next;p->next=s;
    • 返回成功

    <img shuju_004>

    在ai-1和ai+1之间删除ai结点,只需要

    q=p->next;
    p->next=q->next;
    

    单链表第i个数据删除结点的算法思路:

    • 声明一结点p指向链表第一个结点,初始化j从1开始
    • 当j<i时,就遍历链表,让p的指针向后移动,不断指向下一个节点,j累加1
    • 若到链表末尾p为空,则说明第i个元素不存在
    • 否则查找成功,将欲删除的结点p->next赋值给q
    • 单链表的删除标准语句p->next=q->next
    • 将q结点中的数据赋值给e,作为返回
    • 释放q结点
    • 返回成功

    单链表在查询、插入和删除操作上的时间复杂度都是O(n),但是如果需要从第i个位置,插入10个元素,对于顺序存储结构意味着,每一次插入都需要移动n-i个元素,每次都是O(n),而单链表,只需要在第一次时,找到第i个位置的指针,此时为O(n),接下来的时间复杂度都是O(1),所以对于插入或者删除数据越频繁的操作,单链表的效率优势就越是明显

    单链表的整表创建

    单链表整表创建的算法思路:

    • 声明一结点p和计数器变量i
    • 初始化一空链表L
    • 让L的头结点的指针指向NULL,即建立一个带头结点的单链表
    • 循环:

      • 生成一新结点赋值给p
      • 随机生成一数字赋值给p的数据域p->data
      • 将p插入到头结点与前一新结点之间(头插法,始终让新结点在第一的位置),也可以将p插入到终端结点的后面(尾插法)

    单链表的整表删除

    单链表整表删除的算法思路如下:

    • 声明一结点p和q
    • 将第一个结点赋值给p
    • 循环

      • 将下一结点赋值给q
      • 释放p
      • 将q赋值给p

    单链表结构与顺序存储结构优缺点

    • 存储分配方式

      • 顺序存储结构用一段连续的存储单元依次存储线性表的数据元素
      • 单链表采用链式存储结构,用一组任意的存储单元存放线性表的元素
    • 时间性能

      • 查找

        • 顺序存储结构O(1)
        • 单链表O(n)
      • 插入和删除

        • 顺序存储结构需要平均移动表长一半的元素,时间为O(n)
        • 单链表在线出某位置的指针后,插入和删除时间仅为O(1)
    • 空间性能

      • 顺序存储结构需要预分配存储空间,分大了,浪费,分小了易发生上溢
      • 单链表不需要分配存储空间,只要有就可以分配,元素个数也不受限制

    静态链表

    用数组描述的链表叫做静态链表(数组中的元素由两个数据域组成,data和cur)

    <img shuju_005>

    数组中的第一个元素(下标为0)的cur存放备用链表的第一个结点的下标(即下一个元素插入存放的位置),数组的最后一个元素的cur则存放第一个有数值的元素的下标(即存放链头的位置)

    静态链表的插入操作

    将元素”丙”插入到”乙”和”丁”之间

    <img shuju_006>

    静态链表的删除操作

    将元素”甲”删除

    <img shuju_007>

    静态链表优缺点

    • 优点

      • 在插入和删除操作时,只需要修改游标,不需要移动元素,从而改进了在顺序存储结构中的插入和删除操作需要移动大量元素的缺点
    • 缺点

      • 没有解决连续存储分配带来的表长难以确定的问题
      • 失去了顺序存储结构随机存储的特性

    循环链表

    将单链表中终端结点的指针端由空指针改为指向头指针,就使整个单链表形成一个环,这种头尾相接的单链表称为单循环链表,简称循环链表

    双向链表

    双向链表是在单链表的每个结点中,再设置一个指向其前驱结点的指针域

    非空的循环的带头结点的双向链表如下图所示

    <img shuju_008>

    双向链表在插入和删除时,需要更改两个指针变量

    <img shuju_009>

    s->prior = p;
    s->next = p->next;
    p->next->prior = s;
    p->next = s;
    

    删除结点p,只需要下面两步骤

    <img shuju_010>

    p->prior->next = p->next;
    p->next->prior = p->prior;
    free(p);
    
    展开全文
  • 大话数据结构 -- 图

    千次阅读 2018-09-07 09:19:42
    图的各种定义 图是由顶点的有穷非空集合和顶点之间边的集合组成,...图与其他数据结构的不同之处见下表: 数据结构 结点之间关系 数据元素名称 数据元素可否没有 线性表 一对一 元素 可以(...

    图的各种定义

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

    在图形结构中,结点之间的关系可以是任意的,图中任意两个数据元素之间都可能相关。

    图与其他数据结构的不同之处见下表:

    数据结构 结点之间关系 数据元素名称 数据元素可否没有
    线性表 一对一 元素 可以(空表)
    一对多(除根结点外,一个结点有且只有一个双亲结点,但可以有多个孩子) 结点 可以(空树)
    多对多 顶点 不可以

    线性表中,相邻的数据元素之间具有线性关系;树结构中,相邻两层的结点具有层次关系;而图中,任意两个顶点之间都可能有关系,顶点之间的逻辑关系用边来表示,边集可以是空的

     

    无向边:若顶点vi到vj之间的边没有方向,则称这条边为无向边,用无序偶对(vi,vj)来表示。如果图中任意两个顶点之间的边都是无向边,则称该图为无向图。故(vi,vj)也可写作(vj,vi)。

    有向边:若顶点vi到vj之间的边有方向,则称这条边为有向边,也称为。用无序偶对<vi,vj>来表示。vi称为弧尾,vj称为弧头。如果图中任意两个顶点之间的边都是有向边,则称该图为有向图。故(vi,vj)不可写作(vj,vi)。

    在图中,若不存在顶点到其自身的边,且同一条边不重复出现,则称这样的图为简单图。接下来我们要讨论的都是简单图。

    在无向图中,如果任意两个顶点之间都存在边,则称该图为无向完全图含有n个结点的无向完全图有n(n-1)/2 条边。(n个结点都要与剩余n-1个结点相连,重复一倍除以2。)

    在有向图中,如果任意两个顶点之间都存在方向互为相反的两条弧,则称该图为有向完全图含有n个结点的有向完全图有n(n-1) 条边。(有方向,不用除以2。)

    故对于具有n个结点和e条边数的图,无向图0<=e<=n(n-1)/2,有向图0<=e<=n(n-1)。

    有很少条边或弧的图称为稀疏图,反之称为稠密图。这里稀疏和稠密是模糊的概念,都是相对而言的。

    与图的边或弧相关的数叫做。表示从一个顶点到另一个顶点的距离或耗费。这种带权的图通常称为

    假设有两个图G=(V,{E})和G'=(V',{E'}),如果V'∈V且E'∈E,则称G’为G的子图

    对于无向图G=(V,{E}),如果边(v,v')∈E,则称顶点v和顶点v'互为邻接点(Adjacent),即v和v'相邻接。边(v,v')依附(incident)于顶点v和v',或者说(v,v')与顶点v和v'相关联顶点v的(Degree)是和v相关联的边的数目,记为TD(v)。故边数其实就是各顶点度数和的一半,多出的一半是因为重复两次计数。

    对于有向图G=(V,{E}),如果弧<v,v'>∈E,则称顶点v邻接到顶点v'顶点v'邻接自顶点v。弧<v,v'>与顶点v和v'相关联。以顶点v为头的弧的数目称为v的入度,记为ID(v)顶点v为头的弧的数目称为v的出度,记为OD(v);顶点v的度为TD(v)=ID(v)+OD(v)。边数=入度和=出度和

    树中根结点到任意结点的路径是唯一的,但是图中顶点与顶点之间的路径却是不唯一的

    路径的长度是路径上的边或弧的数目

    第一个顶点和最后一个顶点相同的路径称为回路或环

    序列中顶点不重复出现的路径称为简单路径除了第一个顶点和最后一个顶点外,其余顶点不重复出现的回路,称为简单回路或简单环

    在无向图G中,如果从顶点v到顶点v'有路径,则称v和v'是连通的。如果对于图中任意两个顶点vi、vj∈V,vi和vj都是连通的,则称G是连通图

    无向图中的极大连通子图称为连通分量。强调:

     ● 要是子图;

     ● 子图要是连通的;

     ● 联通子图含有极大顶点数

     ● 具有极大顶点数的连通子图包含依附于这些顶点的所有边。

    如图图7-2-12,图1是一个无向非连通图。但是它有两个连通分量,即图2和图3。而图4,尽管是图1的子图,但是它却不满足连通子图的极大顶点数(图2满足)。因此它不是图1的无向图的连通分量。

    在有向图G中,如果对于每一对vi、vj∈V,vivj,从vi到vj和从vj到vi都存在路径,则称G是强连通图有向图中的极大强连通子图称做有向图的强连通分量

    如图7-2-13,图1并不是强连通图,因为顶点A到顶点D存在路径,而D到A就不存在。图2就是强连通图,而且显然图2是图1的极大强连通子图,即是它的强连通分量。

    一个连通图的生成树是一个极小的连通子图,它含有图中全部的n个顶点,但只有足以构成一棵树的n-1条边。比如图7-2-14的图1是一普通图,但显然它不是生成树,当去掉两条构成环的边后,比如图2或图3,就满足n个顶点n-1条边且连通的定义了。它们都是一棵生成树。

    如果一个图有n个顶点和小于n-1条边,则是非连通图,如果它多于n-1条边,必定构成一个环,因为这条边使得它依附的那两个顶点之间有了第二条路径。比如图2和图3,随便加哪两顶点的边都将构成环。不过有n-1条边并不一定是生成树,比如图4。

    如果一个有向图恰有一个顶点的入度为0,其余顶点的入度均为1,则是一个有向树。所谓入度为0其实就相当于树中的根结点,其余顶点入度为1就是说树的非根结点的双亲只有一个。一个有向图的生成森林由若干棵有向树组成,含有图中全部顶点,但只有足以构成若干棵不相交的有向树的弧。如图7-2-15的图1是一棵有向图。去掉一些弧后,它可以分解为两棵有向树,如图2和图3,这两棵就是图1有向图的生成森林。

     

    图的存储结构

    图上任何一个顶点都可被看成是第一个顶点,任一顶点的邻接点之间也不存在次序关系。

    图的结构比较复杂,任意两个顶点之间都可能存在联系。因此,图不可能用简单的顺序存储结构来表示。

    1、邻接矩阵

    用两个数组来表示图。一个一维数组存储图中顶点信息,一个二维数组(称为邻接矩阵)存储图中的边或弧的信息。 

    设图G有n个顶点,则邻接矩阵是一个n×n的方阵,定义为:

    可以看出,无向图的边数组是一个对称矩阵

    有了这个矩阵,我们就可以很容易地知道图中的信息。
    1.我们要判定任意两顶点是否有边无边就非常容易了。
    2.我们要知道某个顶点的度,其实就是这个顶点vi在邻接矩阵中第i行(或第i列)的元素之和。比如顶点v1的度就是1+0+1+0=2。3.求顶点vi的所有邻接点就是将矩阵中第i行元素扫描一遍,arc[i][j]为1就是邻接点。

    我们再来看一个有向图样例,如图7-4-3所示的左图。

    因为是有向图,所以此矩阵并不对称。有向图讲究入度和出度。

    设图G是网图,有n个顶点,则邻接矩阵是一个n×n的方阵。权值wij大多数情况下是正值,但个别时候可能就是0,甚至有可能是负值。因此必须要用一个不可能的值来代表不存在。如图7-4-4左图就是一个有向网图,右图就是它的邻接矩阵。

    邻接矩阵存储的结构: 

    // 顶点类型应由用户定义
    typedef char VertexType;
    // 边上的权值类型应由用户定义
    typedef int EdgeType;
    // 最大顶点数,应由用户定义
    
    #define INFINITY 65535
    typedef struct{
        // 顶点表
        VertexType vexs[MAXVEX];
        // 邻接矩阵,可看作边表
        EdgeType arc[MAXVEX][MAXVEX];
        // 图中当前的顶点数和边数
        int numVertexes,numEdges;
    }MGragh;
    

    有了这个结构定义,我们构造一个图,其实就是给顶点表和边表输入数据的过程。我们来看看无向网图的创建代码。

    void CreateMGragh(MGragh *G){
        int i,j,k,w;
        printf("输入顶点数和边数:\n");
        // 输入顶点数和边数
        scanf("%d,%d",&G->numVertexes,&G->numEdges);
        // 读入顶点信息,建立顶点表
        for(i=0;i<G->numVertexes;i++)
            scanf(&G->vexs[i]);
        for(i=0;i<G->numVertexes;i++)
            for(j=0;j<G->numVertexes;j++)
                // 邻接矩阵初始化
                G->arc[i][j]=INFINITY;
        // 读入numEgdes条边,建立邻接矩阵
        for(k=0;k<G->numEdges;k++)
        {
            printf("输入边(vi,vj)上的下标i,下标j和权w:\n");
            scanf("%d,%d,%d",&i,&j,&w);
            G->arc[i][j]=w;
            // 因为是无向图,矩阵对称
            G->arc[j][i]=w;
        }
    }
    

    从代码中也可以得到,n个顶点和e条边的无向网图的创建,时间复杂度为O(n+n^2+e),其中对邻接矩阵G.arc的初始化耗费了O(n^2)的时间。

    2、邻接表

    邻接矩阵对于边数相对顶点较少的图是存在对存储空间的极大浪费的。

    考虑对边或弧是使用链式存储的方式来避免空间浪费的问题。

    数组与链表相结合:

    1、图中顶点用一个一维数组存储。每个数据元素还需要存储指向第一个邻接点的指针,以便于查找该顶点的边信息;

    2、图中每个顶点vi的所有邻接点构成一个线性表,由于邻接点的个数不定,所以用单链表存储,无向图称为顶点vi的边表,有向图则称为顶点vi作为弧尾出边表。

    有向图由于有方向,我们是以顶点为弧尾来存储边表的,这样很容易就可以得到每个顶点的出度。但也有时为了便于确定顶点的入度或以顶点为弧头的弧,我们可以建立一个有向图的逆邻接表,即对每个顶点vi都建立一个链接以vi为弧头的表。

    此时我们很容易就可以算出某个顶点的入度或出度是多少,判断两顶点是否存在弧也很容易实现。

    对于带权值的网图,可以在边表结点定义中再增加一个weight的数据域,存储权值信息即可,如图7-4-8所示。

    结构定义:

    // 顶点类型应由用户定义
    typedef char VertexType;
    // 边上的权值类型应由用户定义
    typedef int EdgeType;
    // 边表结点
    typedef struct EdgeNode{
        // 邻接点域,存储该顶点对应的下标
        int adjvex;
        // 用于存储权值,对于非网图可以不需要
        EdgeType weight;
        // 链域,指向下一个邻接点
        struct EdgeNode *next;
    } EdgeNode;
    // 顶点表结点
    typedef struct VertexNode{
        // 顶点域,存储顶点信息
        VertexType data;
        // 边表头指针
        EdgeNode *firstedge;
    }VertexNode,AdjList[maxvex];
    typdef strcut{
        AdjList adjlist;
        // 图中当前顶点数和边数
        int numVertexes,numEdges;
    }GraphAdjList;
        

    无向图的邻接表创建代码如下:

    // 建立图的邻接表结构
    void CreateALGragh(GraphAdjList *G)
    {
        int i,j,k;
        EdgeNode *e;
        printf("输入顶点数和边数:\n");
        // 输入顶点数和边数
        scanf("%d,%d",&G->numVertexes,&G->numEdges);
        // 读入顶点信息,建立顶点表
        for (i=0;i<G->numVertexes;i++)
        {
            //输入顶点信息
            scanf(&G->adjList[i].data);
            //将边表置为空表
            G->adjList[i].firstedge=NULL;
        }
        // 建立边表
        for (k=0;k<G->numEdges;k++)
        {
            printf("输入边(vi,vj)上的顶点序号:\n");
            scanf("%d,%d:",&i,&j);
            // 向内存申请空间
            // 生成边表结点
            e=(EdgeNode *)malloc(sizeof(EdgeNode));
            // 邻接序号为j
            e->adjvex=j;
            // 将e指针指向当前顶点指向的结点(头插法)
            e->next=G->adjList[i].firstedge;
            G->adjList[i].firstedge=e;
            // 向内存申请空间
            // 生成边表结点
            e=(EdgeNode *)malloc(sizeof(EdgeNode));
            // 邻接序号为i
            e->adjvex=i;
            // 将e指针指向当前顶点指向的结点(头插法)
            e->next=G->adjList[j].firstedge;
            G->adjList[j].firstedge=e;
        }
    }

     本算法的时间复杂度,对于n个顶点e条边来说,很容易得出是O(n+e)。

    3、十字链表

    对于有向图来说,邻接表是有缺陷的。关心了出度问题,想了解入度就必须要遍历整个图才能知道,反之,逆邻接表解决了入度却不了解出度的情况。而十字链表将邻接表与逆邻接表结合起来

    重新定义顶点表结点结构如表7-4-1所示。

    其中firstin表示入边表头指针,指向该顶点的入边表中第一个结点,firstout表示出边表头指针,指向该顶点的出边表中的第一个结点。

    重新定义的边表结点结构如表7-4-2所示。

    其中tailvex是指弧起点在顶点表的下标,headvex是指弧终点在顶点表中的下标,headlink是指入边表指针域,指向终点相同的下一条边,taillink是指出边表指针域,指向起点相同的下一条边。如果是网,还可以再增加一个weight域来存储权值

    比如图7-4-10,顶点依然是存入一个一维数组{v0,v1,v2,v3},实线箭头指针的图示完全与图7-4-7的邻接表相同。就以顶点v0来说,firstout指向的是出边表中的第一个结点v3。所以v0边表结点的headvex=3,而tailvex其实就是当前顶点v0的下标0,由于v0只有一个出边顶点,所以headlink和taillink都是空。

    虚线箭头其实就是此图的逆邻接表的表示。对于v0来说,它有两个顶点v1和v2的入边。因此v0的firstin指向顶点v1的边表结点中headvex为0的结点,如图7-4-10右图中的①。接着由入边结点的headlink指向下一个入边顶点v2,如图中的②。对于顶点v1,它有一个入边顶点v2,所以它的firstin指向顶点v2的边表结点中headvex为1的结点,如图中的③。顶点v2和v3也是同样有一个入边顶点,如图中④和⑤。

    十字链表的好处就是因为把邻接表和逆邻接表整合在了一起,这样既容易找到以vi为尾的弧,也容易找到以vi为头的弧,因而容易求得顶点的出度和入度。而且它除了结构复杂一点外,其实创建图算法的时间复杂度是和邻接表相同的。

    4、邻接多重表

    如果我们更关注边的操作,比如对已访问过的边做标记,删除某一条边等操作,那就意味着,需要找到这条边的两个边表结点进行操作,这其实还是比较麻烦的。比如图7-4-11,若要删除左图的(v0,v2)这条边,需要对邻接表结构中右边表的阴影两个结点进行删除操作,显然这是比较烦琐的。

    其中ivex和jvex是与某条边依附的两个顶点在顶点表中的下标。ilink指向依附顶点ivex的下一条边,jlink指向依附顶点jvex的下一条边。这就是邻接多重表结构。

    我们开始连线,如图7-4-13。首先连线的①②③④就是将顶点的firstedge指向一条边,顶点下标要与ivex的值相同,这很好理解。接着,由于顶点v0的(v0,v1)边的邻边有(v0,v3)和(v0,v2)。因此⑤⑥的连线就是满足指向下一条依附于顶点v0的边的目标,注意ilink指向的结点的jvex一定要和它本身的ivex的值相同。同样的道理,连线⑦就是指(v1,v0)这条边,它是相当于顶点v1指向(v1,v2)边后的下一条。v2有三条边依附,所以在③之后就有了⑧⑨。连线⑩的就是顶点v3在连线④之后的下一条边。左图一共有5条边,所以右图有10条连线,完全符合预期。

    邻接多重表与邻接表的差别,仅仅是在于同一条边在邻接表中用两个结点表示,而在邻接多重表中只有一个结点。这样对边的操作就方便多了,若要删除左图的(v0,v2)这条边,只需要将右图的⑥⑨的链接指向改为∧即可。

    5、边集数组

    边集数组是由两个一维数组构成。一个是存储顶点的信息;另一个是存储边的信息,这个边数组每个数据元素由一条边的起点下标(begin)、终点下标(end)和权(weight)组成,如图7-4-14所示。显然边集数组关注的是边的集合,在边集数组中要查找一个顶点的度需要扫描整个边数组,效率并不高。因此它更适合对边依次进行处理的操作,而不适合对顶点相关的操作

    这一结构将会在Kruskal算法中应用。

     

    图的遍历

    图的遍历是和树的遍历类似,我们希望从图中某一顶点出发访遍图中其余顶点,且使每一个顶点仅被访问一次,这一过程就叫做图的遍历(Traversing Graph)。

    我们需要在遍历过程中把访问过的顶点打上标记,以避免访问多次而不自知。具体办法是设置一个访问数组visited[n]n是图中顶点的个数,初值为0,访问过后设置为1

    1、深度优先遍历

    也称为深度优先搜索,简称为DFS

    深度优先遍历其实就是一个递归的过程,如果再敏感一些,会发现其实转换成如图7-5-2的右图后,就像是一棵树的前序遍历,没错,它就是。它从图中某个顶点v出发,访问此顶点,然后从v的未被访问的邻接点出发深度优先遍历图,直至图中所有和v有路径相通的顶点都被访问到。事实上,我们这里讲到的是连通图,对于非连通图,只需要对它的连通分量分别进行深度优先遍历,即在先前一个顶点进行一次深度优先遍历后,若图中尚有顶点未被访问,则另选图中一个未曾被访问的顶点作起始点,重复上述过程,直至图中所有顶点都被访问到为止。

    如果我们用的是邻接矩阵的方式,则代码如下:

    /* Boolean是布尔类型,其值是TRUE或FALSE */
    typedef int Boolean;             
    /* 访问标志的数组 */
    Boolean visited[MAX];            
    /* 邻接矩阵的深度优先递归算法 */
    void DFS(MGraph G, int i)
    {
        int j;
        visited[i] = TRUE;
        /* 打印顶点,也可以其他操作 */
        printf("%c ", G.vexs[i]);    
        for (j = 0; j < G.numVertexes; j++)
            if (G.arc[i][j] == 1 && !visited[j])
                /* 对为访问的邻接顶点递归调用 */
                DFS(G, j);           
    }
    /* 邻接矩阵的深度遍历操作 */
    void DFSTraverse(MGraph G)
    {
        int i;
        for (i = 0; i < G.numVertexes; i++)
            /* 初始所有顶点状态都是未访问过状态 */
            visited[i] = FALSE;      
        for (i = 0; i < G.numVertexes; i++)
            /* 对未访问过的顶点调用DFS,若是连通图,只会执行一次 */
            if (!visited[i])         
                DFS(G, i);
    }
    

    对于n个顶点e条边的图来说,邻接矩阵由于是二维数组,要查找每个顶点的邻接点需要访问矩阵中的所有元素,因此都需要O(n

    ^2)的时间。 

    如果图结构是邻接表结构,其DFSTraverse函数的代码是几乎相同的,只是在递归函数中因为将数组换成了链表而有不同,代码如下。

    /* 邻接表的深度优先递归算法 */
    void DFS(GraphAdjList GL, int i)
    {
        EdgeNode *p;
        visited[i] = TRUE;
        /* 打印顶点,也可以其他操作 */
        printf("%c ", GL->adjList[i].data);    
        p = GL->adjList[i].firstedge;
        while (p)
        {
            if (!visited[p->adjvex])
                /* 对为访问的邻接顶点递归调用 */
                DFS(GL, p->adjvex);            
            p = p->next;
        }
    }
    /* 邻接表的深度遍历操作 */
    void DFSTraverse(GraphAdjList GL)
    {
        int i;
        for (i = 0; i < GL->numVertexes; i++)
            /* 对未访问过的顶点调用DFS,若是连通图,只会执行一次 */
            if (!visited[i])                   
                DFS(GL, i);
    }
    
    
    

    而邻接表做存储结构时,找邻接点所需的时间取决于顶点和边的数量,所以是O(n+e)。显然对于点多边少的稀疏图来说,邻接表结构使得算法在时间效率上大大提高

    对于有向图而言,由于它只是对通道存在可行或不可行,算法上没有变化,是完全可以通用的。

    2、广度优先遍历

    又称为广度优先搜索,简称BFS

    如果说图的深度优先遍历类似树的前序遍历,那么图的广度优先遍历就类似于树的层序遍历了。

    我们将下图的第一幅图稍微变形,变形原则是顶点A放置在最上第一层,让与它有边的顶点B、F为第二层,再让与B和F有边的顶点C、I、G、E为第三层,再将这四个顶点有边的D、H放在第四层,如图7-5-3的第二幅图所示。此时在视觉上感觉图的形状发生了变化,其实顶点和边的关系还是完全相同的。

    以下是邻接矩阵结构的广度优先遍历算法。

    /* 邻接矩阵的广度遍历算法 */
    void BFSTraverse(MGraph G)
    {
        int i, j;
        Queue Q;
        for (i = 0; i < G.numVertexes; i++)
            visited[i] = FALSE;
        /* 初始化一辅助用的队列 */
        InitQueue(&Q);                                   
        /* 对每一个顶点做循环 */
        for (i = 0; i < G.numVertexes; i++)              
        {
            /* 若是未访问过就处理 */
            if (!visited[i])                             
            {
                /* 设置当前顶点访问过 */
                visited[i]=TRUE;                         
                /* 打印顶点,也可以其他操作 */
                printf("%c ", G.vexs[i]);                
                /* 将此顶点入队列 */
                EnQueue(&Q,i);                           
                /* 若当前队列不为空 */
                while (!QueueEmpty(Q))                   
                {
                    /* 将队中元素出队列,赋值给i */
                    DeQueue(&Q, &i);                     
                    for (j = 0; j < G.numVertexes; j++)
                    {
                        /* 判断其他顶点若与当前顶点存在边且未访问过 */
                        if (G.arc[i][j] == 1 && !visited[j])
                        {
                            /* 将找到的此顶点标记为已访问 */
                            visited[j]=TRUE;             
                            /* 打印顶点 */
                            printf("%c ", G.vexs[j]);    
                            /* 将找到的此顶点入队列 */
                            EnQueue(&Q,j);               
                        }
                    }
                }
            }
        }
    }

    其中涉及到队列操作:

    /* 用到的队列结构与函数********************************** */
    
    typedef int Status;	/* Status是函数的类型,其值是函数结果状态代码,如OK等 */  
    
    /* 循环队列的顺序存储结构 */
    typedef struct
    {
    	int data[MAXSIZE];
    	int front;    	/* 头指针 */
    	int rear;		/* 尾指针,若队列不空,指向队列尾元素的下一个位置 */
    }Queue;
    
    /* 初始化一个空队列Q */
    Status InitQueue(Queue *Q)
    {
    	Q->front=0;
    	Q->rear=0;
    	return  OK;
    }
    
    /* 若队列Q为空队列,则返回TRUE,否则返回FALSE */
    Status QueueEmpty(Queue Q)
    { 
    	if(Q.front==Q.rear) /* 队列空的标志 */
    		return TRUE;
    	else
    		return FALSE;
    }
    
    /* 若队列未满,则插入元素e为Q新的队尾元素 */
    Status EnQueue(Queue *Q,int e)
    {
    	if ((Q->rear+1)%MAXSIZE == Q->front)	/* 队列满的判断 */
    		return ERROR;
    	Q->data[Q->rear]=e;			/* 将元素e赋值给队尾 */
    	Q->rear=(Q->rear+1)%MAXSIZE;/* rear指针向后移一位置, */
    								/* 若到最后则转到数组头部 */
    	return  OK;
    }
    
    /* 若队列不空,则删除Q中队头元素,用e返回其值 */
    Status DeQueue(Queue *Q,int *e)
    {
    	if (Q->front == Q->rear)			/* 队列空的判断 */
    		return ERROR;
    	*e=Q->data[Q->front];				/* 将队头元素赋值给e */
    	Q->front=(Q->front+1)%MAXSIZE;	/* front指针向后移一位置, */
    									/* 若到最后则转到数组头部 */
    	return  OK;
    }
    /* ****************************************************** */

     

     

    对于邻接表的广度优先遍历,代码与邻接矩阵差异不大,代码如下。

    /* 邻接表的广度遍历算法 */
    void BFSTraverse(GraphAdjList GL)
    {
        int i;
        EdgeNode *p;
        Queue Q;
        for (i = 0; i < GL->numVertexes; i++)
            visited[i] = FALSE;
        InitQueue(&Q);
        for (i = 0; i < GL->numVertexes; i++)
        {
            if (!visited[i])
            {
                visited[i] = TRUE;
                /* 打印顶点,也可以其他操作 */
                printf("%c ", GL->adjList[i].data);    
                EnQueue(&Q, i);
                while (!QueueEmpty(Q))
                {
                    DeQueue(&Q, &i);
                    /* 找到当前顶点边表链表头指针 */
                    p = GL->adjList[i].firstedge;      
                    while (p)
                    {
                        /* 若此顶点未被访问 */
                        if (!visited[p->adjvex])       
                        {
                            visited[p->adjvex] = TRUE;
                            printf("%c ", GL->adjList[p->adjvex].data);
                            /* 将此顶点入队列 */
                            EnQueue(&Q, p->adjvex);    
                        }
                        /* 指针指向下一个邻接点 */
                        p = p->next;                   
                    }
                }
            }
        }
    }
    
    

    对比图的深度优先遍历与广度优先遍历算法,你会发现,它们在时间复杂度上是一样的,不同之处仅仅在于对顶点访问的顺序不同。可见两者在全图遍历上是没有优劣之分的,只是视不同的情况选择不同的算法。

    不过如果图顶点和边非常多,不能在短时间内遍历完成,遍历的目的是为了寻找合适的顶点,那么选择哪种遍历就要仔细斟酌了。深度优先更适合目标比较明确,以找到目标为主要目的的情况,而广度优先更适合在不断扩大遍历范围时找到相对最优解的情况

     

    最小生成树

    所谓的最小成本,就是n个顶点,用n-1条边把一个连通图连接起来,并且使得权值的和最小

    一个连通图的生成树是一个极小的连通子图,它含有图中全部的顶点,但只有足以构成一棵树的n-1条边。那么我们把构造连通网的最小代价生成树称为最小生成树

    1、普里姆(Prim)算法

    我们先构造图7-6-1的邻接矩阵,如图7-6-3的右图所示。

    也就是说,现在我们已经有了一个存储结构为MGragh的G(见本书7.4节邻接矩阵)。G有9个顶点,它的arc二维数组如图7-6-3的右图所示。数组中的我们用65535来代表∞。

    于是普里姆(Prim)算法代码如下,左侧数字为行号。其中INFINITY为权值极大值,不妨是65535,MAXVEX为顶点个数最大值,此处大于等于9即可。

    /* Prim算法生成最小生成树 */
      void MiniSpanTree_Prim(MGraph G)
      {
          int min, i, j, k;
          /* 保存相关顶点下标 */
          int adjvex[MAXVEX];                        
          /* 保存相关顶点间边的权值 */
          int lowcost[MAXVEX];                       
          /* 初始化第一个权值为0,即v0加入生成树 */
          /* lowcost的值为0,在这里就是此下标的顶点已经加入生成树 */
          lowcost[0] = 0;                            
          /* 初始化第一个顶点下标为0 */
          adjvex[0] = 0;                             
          /* 循环除下标为0外的全部顶点 */
          for (i = 1; i < G.numVertexes; i++)        
          {
             /* 将v0顶点与之有边的权值存入数组 */
             lowcost[i] = G.arc[0][i];              
             /* 初始化都为v0的下标 */
             adjvex[i] = 0;                         
         }
         for (i = 1; i < G.numVertexes; i++)
         {
             /* 初始化最小权值为∞, */
             /* 通常设置为不可能的大数字如32767、65535等 */
             min = INFINITY;                        
             j = 1; k = 0;
             /* 循环全部顶点 */
             while (j < G.numVertexes)              
             {
                 /* 如果权值不为0且权值小于min */
                 if (lowcost[j] != 0 && lowcost[j] < min)
                 {                                  
                     /* 则让当前权值成为最小值 */
                     min = lowcost[j];              
                     /* 将当前最小值的下标存入k */
                     k = j;                         
                 }
                 j++;
             }
             /* 打印当前顶点边中权值最小边 */
             printf("(%d,%d)", adjvex[k], k);       
             /* 将当前顶点的权值设置为0,表示此顶点已经完成任务 */
             lowcost[k] = 0;                        
             /* 循环所有顶点 */
             for (j = 1; j < G.numVertexes; j++)    
             {
                 /* 若下标为k顶点各边权值小于此前这些顶点未被加入生成树权值 */
                 if (lowcost[j] != 0 && G.arc[k][j] < lowcost[j])
                 {                                  
                     /* 将较小权值存入lowcost */
                     lowcost[j] = G.arc[k][j];      
                     /* 将下标为k的顶点存入adjvex */
                     adjvex[j] = k;                 
                 }
             }
         }
     }
    

    假设N=(V,{E})是连通网,TE是N上最小生成树中边的集合。算法从U={u0}(u0∈V),TE={}开始。重复执行下述操作:在所有u∈U,v∈V-U的边(u,v)∈E中找一条代价最小的边(u0,v0)并入集合TE,同时v0并入U,直至U=V为止。此时TE中必有n-1条边,则T=(V,{TE})为N的最小生成树。

    总结来说,即从一个结点开始,先找到权值最小的一条边,记录下这条边依附的另一结点,再记录这一结点的各个边的权值,连同之前保存下来的第一个点到各点的距离进行比较,继续找权值最小的边......在此过程中,忽略已经访问过的点。

    由算法代码中的循环嵌套可得知此算法的时间复杂度为O(n^2)。

    2、克鲁斯卡尔(Kruskal)算法

    Prim算法是以某顶点为起点,逐步找各顶点上最小权值的边来构建最小生成树的。

    同样,我们也可以直接就以边为目标去构建,因为权值是在边上,直接去找最小权值的边来构建生成树也是很自然的想法,只不过构建时要考虑是否会形成环路

    此时我们就用到了图的存储结构中的边集数组结构。以下是edge边集数组结构的定义代码:

    // 对边集数组Edge结构的定义
    typedef struct{
        int begin;
        int end;
        int weight;
    }Edge;
    

    我们将图7-6-3的邻接矩阵通过程序转化为图7-6-7的右图的边集数组,并且对它们按权值从小到大排序。

    于是克鲁斯卡尔(Kruskal)算法代码如下,左侧数字为行号。其中MAXEDGE为边数量的极大值,此处大于等于15即可,MAXVEX为顶点个数最大值,此处大于等于9即可。

    // Kruskal 算法生成最小生成树
    // 生成最小生成树
    void MiniSpanTree_Kruskal(MGraph G){
        int i,j,n,m;
        // 定义边集数组
        Edge edges[MAXEDGE];
        /* 用来构建边集数组并排序********************* */
    	for ( i = 0; i < G.numVertexes-1; i++)
    	{
    		for (j = i + 1; j < G.numVertexes; j++)
    		{
    			if (G.arc[i][j]<INFINITY)
    			{
    				edges[k].begin = i;
    				edges[k].end = j;
    				edges[k].weight = G.arc[i][j];
    				k++;
    			}
    		}
    	}
    	sort(edges, &G);
    	/* ******************************************* */
        // 定义一数组用来判断边与边是否形成环路
        int parent[MAXVEX];
        // 此处省略将邻接矩阵G转化为边集数组edges
        // 并按权有小到大排序的代码
        for (i=0;i<G.numVertexes;i++){
            // 初始化数组值为0
            parent[i]=0;
        }
        // 循环每一条边
        for(i=0;i<G.numEdges;i++){
            n= Find(parent,edges[i].begin);
            m= Find(parent,edges[i].end);
            // 假如n与m不等,说明此边没有与现有生成树形成环路
            if(n!=m){
                // 将此边的结尾顶点放入下标为起点的parent中
                // 表示此顶点已经在生成树集合中
                parent[n]=m;
                printf("(%d,%d)%d",edges[i].begin,edges[i].end,edges[i].weight);
            }
        }
    }
    
    // 查找连线顶点的尾部下标
    int Find(int *parent, int f){
        while(parent[f]>0)
            f=parent[f];
        return f;
    }

    其中,构造边集数组时用到了:

    /* 交换权值 以及头和尾 */
    void Swapn(Edge *edges,int i, int j)
    {
    	int temp;
    	temp = edges[i].begin;
    	edges[i].begin = edges[j].begin;
    	edges[j].begin = temp;
    	temp = edges[i].end;
    	edges[i].end = edges[j].end;
    	edges[j].end = temp;
    	temp = edges[i].weight;
    	edges[i].weight = edges[j].weight;
    	edges[j].weight = temp;
    }
    
    /* 对权值进行排序 */
    void sort(Edge edges[],MGraph *G)
    {
    	int i, j;
    	for ( i = 0; i < G->numEdges; i++)
    	{
    		for ( j = i + 1; j < G->numEdges; j++)
    		{
    			if (edges[i].weight > edges[j].weight)
    			{
    				Swapn(edges, i, j);
    			}
    		}
    	}
    	printf("权排序之后的为:\n");
    	for (i = 0; i < G->numEdges; i++)
    	{
    		printf("(%d, %d) %d\n", edges[i].begin, edges[i].end, edges[i].weight);
    	}
    }

    我们其实是有两个连通的边集合A与B中纳入到最小生成树中的,如图7-6-12所示。当parent[0]=1,表示v0和v1已经在生成树的边集合A中。此时将parent[0]=1的1改为下标,由par-ent[1]=5,表示v1和v5在边集合A中,par-ent[5]=8表示v5与v8在边集合A中,par-ent[8]=6表示v8与v6在边集合A中,par-ent[6]=0表示集合A暂时到头,此时边集合A有v0、v1、v5、v8、v6。我们查看parent中没有查看的值,parent[2]=8表示v2与v8在一个集合中,因此v2也在边集合A中。再由parent[3]=7、par-ent[4]=7和parent[7]=0可知v3、v4、v7在另一个边集合B中。

    当i=7时,第10行,调用Find函数,会传入参数edges[7].begin=5。此时第21行,parent[5]=8>0,所以f=8,再循环得par-ent[8]=6。因parent[6]=0所以Find返回后第10行得到n=6。而此时第11行,传入参数edges[7].end=6得到m=6。此时n=m,不再打印,继续下一循环。这就告诉我们,因为边(v5,v6)使得边集合A形成了环路。因此不能将它纳入到最小生成树中,如图7-6-12所示。11.当i=8时,与上面相同,由于边(v1,v2)使得边集合A形成了环路。因此不能将它纳入到最小生成树中,如图7-6-12所示。12.当i=9时,边(v6,v7),第10行得到n=6,第11行得到m=7,因此parent[6]=7,打印“(6,7)19”。此时parent数组值为{1,5,8,7,7,8,7,0,6},如图7-6-13所示。13.此后边的循环均造成环路,最终最小生成树即为图7-6-13所示。

    简单来说,parent数组的作用就是求连通分量。通过层层循环,最终同一个连通分量里的顶点在Find函数中返回的数值是一样的。

    假设N=(V,{E})是连通网,则令最小生成树的初始状态为只有n个顶点而无边的非连通图T={V,{}},图中每个顶点自成一个连通分量。在E中选择代价最小的边,若该边依附的顶点落在T中不同的连通分量上,则将此边加入到T中,否则舍去此边而选择下一条代价最小的边。依次类推,直至T中所有顶点都在同一连通分量上为止。

    此算法的Find函数由边数e决定,时间复杂度为O(loge),而外面有一个for循环e次。所以克鲁斯卡尔算法的时间复杂度为O(eloge)

    克鲁斯卡尔算法主要是针对边来展开,边数少时效率会非常高,所以对于稀疏图有很大的优势;而普里姆算法对于稠密图,即边数非常多的情况会更好一些。

     

    最短路径

    在网图和非网图中,最短路径的含义不同的。由于非网图没有边上的权值,所谓的最短路径,其实就是指两顶点之间经过的边数最少的路径;而对于网图来说,最短路径是指两顶点之间经过的边上权值之和最少的路径,并且我们称路径上的第一个顶点是源点,最后一个顶点是终点

    非网图可以理解为所有边的权值都为1的网

    1、迪杰斯特拉(Dijkstra)算法

    从某个源点到其余各顶点的最短路径问题。按路径长度递增的次序产生最短路径的算法

    它并不是一下子就求出了两个顶点间的最短路径,而是一步步求出它们之间顶点的最短路径,过程中都是基于已经求出的最短路径的基础上,求得更远顶点的最短路径,最终得到结果。

    #define MAXVEX 9
    #define INFINITY 65535
    // 用于存储最短路径下标的数组
    typedef int Patharc[MAXVEX];
    // 用于存储到各点最短路径的权值和
    ShortPathTable[MAXVEX];
    // Dijkstra算法,求有向网G的v0顶点到其余顶点v最短路径P[v]及带权长度D[v]
    // P[v]的值为前驱顶点下标,D[v]表示v0到v的最短路径长度和
    void ShortestPath_Dijkstra(MGraph G, int v0, Patharc *P, ShortPathTable *D){
        int v,w,k,min;
        // final[w]=1表示求得顶点v0至vw的最短路径
        int final[MAXVEX];
        // 初始化数据
        for(v=0;v<G.numVertexes;v++){
            // 全部顶点初始化为未知最短路径状态
            final[v]=0;
            // 将与v0点有连线的顶点加上权值
            (*D)[v]=G.arc[v0][v];
            // 初始化路径数组P为-1
            (*P)[v]=-1;
        }
        // v0至v0不需要求路径
        final[v0]=1;
        // 开始主循环,每次求得v0到某个v顶点的最短路径
        for(v=1;v<G.numVertexes;v++){
            // 当前所知离v0顶点的最近距离
            min=INFINITY;
            // 寻找离v0最近的顶点
            for(w=0;w<G.numVertexes;w++){
                if(!final[w]&&(*D)[w]<min){
                    k=w;
                    min=(*D)[w]
                }
            }
            // 将目前找到的最近的顶点置为1
            final[k]=1;
            // 修正当前最短路径及距离
            for(w=0;w<G.numVertexes;w++){
                // 如果经过v顶点的路径比现在这条路径的长度短的话
                if(!final[w] && (min+G.arc[k][w]<(*D)[w])){
                    // 说明找到了更短的路径,修改D[w]和P[w]
                    // 修改当前路径长度
                    (*D)[w]=min+G.arc[k][w];
                    (*P)[w]=k;
                }
            }
        }
    }

    从循环嵌套可以很容易得到此算法的时间复杂度为O(n^2),尽管有同学觉得,可不可以只找到从源点到某一个特定终点的最短路径,其实这个问题和求源点到其他所有顶点的最短路径一样复杂,时间复杂度依然是O(n^2)。

    可如果我们还需要知道如v3到v5、v1到v7这样的任一顶点到其余所有顶点的最短路径怎么办呢?此时简单的办法就是对每个顶点当作源点运行一次迪杰斯特拉(Dijkstra)算法,等于在原有算法的基础上,再来一次循环,此时整个算法的时间复杂度就成了O(n^3)

    2、弗洛伊德(Floyd)算法

    我们先定义两个二维数组D[3][3]和P[3][3],D代表顶点到顶点的最短路径权值和的矩阵,P代表对应顶点的最小路径的前驱矩阵,用来存储路径

    在未分析任何顶点之前,我们将D命名为D-1,其实它就是初始的图的邻接矩阵。将P命名为P-1,初始化为图中所示的矩阵。

    首先我们来分析,所有的顶点经过v0后到达另一顶点的最短路径。因为只有三个顶点,因此需要查看v-1→v0→v2,得到D-1[1][0]+D-1[0][2]=2+1=3。D-1[1][2]表示的是v1→v2的权值为5,我们发现D-1[1][2]>D-1[1][0]+D-1[0][2],通俗的话讲就是v1→v0→v2比直接v1→v2距离还要近。所以我们就让D-1[1][2]=D-1[1][0]+D-1[0][2]=3,同样的D-1[2][1]=3,于是就有了D0的矩阵。因为有变化,所以P矩阵对应的P-1[1][2]和P-1[2][1]也修改为当前中转的顶点v0的下标0,于是就有了P0。也就是说D0[v][w]=min{D-1[v][w],D-1[v][0]+D-1[0][w]}。

    接下来,其实也就是在D0和P0的基础上继续处理所有顶点经过v1和v2后到达另一顶点的最短路径,得到D1和P1、D2和P2完成所有顶点到所有顶点的最短路径计算工作。

    代码如下,注意因为是求所有顶点到所有顶点的最短路径,因此Pathmatrix和ShortPathTable都是二维数组

    typedef int Pathmatrix[MAXVEX][MAXVEX];
    typedef int ShortPathTable[MAXVEX][MAXVEX];
    // Floyd算法,求网图G中各顶点v到其余顶点w最短路径P[v][w]及带权长度D[v][w]
    void ShortestPath_Floyd(MGragh G,Pathmatrix *P,ShortPathTable *D){
        int v,w,k;
        // 初始化D与P
        for(v=0;v<G.numVertexes;++v){
            for(w=0;w<G.numVertexes;++w){
                // D[v][w]值即为对应点间的权值
                (*D)[v][w]=G.matrix[v][w];
                // 初始化P
                (*P)[v][w]=w;
            }
        }
        for(k=0;k<G.numVertexes;++k){
            for(v=0;v<G.numVertexes;++v){
                for(w=0;w<G.numVertexes;++w){
                    if((*D)[v][w] > (*D)[v][k]+(*D)[k][w]){
                        // 如果经过下标为k顶点路径比原两点间路径更短
                        // 将当前两点间权值设为更小的一个
                        (*D)[v][w]=(*D)[v][k]+(*D)[k][w];
                        // 路径设置经过下标为k的顶点
                        (*P)[v][w]=(*P)[v][k];
                    }
                }
            }
        }
    }

    这段代码简洁到就是一个二重循环初始化加一个三重循环权值修正,就完成了所有顶点到所有顶点的最短路径计算。

    由于它的三重循环,因此也是O(n^3)时间复杂度。如果你面临需要求所有顶点至所有顶点的最短路径问题时,弗洛伊德(Floyd)算法应该是不错的选择。. 

    另外,我们虽然对求最短路径的两个算法举例都是无向图,但它们对有向图依然有效,因为二者的差异仅仅是邻接矩阵是否对称而已。

    区分最小生成树和最短路径:前者是“建路”,即把n个结点连通所付出的最小代价;后者是路已存在,求某两个结点的最短路径。

     

    拓扑排序(无环的图的应用)

    在一个表示工程的有向图中,用顶点表示活动,用弧表示活动之间的优先关系,这样的有向图顶点表示活动的网,我们称为AOV网(ActivityON)。AOV网中的弧表示活动之间存在的某种制约关系

    设G=(V,E)是一个具有n个顶点的有向图,V中的顶点序列v1,v2,……,vn,满足若从顶点vi到vj有一条路径,则在顶点序列中顶点vi必在顶点vj之前。则我们称这样的顶点序列为一个拓扑序列

    图7-8-1这样的AOV网的拓扑序列不止一条。序列v0 v1 v2 v3 v4 v5 v6 v7 v8 v9 v10 v11 v12 v13 v14 v15 v16 是一条拓扑序列,而v0 v1 v4 v3 v2 v7 v6 v5 v8 v10 v9 v12 v11 v14 v13 v15 v16也是一条拓扑序列。

    所谓拓扑排序,其实就是对一个有向图构造拓扑序列的过程。构造时会有两个结果,如果此网的全部顶点都被输出,则说明它是不存在环(回路)的AOV网;如果输出顶点数少了,哪怕是少了一个,也说明这个网存在环(回路),不是AOV网

    对AOV网进行拓扑排序的基本思路是:从AOV网中选择一个入度为0的顶点输出,然后删去此顶点,并删除以此顶点为尾的弧,继续重复此步骤,直到输出全部顶点或者AOV网中不存在入度为0的顶点为止

    前面求最小生成树和最短路径时,我们用的都是邻接矩阵,但由于拓扑排序的过程中,需要删除顶点,显然用邻接表会更加方便。因此我们需要为AOV网建立一个邻接表。考虑到算法过程中始终要查找入度为0的顶点,我们在原来顶点表结点结构中,增加一个入度域in

    因此对于图7-8-2的第一幅图AOV网,我们可以得到如第二幅图的邻接表数据结构。

    在拓扑排序算法中,涉及的结构代码如下。

    // 边表结点
    typedef struct EdgeNode{
        // 邻接点域,存储该顶点对应的下标
        int adjvex;
        int weight;
        // 链域,指向下一个邻接点
        struct EdgeNode *next;
    }
    // 顶点表结点
    typedef struct VertexNode{
        // 顶点入度
        int in;
        // 顶点域,存储顶点信息
        int data;
        // 边表头指针
        EdgeNode *firstedge;
    }VertexNode,AdjList[MAXVEX];
    typedef struct{
        AdjList adjList;
        // 图中当前顶点数和边数
        int numVertexes,numEdges;
    }graphAdjList,*GRaphAdjList

    我还需要辅助的数据结构—用来存储处理过程中入度为0的顶点,目的是为了避免每个查找时都要去遍历顶点表找有没有入度为0的顶点

    // 拓扑排序,若GL无回路,则输出拓扑排序序列
    // 并返回OK,若有回路返回ERROR
    Status TopologicalSort(GraphAdjList GL){
        EdgeNode *e;
        int i,k,gettop;
        // 用于栈指针下标
         int top=0;
        // 用于统计输出顶点的个数
        int count=0;
        // 建栈存储入度为0的顶点
        int *stack;
        stack=(int*)malloc(GL->numVertexes *sizeof(int);
        for(i=0;i<GL->numVertexes;i++)
            if(GL->adjList[i].in==0)
                // 将入度为0的顶点入栈
                stack[++top]=i;
        while(top!=0){
            // 出栈
            gettop=stack[top--];
            // 打印此顶点
            printf("%d->",GL->adjList[gettop].data);
           // 统计输出顶点数
            count++;
            // 对此顶点弧表遍历
            for(e=GL->adjList[gettop].firstedge;e;e=e->next){
                k=e->adjvex;
                // 将k号顶点邻接点的入度减1
                if(!(--GL->adjList[k].in))
                    // 若为0则入栈,以便于下次循环输出
                    stack[++top]=k;
            }
        }
        if(count<GL->numVertexes)
            return ERROR;
        else
            return OK;
    }

     

    关键路径

    拓扑排序主要是为解决一个工程能否顺序进行的问题,但有时我们还需要解决工程完成需要的最短时间问题。

    我们如果要对一个流程图获得最短时间,就必须要分析它们的拓扑关系,并且找到当中最关键的流程,这个流程的时间就是最短时间

    在一个表示工程的带权有向图中,用顶点表示事件,用有向边表示活动,用边上的权值表示活动的持续时间,这种有向图的边表示活动的网,我们称之为AOE网(Activity On Edge Network)。我们把AOE网中没有入边的顶点称为始点或源点没有出边的顶点称为终点或汇点。由于一个工程总有一个开始一个结束,所以正常情况下,AOE网只有一个源点一个汇点

    例如图7-9-2就是一个AOE网。其中v0即是源点,表示一个工程的开始,v9是汇点,表示整个工程的结束,顶点v0,v1,……,v9分别表示事件,弧<v0,v1>,<v0,v2>,……,<v8,v9>都表示一个活动,用a0,a1,……,a12表示,它们的值代表着活动持续的时间,比如弧<v0,v1>就是从源点开始的第一个活动a0,它的时间是3个单位。

    既然AOE网是表示工程流程的,所以它就具有明显的工程的特性。如只有在某顶点所代表的事件发生后,从该顶点出发的各活动才能开始。只有在进入某顶点的各活动都已经结束,该顶点所代表的事件才能发生

    AOV网是顶点表示活动的网,它只描述活动之间的制约关系,而AOE网是用边表示活动的网边上的权值表示活动持续的时间,如图7-9-3所示两图的对比。因此,AOE网是要建立在活动之间制约关系没有矛盾的基础之上,再来分析完成整个工程至少需要多少时间,或者为缩短完成工程所需时间,应当加快哪些活动等问题。

    我们把路径上各个活动所持续的时间之和称为路径长度从源点到汇点具有最大长度的路径关键路径,在关键路径上的活动关键活动。显然就图7-9-3的AOE网而言,开始→发动机完成→部件集中到位→组装完成就是关键路径,路径长度为5.5。

    只有缩短关键路径上的关键活动时间才可以减少整个工期长度

    判断关键活动:活动的最早开始时间等于最晚开始时间

    为此,我们需要定义如下几个参数:
    1.事件的最早发生时间etv(earliest time of vertex):即顶点vk的最早发生时间。
    2.事件的最晚发生时间ltv(latest time of vertex):即顶点vk的最晚发生时间,也就是每个顶点对应的事件最晚需要开始的时间,超出此时间将会延误整个工期。
    3.活动的最早开工时间ete(earliest time of edge):即弧ak的最早发生时间。
    4.活动的最晚开工时间lte(latest time of edge):即弧ak的最晚发生时间,也就是不推迟工期的最晚开工时间。

    我们是由1和2可以求得3和4,然后再根据ete[k]是否与lte[k]相等来判断ak是否是关键活动。

    我们将图7-9-2的AOE网转化为邻接表结构如图7-9-4所示,注意与拓扑排序时邻接表结构不同的地方在于,这里弧链表增加了weight域,用来存储弧的权值。

    求事件的最早发生时间etv的过程,就是我们从头至尾找拓扑序列的过程。因此,在求关键路径之前,需要先调用一次拓扑序列算法的代码来计算etv和拓扑序列列表。为此,我们首先在程序开始处声明几个全局变量。

    int *etc,*ltv;    // 事件最早发生时间和最迟发生时间数组
    int *stack2 // 用于存储拓扑序列的栈
    int top2; // 用于stack2的指针
    

    下面是改进过的求拓扑序列算法。

    // 拓扑排序,用于关键路径计算
    Status TopologicalSort(GraphAdjList GL){
        EdgeNode *e;
        int i,k,gettop;
        // 用于栈指针下标
        int top =0;
        // 用于统计输出顶点的个数
        int count=0;
        // 建议将入度为0的顶点入栈
        int *stack;
        stack=(int*) malloc(GL->numVertexes*sizeof(int));
        for(i=0;i<GL->numVertexes;i++)
            if(0==GL->adjList[i].in)
                stack[++top]=i;
            // 初始化为0
        top2=0;
        // 事件最早发生时间
        etv=(int*)malloc(GL->numVertexes *sizeof(int));
        for(i=0;i<GL->numVertexes;i++)
            // 初始化为0
            etv[i]=0;
        // 初始化
        stack2=(int*)malloc(GL->numVertexes * sizeof(int));
        while(top!=0){
            gettop=stack[top--];
            count++;
            // 将弹出的顶点序号压入拓扑序列的栈
            stack2[++top2]=gettop;
            for(e=GL->adjList[gettop].firstedge;e;e=e->next){
                k=e->adjvex;
                if(!(--GL->adjList[k].in))
                    stack[++top]=k;
                // 求各顶点事件最早发生时间值
                if((etv[gettop]+e->weight)>etv[k])
                    etv[k]=etv[gettop]+e->weight;
            }
        }
        if(count<GL->numVertexes)
            return ERROR;
        else
            return OK;
    }

    顶点最早发生时间,即以该顶点为弧头的弧(活动)均已进行完毕时,该顶点才可开始发生,也即代码中的:

                if((etv[gettop]+e->weight)>etv[k])
                    etv[k]=etv[gettop]+e->weight;

    用了“>"符号的原因。

    下面是求关键路径的算法代码:

    // 求关键路径,GL为有向网,输出GL的各项关键活动
    void CriticalPath(GraphAdjList GL){
        EdgeNode *e;
        int i,gettop,k,j;
        // 声明活动最早发生时间和最迟发生时间变量
        int ete,lte;
        // 求拓扑序列,计算数组etv和stack2的值
        TopologicalSort(GL);
        // 事件最晚发生时间
        ltv=(int*)malloc(GL->numVertexes*sizeof(int));
        for(i=0;i<GL->numVertexes;i++)
            // 初始化ltv
            ltv[i]=etv[GL->numVertexes-1];
        // 计算ltv
        while(top2!=0){
            //将拓扑序列出栈,后进先出
            gettop=stack2[top2--];
            for(e=GL->adjList[gettop].firstedge;e;e=e->next){
                // 求各顶点事件的最迟发生时间ltv值
                k=e->adjvex;
                // 求各顶点事件最晚发生时间ltv
                if(ltv[k]- e->weight<ltv[gettop])
                    ltv[gettop]=ltv[k]-e->weight;
            }
        }
        // 求ete,lte和关键活动
        for(j=0;j<GL->numVertexes;j++){
            for(e=GL->adjList[j].firstedge;e;e=e->next){
                k=e->adjvex;
                // 活动最早发生时间
                ete=etv[j];
                // 活动最迟发生时间
                lte=ltv[k]-e->weight;
                // 两者相等即在关键路径上
                if(ete=lte)
                    printf("<v%d,v%d>length:%d,",GL->adjList[j].data,GL->adjList[k].data,e->weight);
            }
        }
    }

    我们在计算ltv时,其实是把拓扑序列倒过来进行的。因此我们可以得出计算顶点vk即求ltv[k]的最晚发生时间的公式是:

    其中S[K]表示所有从顶点vk出发的弧的集合。比如图7-9-8的S[4]就是<v4,v6>和<v4,v7>两条弧,en<vk,vj>是弧<vk,vj>上的权值。

    ete本来是表示活动<vk,vj>的最早开工时间,是针对弧来说的。但只有此弧的弧尾顶点vk的事件发生了,它才可以开始,因此ete=etv[k]

    而lte表示的是活动<vk,vj>的最晚开工时间,但此活动再晚也不能等vj事件发生才开始,而必须要在vj事件之前发生,所以lte=ltv[j]-len<vk,vj>

    所以最终,其实就是判断ete与lte是否相等,相等意味着活动没有任何空闲,是关键活动,否则就不是。

    最终求关键路径算法的时间复杂度依然是O(n+e)

    不过注意,本例是唯一一条关键路径,这并不等于不存在多条关键路径的有向无环图。如果是多条关键路径,则单是提高一条关键路径上的关键活动的速度并不能导致整个工程缩短工期,而必须提高同时在几条关键路径上的活动的速度

     

    总结

    通常稠密图,或读存数据较多,结构修改较少的图,用邻接矩阵要更合适,反之则应该考虑邻接表。

     

    展开全文
  • 大话数据结构--java版

    千次阅读 2019-04-27 10:50:08
    第三章:线性表 https://blog.csdn.net/liuquan0071/article/details/50382885
  • 通过表示为:G(V,E),其中,G表示一个图,V是图G中顶点的集合(有穷非空),E是图G中边的集合(可以为空)图是一种较线性表和树更加复杂的数据结构,在图形结构中,结点之间的关系可以是任意的,图中任意两个数据...
  • 大话数据结构.pdf 下载 大话设计模式.pdf 下载
  • 于是就明白自己基础太薄弱,准备补充计算机科学基础知识。好友Yang推荐我读《大话数据结构》,对于我这种没有学过数据结构的“小白”而言,再合适不过。
  • 数据结构和算法视频教程

    万人学习 2019-06-25 10:51:39
    数据结构、算法视频培训课程,该教程主要是介绍在游戏开发中经常使用的数据结构,例如数组,链表,栈,队列,二叉树,递归等重要知识点讲解以及将它们里灵活的运用到算法里面。
  • 大话数据结构》边读边感

    万次阅读 2016-12-25 15:06:50
    第一章:数据结构绪论 数据结构:是相互之间存在一种或多种特定关系的数据元素的集合。 数据:是描述客观事物的符号,式计算机可以操作的对象,是能被计算机识别,并输入给计算机处理的符号集合。 数据输入有两个...
  • 大话数据结构 源码 code (代码集合)     说明: 前几篇有关数据结构的文章,包含了大话数据结构的全部代码。  有需要大话数据结构全部源码的的请私信,留下邮箱,我会第一时间发送过去。
  • 数据结构课程是计算机类专业的专业基础课程,在IT人才培养中,起着重要的作用。课程按照大学计算机类专业课程大纲的要求,安排教学内容,满足需要系统学习数据结构的人。系列课程包含11个部分,本课为第1部分,介绍...
  • 数据结构基础系列(6):树和二叉树

    万人学习 2018-10-22 21:38:03
    数据结构课程是计算机类专业的专业基础课程,在IT人才培养中,起着重要的作用。课程按照大学计算机类专业课程大纲的要求,安排教学内容,满足需要系统学习数据结构的人。系列课程包含11个部分,本课为第6部分“树和...
  • 数据结构学习书籍

    千次阅读 2018-03-28 09:49:55
    1.《大话数据结构》 2.《数据结构与算法分析--Java语言描述》 3.《数据结构和抽象问题求解--Java语言描述》 4.《算法导论》
  • 数据结构基础系列(2):线性表

    万人学习 2018-10-22 21:38:03
    数据结构课程是计算机类专业的专业基础课程,在IT人才培养中,起着重要的作用。课程按照大学计算机类专业课程大纲的要求,安排教学内容,满足需要系统学习数据结构的人。系列课程包含11个部分,本课为第2部分,...
  • 之前看大话数据结构这本书封面活泼评论也较好,但是读完前三章发现并不太适合自己。K.N.KING的书我比较喜欢。由浅入深,循序渐进,结构清晰,层次分明,课后设计了较多的练习题和编程题,而且都是紧密结合现实问题的...
1 2 3 4 5 ... 20
收藏数 15,155
精华内容 6,062
关键字:

大话数据结构