男的做直播哪个网站好,如何学好网站开发,郑州app开发哪家好,门户网站wordpress哪个比较好文章目录 图的定义图的存储邻接矩阵法邻接表法邻接矩阵法与邻接表法的区别 图的基本操作图的遍历广度优先遍历#xff08;BFS#xff09;深度优先遍历#xff08;DFS#xff09;图的遍历和图的连通性 图的定义
图G由顶点集V和边集E组成#xff0c;记为G(V,E)#xff0c;… 文章目录 图的定义图的存储邻接矩阵法邻接表法邻接矩阵法与邻接表法的区别 图的基本操作图的遍历广度优先遍历BFS深度优先遍历DFS图的遍历和图的连通性 图的定义
图G由顶点集V和边集E组成记为G(V,E)其中V(G)表示图G中顶点的有限非空集E(G)表示图G中顶点之间的关系边集合用|V|表示图G中顶点的个数也称图G的阶用|E|表示图G中边的条数
注意线性表可以是空表树可以是空树但图不可以是空即V一定是非空集
有向图 若E是有向边也称弧的有限集合时则图G为有向图。弧是顶点的有序对记为v,w其中v、w是顶点v称为弧尾w称为弧头。v,w 不等于 w,v
无向图 若E是无向边简称边的有限集合时则图G为无向图。边是顶点的有序对记为(v,w)。(v,w) 等于 (w,v)
简单图 ①不存在重复的边 ②不存在顶点到自身的边
多重图 图G中某两个结点之间的边数多于一条又允许顶点通过同一条边和自己关联
顶点的度、入读、出度 对于无向图顶点v的度是指依附于该顶点的边的条数记为TD(v) 对于有向图 入度是以顶点v为终点的有向边的数目记为ID(v) 出度是以顶点v为起点的有向边的数目记为OD(v) 顶点v的度等于其入度和出度之和即TD(v)ID(v)OD(v)
顶点-顶点的关系
- 路径——顶点到顶点之间的一条路径
回路——第一个顶点和最后一个顶点相同的路径称为回路或环简单路径——在路径序列中顶点不重复出现的路径称为简单路径路径长度——路径上边的数目点到点的距离——从顶点u出发到顶点v的最短路径若存在则此路径的长度称为从u到v的距离若从u到v根本不存在路径则该距离为无穷∞无向图中若从顶点v到顶点w有路径存在则称v和w是连通的有向图中若从顶点v到顶点w和从顶点w到顶点v之间都有路径则称这两个顶点是强连通的
连通图、强连通图 若图G中 任意两个顶点都是连通的则称图G为 连通图否则称为非连通图 对于n个顶点的无向图G 若G是连通图则最少有 n-1 条边 若G是非连通图则最多可能有条边 若图中 任何一对顶点都是强连通的则称此图为 强连通图 对于n个顶点的有向图G 若G是强连通图则最少有n条边形成回路 图的局部——子图 设有两个图G(V,E)和G’(V’,E’)若V’是V的子集且E’是E的子集则称G‘是G的 子图
若有满足V(G’)V(G)—— 顶点相同的子图G’则称其为G的 生成子图
连通分量 无向图中的 极大连通子图子图必须连通且包含尽可能多的顶点和边称为连通分量
强连通分量 有向图中的 极大强连通子图子图必须连通且包含尽可能多的顶点和边称为强连通分量
生成树 连通图的生成树是包含图中全部顶点的一个极小连通子图
若图中顶点数为n则它的生成树含有n-1条边对生成树而言若砍去它的一条边则会变成非连通图若加上一条边则会形成一个回路
生成森林 在非连通图中连通分量的生成树构成了非连通图的生成森林
边的权、带权图/网 边的权——在一个图中每条边都可以标上具有某种含义的数值该数值称为该边的权值 带权图/网——边上带有权值的图称为带权图也称网 带权路径长度——当图是带权图时一条路径上所有边的权值之和称为该路径的带权路径长度
几种特殊形态的图 无向完全图——无向图中任意两个顶点之间存在边 有向完全图——有向图中任意两个顶点之间都存在方向相反的两条弧 树——不存在回路且连通的无向图 有向树——一个顶点的入度为0其余顶点的入度均为1的有向图
总结 对于n个顶点的无向图G 所有顶点的度之和等于2|E| 若G是连通图则最少有n-1条边树若 |E|n-1则一定有回路 若G是非连通图则最多可能有条边 无向完全图共有条边 对于n个顶点的有向图G 所有顶点的出度之和入度之和 |E| 所有顶点的度之和等于 2|E| 若G是强连接图则最少有n条边形成回路 有向完全图共有条边 图的存储
邻接矩阵法
#define MaxVertexNum 100 // 顶点数目的最大值
typedef struct{char Vex[MaxVertexNum]; // 顶点表int Edge[MaxVertexNum][MaxVertexNum]; //邻接矩阵边表int vexnum,arcnum; // 图的当前顶点数和边数/弧数
}MGraph;邻接矩阵存储带权图
#define MaxVertexNum 100 // 顶点数量的最大值
#define INFINITY // 宏定义常量“无穷”
typedef char VertexType; // 顶点的数据类型
typedef int EdgeType; // 带权图中边上权值的数据类型
typedef struct{VertexType Vex[MaxVertexNum]; // 顶点EdgeType Edge[MaxVertexNum][MaxVertexNum]; // 边的权int vexnum,arcnum; // 图的当前顶点数和弧数
}MGraph;空间复杂度 O(|V|²) ——只和顶点数相关和实际的边数无关 适合于存储稠密图 无向图的邻接矩阵是对称矩阵可以压缩存储只存储上三角区/下三角区
邻接矩阵法的性质 设图G的邻接矩阵为A矩阵元素为0/1则Aⁿ的元素Aⁿ[ i ][ j ]等于由顶点 i 到顶点 j 的长度为 n 的路径的数目
举个 A | A | B | C | D | | A | 0 | 1 | 0 | 0 | | B | 1 | 0 | 1 | 1 | | C | 0 | 1 | 0 | 1 | | D | 0 | 1 | 1 | 0 |
A² [ 1 ] [ 4 ] a(1,1)a(1,4) a(1,2)a(2,4) a(1,3)a(3,4) a(1,4)a(4,4) 1 说明 顶点A到顶点D的长度为2的路径有1条
邻接表法
邻接表法——顺序链式存储
// 边/弧
typedef struct ArcNode{int adjvex; // 边/弧指向哪个结点struct ArcNode *next; // 指向下一条弧的指针
}ArcNode;// 顶点
typedef struct VNode{VertexType data; // 顶点信息ArcNode *first; // 第一条边/弧
}VNode,AdjList[MaxVertexNum];// 用邻接表存储的图
typedef struct{AdjList vertices;int vexnum,arcnum;
}ALGraph;无向图——边结点的数量是2|E|整体空间复杂度为 O(|V|2|E|) 有向图——边结点的数量是|E|,整体空间复杂度为 O(|V||E|) 邻接矩阵法与邻接表法的区别
邻接表邻接矩阵空间复杂度无向图O(∣V∣2∣E∣)有向图O(∣V∣∣E∣)O(∣V∣²)适用于存储稀疏图存储稠密图表示方式不唯一唯一计算度/出度/入度计算有向图的度、入度不方便其余很方便必须遍历对应行或列找相邻的边找有向图的入边不方便其余很方便必须遍历对应行或列
图的基本操作 Adjacent(G,x,y)判断图G是否存在边x,y或(x,y) 邻接矩阵————O(1) 邻接表 ————O(1)~O(|V|) Neighbors(G,x)列出图G中与结点x邻接的边 无向图 邻接矩阵————O(|V|) 邻接表 ————O(1)~O(|V|) 有向图 邻接矩阵————O(|V|) 邻接表 ————出度O(1)~O(|V|)入度O(|E|) InsertVertex(G,x)在图G中插入顶点x 邻接矩阵————O(1) 邻接表 ————O(1) DeleteVertex(G,x)在图G中删除顶点x 无向图 邻接矩阵————O(|V|) 邻接表 ————O(1)~O(|V|) 有向图 邻接矩阵————O(|V|) 邻接表 ————删出边O(1)~O(|V|)删入边O(|E|) AddEdge(G,x,y)若无向边(x,y)或有向边x,y不存在则向图G中添加该边 邻接矩阵————O(1) 邻接表 ————O(1) FirstNeighbor(G,x)求图G中顶点x的第一个邻接点若有则返回顶点号若没有邻接点或图中不存在x则返回-1 无向图 邻接矩阵————O(1)~O(|V|) 邻接表 ————O(1) 有向图 邻接矩阵————O(1)~O(|V|) 邻接表 ————找出边O(1)找入边O(1)~O(|E|) NextNeighbor(G,x,y)假设图G中顶点y是顶点x的一个邻接点返回除y之外顶点x的下一个邻接点的顶点号若y是x的最后一个邻接点则返回-1 邻接矩阵————O(1)~O(|V|) 邻接表 ————O(1) Get_edge_value(G,x,y)获取图G中边(x,y)或x,y对应的权值 Set_edge_value(G,x,y)设置图G中边(x,y)或x,y对应的权值
图的遍历
广度优先遍历BFS
图的广度优先遍历和树的层次遍历很相似 代码实现
bool visited[MAX_VERTEX_NUM]; // 访问标记数组// 广度优先遍历
void BFS(Graph G, int v){ // 从顶点v出发广度优先遍历图Gvisit(v); // 访问初始顶点vvisited[v] true; // 对v做已访问标记EnQueue(Q,v); // 顶点v入队列Qwhile(!isEmpty(Q)){DeQueue(Q,v); // 顶点v出队列for(wFirstNeighbor(G,v);w0;wNextNeighbor(G,v,w)){// 检测v所有邻接点if(!visited[w]){ // w为v的未访问的邻接顶点visit(w); // 访问顶点wvisited[w]true; // 对w做已访问标记EnQueue(Q,w); // 顶点w入队列}}}
}
如果是非连通图则无法遍历完所有的结点以上的代码就出现了Bug 所以先对所有的顶点遍历,还需要加上以下代码
void BfsTraverse(Graph G){for(i0;iG.vexnum;i){visited[i]false; // 访问标记数组}InitQueue(Q); // 初始化辅助队列Qfor(i0;iG.vexnum;i){ // 从0号顶点开始遍历if(!visited[i]) // 对每一个连通分量调用依次BFSBFS(G,i); // vi未访问过从vi开始BFS}
}结论对于无向图调用BFS函数的次数连通分量数
注意 同一个图的邻接矩阵表示方式唯一因此广度优先遍历序列唯一 同一个图的邻接表表示方式不唯一因此广度优先遍历序列不唯一
复杂度分析 对于邻接矩阵存储的图O(|v|²) 对于邻接表存储的图O(|V||E|)
广度优先生成树 由广度优先遍历过程确定将遍历过程中没有经过的边去掉
由于邻接表的表示方式不唯一因此基于邻接表的广度优先生成树也不唯一
遍历非连通图可以得到广度优先生成森林
深度优先遍历DFS
图的深度优先遍历和树的先根遍历很相似
bool visited[MAX_VERTEX_NUM]; // 访问标记数组
void DFSTraverse(Graph G){for(v0;vG.vexnum;v)visited[v]false;for(v0;vG.vexnum;v)if(!visited[v])DFS(G,v)
}void DFS(Graph G,int v){visit(v);visited[v]true;for(wFirstNeighbor(G,v);w0;wNextNeighbor(G,v,w)){if(!visited[w]){DFS(G,w);}}
}结论对于无向图调用D FS函数的次数连通分量数
复杂度分析 空间复杂度O(|v|) 对于邻接矩阵存储的图O(|v|²) 对于邻接表存储的图O(|V||E|)
深度优先遍历序列
注意 同一个图的邻接矩阵表示方式唯一因此深度优先遍历序列唯一 同一个图的邻接表表示方式不唯一因此深度优先遍历序列不唯一
深度优先生成树 由深度优先遍历过程确定将遍历过程中没有经过的边去掉
由于邻接表的表示方式不唯一因此基于邻接表的深度优先生成树也不唯一
遍历非连通图可以得到深度优先生成森林
图的遍历和图的连通性 无向图 DFS/BFS函数调用次数连通分量数 有向图 1、若从起始顶点到其他顶点都有路径则只需要调用1次DFS/BFS函数 2、对于强连通图从任一顶点出发都只需要调用1次DFS/BFS函数
