数据结构(第七章)

蓝Q曦 included in 数据结构

2024-05-05 1947 words 4 minutes

Contents

图

基本概念和术语

图是顶点集和边集组成的二元组G=<V,E>,E中每条边是V中一对顶点**(u,v)**间的联系,如果是无序对，那么称该图为无向图，否则为有向图。
完全图、稠密图和稀疏图、子图
邻接点及关联边
1. 邻接点：边的两个顶点互为邻接点
2. 关联边：若有边e= (v, u), 则称顶点v、u关联边e
网：在图中赋予每条边或弧一定的权值，这种带权的图称为网。
顶点的度、入度和出度

顶点V的度 = 与V相关联的边的数目
1. 在有向图中:
  
  顶点V的出度 = 以V为起点有向边数
  
  顶点V的入度 = 以V为终点有向边数
  
  顶点V的度 = V的出度+V的入度
2. 设图G的顶点数为n，边数为e
  
  图的所有顶点的度数之和 = 2*e
（每条边对图的所有顶点的度数和“贡献”2度）
路径、回路
1. 在图G=<V,E>中，若有顶点序列$v_1,v_2,… ,v_k$,且$<v_i,v_{i+1}>\in E$(有向图)或$(v_i,v_{i+1})\in E$(无向图)，其中i=1,2,…k-1,v=$v_1$,u=$v_k$，则称该序列是从顶点v到顶点u的路径；若v=u，则称该序列为回路
简单路径、简单回路
1. 在一条路径中, 除起点和终点外,若其余顶点各不相同,则称该路径为简单路径。
2. 由简单路径组成的回路称为简单回路
3. 例如在上面的无向图中，V0,V1,V2,V3是简单路径V0,V1,V2,V4,V1不是简单路径；在上面的有向图中，V0,V2,V3,V0是简单回路
连通图、强连通图

在无（有）向图G=<V, E>中，若对任何两个顶点u、v都存在从u到v的路径，则称G是连通图(强连通图)。
连通分量、强连通图分量

在无（有）向图G=<V, E>中，若对任何两个顶点u、v都存在从u到v的路径，则称G是连通图(强连通图)。无（有）向图的极大连通子图称为图的连通分量（强连通分量）
生成树
1. 一个连通图的生成树是一个极小连通子图，它含有图中全部顶点，但只有足以构成一棵树的n-1条边

无向图及其生成树

赋权图

有向图的强连通子图

图的应用示例

图的存储结构

图的存储结构至少要保存两类信息：

顶点的数据
顶点间的关系

如何表示顶点间的关系？

约定:G=<V, E>是图, V={v0,v1,v2, … vn-1 },设顶点的角标为它的编号

在数组表示法中，用邻接矩阵表示顶点间的关系

#define MaxVnum 50
typedef double AdjMatrix[MaxVnum][MaxVnum];   
typedef struct {
   VertexType vexs[MaxVnum]; //顶点向量
   AdjMatrix arcs;         //邻接矩阵
   int vexnum,arcnum; //图的当前顶点数和边数
}Graph;
Graph   G;

数组表示法的特点

无向图的邻接矩阵是对称矩阵，同一条边表示了两次；
顶点v的度：等于二维数组对应行（或列）中值为1的元素个数；
判断两顶点v、u是否为邻接点：只需判二维数组对应分量是否为1
顶点不变，在图中增加、删除边：只需对二维数组对应分量赋值1或清0；
设图的顶点数为 n ,用有n个元素的一维数组存储图的顶点,用邻接矩阵表示边,则G占用的存储空间为：n+n2；图的存储空间占用量只与它的顶点数有关，与边数无关；适用于边稠密的图；

有向图的邻接矩阵不一定是对称的；
顶点v的出度：等于二维数组对应行中值为1的元素个数；
顶点v的入度：等于二维数组对应列中值为1的元素个数；

网的数组表示法

图的邻接表存储结构

在邻接表表示法中

顶点：通常按编号顺序将顶点数据存储在一维数组中关联同一顶点的边：用线性链表存储

网的邻接链表表示

typedef struct ArcNode{
     int      adjvex;
     double  weight;
     struct ArcNode *nextarc;
}ArcNode;

typedef struct {
      VertexType   data;
      ArcNode  *firstarc;
}AdjList[MaxVnum];

typedef struct {
      int vexnum,arcnum;
      AdjList  vertices;
}AGraph;

AGraph G;

有向图的邻接表表示

在邻接表表示中

顶点：通常按编号顺序将顶点数据存储在一维数组中以同一顶点为起点的弧：用线性链表存储

在逆邻接表表示中

顶点：通常按编号顺序将顶点数据存储在一维数组中以同一顶点为终点的弧：用线性链表存储

有向图的十字链表表示

将有向图的邻接表和逆邻接表结合起来得到的链表。

在十字链表中，顶点结点存储数据元素，弧结点存储弧及其上的信息。

将有向图的邻接表和逆邻接表结合起来得到的链表。

在十字链表中，顶点结点存储数据元素，弧结点存储弧及其上的信息。

无向图的邻接多重表表示

无向图的邻接多重表表示中，每条边只表示一次。

图的遍历

从图的某个顶点出发，访问图中的所有顶点，且使每个顶点仅被访问一次。这一过程叫做图的遍历。
图的遍历操作是求解图的连通性问题、拓扑排序等问题的基础。
遍历方法:深度优先遍历和广度优先遍历

深度优先搜索(DFS)

广度优先搜索BFS

广度优先搜索算法(BFS)

图的连通性

利用图的遍历运算求解图的连通性问题
1. 无向图是否连通、有几个连通分量，求解无向图的所有连通分量
  1. 深度优先生成树、生成森林
  2. 广度优先生成树、生成森林
2. 有向图是否是强连通、求解其强连通分量
求无向网的最小代价生成树