当前位置：首页 > news >正文

第六章图（上）【图的基本概念和存储】

news 来源：原创 2024/9/21 9:29:29

1. 图的基本概念

1.1 图的定义

图G由顶点集V和边集E组成，记为G=(V,E)，其中V(G)表示图G中顶点的有限非空集；E(G)表示图G中顶点之间的关系 (边) 集合。若V={V, V2,...,Vn}，则用|V|表示图G中顶点的个数，也称图G的阶，E={(u, v) l u $\epsilon$ V, v $\epsilon$ V}，用|E|表示图G中边的条数。

注意：线性表可以是空表，树可以是空树，但图不可以是空，即V一定是非空集

1.2 相关概念

无向图：若E是无向边（简称边) 的有限集合时，则图G为无向图。边是顶点的无序对，记为(v,w)或(w,v)，因为（v,w)=(w,v)，其中v、w是顶点。可以说顶点w和顶点v互为邻援点。边(v,w)依附于顶点w和v，或者说边(v,w)和顶点v、w相关联。
有向图：若E是有向边(也称弧)的有限集合时，则图G为有向图。弧是顶点的有序对，记为<v.w>，其中v、w是顶点，v称为弧尾，w称为弧头，<v.w>称为从顶点v到顶点w的弧，也称v邻接到w，或w邻接自v。<v, w> $\neq$ <w, v>。
简单图：① 不存在重复边； ② 不存在顶点到自身的边。
多重图：图G中某两个结点之间的边数多于一条，又允许顶点通过同一条边和自己关联,则G为多重图。
顶点的度、入度、出度

① 对于无向图：顶点v的度是指依附于该顶点的边的条数，记为TD(v)

在具有n个顶点、e条边的无向图中，

即：无向图的全部顶点的度的和等于边数的2倍
② 对于有向图：入度是以顶点v为终点的有向边的数目，记为ID(v);出度是以顶点v为起点的有向边的数目，记为OD(v)，顶点v的度等于其入度和出度之和，即TD(v) = ID(v) + OD(v)。

在具有n个顶点、e条边的有向图中，

即：有向图的全部顶点的入度的和与出度的和都等于边数，全部顶点的度的和等于边数的2倍。

其他的概念

连通图：若图G中任意两个顶点都是连通的，则称图G为连通图，否则称为非连通图。
强连通图：若图中任何一对顶点都是强连通的，则称此图为强连通图。
子图：设有两个图G = (V, E)和G’ = (V‘, E’)，若V‘是V的子集，且E’是E的子集，则称G‘是G的子图。
连通分量：无向图的极大连通子图称为连通分量。要求：子图必须连通，且包含
尽可能多的顶点和边

强连通分量：有向图中的极大强连通子图称为有向图的强连通分量。要求：子图必须强连通，同时保留尽可能多的边。

极小连通子图：边尽可能的少，但要保持连通
连通图的生成树（不唯一）：连通图的生成树是包含图中全部顶点的一个极小连通子图。要求：若图中顶点数为n，则它的生成树含有 n-1 条边。对生成树而言，若砍去它的一条边，则会变成非连通图，若加上一条边则会形成一个回路。

生成森林：在非连通图中，连通分量的生成树构成了非连通图的生成森林

边的权：在一个图中，每条边都可以标上具有某种含义的数值，该数值称为该边的权值。
带权图/网：边上带有权值的图称为带权图，也称网。
带权路径长度：当图是带权图时，一条路径上所有边的权值之和，称为该路径的带权路径长度。
无向完全图——无向图中任意两个顶点之间都存在边，共 $\frac{n(n-1)}{2}$ 条边
有向完全图——有向图中任意两个顶点之间都存在方向相反的两条弧,共n(n-1)条
稀疏图：边数很少的图称为稀疏图，反之称为稠密图，没有绝对的界限，

特殊形态的树：

树——不存在回路，且连通的无向图

有向树——一个顶点的入度为0、其余顶点的入度均为1的有向图，称为有向树。

n个顶点的树，必有n-1条边。

2. 图的存储

2.1 邻接矩阵法

2.1.1 图的邻接矩阵定义

图的邻接矩阵(Adjacency Matrix) 存储方式是用两个数组来表示图。一个一维数组存储图中顶点信息，一个二维数组(称为邻接矩阵)存储图中的边或弧的信息。
只要确定了顶点编号，图的邻接矩阵表示方式唯一

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

有向图的度:第i行的非零元素个数+ 第 i列的非零元素个数。

2.1.2 邻接矩阵法代码实现

#define MaxVertexNum 100	//顶点数目的最大值
#define INFINITY INT_MAX    // 定义无穷值
typedef char VertexType;	//顶点的数据类型
typedef int EdgeType;	//带权图中边上权值的数据类型
typedef struct{VertexType Vex[MaxVertexNum];	//顶点表EdgeType Edge[MaxVertexNum][MaxVertexNum];	//邻接矩阵，边表int vexnum, arcnum;	//图的当前顶点数和弧树
}MGraph;

2.1.3 性能分析：

数组实现的顺序存储，空间复杂度高，不适合存储稀疏图
（1）空间复杂度： $O\left ( \left | V \right |^{2} \right )$ ，只和顶点数相关，和实际的边数无关。，邻接矩阵法求顶点的度/出度/入度的时间复杂度为 O(|V|)
（2）适合用于存储稠密图。
（3）无向图的邻接矩阵是对称矩阵，可以压缩存储 (只存储上三角区或者下三角区)。

邻接矩阵法的性质

设图G的邻接矩阵为A（矩阵元素为0/1），则An的元素An[i][j]等于由顶点i到顶点j的长度为n的路径的数目

A^2[1][4],顶点1, 4为点A和D,则由顶点A到顶点D的长度为2的路径只有1条

2.2 邻接表法顺序+链式存储

2.2.1 性能分析：

无向图：边结点的数量是2|E|，整体空间复杂度为O(|V| + 2|E|)

有向图：边结点的数量是|E|，整体空间复杂度为 O(|V| + |E|)

2.2.2 特点

更适合用于稀疏图；
若G为无向图，则顶点的度为该顶点边表的长度若G为有向图，则顶点的出度为该顶点边表的长度，计算入度需要遍历整个邻接表；
邻接表不唯一，边表结点的顺序根据算法和输入不同可能会不同。

2.2.3 代码实现

#define MAXVEX 100	//图中顶点数目的最大值
type char VertexType;	//顶点类型应由用户定义
typedef int EdgeType;	//边上的权值类型应由用户定义
/*边表结点*/
typedef struct EdgeNode{int adjvex;	//该弧所指向的顶点的下标或者位置EdgeType weight;	//权值，对于非网图可以不需要struct EdgeNode *next;	//指向下一个邻接点
}EdgeNode;/*顶点表结点*/
typedef struct VertexNode{Vertex data;	//顶点域，存储顶点信息EdgeNode *firstedge	//边表头指针
}VertexNode, AdjList[MAXVEX];/*邻接表*/
typedef struct{AdjList adjList;int numVertexes, numEdges;	//图中当前顶点数和边数
}

2.3 十字链表

十字链表是有向图的一种链式存储结构

2.3.1 问题引入与解决

2.3.2 十字链表法性能分析

空间复杂度：O(|V|+|E|)

邻接表找顶点的入边不方便，邻接矩阵空间复杂度高 O(|V|2)

如何找到指定顶点的所有出边？——顺着绿色线路找
如何找到指定顶点的所有入边？——顺着橙色线路找

注意：十字链表只用于存储有向图

2.3.3 代码实现

#define MAX_VERTEX_NUM 20	//最大顶点数量struct EBox{				//边结点int i,j; 				//该边依附的两个顶点的位置（一维数组下标）EBox *ilink,*jlink; 	//分别指向依附这两个顶点的下一条边InfoType info; 			//边的权值
};
struct VexBox{VertexType data;EBox *firstedge; 		//指向第一条依附该顶点的边
};
struct AMLGraph{VexBox adjmulist[MAX_VERTEX_NUM];int vexnum,edgenum; 	//无向图的当前顶点数和边数
};