目录

第五章、树和二叉树

1. 树和二叉树的定义

1.1. 树的基本术语

1.2. 二叉树的定义

2. 二叉树的性质

2.1. 案例引入

2.2. 二叉树的相关公式

2.3. 完全二叉树的性质

3. 二叉树的存储结构

3.1. 顺序存储结构

3.2. 链式存储结构

4. 遍历二叉树

4.1. 先中后序遍历

4.2. 层序遍历

4.3. 遍历算法的应用

5. 线索二叉树

6. 树的存储结构

6.1. 双亲表示法

6.2. 孩子链表表示法

6.3. 孩子兄弟表示法

7. 树和森林

7.1. 树与二叉树的转换

7.2. 森林与二叉树的转换

7.3. 树和森林的遍历

8. 哈夫曼树及其应用

8.1. 哈夫曼树的概念

8.2. 构造哈夫曼树

8.3. 哈夫曼算法

8.4. 哈夫曼编码

第六章、图

1. 图的定义和术语

2. 图的存储结构

2.1. 邻接矩阵

2.2. 邻接表

2.3. 十字链表

2.4. 邻接多重表

3. 图的遍历

3.1. 深度优先遍历(DFS)

3.2. 广度优先遍历(BFS)

4. 图的应用

4.1. 生成树

4.2. 最小生成树

4.3. 最短路径

4.4. 拓扑排序

4.5. 关键路径

第五章、树和二叉树

回顾——数据的逻辑结构

线性结构：

• 线性表。
• 栈、队列（栈和队列都是操作受限的线性结构）。
• 字符串、数组、广义表。

非线性结构：

• 树型结构。
• 图型结构。

1. 树和二叉树的定义

1.1. 树的基本术语

树的深度(高度)：树中结点的最大层次。图中树的深度是4。

有序树：树中结点的各子树从左至右有次数（最左边的为第一个还孩子）。

无序树：树中结点的各子树无次序。

森林：m(m≥0)棵互不相交的树的集合。树一定是森林，森林不定是树。

树结构和线性结构的比较

1.2. 二叉树的定义

(1)二叉树的特点：

• **每个结点最多有俩孩子(**二叉树中不存在度大于2的结点)。
• 子树有左右之分，其次序不能颠倒。
• 二叉树****可以是空集合，根可以有空的左子树或空的右子树。

(2)二叉树不是树的特殊情况，二叉树和树是两个不同的概念：

• 二叉树结点的子树要区分****左子树和右子树。即使只有一棵子树也要进行区分，说明它是左子树，还是右子树。
• 树当结点只有一个孩子时，就无需区分它是左还是右的次序。因此，二叉树和树是不同的。这是二叉树和树最主要的区别。

(3)二叉树的5种基本形态

2. 二叉树的性质

2.1. 案例引入

(1)数据压缩问题：可采用哈夫曼树。

(2)利用二叉树求接表达式的值。

2.2. 二叉树的相关公式

(1)二叉树第 i 层结点数量****最多有：2^(i-1)。

(2)深度为 k 的二叉树****最多有 2^k - 1个结点。

(3)对于任何一棵二叉树T，如果叶子树为 n0，度为2的结点数为 n2，则 n0 = n2 + 1。

(4)满二叉树

Ⅰ满二叉树在同样深度的二叉树种****结点个数最多。

Ⅱ满二叉树在同样深度的二叉树种****叶子结点个数最多。

(5)完全二叉树

**注：在满二叉树种，从最后一个结点开始，**连续去掉任意个结点，即是一棵完全二叉树。

满二叉树特点：

• 叶子只可能分布在层次最大的两层上。
• 对任一结点，如果其右子树的最大层次为 i ，则其左子树的最大层次必为 i 或 i + 1。
• 满二叉树一定是完全二叉树。

2.3. 完全二叉树的性质

**(1)具有 n 个结点的完全二叉树的深度为 **[log2n] + 1（向下取整）。

(2)完全二叉树****双亲结点编号和孩子结点编号之间的关系。

3. 二叉树的存储结构

3.1. 顺序存储结构

/**
* 二叉树顺序存储表示
* SqBiTree = Sequence Binary Tree
*/
#define MAXSIZE 100
typedef char TElemType;
​
typedef TElemType SqBiTree[MAXSIZE];    // TElemType 代表二叉树的结点类型
SqBiTree bt;

顺序存储结构特点：

• 结点间关系蕴含在其存储位置之中。
• 浪费空间，适合存****满二叉树或完全二叉树。

例题：二叉树的结点采用顺序存储结构，画出二叉树的表示。

3.2. 链式存储结构

/**
* 二叉链表存储结构
*/
typedef char TElemType;
​
typedef struct _btnode {
    TElemType data;
    struct _btnode *lchild;
    struct _btnode *rchild;
} BTNode;

练习：计算二叉链表种空指针域的数量（空指针域在线索二叉树种可以用到）

4. 遍历二叉树

根据遍历序列确定二叉树

由二叉树的先序序列和中序序列，或由二叉树的后序序列和中序序列可以确定唯一一棵二叉树。

遍历算法

4.1. 先中后序遍历

(1)先序遍历

/**
* 递归先序遍历
*/
void preOrderTraverse(BTNode* T) {
    if(!T) return;                   // 递归的出口
    visit(T);                        // 访问
    preOrderTraverse(T->lchild);     // 递归遍历左子树
    preOrderTraverse(T->rchild);     // 递归遍历右子树
}
​
/**
* 非递归先序遍历
*/
void preOrderTraverse(BTNode* T) {
    if(T == null) return;
    
    Stack s = initStack();
    
    while(!isEmpty(s) || T != null) {
        if(T != null) {
            printf("%c\t", T->data);
            push(s, T);
            T = T->lchild;
        } else {
            BTNode *p = pop(s);
            T = p->rchild;
        }
    }
}

(2)中序遍历

/**
* 递归中序遍历
*/
void inOrderTraverse(BTNode* T) {
    if(!T) return;                   // 递归的出口
    preOrderTraverse(T->lchild);     // 递归遍历左子树
    visit(T);                        // 访问
    preOrderTraverse(T->rchild);     // 递归遍历右子树
}
​
/**
* 非递归中序遍历
*/
void inOrderTraverse(BTNode* T) {
    if(T == null) return;
    
    Stack s = initStack();
    
    while(!isEmpty(s) || T != null) {
        if(T != null) {
            push(s, T);
            T = T->lchild;
        } else {
            BTNode *p = pop(s);
            printf("%c\t", p->data);
            T = p->rchild;
        }
    }
}

(3)后序遍历

void postOrderTraverse(BTNode* T) {
    if(!T) return;                   // 递归的出口
    preOrderTraverse(T->lchild);     // 递归遍历左子树
    preOrderTraverse(T->rchild);     // 递归遍历右子树
    visit(T);                        // 访问
}

遍历算法的分析

4.2. 层序遍历

算法：

• 使用队列，将根结点入队；
• 队列不空时循环：从队列中出列一个结点*p，访问它：
  • 若它有左孩子结点，将左孩子结点进队；
  • 若它有右孩子结点，将右孩子结点进队。

void levelOrderTraverse(BTNode* T) {
    if(T == NULL) return;
    enQueue(Q, T);
    while(!isEmpty(Q)) {
        BTNode* p = deQueue(Q);
        printf("%c\t", p->data);
        if(p->lchild) enQueue(Q, p->lchild);
        if(p->rchild) enQueue(Q, p->rchild);
    }
}

4.3. 遍历算法的应用

应用1——复制二叉树

** 算法：**

• 如果根结点为空，递归结束；
• 否则，申请新结点空间，复制根结点；
  • 递归复制左子树；
  • 递归复制右子树。

void copy(BTNode *T1, BTNode *T2) {
    if(T1 == null) return;
    
    T2 = (BTNode*)malloc(sizeof(BTNode));
    
    T2->data = T1->data;
    copy(T1->lchild, T2->lchild);
    copy(T1->rchild, T2->rchild);
}

应用2——计算二叉树的深度

算法：

• 如果是空树，则深度为0；
• 否则，递归计算左子树的深度为m，递归计算右子树的深度为n，二叉树的深度为 max{m, n} + 1。

int depth(BTNode* x) {
    if(x == NULL) return 0;
    int m = depth(x->lchild);
    int n = depth(x->rchild);
    return (m > n ? m : n) + 1;
}

应用3——计算二叉树结点总数

算法：

• 如果是空树，则结点个数为0；
• 否则，结点个数 = 左子树的结点个数 + 右子树的结点个数 + 1。

int size(BTNode* x) {
    if(x == NULL) return 0;
    return size(x->lchild) + size(x->right) + 1;
}

应用4——计算二叉树叶子结点的数

算法：

• 如果是空树，则叶子结点个数为0；
• 否则，叶子结点个数 = 左子树叶子结点个数 + 右子树叶子结点个数。

int leaves(BTNode* x) {
    if(x == NULL) return 0;                               // 空树就返回0
    if(x->lchild == NULL && x->rchild == NULL) return 1;  // 如果是叶子结点返回1
    return leaves(x->lchid) + leaves(x->rchild);
}

5. 线索二叉树

为什么要研究线索二叉树？？

二叉链表中有 n + 1个空指针域(n为结点数)，则可以利用这些空指针域：

• 如果某个结点的左孩子为空，则将空的左孩子指针域改为****指向其前驱；
• 如果某结点的右孩子为空，则将空的右孩子指针域改为****指向其后继。

这种改变指向的指针称为"线索"，加上了线索的二叉树称为线索二叉树。

对二叉树按某种遍历次序使其变为线索二叉树的过程称为****线索化。

线索二叉树的构建

(1)画线索二叉树

(2)线索二叉树的标志域

为了区分 lchild、rchild指针到底是指向孩子的指针，还是指向前驱或后继的指针，对二叉链表中每个结点增设两个标志域 ltag、rtag。

(3)线索二叉树的存储结构

/**
* Threaded Binary Tree
*/
typedef struct _thrbitnode {
    int data;                            // 数据域
    int ltag, rtag;                      // 标志域
    struct _thrbitnode *lchild;          // 左孩子
    struct _thrbitnode *rchild;          // 右孩子
} ThrBiNode;

(4)先序线索二叉树

(4)中序线索二叉树

6. 树的存储结构

6.1. 双亲表示法

(1)实现：定义结构数组，存放树的结点。

每个结点含有两个域：

• 数据域：存放结点本身信息。
• 双亲域：指示本结点的双亲结点在数组中的位置。

(2)C语言类型描述

#define MAXSIZE 100
typedef char TElemType;

/**
* 定义结点
*/
typedef struct {
    TElemType data;            // 结点
    int parent;                // 双亲下标
} PTNode;

/**
* 定义树
*/
typedef struct {
    PTNode nodes[MAXSIZE];
    int r;                    // 根结点的位置
    int n;                    // 结点总数
} PTree;

6.2. 孩子链表表示法

(1)孩子链表

(2)带双亲的孩子链表

(3)C语言定义

#define MAXSIZE 100
typedef char TElemType;

/**
* 孩子结点定义
*/
typedef struct _childnode {
    int child;
    struct _childnode* next;
} ChildNode;

/**
* 双亲结点的定义
*/
typedef struct {
    TElemType data;
    CNode* firstchild;
} ParentNode;

/**
* 树的定义
*/
typedef struct {
    ParentNode nodes[MAXSIZE];
    int n;                       // 结点数量
    int r;                       // 根节点的位置
} ChildParentBinTree;

6.3. 孩子兄弟表示法

(1)实现：用二叉链表作为树的存储结构。

链表中每个结点左指针域指向其第一个孩子结点，右指针域指向其下一个兄弟结点。

(2)C语言定义。

/**
* 结点的存储结构
*/
typedef struct _cbnode {
    ElemType data;
    struct _cbnode* firstchild;           // 指向的第一个孩子结点
    struct _cbnode* nextbrother;          // 指向的下一个兄弟结点
} ChildBrotherNode;

7. 树和森林

树转二叉树

7.1. 树与二叉树的转换

树转二叉树

树转化成二叉树的步骤：

• 加线(兄弟齐心)：在兄弟之间加一条线。
• 抹线(割袍断义 保大)：对于每个结点，除了其左孩子外，去除该结点与其余孩子之间的关系。

口诀：兄弟相连留长子。

二叉树转树

口诀：

• 左孩右右连双亲，
• 去掉原来右孩线。

7.2. 森林与二叉树的转换

森林转二叉树（二叉树与多棵树之间的关系）

步骤：

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

口诀：树变二叉根相连。

二叉树转森林

口诀：去掉全部右孩线，孤立二叉再还原。

7.3. 树和森林的遍历

树的遍历（三种方式）

• 先根遍历：若树不空，则先访问根结点，然后依次先根遍历各棵子树。
• 后根遍历：若树不空，则先依次后根遍历各棵子树，然后访问根结点。
• 层次遍历：若树不空，则自上而下，从左到右访问树中每个结点。

森林的遍历

(1)将森林看成由三个部分组成

• Ⅰ 森林中第一棵树的根节点；
• Ⅱ 森林中第一棵树的子树森林；
• Ⅲ 森林中其他树构成的森林。

(2)先序遍历：即依次从左到右对森林中的每一棵树进行先根遍历。

• 访问森林中第一棵树的根结点；
• 先序遍历森林中第一棵树的子树森林；
• 先序遍历森林中（除了第一棵树之外）其余树构成的森林。

(3)中序遍历：即依次从左到右对森林中的每一棵树进行后根遍历。

• 中序遍历森林中第一颗树的子树森林；
• 访问森林中第一棵树的根节点；
• 中序遍历森林中（除第一棵树之外）其余树构成的森林。

8. 哈夫曼树及其应用

8.1. 哈夫曼树的概念

路径：从树中一个结点到另一个结点之间的分支构成这两个结点间的路径。

结点的路径长度：两结点间路径上的分支数。

树的路径长度：从树根到每一个结点的路径长度之和。记作：TL。

• 结点数目相同的二叉树中，完全二叉树是路径长度最短的二叉树，反之不对。

TL(a) = 1 + 1 + 2 + 2 + 3 + 3 + 4 + 4 = 20。

TL(b) = 1 + 1 + 2 + 2 + 2 + 2 + 3 + 3 = 16。

权：将树中结点赋予一个有某种含义的值。

结点的带权路径长度：从根结点到该结点之间的路径长度与该结点的权的乘积。

树的带权路径长度：树中所有叶子结点的带权路径长度之和。记作：WPL(Weighted Path Length)。

哈夫曼树：最优树。带权路径长度(WPL)最短的树。

注："带权路径长度最短"是在"度相同"的树中比较而得的结果，因此有最优二叉树、最优三叉树之称等等。

哈夫曼树：最优二叉树。带权路径长度(WPL)最短的树。

8.2. 构造哈夫曼树

哈夫曼树的特点：

• n个叶子结点的哈夫曼中共有 2n-1个结点。
• 哈夫曼树的d结点的度为0或2，没有度为1的结点。
• 包含n棵树的森林要经过 n-1次合并才能形成哈夫曼树，共产生 n-1个新结点。且这 n-1个新结点都是具有两个孩子的分支结点。

8.3. 哈夫曼算法

(1)结点类型定义

/**
* 使用顺序存储结构——一维数组
* 定义结点
*/
typedef struct {
    int weight;
    int parent;
    int lchild;
    int rchild;
} HuffmanTreeNode;

(2)实现哈夫曼树

(3)算法

• 初始化哈夫曼树：lchild = rchild = 0；
• 初始化n个叶子结点：初始化 [1....n]的权值；
• 进行以下n-1次合并，依次产生n-1个新结点 HT[i], i = n+1...2n-1：
  • Ⅰ在 HT[1...i-1]中选两个未被选过(parent == 0)的weight最小的两个结点HT[s1]和HT[s2]，s1、s2为两个最小结点的下标；
  • Ⅱ修改HT[s1]和HT[s2]的parent值：HT[s1].parent = i; HT[s2].parent = i；
  • Ⅲ修改新产生的HT[i]：HT[i].lchild = s1; HT[i].rchild = s2; HT[i].weight = HT[s1].weight + HT[s2].weight；

void createHuffmanTree(HuffmanTreeNode* HT, int n) {
    if(n <= 1) return;
    int m = 2 * n - 1;                // 哈夫曼树结点总数 n + n - 1 = 2n - 1
  
    // 数组的0号单元没有用，HT[m]表示根结点
    HT = (HuffmanTreeNode*)malloc(sizeof(HuffmanTreeNode) * (m + 1));
  
    // 将整个数组初始化
    for(int i = 1; i <= m; i++) {
        HT[i].lchild = 0;
        HT[i].rchild = 0;
        HT[i].parent = 0;
    }
  
    // 输入前n个元素的weight值
    for(int i = 1; i <= n; i++) scanf("%d", &HT[i].weight);
  
    // ~ ~ ~ ~ ~ ~ ~ ~ 初始化结束 下面开始建立哈夫曼树 ~ ~ ~ ~ ~ ~ ~ ~ 
    int s1 = 0;
    int s2 = 0;
    for(int i = n + 1; i <= m; i++) {
        // 在HT[k](1 ≤ k ≤ i-1)中查找权值最小两个结点(s1和s2表示下标)
        select(HT, i-1, &s1, &s2);
      
        // 为两个权值最小的结点设置parent
        HT[s1].parent = i;
        HT[s2].parent = i;
      
        // 为新构造的结点设置lchild和rchild
        HT[i].lchild = s1;
        HT[i].rchild = s2;
        HT[i].weight = HT[s1].weight + HT[s2].weight;
    } 
}

8.4. 哈夫曼编码

构造哈夫曼编码的方法

哈弗编码例题

哈夫曼编码算法实现

typedef struct {
    int weight;
    int parent;
    int lchild;
    int rchild;
} HuffmanTreeNode;

/**
* 构建哈夫曼编码
* @Param HT 哈夫曼树(一维数组的指针)
* @Param HC 存放哈夫曼编码的字符数组
* @Param n  哈夫曼树有效结点数量
*/
void createHuffmanCode(HuffmanTreeNode* HT, HuffmanCode &HC, int n) {
    Hc = new char* [n+1];                             // 最后保存的哈夫曼编码数组
    cd = new char[n];                                 // 临时一维字符数组
    cd[n-1] = '\0';                                   // 临时一维字符数组最后一位为'\0'
    for(int i = 1; i <= n; i++) {
        int start = n -1;                             // 临时一维字符数组的下标
        int c = i;                                    // 孩子
        int f = HT[i].parent;                         // 双亲
      
        // 从叶子结点一直向上回溯,直到根结点
        while(f != 0) {
            start--;                            // 回溯一次，临时一维字符数组指针向前移动一次
          
            // 判断当前的i(c)是f的左孩子还是右孩子
            if(HT[f].lchild == c) cd[start] = '0'; 
            else cd[start] == '1';
          
            // 继续向上回溯
            c = f;
            f = HT[f].parent;
        }
        HC[i] = new char[n-start];                    // 为字符数组的第i行开辟空间
        strcpy(HC[i], &cd[start]);                    // 将临时一维字符数组复制到指定位置
    }
    free cd;
}

第六章、图

回顾：数据的逻辑结构

• **集合：数据元素间除了"**同属于一个集合"外，无其他关系。
• **线性结构：一对一的关系，**每个数据元素最多只有一个前驱结点和一个后继结点。如线性表、栈、队列。
• **树形结构：一对多的关系，**每个数据元素可以有一个前驱结点和多个后继结点。如树，其中根结点没有前驱，叶子结点没有后继。
• **图形结构：多对多的关系，**每个数据元素可以多个前驱结点和多个后继结点。

1. 图的定义和术语

图：G = (V,E)

• V：顶点(数据元素)的****有穷非空集合。
• E：边的****有穷集合。

无向图：每条边都是无方向的图。

有向图：每条边都是有方向的图。

完全图：图中任意两个顶点都有一条边相连。

稀疏图：有很少边或弧的图(e < nlogn)。其中n代表顶点的数量。

稠密图：有较多边或弧的图。

网：边/弧带权的图。

邻接：若两个顶点之间有边/弧相连，称这两个顶点邻接，反之则不邻接。

• 存在(vi,vj)，则称vi和vj****互为邻接点。
• 存在<vi,vj>，则称vi****邻接到vj，vj邻接于vi。

关联(依附)：边/弧与顶点之间的关系。

• 存在(vi,vj)/<vi,vj>，则称该边/弧****关联于vi和vj。

顶点的度：与该顶点相关联的边的数目，记为 TD(v)。在有向图中，顶点的度 = 入读 + 出度。

路径：接续成的顶点序列。

路径长度：路径上边或弧的数目/权值之和。

回路(环)：第一个顶点和最后一个顶点相同的路径。

简单路径：除路径起点和终点可以相同外，其余顶点均不相同的路径。

简单回路(简单环)：除路径起点和终点相同外，其余顶点均不相同的路径。

连通图(强连通图)：在无(有)向图 G = (V,{E})中，如果对任何两个顶点 v、u 都存在从 v 到 u 的路径，则称G是连通图(强连通图)。

权和网：

• 图中边或弧所具有的相关数称为****权。表明从一个顶点到另一个顶点的距离或耗费。
• 带权的图称为****网。

子图：设有两个图 G = (V,{E})、G1 = (V1,{E1})，若 V1 ∈ V 且 E1 ∈ E，则称G1是G的子图。

连通分量：

• 无向图G的****极大连通子图称为G的连通分量。
• 极大连通子图：该子图是G的连通子图，将G的任何不在该子图中的顶点加入，子图不再连通。

强连通分量：

• 有向图G的****极大强连通子图称为G的强连通分量。
• 极大强连通子图：该子图是G的强连通子图，将G的任何不在该子图中的顶点加入，子图不再强连通。

极小连通子图：该子图是G的连通子图，在该子图中删除任何一条边，子图不再连通。

生成树：包含无向图G所有顶点的极小连通子图。

2. 图的存储结构

2.1. 邻接矩阵

图的逻辑结构是：多对多的关系。图没有顺序存储结构，但是可以借助二维数组表示元素间的关系。

无向图的邻接矩阵

建立一个****顶点表(记录各个顶点的信息) 和一个邻接矩阵(表示各个顶点之间的关系)。

有向图的邻接矩阵

网(即有权图)的邻接矩阵

邻接矩阵的存储表示

(1) 用两个数组分别存储顶点表和邻接矩阵。

#define MaxInt 32767                          // 表示极大值,即∞
#define MaxVexsNum 100                        // 最大顶点数
typedef char VertexType;                      // 设顶点的数据类型为字符型
typedef int ArcType;                          // 设边的权值类型为整型，若不是带权图用0和1表示

typedef struct {
    VertexType vexs[MaxVexsNum];              // 顶点表
    ArcType arcs[MaxVexsNum][MaxVexsNum];     // 邻接矩阵
    int vexnum;                               // 图的当前顶点数
    int arcnum;                               // 图的边数
} AMGraph;                                    // Adjacency Matrix Graph

(2) 采用邻接矩阵表示法创建无向网

算法：

• 输入****总顶点数和总边数。
• 依次输入****顶点的信息存入顶点表中。
• 初始化邻接矩阵，使每个权值初始化为极大值。
• 构造邻接矩阵。

/**
* Undirected Network 无向网
* &表示引用 不是取地址运算
*/
Status createUND(AMGraph &G) { 
    // 1.输入总顶点数和总边数并存储
    cin >> G.vexnum >> G.arcnum;              // 输入顶点数目和总边数
  
    // 2.初始化顶点表
    for(int i = 0; i < G.vexnum; i++) {
        cin >> G.vexs[i];                     // 依次输入顶点信息
    }
  
    // 3.初始化邻接矩阵
    for(int i = 0; i < G.vexnum; i++) {
        for(int j = 0; j < G.vexnum; j++) {
            G.arcs[i][j] = MaxInt;            // 边的权值均设置为最大值
        }
    }
  
    // 4.构造邻接矩阵
    for(int k = 0; k < G.arcnum; k++) {
        cin >> v1 >> v2 >> w;                 // 输入一条边所依附的顶点及边的权值
        i = LocateVertex(G, v1);
        j = LocateVertex(G, v2);              // 确定v1和v2在G中的位置
        G.arcs[i][j] = w;                     // 边<v1, v2>的权值置为w
        G.arcs[j][i] = G.arcs[i][j];          // 置<v1, v2>的对称边<v2, v1>的权值为w
    }
  
    return OK;
}

/**
* 在顶点表中查找顶点u的下标，存在则返回顶点表中的下标;否则返回-1
*/
int LocateVertex(AMGraph G, VertexType u) {
    for(int i = 0; i < G.vexnum; i++) {
        if(u == G.vexs[i]) return i;
    }
    return -1;
}

(3)采用邻接矩阵表示法创建无向图、有向网、有向图

邻接矩阵存储图的优点和缺点

优点：

• 直观、简单、好理解。
• 方便检查任一对顶点之间是否存在边。
• 方便找任一顶点的所有"邻接点"(有边直接相连的顶点)。
• 方便计算任一顶点的"度"(从该点出发的边数为出度，指向该点的边数为入度)。

缺点：

• 不便于增加和删除顶点。
• 浪费空间——存稀疏图有大量无效元素。
  • 对于稠密图(特别是完全图)还是很合算的。
• 浪费时间——统计稀疏图中一共有多少条边。

2.2. 邻接表

邻接表表示法

无向图的邻接表

有向图的邻接表

邻接表和逆邻接表

图的邻接表存储表示

(1)定义邻接表的表头结点

/**
* 说明：AdjList v; 等价于 vNode v[MVNum];
*/
typedef struct _vnode {
    VertexType data;              // 顶点信息
    ArcNode* firstarc;            // 指向第一条依附该顶点的边的指针
} vNode, AdjList[MVNum];          // AdjList表示邻接表

(2)定义邻接表的边(弧)结点

#define MVNum 100                 // 最大顶点数     
typedef struct _arcnode {
    int adjvex;                   // 该边所指向的顶点的下标
    struct _arcnode* nextarc;     // 指向下一条边的指针
    OtherInfo info;               // 和边相关的信息(权重)
} ArcNode;

(3)图的结构定义

typedef struct {
    AdjList vertices;             // vertices --- vertex的复数
    int vexnum;                   // 图的当前顶点数
    int arcnum;                   // 图的边数
} ALGraph;

(4)采用邻接表表示法创建无向图

算法：

• 输入****总顶点数和总边数。
• 建立****顶点表(邻接表的表头数组)：
  • 依次输入点的信息****存入顶点表中；
  • 使每个表头结点的****指针域初始化为NULL。
• 创建邻接表：
  • 依次输入每条边依附的两个顶点；
  • 确定两个顶点的序号 i、j，建立边结点；
  • 将此边结点分别插入到 vi、vj对应的两个边链表的头部(头插法)。

/**
* 采用邻接表表示法创建无向图G
*/
Status createUDG(ALGraph &G) {
    cin >> G.vexnum >> G.arcnum;               // 输入图的顶点数和边数并保存
  
    // 输入各点构造表头结点
    for(int i = 0; i < G.vexnum; i++) {
        cin >> G.vertices[i].data;             // 输入顶点的值
        G.vertices[i].firstarc = NULL;         // 初始化表头结点的指针域为NULL
    }
  
    // 输入各边构造邻接表(头插法)
    for(int k = 0; k < G.arcnum; k++) {
        cin >> v1 >> v2;
        int i = locateVertex(G, v1);
        int j = locateVertex(G, v2);
      
        ArcNode* p1 = (ArcNode*)malloc(sizeof(ArcNode));   // 创建新的结点
        p1->adjvex = j;                                    // 邻接点序号为j
        p1->nextarc = G.vertices[i].firstarc;              // 6666666
        G.vertices[i].firstarc = p1;                       // 将新结点p1插入结点vi的边表头部
      
        // 由于是无向图所以还要对称着插入一次(有向图这部分代码直接不用写了)
        ArcNode* p2 = (ArcNode*)malloc(sizeof(ArcNode));
        p2->adjvex = i;
        p2->nextarc = G.vertices[j].firstarc;
        G.vertices[j].firstarc = p2;
    } 
    return OK;
}

邻接表的特点

• 方便找任一顶点的所有"邻接点"。
• 节约稀疏图的空间：
  • 需要N个头指针 + 2E个结点(每个结点至少两个域)。
• 方便计算任一顶点的"度"？？
  • 对于无向图：是；
  • 对于有向图：邻接表(计算出度) + 逆邻接表(计算入度)。
• 不方便检查任一对顶点间是否存在边。

邻接矩阵和邻接表表示法之间的关系

(1)联系：邻接表中每个链表对于邻接矩阵中的一行，链表中结点个数等于一行中非零元素的个数。

(2)区别：

• 对于任一确定的无向图，****邻接矩阵是唯一的(行列号与顶点编号一致)，但是邻接表不唯一(链表次序与顶点编号无关)。
• 邻接矩阵的空间复杂度为 O(n2)，而邻接表的空间复杂度为 O(n+e)。

(3)用途：邻接矩阵多用于稠密图；而邻接表都用于稀疏图。

2.3. 十字链表

十字链表可以看成：将有向图的邻接表和逆邻接表结合起来形成的一种链表。

2.4. 邻接多重表

typedef char ElemTyde;

// ivex,jvex该边依附的两个顶点在表头中的位置
typedef struct _arcnode {
    int mark;                     // 标志位
    int ivex;
    struct _arcnode* ilink;       // 依附于ivex的下一条边
    int jvex;
    struct _arcnode* jlink;       // 依附于jvex的下一条边
} ArcNode;

typedef struct {
    ElemTyde data;                // 与顶点有关的信息
    ArcNode* firstarc;            // 指向第一条依附于顶点的边
} VNode;

3. 图的遍历

遍历定义：从已给的连通图中某一顶点出发，沿着一些边访遍全图中所有的顶点，且使每个顶点仅被访问一次，就叫做图的遍历。

遍历实质：找每个顶点的邻接点的过程。

3.1. 深度优先遍历(DFS)

深度优先遍历：一条路走到黑。

深度优先遍历——邻接矩阵上的遍历算法

#define MaxVexsNum 100
typedef char VertexType;
typedef int ArcType;

/**
* 定义邻接矩阵
*/
typedef struct {
    VertexType vexs[MaxVexsNum];
    ArcType arcs[MaxVexsNum][MaxVexsNum];
    int vexnum;
    int arcnum;
} AMGraph;

/**
* 辅助数组：标记顶点是否被访问过
*/
int visited[MaxVexsNum];

/**
* 邻接矩阵上的深度优先算法
* @Param G表示为邻接矩阵类型
* @Param v表示访问第v个顶点,赋值时表示起始顶点
*/
void DFS(AMGraph G, int v) {
    cout << v;                                // 输出起始顶点
    visited[v] = 1;                           // 辅助数组记录 1表示该顶点被访问过了
  
    // 依次检查邻接矩阵v所在的行(w表示邻接矩阵的列)
    for(int w = 0; w < G.vexnum; w++) {
        // 邻接矩阵上的值为1 并且 在辅助数组中没有被访问过, 就对该点继续DFS
        if(G.arcs[v][w] != 0 && !visited[W]) DFS(G, w);
    }
}

深度优先遍历——邻接表上的遍历算法

#define MVNum 100
typedef char VertexType;

/**
* 定义边结点
*/
typedef struct _arcnode {
    int adjvex;
    struct _arcnode* nextarc;
} ArcNode;

/**
* 定义顶点
*/
typedef struct _vnode {
    VertexType data;
    ArcNode* firstarc;
} VNode, AdjList[MVNum];

/**
* 定义邻接表
*/
typedef struct {
    AdjList vertices;
    int vexnum;
    int arcnum;
} ALGraph;

/**
* 辅助数组
*/
int visited[MVNum];

/**
* 邻接表的深度优先遍历
* @Param G代表邻接表
* @Param v代表起点编号
*/
void DFS(ALGraph* G, int v) {
    ArcNode* P;
  
    cout << v;                                       // 输出起始顶点
    visited[v] = 1;                                  // 辅助数组记录 1表示该顶点被访问过了
    p = G->vertices[v].firstarc;                     // p指向顶点v的第一条边
    while(p) {
        // 如果顶点未被访问,则递归访问它
        if(visited[p->adjvex] == 0) DFS(G, p->adjvex);
        p = p->nextarc;
    }
}

DFS算法分析

• 用****邻接矩阵来表示图，遍历图中每一个顶点都要从头扫描该顶点所在行，时间复杂度为 O(n2)。
• 用****邻接矩阵来表示图，虽然有 2e 个表结点，但只需要扫描 e 个结点即可完成遍历，时间复杂度为 O(n+e)。
• 稠密图适于在邻接矩阵上进行深度优先遍历；稀疏图适于在邻接表上进行深度优先遍历。

3.2. 广度优先遍历(BFS)

广度优先遍历：和树的层序遍历非常相似。

广度优先遍历——邻接矩阵上的遍历算法

需要借助队列和辅助数组实现。

#define MVNum 100
typedef char VertexType;

/**
* 定义边结点
*/
typedef struct _arcnode {
    int adjvex;
    struct _arcnode* nextarc;
} ArcNode;

/**
* 定义顶点
*/
typedef struct {
    VertexType data;
    ArcNode* firstarc;
} VNode, AdjList[MVNum];

/**
* 定义邻接表
*/
typedef struct {
    AdjList vertices;
    int vexnum;
    int arcnum;
} ALGraph;

/**
* 辅助数组
*/
int visited[MVNum];

/**
* 邻接表的广度优先遍历(非递归算法)
* @Param G代表邻接表
* @Param v代表起点编号
*/
void BFS(ALGraph G, int v) {
    ArcNode* p;
    cout << v;                                  // 访问第v个顶点
    visited[v] = 1;                             // 更新辅助数组
    initQueue(Q);                               // 辅助队列Q初始化，默认为空
    enQueue(Q, v);                              // v进队
  
    // 队列不为空，则出队
    while(!isEmpty(Q)) {
        int j = deQueue(Q);                     // 队头元素出队
        p = G.vertices[j].firstarc;             // p指向出队顶点j的第一条边
      
        // 将p的所有邻接点中未被访问的入队
        while(p) {
            if(visited[p->adjvex] == 0) {       // 当前邻接点未被访问，则入队
                cout << p->adjvex;
                visited[p->adjvex] = 1;
                enQueue(Q, p->adjvex);
            }
            p = p->nextarc;
        }
    }
}

BFS算法分析

• 如果使用****邻接矩阵，则BFS对于每一个被访问到的顶点，都要循环检测矩阵中的整整一行(n个元素)，时间复杂度为 O(n2)。
• 用****邻接表来表示图，虽然有2e个表结点，但只需扫描e个结点即可完成遍历，加上访问n个头结点的时间，时间复杂度为 O(n+e)。

DFS和BFS算法效率比较

• 空间复杂度相同，都是 O(n)(借助了栈或者是队列)。
• 时间复杂度只与存储结构(邻接矩阵或邻接表)有关，而与搜索路径无关。

4. 图的应用

4.1. 生成树

概念回顾——生成树

生成树：

• 包含无向图G所有顶点的极小连通子图。即：所有顶点均由边连接在一起，但****不存在回路的图。
• 一个图可以有许多棵不同的生成树。

所有生成树具有以下共同特点：

• 生成树的顶点个数与图的****顶点个数相同。
• 生成树是图的****极小连通子图，去掉一条边则非连通。
• 在生成树中再加一条边必然形成回路。
• 一个有n个顶点的连通图的生成树有 n-1条边。
• 含有n个顶点 n-1条边的图不一定是生成树。
• 生成树中任意两个顶点间的****路径是唯一的。

无向图的生成树

深度优先遍历算法——深度优先生成树。

广度优先遍历算法——广度优先生成树。

4.2. 最小生成树

MST性质

MST性质解释

• 在生成树的构造过程中，图中n个顶点分属两个集合：
  • 已落在生成树上的顶点集(U)。
  • 尚未落在生成树上的顶点集(V-U)。
• 接下来则应在所有连通 U 中顶点和 V-U 中顶点的边中选取权值最小的边。

普利姆(Prim)算法：{U}和{V-U}中选取权值最小的边，MST性质的应用。从顶点出发

克鲁斯卡尔(Kruskal)算法：从边出发

Prim和Kruskal之间的比较

4.3. 最短路径

最短路径：

• 在****有向网中A点(源点)到达B点(终点)的多条路径中，寻找一条各边权值之和最小的路径，即最短路径。
• 最短路径与最小生成树不同，最短路径上不一定要包含n个顶点，也不一定包含n-1条边。

最短路径的两类问题

(1)第一类问题：两点间最短路径——Dijkstra(迪杰斯特拉)算法。

(2)第二类问题：求图中各顶点间最短路径——Floyd(弗洛伊德)算法。

Dijkstra算法(和prim类似)：按路径长度递增次序产生最短路径

**Floyd算法：求图中各顶点间的路径 **

4.4. 拓扑排序

有向无环图及其应用

(1)有向无环图？

有向无环图：无环的有向图，简称DAG图(Directed Acyclic Graph)。

(2)AOV网和AOE网

AOV网：拓扑排序。

AOE网：关键路径。

(3)AOV网的特点

拓扑排序

(1)拓扑排序的方法

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

(2)拓扑排序的重要应用：检测AOV网中是否存在环

4.5. 关键路径

(1)AOE网各部分的意思

• 把工程计划表示为****边表示活动的网络，即AOE网；
• 用顶点表示****事件；
• 弧表示****活动；
• 弧的权代表****活动时间。

(2)对于AOE网我们关心的两个问题

• Ⅰ 完成整项工程至少需要多少时间？
• Ⅱ 哪些活动是影响工程进度的关键？

以上两个问题都是关键路径问题。

关键路径——路径长度最长的路径。

路径长度——路径上各持续时间之和。

确定关键路径

(1)定义4个重要的描述量

(2)计算事件的最早发生事件 ve(v1)和最迟发生事件 vl(v2)

(3)如何找 l(i) == e(i)的关键活动？

(4)求关键路径的步骤