做网站需要注意的问题,减肥单页网站,软件专利怎么申请,萧山城区建设有限公司网站图论理论基础
1、图的种类
整体上一般分为 有向图 和 无向图。
加权有向图#xff0c;就是图中边是有权值的#xff0c;加权无向图也是同理。
2、度
无向图中有几条边连接该节点#xff0c;该节点就有几度
在有向图中#xff0c;每个节点有出度和入度。出度#xff…图论理论基础
1、图的种类
整体上一般分为 有向图 和 无向图。
加权有向图就是图中边是有权值的加权无向图也是同理。
2、度
无向图中有几条边连接该节点该节点就有几度
在有向图中每个节点有出度和入度。出度从该节点出发的边的个数。入度指向该节点边的个数。
3、连通性
在图中表示节点的连通情况我们称之为连通性
连通图和强连通图
在无向图中任何两个节点都是可以到达的我们称之为连通图。如果有节点不能到达其他节点则为非连通图。在有向图中任何两个节点是可以相互到达的我们称之为 强连通图。
连通分量和强连通分量
在无向图中的极大连通子图称之为该图的一个连通分量。在有向图中极大强连通子图称之为该图的强连通分量。
4、图的构造
一般使用邻接表、邻接矩阵 或者用类来表示。主要是 朴素存储、邻接表和邻接矩阵。
邻接矩阵 使用 二维数组来表示图结构。 邻接矩阵是从节点的角度来表示图有多少节点就申请多大的二维数组。
邻接矩阵
优点
表达方式简单易于理解检查任意两个顶点间是否存在边的操作非常快适合稠密图在边数接近顶点数平方的图中邻接矩阵是一种空间效率较高的表示方法。
缺点
遇到稀疏图会导致申请过大的二维数组造成空间浪费 且遍历 边 的时候需要遍历整个n * n矩阵造成时间浪费邻接表 使用 数组 链表的方式来表示。 邻接表是从边的数量来表示图有多少边 才会申请对应大小的链表。
邻接表
优点
对于稀疏图的存储只需要存储边空间利用率高遍历节点连接情况相对容易
缺点
检查任意两个节点间是否存在边效率相对低需要 O(V)时间V表示某节点连接其他节点的数量。实现相对复杂不易理解
5、图的遍历方式
深度优先搜索dfs广度优先搜索bfs
深搜理论基础
关键就两点
搜索方向是认准一个方向搜直到碰壁之后再换方向换方向是撤销原路径改为节点链接的下一个路径回溯的过程
代码框架
void dfs(参数) {if (终止条件) {存放结果;return;}for (选择本节点所连接的其他节点) {处理节点;dfs(图选择的节点); // 递归回溯撤销处理结果}
}
98. 所有可达路径卡码网
深搜三部曲
确认递归函数参数确认终止条件处理目前搜索节点出发的路径
邻接矩阵写法
def dfs(graph, x, n, result, path):# 当前遍历的节点x 到达节点n if x n: # 找到符合条件的一条路径result.append(path[:])returnfor i in range(1, n1): # 遍历节点x链接的所有节点if graph[x][i] 1: path.append(i)dfs(graph, i, n, result, path)path.pop()if __name__ __main__:n, m map(int, input().strip().split())# 节点编号从1到n所以申请 n1 这么大的数组graph [[0] * (n 1) for _ in range(n1)]for _ in range(m):s, t map(int, input().strip().split())# 使用邻接矩阵 表示无线图1 表示 s 与 t 是相连的graph[s][t] 1result []dfs(graph, 1, n, result, [1])# 输出结果if len(result) 0:print(-1)for path in result:print( .join([str(i) for i in path]))邻接表写法
def dfs(graph, x, n, result, path):# 当前遍历的节点x 到达节点n if x n: # 找到符合条件的一条路径result.append(path[:])returnfor i in graph[x]: # 遍历节点x链接的所有节点path.append(i)dfs(graph, i, n, result, path)path.pop()if __name__ __main__:n, m map(int, input().strip().split())# 节点编号从1到n所以申请 n1 这么大的数组graph [[] for _ in range(n1)] # 邻接表for _ in range(m):s, t map(int, input().strip().split())# 使用邻接表graph[s].append(t)result []dfs(graph, 1, n, result, [1])# 输出结果if len(result) 0:print(-1)for path in result:print( .join([str(i) for i in path]))
主要在生成图和遍历图的时候不一样
广搜理论基础
广搜的使用场景
广搜的搜索方式就适合于解决两个点之间的最短路径问题。因为广搜是从起点出发以起始点为中心一圈一圈进行搜索一旦遇到终点记录之前走过的节点就是一条最短路。
代码框架
int dir[4][2] {0, 1, 1, 0, -1, 0, 0, -1}; // 表示四个方向
// grid 是地图也就是一个二维数组
// visited标记访问过的节点不要重复访问
// x,y 表示开始搜索节点的下标
void bfs(vectorvectorchar grid, vectorvectorbool visited, int x, int y) {queuepairint, int que; // 定义队列que.push({x, y}); // 起始节点加入队列visited[x][y] true; // 只要加入队列立刻标记为访问过的节点while(!que.empty()) { // 开始遍历队列里的元素pairint ,int cur que.front(); que.pop(); // 从队列取元素int curx cur.first;int cury cur.second; // 当前节点坐标for (int i 0; i 4; i) { // 开始想当前节点的四个方向左右上下去遍历int nextx curx dir[i][0];int nexty cury dir[i][1]; // 获取周边四个方向的坐标if (nextx 0 || nextx grid.size() || nexty 0 || nexty grid[0].size()) continue; // 坐标越界了直接跳过if (!visited[nextx][nexty]) { // 如果节点没被访问过que.push({nextx, nexty}); // 队列添加该节点为下一轮要遍历的节点visited[nextx][nexty] true; // 只要加入队列立刻标记避免重复访问}}}}
