数据结构笔记4

目录

• 5 图
  • 5.1 有关图
    • 5.1.1 图的定义
    • 5.1.2 图定义解释
    • 5.1.3 图的特点
    • 5.1.4 图的术语
  • 5.2 图的存储结构及实现
    • 5.2.1 邻接矩阵
    • 5.2.2 算法实现

5 图

5.1 有关图

现实导航
公路规划及造价预算
网络路由表同步
教学计划安排
……

5.1.1 图的定义

• 图的特点

  非线性结构
  结点之间的邻接关系可以是任意的

• 图的定义
  由两个集合构成，一个非空但有限的顶点集合V（不可以空），另一个是描述顶点关系的边集合E（可以空）

• 图的数学描述方式
  G=(V, E)，每条边是一顶点对(v, w)，且v, wV
  通常用|V|表示顶点的数量，|E|表示边的数量

5.1.2 图定义解释

图G含有n (n > 0)个结(顶)点，它们组成顶点的有限集合V(G)，其中n个顶点之间的关系组成集合E(G)，E(G)：

1. 可以是空集；若E(G)为空，则图G只有顶点，没有边

2. 若图G中的每条边都有方向，则称G为有向图

3. 若图G中的每条边都没有方向，则称G为无向图

4. 有向边表示为 <vi, vj> (注意 <vi, vj>和 <vj, vi> 为两条不同的边)；无向边表示为 (vi, vj)

5.1.3 图的特点

1. 顶点可以有多个前驱，或者后继

2. 顶点间是多对多（N:M）的关系

3. 无向图顶点关系是对称的，有向图顶点关系不对称

5.1.4 图的术语

术语	英文	定义
顶点	Vertex	即图上的数据元素
无向图	Undirected Graph	顶点间关系是无方向，即图中任意两顶点间关系是对称的。无向边表示为 (v, w)，说明顶点间对称的关系
边	Edge	顶点间对称关系的描述
有向图	Directed Graph	顶点间关系是有序的，即图中顶点间存在不对称关系。顶点间有序关系表示为 <v, w>，即有向边
弧	Arc	顶点间不对称关系的描述
弧尾	Tail	有向边的初始点（出端）
弧头	Head	有向边的终端点（入端）

术语	定义	示例 / 补充说明
邻接点	存在关系的两个顶点互为相邻，即邻接	-
路径	一个顶点序列，包含从一个顶点到另一个顶点所经过的全部顶点序列	如：v1v3v4v1v2、v1v4v3v5v4v3v2
简单路径	序列中顶点不重复出现的路径	如：v1v3v4v2、v1v4v5v3v2
回路（环）	第一个顶点和最后一个顶点相同的简单路径	如无向图：v1v4v5v3v2v1
完全图	顶点间可以存在的关系全存在，拥有该类型图中最多的边数	无向完全图边数：n(n−1)/2；有向完全图边数：n(n−1)（为无向的 2 倍）

术语	定义	补充说明
顶点的度	与顶点相关联的边数	-
入度	以顶点为弧头的弧的数目	仅适用于有向图
出度	以顶点为弧尾的弧的数目	仅适用于有向图
稀疏图	边或弧数量很少的图	-
稠密图	非稀疏图	-
加权图	边或弧上带有相关数据（权值）的图	-
网络 (Network)	带权的连通图	-
子图	顶点和边都属于另一幅图的图	数学定义：设 G=(V,E)，G1=(V1,E1)，且 V1⊆V，E1⊆E，E1 关联的顶点都在 V1 中，则称 G1 是 G 的子图
连通	两顶点间存在路径，则称两顶点连通	-
连通图	无向图中任意两顶点都连通	-
连通分量	无向图的极大连通子图	-
强连通图	有向图中任意两顶点间都存在往返路径	-
强连通分量	有向图的极大强连通子图	-
生成树	连通图的生成树是包含全部顶点的极小连通子图	包含且仅包含 n-1 条边；对有向图，生成树仅有一个顶点入度为 0，其余顶点入度均为 1

5.2 图的存储结构及实现

问题抽象—>建模

5.2.1 邻接矩阵

静态结构 用数组存储

邻接矩阵——表示顶点之间相邻关系的矩阵，用数组表示。设G=(V, E)是具有n个顶点的图，则G的邻接矩阵是具有如下性质的n阶方阵：

若G是网络，则邻接矩阵定义为

其中 W_ij表示边上的权值，表示一个计算机允许的、大于所有边上权值的数，如

5.2.2 算法实现

• 邻接矩阵定义

#define MaxVertexNum 100
#deifne INFINITY   65535
typedef char VexType;
typedef float AdjType;typedef struct {VexType vex[MaxVertexNum]; //一维数组存储图的顶点向量AdjType arcs[MaxVertexNum][MaxVertexNum]; //邻接矩阵存储图的边int n, e;         //图的当前顶点数和弧数
}MGraph;

• 创建无向图邻接矩阵算法（顺序表）

void createMGraph(Mgraph *G) {int i, j, k, w;scanf(&G->n,  &G->e); //顶点数，边数for (i=0; i<G->n; i++) scanf(&G->vex[i]); //构造顶点向量for (i=0; i<G->n; i++) for (j=0; j<G->n; j++) G->arcs[i][j]=INFINITY; //初始化邻接矩阵 for (k=0; k<G->e; k++) { //构造邻接矩阵scanf(&i, &j, &w); //输入一条边依附的顶点和权值G->arcs[i][j]=w; //边(v1, v2)的权值G->arcs[j][i]=G->arcs[i][j]; //置(v1, v2)的对称边(v2, v1)}return ;
}//Createl

• 邻接链表