国内自适应网站案例,数据分析网,百色市右江区了建设局网站,甘肃省建设工程网站何为图论
见名知意#xff0c;图论 (Graph Theory) 就是研究 图 (Graph) 的数学理论和方法。图是一种抽象的数据结构#xff0c;由 节点 (Node) 和 连接这些节点的 边 (Edge) 组成。图论在计算机科学、网络分析、物流、社会网络分析等领域有广泛的应用。
如下#xff0c;这…何为图论
见名知意图论 (Graph Theory) 就是研究 图 (Graph) 的数学理论和方法。图是一种抽象的数据结构由 节点 (Node) 和 连接这些节点的 边 (Edge) 组成。图论在计算机科学、网络分析、物流、社会网络分析等领域有广泛的应用。
如下这就是一个图可以看到这个图有 5 5 5 个顶点分别编号为 { 0 , 1 , 2 , 3 , 4 } \{0, 1, 2, 3, 4\} {0,1,2,3,4}。同时这个图有 4 4 4 条边例如在顶点 2 2 2 和 顶点 4 4 4 之间存在着一条边。 图的基本概念
在详细讲解图论和有关图论算法之前先来了解一下在图论中的一些基本表述和规范。
图 (Graph)图是一种由一组顶点和一组边组成的数据结构记做 G ( V , E ) G (V, E) G(V,E)其中 V V V 代表顶点集合 E E E 代表边集合。顶点 (Vertex)顶点是图的基本单位也称为节点。边 (Edge)一条边是连接两个顶点的线段或弧。可以是无向的也可以是有向的。一条边可以记做为 ( u , v ) (u, v) (u,v)。在无向图中若存在一条 ( u , v ) (u, v) (u,v)表示可以从 u u u 点直接走到 v v v 点反之亦然。但若在有向图中存在一条边 ( u , v ) (u, v) (u,v)表示可以从 u u u 节点直接走向 v v v 节点如果不存在一条边 v , u v, u v,u那么 v v v 节点就没有办法直接走向 u u u 节点。无向图 (Undirected Graph)图中的边没有方向即 ( u , v ) (u, v) (u,v) 和 ( v , u ) (v, u) (v,u) 是同一条边。有向图 (Directed Graph/ Digraph)图中的边有方向即 ( u , v ) (u, v) (u,v) 和 ( v , u ) (v, u) (v,u) 不是同一条边。简单图 (Simple Graph)表示含有重边两个顶点之间的多条边和自环顶点到自身的边的图。多重图 (Multigraph)允许有重边和自环的图。边权 (Weight of an Edge)一般表示经过这一条边的代价代价一般是由命题人定义的。
如下图就是一个有向的简单图通常来说在有向图中边的方向用箭头来表示 如下图就是一个无向的多重图其中存在两条边可以从顶点 5 5 5 到顶点 2 2 2 与此同时为了方便起见对于无向图的处理我们只需要在两个顶点之间建立两个方向相反的无向边就可以表示一个无向图具体如下 图的表示方法
在计算机中图可以通过许多方式来构建和表示。总的可以分成图的邻接矩阵和邻接表两种方法关于链式前向星本文不过多展开叙述有兴趣的可以自行查阅相关文档。
图的邻接矩阵 (Adjacency Matrix)
若一个图中有 N N N 个顶点那么我们就可以用一个 N × N N \times N N×N 的矩阵来表示这个图。我们一般定义若矩阵的元素 A i , j ≠ − ∞ A_{i, j} \neq -\infty Ai,j−∞ 表示从节点 i i i 到 j j j 有一条有向边其中边的权值为 A i , j A_{i, j} Ai,j。
假设存在一个有 3 3 3 个顶点的图并且有三条有向边 E { ( 1 , 2 ) , ( 2 , 3 ) , ( 3 , 2 ) } E \{(1, 2), (2, 3), (3, 2)\} E{(1,2),(2,3),(3,2)}那么就可以用邻接矩阵表示为 G [ 1 2 3 1 0 1 0 2 0 0 1 3 0 1 0 ] G \begin{bmatrix} \mathtt{1} \mathtt{2} \mathtt{3}\\ \mathtt{1} 0 1 0 \\ \mathtt{2} 0 0 1 \\ \mathtt{3} 0 1 0 \end{bmatrix} G 123100021013010 画成可视化的图就长这个样子 在 C 中我们可以简单地用一个二维数组来表示
// 定义一个矩阵。
int map[50][50];// 将所有的边初始化为负无穷大。
for (int i1; i50; i)for (int j1; j50; j)map[i][j] -0x7f7f7f7f;// 建边其中所有的边权为1。
map[1][2] map[2][3] map[3][2] 1;图的邻接表 (Adjacency List)
邻接表本质上就是用链表表示图。数组的每个元素表示一个顶点元素的值是一个链表链表中存储该顶点的所有邻接顶点。假设存在一个有 4 4 4 个顶点的图并且有四条有向边 E { ( 1 , 2 ) , ( 2 , 3 ) , ( 3 , 2 ) , ( 3 , 4 ) } E \{(1, 2), (2, 3), (3, 2), (3, 4)\} E{(1,2),(2,3),(3,2),(3,4)}那么就可以用邻接表表示为 画成可视化的图就长这个样子 在 C 中我们可以使用 STL模板库 中的 vector 来实现
#include vector
vectorint G[50]; // 建图。
G[1].push_back(2);
G[2].push_back(3);
G[3].push_back(2);
G[3].push_back(4);一般情况下推荐使用邻接表的方式来存图因为使用邻接矩阵比较浪费空间。在顶点数量非常多但边非常少的图中 N 2 N^2 N2 的时空复杂度会导致 MLE 或 TLE 等问题。
图的各种性质
度数 (Degree)一个顶点的度是连接该顶点的边的数量。在有向图中有 入度 (Indegree) 和 出度 (Outdegree) 之分具体例子见后文。路径 (Path)从一个顶点到另一个顶点的顶点序列路径上的边没有重复。回路 (Cycle)起点和终点相同的路径。连通图 (Connected Graph)任意两个顶点之间都有路径相连的无向图。强连通图 (Strongly Connected Graph)任意两个顶点之间都有路径相连的有向图。
对于下面这个无向图不连通图顶点 1 1 1 的度数为 1 1 1顶点 2 2 2 的度数为 2 2 2顶点 3 3 3 的度数为 1 1 1顶点 4 4 4 的度数为 0 0 0。同时由于 4 4 4 号顶点没有度数所以该顶点没有办法到达任何一个其他的顶点所以这个图是一个不连通图 如下图就是一个有向不强连通图。其中顶点 1 1 1 的入度为 0 0 0出度为 2 2 2顶点 2 2 2 的入度为 1 1 1出度也为 1 1 1顶点 3 3 3 的入度为 2 2 2但出度为 0 0 0。由于顶点 1 1 1 和顶点 2 2 2 可以走到顶点 3 3 3但顶点 3 3 3 没有办法走到顶点 1 1 1 或顶点 2 2 2因此下面的图不是一个强连通图 对于下图来说 1 → 2 → 3 → 4 1\to 2\to 3\to 4 1→2→3→4 是一条从顶点 1 1 1 到顶点 4 4 4的路径。 2 → 3 → 4 → 2 → 3 2\to 3\to 4 \to 2\to 3 2→3→4→2→3 就不是一个路径因为相同的边 ( 2 , 3 ) (2, 3) (2,3) 被多次走到了。 1 → 2 → 3 → 1 1\to 2\to 3\to 1 1→2→3→1 就是一个回路因为这个路径的起点和终点相同 图的遍历
图通常采用 深度优先搜索/ 广度优先搜索 这两个算法来遍历。其中深度优先算法是最常见的遍历算法。
对于一个用 邻接矩阵 保存的图其深度优先搜索遍历的 C 代码如下
int vis[105], map[105][105];void dfs(int node){if (vis[node]) return ;vis[node] 1;cout node endl;for (int i1; in; i)if (map[node][i] ! -0x7f7f7f7f)dfs(i);return ;
}// 函数调用dfs(1); 表示从1号顶点开始遍历。对于一个用 邻接表 保存的图其深度优先搜索遍历的 C 代码如下
#include vector
vectorint G[105];
int vis[105];void dfs(int node){if (vis[node]) return ;vis[node] 1;cout node endl;for (int to : G[node])dfs(to);return ;
}// 函数调用dfs(1); 表示从1号顶点开始遍历。广度优先搜索的方式也类似
#include queue
vectorint G[105];
int vis[105];void bfs(int node){queueint que;que.push(node);while(!que.empty()){int t que.front();cout t endl;que.pop();for (int to : G[node]){if (!vis[to]) {vis[to] 1;que.push(to);}}}return ;
}// 函数调用bfs(1); 表示从1号顶点开始遍历。对于判断无向图的连通性我们只需要从任意一个点开始跑一遍深搜或者广搜就行了。如果所有顶点的 vis 都被标记了则证明图是联通的否则图就是不连通的。
例题讲解
P3916 图的遍历
模板题目从每一个顶点开始用深搜遍历一遍就可以了。但从每一个点考虑能走到的最大点比较麻烦一个更优的解决办法是反向建边从最大的点开始遍历这样子就可以一次性计算出多个结果。
#include iostream
#include algorithm
#include vector
#include cstring
using namespace std;const int N 10005;
int n, m, ans, vis[N];
vectorint G[N];void dfs(int node, int d){if (vis[node]) return ;vis[node] d;ans max(node, ans);for (int to : G[node]) dfs(to, d);return ;
}int main(){cin n m;for (int i0, u, v; im; i){cin u v;G[v].push_back(u); // 反向建边。}for (int in; i1; i--) dfs(i, i);for (int i1; in; i) cout vis[i] ;return 0;
}P5318 【深基18.例3】查找文献
也是一道模板题目正常遍历即可。
#include iostream
#include algorithm
#include vector
#include queue
using namespace std;
const int MAXN 100005;int n, m;
int vis1[MAXN], vis2[MAXN];
queueint que;
vectorint G[MAXN];void dfs(int node, int current){vis1[node] 1;cout node ;if (current n) return ;for (int i0; iG[node].size(); i){if (vis1[G[node][i]]) continue;dfs(G[node][i], current1);}return ;
}void dfs(int node){vis2[node] 1;que.push(node);while(que.size()){int t que.front();cout t ;for (int i0; iG[t].size(); i){if (vis2[G[t][i]]) continue;vis2[G[t][i]] 1;que.push(G[t][i]);}que.pop();}return ;
}int main(){cin n m;for (int i0; im; i){int t1, t2;cin t1 t2;G[t1].push_back(t2);}for (int i1; in; i) sort(G[i].begin(), G[i].end());dfs(1, 0), cout endl, dfs(1);return 0;
}番外 - 图的常见算法
更多关于图论的算法请持续关注后续更新。
深度优先搜索 (DFS)适用于遍历图和检测图中的回路。广度优先搜索 (BFS)适用于寻找最短路径无权图。Dijkstra 算法适用于加权图中寻找单源最短路径。Bellman-Ford 算法适用于有负权边的图中寻找单源最短路径。Floyd-Warshall 算法适用于寻找所有顶点对之间的最短路径。Kruskal 算法用于求解最小生成树 (MST - Minimum Spanning Tree)。Prim 算法另一种求解最小生成树的方法。拓扑排序 (Topological Sorting)适用于有向无环图 (DAG)用于任务调度等应用。Tarjan 算法用于求解图中的强连通分量、割点、桥。
