网站建设案例百度云,上海网站排名推广,秘密直播,网站备案成功后可以改吗文章目录 图的概念图的基本概念图的类型图的表示方法 图的相关基本概念1. 路径#xff08;Path#xff09;2. 连通性#xff08;Connectivity#xff09;3. 图的度#xff08;Degree#xff09;4. 子图#xff08;Subgraph#xff09;5. 生成树#xff08;Spanning Tr… 文章目录 图的概念图的基本概念图的类型图的表示方法 图的相关基本概念1. 路径Path2. 连通性Connectivity3. 图的度Degree4. 子图Subgraph5. 生成树Spanning Tree6. 二分图Bipartite Graph7. 拓扑排序Topological Sort8. 欧拉图和哈密顿图 实现图邻接矩阵实现图邻接矩阵的基本框架核心接口 邻接表实现图邻接表实现图的基本框架核心接口 总结 图的概念
图Graph是离散数学中的一种重要数据结构用于描述对象称为顶点或节点之间的关系称为边。图可以表示各种事物之间的连接关系比如网络中的路由器、社交网络中的用户、城市之间的道路等。
图的基本概念 顶点Vertex 图中的基本单位也称为节点Node。一个图通常由若干个顶点组成用来表示实体或对象。 边Edge 顶点之间的连接关系称为边。边可以是有方向的有向图或无方向的无向图。在无向图中边表示双向关系在有向图中边表示单向关系。 有向图Directed Graph, Digraph 在有向图中边是有方向的表示从一个顶点指向另一个顶点的单向连接。通常用有向边表示诸如“影响”或“依赖”的关系。 无向图Undirected Graph 无向图中的边没有方向表示两个顶点之间的对称关系如“相邻”或“连接”。 邻接Adjacency 如果两个顶点之间有一条边连接这两个顶点称为邻接的。 度Degree 一个顶点的度是连接到该顶点的边的数目。在有向图中区分入度In-degree和出度Out-degree分别表示进入该顶点和从该顶点发出的边的数量。
图的类型 稀疏图Sparse Graph 边的数量远远少于顶点数量的平方E V²大部分顶点之间没有边连接。 稠密图Dense Graph 边的数量接近顶点数量的平方E ≈ V²大多数顶点之间有边连接。 加权图Weighted Graph 图中的每条边带有一个权重用来表示顶点之间的某种度量如距离、成本或容量。 连通图Connected Graph 对于无向图若任意两个顶点之间都有路径相连则称为连通图。有向图中则需区分强连通和弱连通。 简单图Simple Graph 不包含自环和多重边的图。自环是指从顶点到自身的边多重边是指两个顶点之间存在多条边。 完全图Complete Graph 图中任意两个顶点之间都有边相连通常表示为 K n K_n Kn其中 n n n 是顶点数。
图的表示方法 邻接矩阵Adjacency Matrix 使用一个二维矩阵来表示顶点之间的连接关系矩阵中的元素表示边的存在性或权重。 邻接表Adjacency List 对每个顶点维护一个链表或数组来存储与之相邻的顶点列表适合稀疏图。 边集列表Edge List 直接列出图中所有的边用边的起点和终点来描述适合图的遍历或算法中的具体操作。
图的相关基本概念
在理解图的结构和操作时有一些与图密切相关的概念有助于更好地分析和处理图的算法和应用。
1. 路径Path
路径是在图中从一个顶点到另一个顶点的行进序列它由一系列边和顶点组成。根据图的类型和要求路径可以分为几类
简单路径Simple Path路径中的顶点不重复出现。回路Cycle路径的起点和终点是同一个顶点且路径中的其他顶点不重复。
2. 连通性Connectivity
图的连通性描述了图中顶点与顶点之间的可达性。
连通图Connected Graph对于无向图如果从任意一个顶点能到达其他所有顶点则图是连通的。强连通图Strongly Connected Graph对于有向图如果任意两个顶点之间都有路径相通则图是强连通的。弱连通图Weakly Connected Graph对于有向图如果将其所有边看作无向边能够使整个图连通则图是弱连通的。
3. 图的度Degree
图中一个顶点的度表示与该顶点连接的边的数量。
入度In-degree有向图中指向该顶点的边的数量。出度Out-degree有向图中从该顶点发出的边的数量。
4. 子图Subgraph
子图是从原始图中选取部分顶点和边构成的图。常见的子图类型包括
生成子图Spanning Subgraph包含图的所有顶点但边可能有所删减。诱导子图Induced Subgraph包含图中某些顶点及这些顶点之间的所有边。
5. 生成树Spanning Tree
生成树是无向图的一个子图包含图中的所有顶点且是一个树形结构无环、连通。
最小生成树Minimum Spanning Tree, MST在加权图中生成树的边权和最小的生成树。
生成树 最小生成树
6. 二分图Bipartite Graph
二分图是一种特殊的图可以将顶点集合分为两个不相交的子集且所有边都连接两个不同子集中的顶点而子集中没有内部连接。
7. 拓扑排序Topological Sort
对于有向无环图DAG拓扑排序是一种将顶点按依赖关系线性排序的算法通常用于解决调度、依赖管理等问题。
8. 欧拉图和哈密顿图
欧拉路径Eulerian Path经过图中每条边一次且仅一次的路径。如果这样的路径是闭合的即路径的起点和终点相同则称为欧拉回路Eulerian Circuit。哈密顿路径Hamiltonian Path经过图中每个顶点一次且仅一次的路径。如果这样的路径是闭合的则称为哈密顿回路Hamiltonian Circuit。
实现图
邻接矩阵实现图 如果是无向图的话那么邻接矩阵就是沿着对角线对称的。 如果是无向图的话那么就可以通过压缩只存储一半。 除了需要一个存储权值的邻接矩阵我们还需要一个vector来存储顶点如果涉及到邻接矩阵那么就会涉及到下标所以我们应该还需要一个顶点映射下标的map。
邻接矩阵的基本框架 // 顶点 weight 有向图/无向图 templateclass V, class W, W MAX_W INT_MAX, bool Direction falseclass Graph{public:private:vectorV _vertexs; //顶点集合mapV, int _indexMap; //顶点对应下标的关系顶点----下标vectorvectorW _matrix; //邻接矩阵};
}
核心接口
初始化
Graph(const V* a, size_t n)
{// 开辟n个空间_vertexs.resize(n);for (size_t i 0;i n;i){_vertexs[i] a[i];//顶点-----下标_indexMap[a[i]] i;}_matrix.resize(n);//权值用MAX_W初始化for (size_t i 0;i n;i) _matrix[i].resize(n, MAX_W);
}获取顶点的下标
size_t GetVertexIndex(const V v)
{auto it _indexMap.find(v);if (it ! _indexMap.end()) return it-second;else{// 抛异常出去throw invalid_argument(顶点不存在);// 过编译器逻辑return -1;}
}通过map的接口find找到v对应的下标如果it为end()说明没有这个顶点直接抛异常如果存在则返回对应的下标 添加边
// 原点 目标点 权值
void AddEdge(const V src, const V dst, const W w)
{// 获取原点下标size_t srci GetVertexIndex(src);size_t dsti GetVertexIndex(dst);_matrix[srci][dsti] w;// 无向图添加两个权值if (Direction false) _matrix[dsti][srci] w;
}找到原点和目标点对应的下标如果是有向图的话只需要添加原点到目标点的边如果是无向图的话就需要反向添加一下目标点到原点的边了。
邻接表实现图
邻接表是图的一种存储表示方法常用于存储稀疏图即边数相对较少的图。它通过每个顶点对应一个链表或数组来记录与其相邻的顶点。邻接表的空间复杂度相对较小适合存储大规模图。 对于无向图来说不存在入度和出度的概念所以只需要一个邻接表表示下标的邻接表就是用来表示边的集合。 拿第一个点为例这里使用一个结构体来维护的这个结构体中有指向一下下一个边集的指针还有一个权值和目标点的下标。 我们说形象一点
类似于哈希桶的那个做法
邻接表实现图的基本框架
templateclass W
struct Edge
{int _dsti; //目标点的下标W _w; //权值EdgeW* _next;Edge(int dsti,const W w):_dsti(dsti),_w(w),_next(nullptr){}
};
// 顶点 weight 有向图/无向图
templateclass V, class W,bool Direction false
class Graph
{typedef EdgeW Edge;
public:private:vectorV _vertexs; //顶点集合mapV, int _indexMap; //顶点对应下标的关系顶点----下标vectorEdge* _tables; //邻接表
};核心接口
初始化
Graph(const V* a, size_t n)
{// 开辟n个空间_vertexs.resize(n);for (size_t i 0;i n;i){_vertexs[i] a[i];//顶点-----下标_indexMap[a[i]] i;}_tables.resize(n,nullptr);//给tables开辟n个空间n个顶点
}获取顶点对应下标
size_t GetVertexIndex(const V v)
{auto it _indexMap.find(v);if (it ! _indexMap.end()) return it-second;else{// 抛异常出去throw invalid_argument(顶点不存在);// 过编译器逻辑return -1;}
}添加边
void AddEdge(const V src, const V dst, const W w)
{// 获取原点下标size_t srci GetVertexIndex(src);size_t dsti GetVertexIndex(dst);//1 -- 2//原点到目标的权值Edge* eg new Edge(dsti, w);//这里进行头插eg-_next _tables[srci];_tables[srci] eg;//无向图进行特殊处理//2 -- 1if (Direction false){//反向指向Edge* eg new Edge(srci, w);eg-_next _tables[dsti];_tables[dsti] eg;}
}这个和邻接矩阵就不一样邻接表中添加边应该先创建一个对应边的结构体然后将这个结构体头插到原点对应下标的边集的位置上如果是无向图的话需要反向添加一条目标点到原点的边。注意头插之后需要改变头的位置
总结
通过本篇文章的介绍我们初步了解了图的基本概念、图的表示方法如邻接矩阵和邻接表、以及图中的各种基本性质。图论作为计算机科学和数学中的一个重要分支其应用范围广泛从网络设计到路径规划都有着广泛的应用场景。
在接下来的学习中我们可以进一步探讨更高级的图算法如最短路径算法Dijkstra、Bellman-Ford 等、图的遍历算法深度优先搜索、广度优先搜索、以及图的连通性和最小生成树等高级主题。这些内容将为解决更复杂的实际问题提供坚实的理论基础。
图论的世界广阔而有趣期待你能在之后的学习和实践中不断挖掘其奥秘
