图Graph

#图的基本概念

数组表示法(邻接矩阵)

• 无向图（该图有n个顶点、e条边）

• 无向图中，顶点Vi的度TD(Vi)是邻接矩阵A中第i行元素之和.
• 有向图中：
• 顶点Vi的出度是A中第i行元素之和
• 顶点Vi的入度是A中第i列元素之和

邻接表Adjacency

方法

• 为图中每个顶点建立一个单链表，第i个单链表中的结点表示依附于顶点Vi的边（有向图中指以Vi为尾的弧）

层次渐进，由小到大建Graoh

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

#define MAX_VERTEX_NUM 20

//边/弧结点的类型定义
typedef struct ArcNode{
int adjvex;//边/弧的另一顶点在数组中的位置
struct ArcNode *nextaec;//指向下一条边/弧的指针
}ArcNode;

//顶点结点和数组的类型定义
typedef struct VNode{
VertexType data;//顶点信息
ArcNode *firststrac;//指向关联该顶点的边/弧链表
}Vnode, AdjList[MAX_VERTEX_NUM];


typedef struct {
AdjList  vertices;
int  vexnum, arcnum;    //图的当前顶点数和弧数
int   kind;    //图的种类标志
}ALGraph;

特点

• 无向图
• 顶点Vi的度为第i个单链表中的结点数
• 有向图
• 顶点Vi的出度–为第i个单链表中的结点个数
• 顶点Vi的入度–为整个单链表中邻接点域值是i的结点个数
• 领结表的缺点：
• 无向图中，边是一种“对称”关系。导致任一条边的结点都有两个，而且分别在两个不同的链表中。即：存贮表示中信息有冗余，维护不容易

无向图的邻接多重表Adjacency Multilist

图的遍历Traversing Graph

从图中某一个顶点出发，访问图中的其余顶点，且使每个顶点仅被访问一次。

• 两种方法对无向图和有向图都适用
• 深度优先搜索类似于树的先根遍历
• 广度优先搜索类似于树的层次遍历

深度优先遍历

无向图

有向图

广度优先遍历

无向图

有向图

图的连通性

生成树

• 所有顶点均由边连接在一起，但不存在回路
• 一个图可以有许多棵不同的生成树
• 一个有n个顶点的连通图的生成树有n-1条边
• 生成树中任意两个顶点间的路径是唯一的
• 在生成树中再加一条边必然形成回路
• 生成树是图的极小连通子图
• 生成树的顶点个数与图的顶点个数相同

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

最小生成树

每条边上权值之和最小

普里姆算法Prim

从一个点开始，不断的去寻找最小的边，进而找到那个点，然后继续

• 算法评价：T(n)=O(n²)
• 算法实现：图用邻接矩阵表示

柯鲁思卡尔算法 Kruskal

先将所有店写出，再去找最小的边

拓扑排序

问题提出：学生选修课程问题

• 顶点——表示课程
• 有向弧——表示先决条件
• 若课程i是课程j的先决条件，则图中有弧

学生应按怎样的顺序学习这些课程，才能无矛盾、顺利地完成学业
——拓扑排序

AOV网 （Activity On Vertex network）

用顶点表示活动，用弧表示活动间优先关系的有向图

• 是图中有向边，则vi是vj的直接前驱；vj是vi的直接后继
• AOV网中不允许有回路，这意味着某项活动以自己为先决条件

拓扑排序

把AOV网络中各顶点按照它们相互之间的优先关系排列成一个线性序列的过程

• 在有向图中选一个没有前驱的顶点且输出它
• 从图中删除该顶点和所有以它为尾的弧
• 重复上述两步，直至全部顶点均已输出；或者当图中不存在无前驱的顶点为止

题目：

步骤：

关键路径AOE（Activity On Edge）

问题提出：工程问题

把工程计划表示为有向图，用顶点表示事件，弧表示活动；

每个事件表示在它之前的活动已完成，在它之后的活动可以开始

边表示活动的网.AOE网是一个带权的有向无环图，其中顶点表示事件，弧表示活动，权表示活动持续时间.

• 路径长度——路径上各活动持续时间之和
• 关键路径——路径长度最长的路径
• Ve(j)——事件Vj的最早发生时间
• Vl(j)——事件Vj的最晚发生时间
• e(i)——表示活动ai的最早开始时间
• l(i)——表示活动ai的最晚开始时间
• l(i)-e(i)——表示完成活动ai的时间余量
• 关键活动——关键路径上的活动（即：l(i)=e(i)的活动）

⚠️注意注意

###最长路径长度叫做时间的最早发生时间，不是让你找权值最小的

最短路径

从图中的某个顶点出发到达另外一个顶点的所经过的边的权重和最小的一条路径，称为最短路径

问题提出：交通运输网

• 顶点——表示城市
• 边——表示城市间的交通联系
• 权——表示此线路的长度或沿此线路运输所花的时间或费用等

问题：从某顶点出发，沿图的边到达另一顶点所经过的路径中，各边上权值之和最小的一条路径。

方法一：迪杰斯特拉算法思想Dijkstra

步骤

• 初使时令 S={V0},T={其余顶点}，T中顶点对应的距离值
• 若存在，为弧上的权值
• 若不存在，为无穷
• 从T中选取一个其距离值为最小的顶点W，加入S
• 对T中顶点的距离值进行修改：若加进W作中间顶点，从V0到Vi的距离值比不加W的路径要短，则修改此距离值
• 重复上述步骤，直到S中包含所有顶点，即S=V为止

方法二：弗洛伊德(Floyd)算法

略

【自我小总结】

• 最小生成树
• 权值最小的极小连同子图
• Prim
• Kruskal
• 拓扑排序
• 学生选课问题，有先决条件
• 不断删除以它为尾的线
• 关键路径
• 工程问题
• 最长路径叫做时间的最早发生时间
• 最短路径
• 交通运输网
• Dijkstra
• Floyd
• 点到点

树的存储表示

双亲表示法

• 树的双亲表示法的存储结构
• 现：定义结构数组存放树的结点，每个结点含两个域
• 数据域：存放结点本身信息
• 双亲域：指示本结点的双亲结点在数组中位置
• 特点：找双亲容易，找孩子难

1
2
3
4
5
6
7
8
9
10
11

#define MAX_TREE_SIZE    100
typedef struct PTNode
{
TElemType data;        // 数据元素
int  Parent;              // 双亲结点在存贮区中的位置
}PTNode;
typedef struct
{
PTNode  Nodes[ MAX_TREE_SIZE ];
int n;            // 结点数
}PTree;

孩子表示法

• 多重链表：每个结点有多个指针域，分别指向其子树的根

任何一个数据域，有0个或多个孩子

• 链式存储结构，其结点除放置数据元素外，还可以放置若干指针，分别用来指示该结点的所有孩子结点在存储空间中的位置

带双亲的孩子链表

孩子兄弟表示法

• 实现：用二叉链表作树的存储结构，链表中每个结点的两个指针域分别指向其第一个孩子结
• 特点
• 操作容易
• 破坏了树的层次

1
2
3
4
5
6

typedef struct CSNode
{
TElemType    data;
struct CSNode      *pFirstChild;
struct CSNode      *pNextSibling;
}CSNode, *CTree;

森林与二叉树转换

树转换为二叉树

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

二叉树转换为树

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

森林转换为二叉树

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

二叉树转换成森林

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

树的遍历

先根、后根、层序遍历

森林遍历

先序、中序 没有后序（不然就把一棵树割裂了）

哈夫曼树Huffman

带权路径长度最短的树

考题

哈夫曼编码

#数组和广义表

##数组
n维数组中的每个元素都受n个线性关系的约束

基本操作

#串

###定义

串是由零个或多个字符组成的有限序列（s = ‘a1,a2, a3, … an’）

###基本操作

• 连接操作 Concat( &T,S1,S2)
• 求子串操作SubString( &Sub,S, pos,len)
• 求子串位置操作Index( S,T,pos )
• 串插入操作 StrInsert( &S,pos,T)
• 串删除操作 StrDelete( &S,pos,len)

###存储方式

• 定长存储

类似字符数组，用一组地址连续的存储单元存放

1
2

#define MAXSTRLEN 255
Typedef unsigned char SString[MAXSTRLEN+1]

• 堆分配存储

类似于线性表的顺序存储结构

1
2
3
4

typedef struct {
char *ch;  //指向存放串值的存储空间基址
int  length;  // 整型域：存放串长
}Hstring;

#线性链表

##基础概念

• 顺序存储：
  用一组连续的内存单元存放数据元素，用元素相对的存储位置表示元素之间的结构关系；

• 链式存储：用任意一组存储单元存储数据元素，对每个数据元素除了保存自身信息外，还保存相关元素的存储位置。

##单链表初始化
结点中只含一个指针域的链表叫线性链表，也叫单链表

1
2
3
4
5
6
7
8

typedef struct LNode {
ElemType data;
struct LNode  *next;
}LNode,*LinkList;


LNode   *p;
LinkList  L；

• (*p)表示L所指向的结点
• (*p).datap->data表示p指向结点的数据域
• (*p).nextp->next表示p指向结点的指针域
• 生成新结点：p=(LinkList )malloc(sizeof(LNode));
• 系统回收p结点：free(p)

##插入

###算法思想：

• 寻找第i-1个元素结点（顺指针向后查找，直到p指向第i-1个元素或p为空）
• 分配新结点
• 插入新结点

1
2
3
4
5
6
7
8
9
10
11
12

Status ListInsert_L(LinkList &L, int i, ElemType e){
//在带头结点的线性链表L中第i元素结点之前插入元素e
p=L; j=0
while (p&&j<i-1)
{p=p->next; ++j;}//寻找第i-1个元素结点
if(!p||j>i-1)return ERROR; // i小于1  则 j>i-1
// i大于表长+1 则p为空
s=(LinkList)malloc(sizeof(LNode)); //分配新结点
s->data=e;
s->next=p->next; p->next=s;   //插入新结点
return OK;
}//LinstInsert_L

##删除

###算法思想：

• 寻找第i-1个结点
  (顺指针向后查找，直到p指向第i-1个元素或p->next为空)
• 删除结点(修改其后继指针)
• 回收（释放）结点空间

1
2
3
4
5
6
7
8
9
10
11
12
13
14

删除操作算法：
Status ListDelete_L(LinkList &L, int i, ElemType &e){
//在带头结点的单链线性表L中，删除第i个元素，并由e返回其值
p=L; j=0;
while (p->next&&j<i-1){  //寻找第i-1个结点
p=p->next; ++j;
}
if(!p->next)||j>i-1)return ERROR; //  表中无第i个结点(i不合法)
//  i<1        则 j>i-1
//   i>表长  则 p->next为空
q=p->next;p->next=q->next;   //删除结点
e =q->data; free(q);                //  回收（释放）结点空间
return OK;
}//LinstDelete_L

##逆置线性链表

###算法思想：

• 标志后继结点为空)
• 修改指针（将*p插入在头结点之后）
• 重置结点*p（p重新指向原表中后继）

1
2
3
4
5
6
7
8
9
10

void  inverse(LinkList &L) {
// 逆置带头结点的单链表 L
p=L->next;  L->next=NULL;
while ( p) {
succ=p->next;    // succ指向*p的后继
p->next=L->next;
L->next=p;       // *p插入在头结点之后
p = succ;
}
}

Welcome to Hexo! This is your very first post. Check documentation for more info. If you get any problems when using Hexo, you can find the answer in troubleshooting or you can ask me on GitHub.

Quick Start

Create a new post

1

$ hexo new "My New Post"

More info: Writing

Run server

1

$ hexo server

More info: Server

Generate static files

1

$ hexo generate

More info: Generating

Deploy to remote sites

1

$ hexo deploy

More info: Deployment