一个营销型网站模板,wordpress 8.0怎么登录,做酒店网站多少钱,免费奖励的网站有哪些数据结构《图论》
图的性质
一、无向图#xff08;Undirected Graph#xff09;
定义 由一组顶点#xff08;Vertex#xff09;和一组无向边#xff08;Edge#xff09;构成。 每条无向边用一条无方向的线段连接两个顶点#xff0c;记为 ( (u, v) )#xff0c;其中…数据结构《图论》
图的性质
一、无向图Undirected Graph
定义 由一组顶点Vertex和一组无向边Edge构成。 每条无向边用一条无方向的线段连接两个顶点记为 ( (u, v) )其中 ( u ) 和 ( v ) 是顶点且 ( u \neq v )。若允许自环可表示为 ( (u, u) )。 核心性质 性质 定义与特点
顶点集 记为 ( V )大小为 ( V )。 边集 记为 ( E )每条边是无序对 ( {u, v} \subseteq V )大小为 ( E )。若允许多重边则边可重复出现。 度Degree 顶点 ( u ) 的度为与之相连的边的数量即 ( d(u) \text{number of edges incident to } u )。无向图中每个边贡献度数 1。 简单图 不含自环且不含多重边的无向图。 连通性 若两个顶点之间存在至少一条路径则称它们是连通的否则属于不同的连通分量Connected Component。 桥Bridge 若删除某条边后图的连通分量数目增加则该边为桥。桥是图中唯一的连接两个部分的边。 割点Articulation Point 删除该顶点后图的连通分量数目增加则该顶点为割点。
特殊类型
树Tree无环且连通的无向图满足 ( E V - 1 )。森林Forest若干棵互不连通的树的集合。完全图Complete Graph每对顶点之间均存在一条边记为 ( K_n )( n ) 个顶点。环图Cycle Graph所有顶点构成一个单一环满足 ( E V )。 二、有向图Directed Graph
定义 由一组顶点和一组有向边Directed Edge构成。 每条有向边用箭头表示方向记为 ( (u, v) )其中 ( u ) 是起点Source( v ) 是终点Target。允许自环( u v )和多重边。 核心性质 性质 定义与特点
顶点集 记为 ( V )大小为 ( V )。 边集 记为 ( E )每条边是有序对 ( (u, v) \subseteq V \times V )允许重复边多重边。 入度InDegree 顶点 ( v ) 的入度为指向它的边的数量即 ( d_{\text{in}}(v) \sum_{u \in V} \text{number of edges } (u, v) )。 出度OutDegree 顶点 ( u ) 的出度为从它出发的边的数量即 ( d_{\text{out}}(u) \sum_{v \in V} \text{number of edges } (u, v) )。 强连通分量SCC 若有向图中任意两个顶点均可互相到达则该子图为强连通分量。强连通分量是极大强连通子图。 弱连通分量 将有向图视为无向图后其连通性称为弱连通性。 路径与环 路径顶点序列 ( v_0 \rightarrow v_1 \rightarrow \cdots \rightarrow v_k )边方向一致。 环起点和终点相同的路径且至少包含一条边。
特殊类型
有向树DAG中的树结构父节点到子节点的单向边构成无环。竞赛图Tournament Graph每对顶点之间恰好存在一条有向边。完全有向图Complete Directed Graph每对顶点之间存在两条方向相反的有向边记为 ( \overleftrightarrow{K_n} )。欧拉回路与路径 - 欧拉回路存在一条回路遍历每条边恰好一次且起点终点需满足所有顶点的入度出度。 - 欧拉路径存在一条路径遍历每条边恰好一次且起点≠终点需满足恰有一个顶点出度入度1起点另一个顶点入度出度1终点。 三、无向图 vs 有向图的对比 对比维度 无向图 有向图
边方向性 边无方向( (u, v) \equiv (v, u) )。 边有方向( (u, v) \neq (v, u) )。 度 每个边贡献顶点度数 1。 分为入度和出度每条边仅贡献起点的出度 1 和终点的入度 1。 连通性 弱连通性等价于无向图的连通性。 强连通分量是更严格的连通条件。弱连通性需忽略边方向后判断。 环的存在性 环至少需要三个顶点三角形环。 可以存在自环单个顶点的环。 典型算法 BFS/DFS、最小生成树Prim/Kruskal、最短路径Dijkstra未加权。 Tarjan算法找强连通分量、BellmanFord检测负权环、拓扑排序。 四、数学表示与存储
数学表示 邻接矩阵Adjacency Matrix 无向图对称矩阵 ( A_{uv} A_{vu} )。有向图非对称矩阵 ( A_{uv} ) 表示边 ( u \rightarrow v ) 是否存在。 邻接表Adjacency List 无向图每个顶点维护相邻顶点列表边存储两次如 ( u \rightarrow v ) 和 ( v \rightarrow u )。有向图每个顶点维护出边列表边仅存储一次。 存储复杂度 数据结构 空间复杂度最坏情况
邻接矩阵 ( O(V^2) ) 邻接表 ( O(V E) ) 五、应用场景
无向图社交网络关系建模、交通路线规划、分子结构分析。有向图网页链接分析PageRank、任务调度依赖关系、神经网络建模。 查考点 一、基础概念与性质 顶点与边 顶点集 ( V ) 和边集 ( E )边的表示为无序对 ( {u, v} )。简单图无自环边 ( {u, u} ) 不允许且无多重边。多重图允许多条边连接同一对顶点。 度Degree 每个顶点的度数 ( d(u) \text{与该顶点相连的边数} )。奇点与偶点度数为奇数的顶点称为奇点否则为偶点。握手定理图中所有顶点的度数之和为偶数每条边贡献两次度数。 连通性 连通图任意两个顶点之间存在至少一条路径。连通分量图的极大连通子图非连通图的每个子图都是一个连通分量。强连通分量仅适用于有向图无向图的弱连通性即忽略方向后的连通性。 二、图的遍历 广度优先搜索BFS 层序遍历从起点出发逐层扩展记录访问顺序。应用寻找最短路径无权图、连通分量标记。 深度优先搜索DFS 递归或栈实现优先探索某一分支到底。应用检测环、生成树、拓扑排序需配合有向图。 三、特殊图结构 树与森林 树无环且连通的无向图满足 ( E V - 1 )。森林多个互不连通的树的集合。二叉树每个节点最多有两个子节点左、右子节点前序/中序/后序遍历。 完全图与环图 完全图每对顶点间均有一条边( K_n )。环图所有顶点构成单一环( C_n )满足 ( E V )。 欧拉回路与路径 欧拉回路存在一条回路经过所有边恰好一次条件是所有顶点度数为偶数。欧拉路径存在一条路径经过所有边恰好一次条件是恰有两个奇点作为起点和终点。 四、经典算法 最小生成树MST Prim算法贪心策略每次选择当前顶点到生成树的最小边。Kruskal算法基于边权排序使用并查集Union-Find避免环。 最短路径算法 Dijkstra算法适用于无权图或边权非负的情况找到单源最短路径。Floyd-Warshall算法计算所有顶点对之间的最短路径多源最短路径。 连通分量统计 使用DFS/BFS遍历整个图标记未访问的顶点统计连通分量个数。 五、高频题型与解题思路 理论题 判断图的连通性通过BFS/DFS遍历后检查是否所有顶点都被访问。证明握手定理利用边对度数的贡献进行归纳或数学推导。 编程题 构建图的邻接表无向图需为每条边存储两次如 ( u \rightarrow v ) 和 ( v \rightarrow u )。求最小生成树实现Kruskal算法需排序边并用并查集去重。检测欧拉回路统计所有顶点度数是否均为偶数。 应用题 交通路网建模城市作为顶点道路作为边求解最短路径或最小生成树。社交网络分析用户关系建模为无向图寻找连通分量或社区划分。 六、易错点总结
无向图的边存储邻接表中每条边需双向存储邻接矩阵需保证对称性。连通分量与强连通分量无向图的连通分量无需考虑方向而有向图的强连通分量需严格满足双向可达。度数计算自环边贡献度数 1多重边需逐条计数。 七、推荐练习
手写代码实现 BFS/DFS遍历无向图。Kruskal算法生成最小生成树。 在线平台题目 LeetCode 1274. Minimum Window Substring需图遍历思想。牛客网 1228. 括号生成树结构的应用。 通过掌握上述知识点并配合大量练习可以系统性地应对无向图相关的理论考察和编程问题。
#include stdio.h
#include stdbool.h#define MAX_VERTICES 4 // 定义最大顶点数// 定义图的结构体
typedef struct {int numVertices; // 顶点数bool adjMatrix[MAX_VERTICES][MAX_VERTICES]; // 邻接矩阵char vertexNames[MAX_VERTICES]; // 顶点名称
} Graph;// 函数声明
void initializeGraph(Graph* graph, int numVertices, char vertexNames[]);
void addEdge(Graph* graph, int src, int dest);
void printAdjMatrix(const Graph* graph); // 使用 const 防止修改// 初始化图
void initializeGraph(Graph* graph, int numVertices, char vertexNames[]) {graph-numVertices numVertices;// 初始化顶点名称for (int i 0; i numVertices; i) {graph-vertexNames[i] vertexNames[i];}// 初始化邻接矩阵for (int i 0; i numVertices; i) {for (int j 0; j numVertices; j) {graph-adjMatrix[i][j] false; // 初始化为 false表示没有边}}
}// 添加边
void addEdge(Graph* graph, int src, int dest) {// 无向图需要对称设置graph-adjMatrix[src][dest] true;graph-adjMatrix[dest][src] true;
}// 打印邻接矩阵
void printAdjMatrix(const Graph* graph) {printf(邻接矩阵\n);for (int i 0; i graph-numVertices; i) {for (int j 0; j graph-numVertices; j) {printf(%d , graph-adjMatrix[i][j]);}printf(\n);}
}int main() {// 定义图的顶点名称char vertexNames[MAX_VERTICES] { A, B, C, D };// 创建图并初始化Graph graph;initializeGraph(graph, MAX_VERTICES, vertexNames);// 添加边addEdge(graph, 0, 1); // A - BaddEdge(graph, 0, 2); // A - CaddEdge(graph, 1, 3); // B - DaddEdge(graph, 2, 3); // C - D// 打印邻接矩阵printAdjMatrix(graph);return 0;
}图的表示
在代码中图是通过邻接矩阵表示的。邻接矩阵是一个二维数组 adjMatrix其中
adjMatrix[i][j] true 表示顶点 i 和顶点 j 之间有一条边。adjMatrix[i][j] false 表示顶点 i 和顶点 j 之间没有边。
对于无向图邻接矩阵是对称的即 adjMatrix[i][j] adjMatrix[j][i]。 顶点编号
在代码中顶点被编号为
A → 0B → 1C → 2D → 3 添加边的操作
addEdge 函数的定义如下
void addEdge(Graph *graph, int src, int dest) {// 无向图需要对称设置graph-adjMatrix[src][dest] true;graph-adjMatrix[dest][src] true;
}它的作用是在邻接矩阵中设置两个顶点之间的边。由于是无向图需要同时设置 adjMatrix[src][dest] 和 adjMatrix[dest][src]。 具体操作分析
1. 添加边 A - B
addEdge(graph, 0, 1); // A - Bsrc 0Adest 1B。设置 adjMatrix[0][1] true表示 A 和 B 之间有一条边。设置 adjMatrix[1][0] true表示 B 和 A 之间有一条边。
邻接矩阵更新为
A [ 0, 1, 0, 0 ]
B [ 1, 0, 0, 0 ]
C [ 0, 0, 0, 0 ]
D [ 0, 0, 0, 0 ]2. 添加边 A - C
addEdge(graph, 0, 2); // A - Csrc 0Adest 2C。设置 adjMatrix[0][2] true表示 A 和 C 之间有一条边。设置 adjMatrix[2][0] true表示 C 和 A 之间有一条边。
邻接矩阵更新为
A [ 0, 1, 1, 0 ]
B [ 1, 0, 0, 0 ]
C [ 1, 0, 0, 0 ]
D [ 0, 0, 0, 0 ]3. 添加边 B - D
addEdge(graph, 1, 3); // B - Dsrc 1Bdest 3D。设置 adjMatrix[1][3] true表示 B 和 D 之间有一条边。设置 adjMatrix[3][1] true表示 D 和 B 之间有一条边。
邻接矩阵更新为
A [ 0, 1, 1, 0 ]
B [ 1, 0, 0, 1 ]
C [ 1, 0, 0, 0 ]
D [ 0, 1, 0, 0 ]4. 添加边 C - D
addEdge(graph, 2, 3); // C - Dsrc 2Cdest 3D。设置 adjMatrix[2][3] true表示 C 和 D 之间有一条边。设置 adjMatrix[3][2] true表示 D 和 C 之间有一条边。
邻接矩阵更新为
A [ 0, 1, 1, 0 ]
B [ 1, 0, 0, 1 ]
C [ 1, 0, 0, 1 ]
D [ 0, 1, 1, 0 ]最终邻接矩阵
经过上述操作后邻接矩阵如下 A B C D
A [ 0, 1, 1, 0 ]
B [ 1, 0, 0, 1 ]
C [ 1, 0, 0, 1 ]
D [ 0, 1, 1, 0 ]可视化图结构
根据邻接矩阵图的结构可以可视化如下
A -- B
| \ |
| \ |
C -- DA 与 B、C 相连。B 与 A、D 相连。C 与 A、D 相连。D 与 B、C 相连。 总结
addEdge 函数通过修改邻接矩阵来表示顶点之间的边。对于无向图需要同时设置 adjMatrix[src][dest] 和 adjMatrix[dest][src]。通过多次调用 addEdge可以逐步构建出完整的图结构。
邻接矩阵的算法分析
邻接矩阵是图的一种常见表示方法特别适用于稠密图即边数接近顶点数平方的图。以下是对邻接矩阵的算法分析以及优劣分析从时间复杂度、空间复杂度、适用场景等方面进行详细科学分析。 1. 邻接矩阵的定义
邻接矩阵是一个二维数组 matrix其中
matrix[i][j] 1或权重值表示顶点 i 和顶点 j 之间有一条边。matrix[i][j] 0或无穷大表示顶点 i 和顶点 j 之间没有边。
对于无向图邻接矩阵是对称的对于有向图邻接矩阵不一定对称。 2. 算法分析
(1) 空间复杂度
邻接矩阵的空间复杂度为 O(V²)其中 V 是顶点数。无论图中实际有多少条边邻接矩阵都需要存储 V × V 个元素。对于稀疏图边数远小于顶点数平方邻接矩阵会浪费大量空间。
(2) 时间复杂度
查询两个顶点之间是否有边
时间复杂度为 O(1)。直接访问 matrix[i][j] 即可判断顶点 i 和顶点 j 之间是否有边。
遍历某个顶点的所有邻居
时间复杂度为 O(V)。需要遍历该顶点对应的整行或整列检查哪些位置的值为 1。
添加或删除一条边
时间复杂度为 O(1)。直接修改 matrix[i][j] 和 matrix[j][i]无向图即可。
初始化邻接矩阵
时间复杂度为 O(V²)。需要初始化一个 V × V 的二维数组。 3. 优劣分析
(1) 优点 查询边的存在性高效 时间复杂度为 O(1)适合需要频繁查询边是否存在的场景。 适合稠密图 当图的边数接近顶点数平方时邻接矩阵的空间利用率较高。 易于实现 邻接矩阵的实现简单直观适合初学者理解和实现。 支持快速修改 添加、删除或修改边的时间复杂度为 O(1)。 适合存储带权图 邻接矩阵可以直接存储边的权重适合需要处理带权图的场景。 (2) 缺点 空间复杂度高 空间复杂度为 O(V²)对于稀疏图会浪费大量空间。 遍历邻居效率低 遍历某个顶点的所有邻居需要 O(V) 时间即使该顶点的实际邻居很少。 不适合动态图 如果图的顶点数动态变化邻接矩阵需要重新分配和复制数据效率较低。 无法高效存储稀疏图 对于稀疏图邻接表Adjacency List是更优的选择。 4. 适用场景
(1) 适合使用邻接矩阵的场景 稠密图 边数接近顶点数平方的图邻接矩阵的空间利用率高。 需要频繁查询边的存在性 例如某些图算法需要快速判断两个顶点是否相邻。 带权图 邻接矩阵可以直接存储边的权重适合处理带权图。 小规模图 当顶点数较少时邻接矩阵的空间开销可以接受。 (2) 不适合使用邻接矩阵的场景 稀疏图 边数远小于顶点数平方的图邻接矩阵会浪费大量空间。 大规模图 当顶点数很大时邻接矩阵的空间开销会变得不可接受。 动态图 顶点数动态变化的图邻接矩阵的调整成本较高。 5. 与邻接表的对比
特性邻接矩阵邻接表空间复杂度O(V²)O(V E)查询边的存在性O(1)O(degree(V))遍历邻居O(V)O(degree(V))添加边O(1)O(1)删除边O(1)O(degree(V))适合的图类型稠密图稀疏图实现复杂度简单较复杂 6. 总结
邻接矩阵适合稠密图、带权图以及需要频繁查询边存在性的场景。邻接表适合稀疏图、大规模图以及需要高效遍历邻居的场景。在实际应用中应根据图的特点稠密或稀疏和操作需求查询、遍历、修改等选择合适的表示方法。
