算法数据结构

数据结构与算法课程

发布日期: 2022-08-23

更新日期: 2023-07-21

文章字数: 12.1k

阅读时长: 51 分

ch6.树

非线性数据结构主要有集中式、分散式、集散式等。树型结构是一类重要的非线性数据结构。

树的递归定义—–>算法递归

at least one base（出口条件）
recursive case（递归情况）：往base case走

6.1 树的定义及基本术语

树的定义：

树是n（n大于等于0）个结点的有限集合。在任意一棵非空树中应满足：

（1）有且仅有一个特定的称为根的结点。

（2）当n大于1时，其余结点可分为m个互不相交的有限集合${T_{1},T_{2},…,T_{m}}$，其中每个集合本身又是一棵树，并且称为根结点的子树。

基本术语：

树的结点包含一个数据元素及若干指向其子树的分支
结点拥有的子树数称为结点的度（degree）
结点的深度（depth）是指从根结点到此结点的长度
结点的高度（height）是指从此结点到最深结点（the deepest leaf）的长度
结点的层次（level）等于父结点的层次+1，基情况国内定义为1，level=depth。
假设有一度为m的树，则称其为m-ary(叉) tree。

【区分】：

树的度（度为m的树）：各结点的度的最大值，任意结点的度小于等于m，至少有一个结点度=m（有m个孩子），且该树至少有m+1个结点。

m叉树：每个结点最多只能有m个孩子的树，允许所有结点的度都小于m，且可以是空树。
二叉树是一种特殊的树形结构，它的树型要么为空（empty），要么存在3个disjoint（不相交）的subsets（子集）【分别为root、左子树、右子树】。在严格二叉树中，若存在$n$个叶子结点（leaves），则存在$2n-1$个总结点数。

二叉排序树：

一个二叉树或是空二叉树，是具有以下性质的二叉树：

左子树上所有结点的关键字均小于根节点的关键字；右子树上所有结点的关键字均大于根节点的关键字。

左子树和右子树又各是一棵二叉排序树。

平衡二叉树：

树上任一结点的左子树和右子树的深度之差不超过1。平衡二叉树是“胖胖的、丰满的树”，能有更高的搜索效率。

6.2 二叉树的性质

二叉树中，结点数=总度数+1
对于任意一棵二叉树T，若其终端结点数为$n_{0}$，度为2的结点数为$n_{2}$，则$n_{0}=n_{2}+1$.
在二叉树的第i层上至多有$2^{i-1}$个结点（n叉则为$n^{i-1}$），深度为k的二叉树至多有$2^{k}-1$个结点。

**[推广]**高度为h的m叉树至多有$\frac{m^{h} - 1}{m - 1}$个结点。（第一层最多m的0次，第二层m的1次，第三层m的2次，进行等比数列求和）

6.3 二叉树的存储结构

6.3.1 顺序存储

法1：用一组地址连续的存储单元依次自上而下、自左至右存储完全二叉树上的结点元素。

#define MaxSize 100
struct TreeNode{
    ElemType value;		//结点中的数据元素
    bool isEmpty;		//结点是否为空
}

定义一个长度为MaxSize的数组t：TreeNode t[MaxSize]，按照从上至下、从左至右的顺序依次存储完全二叉树中的各个结点。初始化时利用循环将所有结点标记为空：t[i].isEmpty=true;

二叉树的顺序存储中，要把二叉树的结点编号与完全二叉树对应起来。最坏情况是：高度为h且只有h个结点的单支树（所有结点只有右孩子），也至少需要$2^{h} - 1$个存储单元。这种顺序存储方式只适合存储完全二叉树。

注：顺序存储结构若需判空，则一般设置一个长度length变量，存储当前存储了多少结点。

法2：定义结点类型，存储数据data和它在完全二叉树中的编号，定义树使用结构体数组。

data	No.

法3：定义结点类型，存储数据data、它双亲的编号以及一个变量LR标记它是左孩子还是右孩子，定义树使用结构体数组。

data	parent	LR(孩子)

6.3.2 链式存储

三叉链表增设parent指针

在n个结点的二叉链表共有n+1个空链域。

[推导]在含有n个结点的二叉链表中，链域一共有2*n个（每个点有两个链域），而除根结点以外，其余结点均有前驱，则有n-1个前驱，即一共有n-1个指针指向某个结点，故在n个结点的二叉链表共有n+1个空链域。（空链域可用于构造线索二叉树）

typedef struct BiTNode
{
    ElemType data;						//数据域
    struct BiTNode *lchild,*rchild;		//左、右孩子指针
}BiTNode,*BiTree;
//定义一棵空树
BiTree root=NULL;
//插入根结点
root= (BiTree)malloc(sizeof(BiTNode));
root->data={1};
root->lchild=NULL;
root->rchild=NULL;
//插入新结点
BiTNode *p= (BiTNode *)malloc(sizeof(BiTNode));
p->data={2};
p->lchild=NULL;
p->rchild=NULL;
root->lchild=p;		//作为根结点的左孩子

6.3.3 静态链表方式存储

6.4 二叉树的遍历

6.4.1 先中后序遍历

根结点集合仅1个元素，以此划分为：

先序遍历：根左右（NLR）中序遍历：左根右（LNR）后序遍历：左右根（LRN）

以先序遍历为例：

非空：访问根，遍历左子树，遍历右子树
为空：返回

void Preorder(BiTNode *bt)
{
   if(bt!=NULL)
   {  
      printf("%d\t",bt->data);
      Preorder(bt->lchild);
      Preorder(bt->rchild);
   }
}

中序遍历的非递归方式：

void Inorder(BiTNode *bt)
{   
    int i=0;
    BiTNode *p,*s[M];
    p=bt;
    do
    {  while(p!=NULL)
       {   s[i++]=p;
           p=p->lchild;
       }
       if(i>0)
       {   p=s[--i];
           printf("%d\t",p->data);
           p=p->rchild;
       }
    }while(i>0||p!=NULL);
}

[注]

若先序与中序的序列相同，则有VLR=LVR，则VR=VR，仅有右子树，没有左子树。下面有各种情况的总结。
已知两种序列（需包括中序序列）可以唯一确定二叉树的形态，根据根的位置先划清界限，然后进行判断即可。

树的深度：后序遍历，取左子树、右子树的最大深度+1。
表达式树（Expression Tree）：用于表示一种树状的数据结构，树上的每一个节点都表示为某种表达式类型，如图：

遍历序列的一些总结：

一、前序序列与后序序列
1.前序序列和后序序列相同—->空树或者只有根节点的二叉树。

2.前序序列和后序序列相反
(1)当且仅当二叉树中只有一个叶子节点。
(2)二叉树的高度和其节点个数相同。

二、前序序列与中序序列
1.前序序列和中序序列相同
空树或缺左子树的单支二叉树。

2.前序序列和中序序列相反
(1)二叉树为空或者只有一个节点。
(2)若二叉树不为空，则任意节点不能同时用于左孩子和右孩子。
(3)若二叉树不为空，则任意节点没有右孩子。

三、中序序列与后序序列
1.中序序列和后序序列相同
空树或者缺右子树的单支二叉树。

2.中序序列和后序序列相反
任意节点没有左孩子节点。

6.4.2 层序遍历

采用先进先出的方式，故采用队列这一数据结构。

==算法模式==：

void PrintLevelOrder(T)
{   
     InitQueue(Q);
     Enqueue(Q,T);				//将根结点入队
     while (!Q.IsEmpty()){
         t = DeQueue(Q); 		//或DeQueue(Q,t);将队首元素出队
         visit(t);				//访问该结点
         if(t->lchild)	 EnQueue(Q,t->lchild);
         if(t->rchild)	 EnQueue(Q,t->rchild);
    }     
}

层序求树的高度，则关键问题是知道每层的最后一个结点（可以通过前层最后一个入队的孩子获取）。

[例]翻转二叉树。

从根节点开始，左右孩子交换，然后递归

public TreeNode invertTree(TreeNode root) {
    if (root==null)return null;
    //从上往下递归交换（左右交换）
    TreeNode plate = root.left;
    root.left = root.right;
    root.right = plate;
    if (root.left!=null)invertTree(root.left);
    if (root.right!=null)invertTree(root.right);
    return root;
}

求树高：

int Hight(Node* root)	// 递归
{
	if(root == null) return 0;
	return max(Hight(root->left),Hight(root->right))+1;
}

6.5 线索二叉树

线索是一种对二叉树的操作，意思是对二叉树进行线索化，其目的是使线索化后的二叉树具有方便被遍历的特点，即不使用递归和栈也可以对线索化之后的树进行中序遍历。

线索指向的是该序的前驱/后继。

BiTNode *zxxsh(BiTNode *bt)
{
   BiTNode *p,*pr,*s[M],*t;
   int i=0;
   t=(BiTNode *)malloc(sizeof(BiTNode));
   t->leftthread=0; t->rightthread=1;   t->rc=t;
   if(bt==NULL)       t->lc=t;
   else
   {  t->lc=bt;  pr=t;   p=bt;
      do{   while(p!=NULL)
	{   s[i++]=p;  p=p->lc; }
	  if(i>0)
	  {   p=s[--i];
	      printf("%c  ",p->data);
	      if(p->lc==NULL)
	      {   p->leftthread=1;  p->lc=pr;}
	      if(pr->rc==NULL)
	      {   pr->rightthread=1; pr->rc=p;}
	      pr=p;    p=p->rc;
	  }
      }while(i>0||p!=NULL);
      pr->rc=t; pr->rightthread=1;  t->rc=pr;
   }
   return t;
}

==在中序线索二叉树中找结点后继的方法==：

（1）若rt=1, 则rc域直接指向其后继

（2）若rt=0, 则结点的后继应是其右子树的左链尾（lt=1)的结点

==在中序线索二叉树中找结点前驱的方法==：

（1）若lt=1, 则lc域直接指向其前驱

（2）若lt=0, 则结点的前驱应是其左子树的右链尾（rt=1)的结点

在线索树上进行遍历，只要先找到序列中的第一个结点，然后一次找结点后继，直至后继为空：

BiTNode PreInThread(P)
{
    if(p->ltag==1)
        return p->lc;
    else{
        q = p->lc;
        while(q->rtag==0){
            q=q->rc;
        }
        return q;
    }
}

下面详细介绍线索二叉树找前驱/后继的方法：

1.中序线索二叉树

中序遍找历中序后继：

左根右

左根 (左根右)

左根 (左根右) 根右)

在中序线索二叉树中找到指定结点*p的中序后继next：

（1）若p->rtag==1，则next=p->rchild；

（2）若p->rtag==0，则p必有有孩子。

//找到以p为根的子树中，第一个被中序遍历的结点
ThreadNode *Firstnode(ThreadNode *p)
{
    //循环找到最左下结点（不一定是叶结点）
    while(p->ltag==0) p=p->lchild;
    return p;
}
//在中序线索二叉树中找到结点p的后继结点
ThreadNode *NextNode(ThreadNode *p)
{
    if(p->rtag==0) return Firstnode(p->rchild);
    else return p->rchild;		//rtag==1直接返回后继线索
}
//对中序线索二叉树进行中序遍历（利用线索实现的非递归算法）
void Inorder(ThreadNode *T)
{
    for(ThreadNode *p=FirstNode(T);p!=NULL;p=NextNode(p))
    	visit(p);
}

2.先序线索二叉树

先序遍历找先序后继：（假设有左孩子）

根左右

根 (根左右) 右

[结论]若p有左孩子，则先序后继为左孩子。

（假设没有左孩子）

根右

根 (根左右)

[结论]若p有右孩子，则先序后继为右孩子。

在中序线索二叉树中找到指定结点*p的先序后继next：

（1）若p->rtag==1，则next=p->rchild

（2）若p->rtag==0，则p必有右孩子。

（仅改用三叉链表或从根开始遍历寻找才能完成）

3.后序线索二叉树

后序遍历找后序前驱：（假设有右孩子）

左右根

左 (左右根) 根

[结论]若p有右孩子，则后序前驱为左孩子。

（假设没有右孩子）

左根

(左右根) 根

[结论]若p没有右孩子，则后序前驱为左孩子。

在中序线索二叉树中找到指定结点*p的后续前驱next：

（1）若p->ltag==1，则next=p->lchild

（2）若p->ltag==0，则p必有左孩子。

6.6 哈夫曼树

编码方式：流水号、前缀码、定长码（fixed-length）、变长码（variable-length）[使用频率高，码长短]。

6.6.1 哈夫曼树的定义及特点

结点的权：有某些现实含义的数值；

结点的带权路径长度(WPL)：从树的根到该结点的路径长度（经过的边数）与该结点上权值的乘积。

在含有n个带权叶结点的二叉树中，带权路径长度(WPL)最小的二叉树称为哈夫曼树，也称最优二叉树。

哈夫曼树的特点：

每个初始结点最终都成为叶结点，且权值越小的结点到根结点的路径长度越大
哈夫曼树有$2n-1$个结点，它是严格二叉树，不存在度为1的结点
哈夫曼树形态不唯一，但WPL必然相同且为最优

6.6.2 哈夫曼算法

给定n个权值分别为$w_{1}, w_{2},…, w_{n}$的结点，构造哈夫曼树的算法（==哈夫曼算法==）描述如下：

给定N个子树，初始化声明集合$F=\left { T_{1},T_{2},……,T_{n} \right } $（仅含根结点且带权值）
从F中选根结点权值最小的两棵树$T_{i},T_{j}$作为左右子树构造一棵新的二叉树S，有：
- $S\rightarrow lc \Leftarrow T_{i}$
- $S\rightarrow rc \Leftarrow T_{j}$
- 新二叉树根结点的权值：$W_{S}=W_{T_{i}}+W_{T_{j}}$
在$F$中删除$T_{i},T_{j}$，同时将新得到的二叉树$S$加入$F$中
重复2-3步，直到$F$中只有一棵子树。

存储结构：**问题规模已知—>==静态链表==**。

typedef struct {
    unsigned int weight;
    unsigned int parent,lc,rc;
}HTNode,*HuffmanTree;			//动态分配数组存储哈夫曼树
typedef char ** HuffmanCode;	//动态分配数组存储哈夫曼编码表

遍历使用“栈”这一数据结构。

6.7 哈夫曼编码

可变长度编码：允许对不同字符用不等长的二进制位表示（使得总编码长度尽量减少）。

前缀编码必须保证任意一个字符的编码都不是另一个字符的编码的前缀，可以利用二叉树来设计二进制的前缀编码。

求哈夫曼编码的算法代码实现如下：

void HuffmanCoding(&HT, &HC, w, n)
{
    if (n <= 1)    return;
    m = 2n - 1;
    HT = (HuffmanTree)malloc((m + 1) * sizeof(HTNode));
    for (p = HT, i = 1; i <= n; ++i, ++p, ++w)
        *p = { *w,0,0,0 };
    for (; i <= m; ++i, ++p) *p = { 0,0,0,0 };
    for (i = n + 1; i <= m; i++) {		//建立哈夫曼树
       //将产生n-1个中间结点
        select(HT, i - 1, s1, s2);		//在HT[1,…,i-1]中选择parent为0且weight最小的两个结点
        HT[s1].parent = i; HT[s2].parent = i;
        HT[i].lc = s1; HT[i].rc = s2;
        HT[i].weight = HT[s1].weight + HT[s2].weight;
    }
    //从叶子到根逆向求每个字符的哈夫曼编码
    HC = (HuffmanCode)malloc((n + 1) * sizeof(char));
    cd = (char*)malloc(n * sizeof(char));
    cd[n - 1] = '\0';
    for (i = 1; i <= n; i++)
    {
        start = n - 1;
        for (c = i, f = HT[i].parent; f != 0; c = f, f = HT[f].parent){
            //从叶子到根逆向求编码，f!=0判断是否到达根节点
            if (HT[f].lc == c) cd[--start] = '0';
            	else cd[--start] = '1';
        }
        HC[i] = (char*)malloc((n - start) * (char));	//为i个字符的编码分配空间
        strcpy(HC[i], &cd[start]);		//从cd复制编码串到HC
    }
    free(cd);
}

6.8 树的存储结构

6.8.1 双亲表示法

箭头向上指，每个结点保存指向双亲的指针。

双亲表示法

6.8.2 孩子表示法

顺序存储各个节点，每个节点中保存孩子的链表头指针

孩子链表 带双亲的孩子链表

存储结构：

data	child1	child2	child3	……	child d

6.8.3 孩子兄弟表示法

存储结构：

data	firstchild	nextSibling

该存储结构便于实现很多树的操作，如易于实现找结点孩子的操作，如访问结点x的第i个孩子，只要先从firstchild域找到第1个孩子，然后沿着nextsibling域连续走i-1步，即可找到x的第i个孩子。

6.9 树的转换与遍历

6.9.1 树与二叉树的转换

将树转换成二叉树：

加线：在兄弟之间加一连线
抹线：对每个结点，除了其左孩子外，去除其与其余孩子之间的关系
旋转：以树的根结点为轴心，将整树顺时针转45°

将二叉树转换成树：

加线：若p结点是双亲结点的左孩子，则将p的右孩子，右孩子的右孩子，……沿分支找到的所有右孩子，都与p的双亲用线连起来
抹线：抹掉原二叉树中双亲与右孩子之间的连线
调整：将结点按层次排列，形成树结构

树与二叉树的转换

6.9.2 树的遍历

先根遍历：先访问树的根结点，然后依次先根遍历根的每棵子树——->对应二叉树的先序遍历
后根遍历：先依次后根遍历每棵子树，然后访问根结点——->对应二叉树的中序遍历
按层次遍历：先访问第一层上的结点，然后依次遍历第二层，……，第n层的结点

6.9.3 树与森林的转换

森林转换成二叉树：

将各棵树分别转换成二叉树
将每棵树的根结点用线相连
以第一棵树根结点为二叉树的根，再以根结点为轴心，顺时针旋转，构成二叉树型结构

二叉树转换成森林：

抹线：将二叉树中根结点与其右孩子连线，及沿右分支搜索到的所有右孩子间连线全部抹掉，使之变成孤立的二叉树
还原：将孤立的二叉树还原成树

ch7.图

7.1 图的相关术语

7.1.1 图的定义

图$G$由顶点集$V$和边集$E$组成，记为$G = (V, E)$，其中$V(G)$表示图$G$中顶点的有限非空集；$E(G)$表示图G中顶点之间的关系（边）集合。若$V = {v_{1}, v_{2}, … , v_{n}}$，则用$|V|$表示图$G$中顶点的个数，也称图$G$的阶，$E = {(u, v) | u∈V, v∈V}$，用$|E|$表示图$G$中边的条数。

若图是有向图，则$<v,w>$表示从$v$到$w$的一条弧，且称$v$为弧尾，$w$为弧头。

在无向图中，顶点的度是指与其相关联的边的数目；

在有向图中，定义：

以顶点v为头的弧的数目称为v的入度(InDegree)，记作ID(v)，

以顶点v为尾的弧的数目称为v的出度(OutDegree)，记作OD(v)。

对于无向图，边的数目$e$的取值是$(0,\frac{1}{2} n(n-1))$（上界即$C_{n}^{2} $），有$\frac{1}{2} n(n-1)$条边的无向图称为完全图。

对于有向图，边的数目$e$的取值是$(0,n(n-1))$（上界即$P_{n}^{2} $，P即Permutation排列），有$n(n-1)$条边的有向图称为有向完全图。

有很少条边的图称为稀疏图(Sparse graph)，反之称为稠密图(Dense graph)。

序列中顶点不重复出现的路径称为简单路径；除了第一个顶点和最后一个顶点之外，其余顶点不重复出现的回路，称为简单回路或简单环(Cycle)。

注：

线性表可以是空表，树可以是空树，但图不可以是空，即V一定是非空集；但图的边集可为空集。

7.1.2 (强)连通图与连通子图

在无向图$G$中，如果从顶点$v$到顶点$v^{‘}$有路径，则称$v$和$v^{‘}$是连通的。

在无向图中，若对于图中任意两个顶点$v_{i}、v_{j}\in V$，$v_{i}、v_{j}$都是连通的，则称**$G$是连通图**。

无向图中的极大连通子图称为连通分量（Connected Component）。（子图必须连通，且包含尽可能多的顶点和边，最小为1，最大为n）

注：

若G是连通图，则最少有n-1条边；

无环连通图是树。

在有向图$G$中，如果对于每一对$v_{i}、v_{j}\in V,v_{i}≠v_{j}$，从$v_{i}$到$v_{j}$和从$v_{j}$到$v_{i}$都存在路径，则称$G$是强连通图。

若G是强连通图，则最少有n条边（形成回路）;

若G是非连通图，则最多有可能有$C_{n-1}^{2}$条边（抛开最后一个顶点，其余的连满）。

有向图中的极大强连通子图称为强连通分量。（子图必须连通，且保留尽可能多的边）

设有两个图$G=(V,E)$和$G’=(V’,E’)$，若$V’$是$V$的子集，且$E’$是$E$的子集，则称$G’$是$G$的子图。

若有满足$V(G’)=V(G)$的子图$G’$,则称其为$G$的生成子图。

连通图的生成树是包含图中全部顶点的一个极小连通子图。（边尽可能地少，但要保持连通）

边上带有权值的图称为带权图，也称网。

7.2 图的存储

图的存储方式很多，主要介绍以下几种方法：

邻接矩阵（稠密图）
邻接表（稀疏图）
邻接多重表（无向图）
十字链表（有向图）

除了上述方法外，还有用序偶来表示（共有$|V|$条序偶，插删、查找不方便，适用于稀疏图）等：

$v_{i}$	$v_{j}$
……	……

7.2.1 邻接矩阵法

typedef struct {
    VertexType vexs[MAX_VERTEX_NUM]; 				//顶点向量
    int arcs[MAX_VERTEX_NUM][MAX_VERTEX_NUM]; 		//邻接矩阵边表
    int vexnum, arcnum; 							//图当前顶点数和弧数
    GraphKind kind; 
}MGraph;

邻接矩阵的行为出边邻接点（弧尾），列为入边邻接点（弧头）。

无向图：第i个结点的度=第i行（或第i列）的非零元素个数。

有向图：第i个结点的出度=第i行的非零元素个数；

第i个结点的入度=第i列的非零元素个数；

第i个结点的度=第i行、第i列的非零元素个数之和。

空间复杂度：$O\left( \left| n \right|^{2} \right)$,适合存储稠密图。

无向图的邻接矩阵是对称矩阵，可以压缩存储（只存储上三角区/下三角区）。

$A^{n}$的元素$A^{n}[i][j]$等于由顶点i到顶点j的长度为n的路径的数目。

Status CreateVDN(MGraph &g){
	int i,j,k;
  	float w;
 	scanf("%d%d",&g.vernum,&g.arcnum);
 	for(i=0;i<g.vernum;i++)      g.vex[i]=getchar();
  	for(i=0;i<g.vernum;i++)
    	for(j=0;j<g.vernum;j++)
     	  g.arcs[i][j]={INFINITY,NULL};
    for(k=0;k<g.arcnum;++k)
    {
        scanf("%d%d%f",&i,&j,&w);
        g.arcs[i][j]=w;
        g.arcs[j][i]=w;
    }
    return ok;
}

7.2.2 邻接表

带权则加一个域表示权值。对于有向图，分为入边表和出边表。

#define MAX_VERTEX_NUM 20
typedef struct ArcNode{
  int adjvex; 
  struct ArcNode *nextarc; 	//指向下一条弧的指针
} ArcNode;
typedef struct VNode{
  VertexType data; 
  ArcNode *firstarc; 		//指向第一条依附该顶点的弧的指针
} VNode, AdjList[MAX_VERTEX_NUM];
typedef struct {
  AdjList vertices;
  int vernum, arcnum; 
  int kind;
} ALGraph;
//得到图的邻接表
VNode *creat_ALgraph(int e)
{
    int i,k,j;
     VNode *G;
     ArcNode *p;
     scanf(“%d%d”,&g.vernum,&g.arcnum); 
     G=(VNode *)malloc(g.vernum*sizeof(VNode));
     printf("Input vertex:\n");
     for (i=0;i<g.vernum;++i)
     { 
         scanf("%c",&G[i].data);
     	 G[i].firstarc=NULL;
     }
	 for(k=0;k<g.arcnum;k++)
     { 
         printf("Input the i,j\n"); 
         scanf("%d%d",&i,&j);
         p=(ArcNode *)malloc(sizeof(ArcNode));
         p->adjvex=j;
         p->nextarc=G[i].firstarc;
         G[i].firstarc=p;
         p=(ArcNode *)malloc(sizeof(ArcNode));
         p->adjvex=i;
         p->nextarc=G[j].firstarc;
         G[j].firstarc=p;
     }
    return G;
}

无向图边结点的数量是$2|E|$（$E$表示边，$2|E|$即表示存在冗余存储）；

有向图的空间复杂度为$O\left( \left| V \right|+\left| E \right|\right)$。

7.2.3 邻接多重表

无向图的存储可以使用邻接表，但在实际使用时，如果想对图中某顶点进行实操（修改或删除），由于邻接表中存储该顶点的节点有两个，因此需要操作两个节点。为了提高在无向图中操作顶点的效率，引入适用于存储无向图的方法——邻接多重表。

7.2.4 十字链表

用于存储有向图，其存储的空间复杂度为$O\left( \left| V \right|+\left| E \right|\right)$.

边结点的结构：

mark	tailvex	headvex	tlink	hlink
/	尾域指示弧尾顶点的位置	头域指示弧头顶点的位置	链域指向弧尾相同的下一条弧	链域指向弧头相同的下一条弧

顶点结点的结构：

data	Firstin	Firstout
/	以该顶点为弧头的第一个弧结点	以该顶点为弧尾的第一个弧结点

存储结构通过定义边结点和顶点结点，然后定义十字链表下的图结构即可。

7.3 图的遍历

7.3.1 广度优先遍历(BFS)

广度优先遍历类似于树的按层序遍历的过程。其要点如下：

（1）找到与一个顶点相邻的所有顶点；（2）标记哪些顶点被访问过；（3）需要一个辅助队列visited[M]。

邻接矩阵实现：

void BFS(g,k,visited)
{
    // using adjmatrix,采用的方式为非递归遍历图g,需要采用辅助队列和访问标志数组visited
    setnull(Q);
    Enqueue(q,k);   
    while (!empty(q)) {		//队列不为空
        i=dequeue(q); 
        printf("%c\n",g.vexs[i]);
        visited[i]=true; 
        for (j=0;j<n;j++){
            if ((g.arcs[i][j]==1) && (!visited[j])) 
            {
                //(i,j)->T,T代表的是图的广度优先生成树
                Enqueue(q,j);
            }
        }
	}
}
void Traverse(g[],n)
{
    int i;
    static int visited[M];
    for(i=1;i<=n;i++){
        visited[i] = 0;
    }
    for(i=1;i<=n;i++){
        if(visited[i]==0)
        {
            //count++;  记录连通分量的数量
            BFS(g,i,visited);
        }
    }
}

邻接表实现：

#include<iostream>
#include<queue>
using namespace std;
#define NUMBER_VERTEX 5
//边节点定义
typedef struct edgenode{
	int index;
	edgenode *nextEdge;
}edgeNode ,*peNode;
//顶点节点定义
typedef struct vertexnode
{
	char data;
	edgeNode *firstEdge;
}vertexNode;
//邻接表定义
// typedef struct adjTable
// {
// 	vertexNode adjGraph[NUMBER_VERTEX]; 
//  int vertexNumber;
//  int edgeNumber;
// };
//定义一个是否已经访问过的标志数组,0表示没访问过
int visited[NUMBER_VERTEX]={0};  //这里为了简化结构写成全局变量，也可把他作为结构体的一部分；
//清空标志位visited;
void clearflag(void){
	for(int i=0;i<NUMBER_VERTEX;i++){
		visited[i]=0;
	}
}
//访问某个图的几号顶点
void visit(vertexNode *pVertex,int index){
	cout<<(pVertex+index)->data;
	visited[index]=1;
}
//连通图的广度优先搜索
void bfs_connect(vertexNode *pVertex,int index){
	visit(pVertex,index);
	//访问入口顶点
	queue<int> q; //存储顶点的编号
	q.push(index);
	while(!q.empty()){
		int cur = q.front();
		q.pop();
		//查找所有cur顶点的未被访问的邻接点
		peNode temp = (pVertex+cur)->firstEdge;
		while(temp!=NULL){
			int num_nextedge = temp->index;
			if(visited[num_nextedge]==0){
				visit(pVertex,num_nextedge);
				q.push(num_nextedge);
			}
			temp = temp->nextEdge;
		}
	}
}
//整个图的广度优先搜索
void bfs(vertexNode *pVertex,int index){
	bfs_connect(pVertex,index);
	// 遍历每一个连通分量
	for(int i=0;i<NUMBER_VERTEX;i++){
		if(visited[i]==0){
			bfs_connect(pVertex,i);
		}
	}
}

邻接矩阵存储的图：

访问$\left| V \right|$个顶点需要$O\left( \middle| V \middle| \right)$的时间。查找每个顶点的邻接点都需要$O\left( \middle| V \middle| \right)$的时间，而总共有$\left| V \right|$个顶点，其时间复杂度=$O\left( \left| V \right|^{2} \right)$。

邻接表存储的图：

【注】其实对于无向图来说，查找每个顶点的邻接点都需要$O\left( 2\middle| E \middle| \right)$的时间。

7.3.2 深度优先遍历(DFS)

基本思路：采用递归算法。

从图中某个顶点出发，访问此顶点，然后依次从其未被访问的邻接点出发深度优先遍历图，直至所有与其有路径相同的顶点都被访问到；若此时图中尚有顶点未被访问，则另选图中一个未被访问的顶点作为起始点，重复以上过程，直至图中所有顶点都被访问到为止。

depthFirstSearch(v)
{
   Label vertex v as reached
   for (each unreached vertex u adjacent from v)
      depthFirstSearch(u);
}

代码如下：

Boolean visited[MAX]; 
Status (* VisitFunc)(int v); 
//dfs using adjmatrix
void dfs(i)
{
   //count++;  记录连通分量的数量
   printf("node:%c\n",g.vexs[i]);
   visited[i]= TRUE;
   for (j=0;j<n;j++)
   {
       if ((g.arcs[i][j]==1) && (!visited[j]))
       {
           //(i,j)->T,T代表的是图的深度优先生成树
           dfs(j);
       }
   }
}

//dfs using adjlist
void dfs(i)
{
    printf("node:%c\t",gl[i].vertex);
    visited[i]=1;
    p=gl[i].link;
    while (p!=NULL)  
    {
        if (!visited[p->adjvex])
            dfs(p->adjvex);
        p=p->next;//找下一邻接点
    }
}

复杂度分析：

空间复杂度：来自函数调用栈，最坏情况，递归深度为$O\left( \middle| V \middle| \right)$.

时间复杂度与BFS是一样的，主要取决于使用哪种数据结构来存储图：

邻接矩阵存储的图：

邻接表存储的图：

7.4 最小生成树

对于带权连通无向图 $G=(V,E)$，生成树不同，每棵树的权（即树中所有边上的权值之和）也可能不同。设$R$为$G$的所有生成树的集合，若 $T$ 为 $R$ 中边的权值之和最小的生成树，则 $T$ 称为 $G$ 的最小生成树（MST）。

生成树的一些概念：

深度优先生成树与广度优先生成树（前面一节有讲怎么构成）

生成森林：非连通图每个连通分量的生成树一起组成非连通图的集合叫做生成森林。

[说明]

一个图可以有许多棵不同的生成树，所有生成树具有以下共同特点：

生成树的顶点个数与图的顶点个数相同

生成树是图的极小连通子图

一个有 $n$ 个顶点的连通图的生成树有 $n-1$ 条边

生成树中任意两个顶点间的路径是唯一的

在生成树中再加一条边必然形成回路

含 $n$ 个顶点 $n-1$ 条边的图不一定是生成树

最小生成树有以下重要性质：==[注意红、蓝、紫的颜色标记]==

假设$(u,v)$具有最小权，其中$u\in U[red],v\in V-U[blue]$，则必定$\exists MST; contains; (u,v)[purple]$。

下面的算法将用到这一性质。

7.4.1 Prim算法

从某一个顶点开始构建生成树；每次将代价最小的新顶点纳入生成树，直到所有顶点都纳入为止。算法的步骤如下：

Step 1: $x\in V$, $Let;A = {x}, B = V - {x}$
Step 2: Select $(u, v)\in E$, $u\in A, v\in B$ such that $(u, v)$ has the smallest weight between A and B
Step 3: $(u, v)$ is in the tree. $A = A\cup {v}, B = B - {v}$
Step 4: If $B =\varnothing$, stop; otherwise, go to Step 2.

其时间复杂度为$O\left( n^{2} \right)$（其中$n=\left| V \right|$），适合用于边稠密图。

Red、Blue点可用以下方式标记：

Color Mark O(n)
set 集合 O(n)
BitString 位串

代码实现：

有两个需要注意的变量：

lowcost[v]
adjvex[v]记录是哪里来的结点

typedef struct {
    VertexType adjvex;
    VRType lowcost;
}closedge[MAX_VERTEX_NUM];

//USING Matrix
//closedge[k].lowcost=0 	//red point notation
void MiniSpanTree_Prim(MGraph G, VertexType u) {
    k = LocateVex(G, u);								//u为开始结点
    for (j = 0; j < G.vexnum; ++j)
        if (j != k)
            closedge[j] = { u, G.arcs[k][j].adj };
    closedge[k].lowcost = 0; 						// U＝{u}
    for (i = 0; i < G.vexnum; ++i) {
        k = Minimum(closedge);						//求出下一个结点
        printf(closedge[k].adjvex, G.vexs[k]);		//求出生成树的边
        closedge[k].lowcost = 0; 					//加入red point set
        for (j = 0; j < G.vexnum; ++j) {
            if (G.arcs[k][j].adj < closedge[j].lowcost && closedge[j].lowcost != 0)
                //新节点并入后重新表示蓝点的最短路径
                closedge[j] = { G.vexs[k], G.arcs[k][j].adj };
        }
    }
}

7.4.2 Kruskal算法

每次选择一条权值最小的边，使这条边的两头连通（原先已经连通的就不选），直到所有结点都连通。

在这个算法中需要关注的问题是：

一个点能否遍历到另一个点
两端点是否在连通分量（集合）中（该算法使用）——->避圈法

在该算法中运用到的是并查集（Union-Find Set，存在查找集合和合并集合），并查集使用树的双亲表示法。

作为“双亲”，初始双亲指向自己；双亲可以直接指向根（通过经历的边寻找），并即是一个树的根=另一个树的根（双亲）。

在算法中，当n-1条边全部进入生成树中时则结束。算法的时间复杂度为 $O\left( \left| E \right|{log}\left| V \right| \right)$，适合用于边稀疏图。

7.5 最短路径(SP)问题

7.5.1 BFS算法

只适用于不带权图。

#define infinity 1000000
//求顶点u到其他顶点的最短路径
void BFS_MIN_Distance(Graph G, int u)
{
	//d[i]表示从u到i结点的最短路径
	for (int i = 0;i < G.vexnum;i++)
	{
		//d[i]表示从u到i结点的最短路径
		for (i = 0;i < G.vexnum;i++)
		{
			d[i] = infinity;	//初始化路径长度
			path[i] = -1;		//最短路径从哪个顶点过来
		}
		d[u] = 0;
		visited[u] = TRUE;
		EnQueue(Q, u);
		while (!isEmpty(Q))		//BFS算法主过程
		{
			DeQueue(Q, u);		//队头元素出队
			for (w = FirstNeighbor(G, u);w > 0;w = NextNeighbor(G, u, w))
			{
				if (!visited[w])		//w为u的尚未访问的邻接顶点
				{
					d[w] = d[u] + 1;	//路径长度加1
					path[w] = u;		//最短路径应从u到w
					visited[w] = TRUE;  //设为已访问标记
					EnQueue(Q, w);		//顶点w入队
				}
			}
		}
	}
}

7.5.2 Dijkstra算法

算法求单个源点到其余各顶点的最短路径，计算思路是离源点最低路径长度的开序。——贪心算法（每次取离源点最近的点）

设C数组为蓝点集，起点为红点。当红点集合加入值时，关联的蓝点将更新SP[对比Prim算法，更新的判断式子不同]。执行以下操作：

//arcs[i,j]: the weight along path from i to j.  
//Dist[k]: length of the shortest special path from source to k.
//j in C : 	shortest path from source to j is not known. 
//k in S : shortest path from source to k is known.
Dijkstra (arcs[1…n, 1…n]) : array [2…n] 
array Dist [2…n]
C <- {2,3,…,n}
for i <- 2 to n do Dist[i] <- arcs[1,i] 
repeat n - 2 times 
     v <- some element of C minimizing Dist[v] 
     C <- C \ {v} 
     for each w in C do 
   		Dist[w] <- min (Dist[w] , Dist[v] + arcs[v,w])
return Dist

算法实现代码如下：

void Shortpath(cost,v0,dist)  //cost数组记录邻接点的带权长度
{
    for (i=0;i<n;i++)
    { 
        dist[i] = cost[v0][i];
     	s[i] = 0;			 //设为蓝点
        p[i] = 0;
    }
    s[v0]=1;				 //将起始顶点设为红点
    do {
        wm = Maxint;		 //初值设为无穷大,该变量记录当前比较的最短路径
        u = v0;
        for (i=0;i<n;i++)
            if (s[i]==0)	 //是蓝点
                if (dist[i]) < wm)
                {
                    u= i;
                    wm = dist[i];
                };
        s[u]=1;				//将u设为红点
        for (i=0;i<n;i++){
            //更新蓝点的最短路径
            if (s[i]==0)
                if (dist[u] + cost[u][i] < dist[i])
                {
                    dist[i] = dist[u]+cost[u][i];
        			p[i] = u;			//用p数组记录经过的红点
                }
        }
		num++;
    } while(num != n-1);
}

path数组可以通过记录经过的红点，可以读取源点0到终点v的最短路径。以下表中的顶点4为例：

path[4] = 2 → path[2] = 3 →path[3] = 0，反过来排列，得到路径0, 3, 2, 4，这就是源点0到终点4的最短路径。

Dijkstra算法中各辅助数组的变化：

Dijkstra算法的时间复杂度：

对于邻接矩阵表示，为$O\left( n^{2} \right)$（其中$n=\left| V \right|$）；
对于邻接表表示，为$O\left( n+|E|\right)$（其中$n=\left| V \right|$，$|E|$为边数[结点的度的加和]）。

注：

若要用Dijkstra算法求每一对顶点之间的最短路径，则再加入一个for循环即可，算法的时间复杂度为$O\left( n^{3} \right)$；

当图中含负权边时算法不一定获得正确结果。

7.5.3 Floyd算法

Floyd算法求每一对顶点之间的最短路径的时间复杂度也为$O\left( n^{3} \right)$，但算法形式比Dijkstra算法要简单。

Floyd算法是在研究传递闭包问题时设计的。

求出每一对顶点之间的最短路径。使用动态规划思想：

将顶点的集合设为n个点序列，k从起始位置到结束位置依次遍历，计算Dist[i,j]=min(Dist[i,j],Dist[i,k]+Dist[k,j])。

void ShortestPath_FLOYD(MGraph G,PathMatrix &path,DistancMatrix &d)
{
    for ( int i = 0; i < n; i++ )
        for ( int j = 0; j < n; j++ ) {
            d[i][j] = G.arcs[i][j];			//将初始邻接矩阵的距离赋值给d数组
            if ( i <> j && d[i][j] < MAXINT ) 
                path[i][j] = i;	    		// i到j有路径,记录经过的红点(该怎么走)	
            else path[i][j] = 0;			// i到j无路径	
        }
    for ( int k = 0; k < n; k++ )
        for ( i = 0; i < n; i++ )
            for ( j = 0; j < n; j++ )
                if ( d[i][k] + d[k][j] < d[i][j] ) { 		//下图矩阵的第k行第k列
                    d[i][j] = d[i][k] + d[k][j];
                    path[i][j] = path[k][j];
                }      						//缩短路径长度, 绕过k到j 
    }    
}

对于a[1][0] = 11, path数组有：path[1][0] = 2，path[1][2] = 3，path [1][3] = 1，则：

最短路径为：vertex 0 <- vertex 2 <- vertex 3 <- vertex 1，即**<1, 3>,<3, 2>,<2, 0>**。

Floyd算法的时间复杂度为$O\left( \left| V \right|^{3} \right)$，空间复杂度为$O\left( \left| V \right|^{2} \right)$。其可以用于“负权值”的图，但不能解决带有“负回路“的图（有负权值的边组成回路），这种图有可能没有最短路径。

7.6 AOV网与拓扑排序

7.6.1 基本概念

若一个有向图中不存在环，则称为有向无环图，简称DAG图（Directed Acyclic Graph）。

可以用有向图表示一个工程。在这种有向图中，用顶点表示活动，用有向边$<V_{i},V_{j}>$表示活动$V_{i}$必须先于活动$V_{j}$进行。这种有向图叫做顶点表示活动的AOV网络 （Activity On Vertices）。

拓扑排序是由某个集合上的一个偏序得到该集合上的一个线序（全序）的排序。

一个DAG的拓扑序列通常表示某种方案切实可行
一个DAG可能有多个拓扑序列

注：

[1]线序意即：要么xRy，要么yRx。

[2]在图论中，由一个有向无环图的顶点组成的序列，当且仅当满足下列条件时，称为该图的一个拓扑排序：

每个顶点出现且只出现一次；

若顶点A在序列中排在顶点B的前面，则在图中不存在从顶点B到顶点A的路径。

7.6.2 拓扑排序的实现

（1）从AOV网中选择一个没有前驱（入度为0）的顶点并输出；

（2）从网中删除该顶点和所有以它为尾的弧；

（3）重复（1）和（2）直到当前的AOV网为空或当前网中不存在无前驱的顶点为止（即有向图中存在环）。

入度可以同通过在邻接表的表头结点增加一个ID域，记录入度，或创建一个ID数组。

为了避免重复检测入度为0的顶点，可用栈暂存所有入度为0的顶点（也可以使用队列）。栈的构造方式可以是独立的辅助栈，表示如后面的图所示，也可以是ID域栈（静态链栈）。方法是：

设一个栈顶位置的指针，将所有未处理过的入度为0的结点连接起来，形成一个链栈；栈初始化时将top指针赋为-1，表示该栈为空栈。

将顶点i进栈时，使用头插法，执行以下指针的修改：

//id相当于后继next,将入度为0的顶点链起来
dig[i].id = top;
top = i;

退栈操作，使用头删法，可以写成：

//位于栈顶的顶点位置记于j,top退到次栈顶
j = top;
top = dig[i].id;

使用Queue暂存的排序方式称为广度拓扑排序，使用Stack暂存的排序方式称为深度拓扑排序。

独立的辅助栈表示如下：

==静态链栈的代码实现==如下：

typedef int datatype;
typedef int vextype;
typedef  struct  node
{
    int  adjvex;
    struct node* next;
} edgenode;
typedef  struct {
    vextype  vertex;
    int id;
    edgenode* link;
} vexnode;
vexnode  dig[n];		// Directed Graph(有向图)

void Topsort(dig)
{
    top = -1;
    for (i = 0; i < n; i++){
        if (dig[i].id == 0)
        {
            dig[i].id = top;
            top = i;
        }
    }
    while (top != -1)
    {
        j = top;				// 出栈,接下来对其有关的顶点入度进行操作
        top = dig[top].id;		 // 栈顶指针指向次栈顶的顶点
        printf("%d\t",dig[j].vertex);
        count ++;				// 代表有多少顶点进行了拓扑排序,对输出顶点进行计数
        p = dig[j].link;
        while (p)
        {
            k = p->adjvex;		// 邻接点的数字信息
            dig[k].id --;
            if (dig[k].id == 0)
            {
                dig[k].id = top;
                top = k;
            }
            p = p->next;		// 对下一个邻接点进行操作
        }	// while p
    }  		// while top
    if (count < n)  printf("has a cycle!\n");		// 该有向图有回路
}

其时间复杂度为$O\left( \left| V \right| + \left| E \right| \right)$；若采用邻接矩阵，则需$O\left( \left| V \right|^{2} \right)$。

*7.6.3 逆拓扑排序的实现

利用DFS算法实现，在顶点退栈前输出。

void DFSTraverse(Graph G)		// 对图G进行深度优先遍历
{
    for(v=0;v<G.vexnum;v++)
    {
        visited[v]=FALSE;		// 初始化已访问标记数据
	}
    for(v=0;v<G.vexnum;v++)
    {
        if(!visited[v])
            DFS(G,v);
    }
}
void DFS(Graph G,int v)
{
    // 从顶点v出发，深度优先遍历图G
    visited[v]=TRUE;			// 设已访问标记
    for(w=FirstNeighbor(G,v);w>=0;x=NextNeighbor(G,v,w))
    {
        if(!visited[w])			// w为u的尚未访问的邻接顶点
            DFS(G,w);
    }
    print(v);					// 输出顶点
}

7.7 AOE网与关键路径

7.7.1 AOE网

在带权有向图中，以顶点表示事件，以有向边表示活动，以边上的权值表示完成该活动的开销（如完成活动所需的时间），称之为用边表示活动的网络，简称AOE网（Activity On Edge NetWork）。

AOE网具有以下两个性质：

（1）只有在某顶点所代表的事件发生后，从该顶点出发的各有向边所代表的活动才能开始；

（2）只有在进入某顶点的各有向边所代表的活动都已结束时，该顶点所代表的事件才能发生。

另外，有些活动可以并行进行。

在AOE网中仅有一个入度为0的顶点，称为开始顶点（源点），它表示整个工程的开始；

也仅有一个出度为0的顶点，称为结束顶点（汇点），它表示整个工程的结束。

7.7.2 关键路径概述

定义：从源点到汇点的有向路径可能有多条，所有路径中，具有最大路径长度的路径称为关键路径，而把关键路径上的活动称为关键活动。

完成整个工程的最短时间就是关键路径的长度。若关键活动不能按时完成，则整个工程的完成时间就会延长。

事件$v_{k}$的最早发生时间ve(k)——假设开始点是$v_{1}$，则从$v_{1}$到$v_{i}$的最长路径长度称为其最早开始时间，决定了所有从$v_{k}$开始的活动能够开工的最早时间
活动$a_{i}$的最早开始时间e(i)——指该活动弧的起点所表示的事件的最早发⽣时间
事件$v_{k}$的最迟发生时间vl(k)——它是指在不推迟整个工程完成的前提下，该事件最迟必须发⽣的时间
活动$a_{i}$的最迟开始时间l(i)——它是指该活动弧的终点所表示事件的最迟发生时间与该活动所需时间之差
活动$a_{i}$的时间余量d(i)=l(i)-e(i)，表示在不增加完成整个⼯程所需总时间的情况下，活动$a_{i}$可以拖延的时间

若⼀个活动的时间余量为零，则说明该活动必须要如期完成，d(i)=0即==l(i) = e(i)的活动是关键活动==；关键活动确定后，路径上的获得都是关键活动的路径就是关键路径。

7.7.3 求关键路径

求Ve(i)：事件的最早发生时间——==拓扑排序==可以得到

$v_{e}(k)=\left{\begin{array}{ll}
0 & (k=1) \
\max \left{v_{e}(j)+weight\left(<v_{j}, v_{k}>\right}\right. & \left(<v_{j}, v_{k}>\in p(k))\right.
\end{array}\right.$

其中$p(k)$表示所有到达$v_{k}$的有向边的集合，$weight(<v_{j},v_{k}>)$为有向边$<v_{j},v_{k}>$上的权值。

求Vl(j)：事件的最迟发生时间——==逆拓扑排序==可以得到

$v_{l}(k)=\left{\begin{array}{ll}
v_{e}(n) & (k=n) \
\min \left{v_{l}(j)-weight\left(<v_{k}, v_{j}>\right}\right. & \left(<v_{k}, v_{k}>\in s(k))\right.
\end{array}\right.$

其中$s(k)$为所有从$v(k)$发出的有向边的集合。

**求e(i)**：活动的最早开始时间

若活动$a_{i}$是由弧$<v_{k},v_{j}>$表示的，则只有事件$v_{k}$发生了，活动$a_{i}$才能开始，则活动$a_{i}$的最早开始时间应等于事件$v_{k}$的最早开始时间，即：$e(i)=v_{e}(k)$。

**求l(i)**：活动的最迟开始时间

活动$a_{i}$的最晚开始时间是指在不推迟整个工程完成日期的前提下，必须开始的最晚时间。若由弧$<v_{k},v_{j}>$表示，则$a_{i}$的最晚开始时间要保证事件$v_{j}$的最迟发生时间不拖后，则有：$l(i)=v_{l}(j)-weight(<v_{k},v_{j}>)$。

计算l(i)-e(i)

l(i)-e(i)称为活动的时间余量；若$l(i) = e(i)$，则该活动为关键活动。

关键路径代码求解如下：

void CriticalPath() {
    //在此算法中需要对邻接表中单链表的结点加以修改, 在各结点中增加一个int域cost, 记录该结点所表示的边上的权值。
    for (i = 0; i < n; i++) Ve[i] = 0;
    for (i = 0; i < n; i++) {
        p = NodeTable[i].firstadj;
        while (p != NULL) {
            k = p->adjvex;
            if (Ve[i] + p->cost > Ve[k])
                Ve[k] = Ve[i] + p->cost;
            p = p->nextadj;
        }
    }
    for (i = 0; i < n; i++)
        Vl[i] = Ve[n - 1];
    for (i = n - 2; i; i--) {
        p = NodeTable[i].firstadj;
        while (p != NULL) {
            k = p->adjvex;
            if (Vl[k] - p->cost < Vl[i])
                Vl[i] = Vl[k] - p->cost;
            p = p->nextadj;
        }
    }
    for (i = 0; i < n; i++) {
        p = NodeTable[i].adj;
        while (p != NULL) {
            k = p->adjvex;
            e = Ve[i];  l = Vl[k] - p->cost;
            if (l == e)			//输出<i, k>是关键活动
            	p = p->link;
        }
    }
}

在拓扑排序求Ve(i)和逆拓扑有序求Vl(i)时, 所需时间为$O(n+e)$, 求各个活动的e(k)和l(k)时所需时间为$O(e)$, 则算法的时间复杂度仍然是$O(n+e)$。

ShiQuLiZhi

https://www.qqzzss.top/2022/08/23/ds-algorithm/shu-ju-jie-gou-02-shu-ju-jie-gou-2/

本博客所有文章除特别声明外，均采用 CC BY 4.0 许可协议。转载请注明来源 ShiQuLiZhi !

算法数据结构

数据结构3:查找与排序

2022-08-23 数据结构与算法课程

算法数据结构

数据结构1:线性表,栈,队列,字符串,广义表,数组

2022-08-23 数据结构与算法课程

算法数据结构

数据结构2:树与图

ch6.树

6.1 树的定义及基本术语

6.2 二叉树的性质

6.3 二叉树的存储结构

6.3.1 顺序存储

6.3.2 链式存储

6.3.3 静态链表方式存储

6.4 二叉树的遍历

6.4.1 先中后序遍历

6.4.2 层序遍历

6.5 线索二叉树

6.6 哈夫曼树

6.6.1 哈夫曼树的定义及特点

6.6.2 哈夫曼算法

6.7 哈夫曼编码

6.8 树的存储结构

6.8.1 双亲表示法

6.8.2 孩子表示法

6.8.3 孩子兄弟表示法

6.9 树的转换与遍历

6.9.1 树与二叉树的转换

6.9.2 树的遍历

6.9.3 树与森林的转换

ch7.图

7.1 图的相关术语

7.1.1 图的定义

7.1.2 (强)连通图与连通子图

7.2 图的存储

7.2.1 邻接矩阵法

7.2.2 邻接表

7.2.3 邻接多重表

7.2.4 十字链表

7.3 图的遍历

7.3.1 广度优先遍历(BFS)

7.3.2 深度优先遍历(DFS)

7.4 最小生成树

7.4.1 Prim算法

7.4.2 Kruskal算法

7.5 最短路径(SP)问题

7.5.1 BFS算法

7.5.2 Dijkstra算法

7.5.3 Floyd算法

7.6 AOV网与拓扑排序

7.6.1 基本概念

7.6.2 拓扑排序的实现

*7.6.3 逆拓扑排序的实现

7.7 AOE网与关键路径

7.7.1 AOE网

7.7.2 关键路径概述

7.7.3 求关键路径