如何做招聘网站的方案,市场调研报告模板ppt,wordpress直排主题,公司简介模板图片图论理论基础
图的种类
整体上一般分为 有向图 和 无向图。
度
无向图中有几条边连接该节点#xff0c;该节点就有几度。
在有向图中#xff0c;每个节点有出度和入度。
出度#xff1a;从该节点出发的边的个数。
入度#xff1a;指向该节点边的个数。
连通性
在图…
图论理论基础
图的种类
整体上一般分为 有向图 和 无向图。
度
无向图中有几条边连接该节点该节点就有几度。
在有向图中每个节点有出度和入度。
出度从该节点出发的边的个数。
入度指向该节点边的个数。
连通性
在图中表示节点的连通情况我们称之为连通性。
连通图
在无向图中任何两个节点都是可以到达的我们称之为连通图
如果有节点不能到达其他节点则为非连通图
强连通图
在有向图中任何两个节点是可以相互到达的我们称之为 强连通图。
强连通图是在有向图中任何两个节点是可以相互到达 连通分量
在无向图中的极大连通子图称之为该图的一个连通分量。
强连通分量
在有向图中极大强连通子图称之为该图的强连通分量。
图的构造
一般使用邻接表、邻接矩阵 或者用类来表示。
主要是 朴素存储、邻接表和邻接矩阵。
邻接矩阵
邻接矩阵 使用 二维数组来表示图结构。 邻接矩阵是从节点的角度来表示图有多少节点就申请多大的二维数组。
这种表达方式邻接矩阵 在 边少节点多的情况下会导致申请过大的二维数组造成空间浪费。而且在寻找节点连接情况的时候需要遍历整个矩阵即 n * n 的时间复杂度同样造成时间浪费。
邻接矩阵的优点
表达方式简单易于理解检查任意两个顶点间是否存在边的操作非常快适合稠密图在边数接近顶点数平方的图中邻接矩阵是一种空间效率较高的表示方法。
缺点
遇到稀疏图会导致申请过大的二维数组造成空间浪费 且遍历 边 的时候需要遍历整个n * n矩阵造成时间浪费
#邻接表
邻接表 使用 数组 链表的方式来表示。 邻接表是从边的数量来表示图有多少边 才会申请对应大小的链表。
邻接表的优点
对于稀疏图的存储只需要存储边空间利用率高遍历节点连接情况相对容易
缺点
检查任意两个节点间是否存在边效率相对低需要 O(V)时间V表示某节点连接其他节点的数量。实现相对复杂不易理解
图的遍历方式
图的遍历方式基本是两大类
深度优先搜索dfs广度优先搜索bfs
dfs 与 bfs 区别
dfs是可一个方向去搜不到黄河不回头直到遇到绝境了搜不下去了再换方向换方向的过程就涉及到了回溯。bfs是先把本节点所连接的所有节点遍历一遍走到下一个节点的时候再把连接节点的所有节点遍历一遍搜索方向更像是广度四面八方的搜索过程。
dfs
搜索方向是认准一个方向搜直到碰壁之后再换方向换方向是撤销原路径改为节点链接的下一个路径回溯的过程
代码框架
void dfs(参数) {if (终止条件) {存放结果;return;}for (选择本节点所连接的其他节点) {处理节点;dfs(图选择的节点); // 递归回溯撤销处理结果}
}
深搜三部曲
1.确认递归函数参数
一般情况深搜需要 二维数组数组结构保存所有路径需要一维数组保存单一路径这种保存结果的数组我们可以定义一个全局变量避免让我们的函数参数过多。
2.确认终止条件
终止添加不仅是结束本层递归同时也是我们收获结果的时候。
3.处理目前搜索节点出发的路径
for (选择本节点所连接的其他节点) {处理节点;dfs(图选择的节点); // 递归回溯撤销处理结果
} 98. 所有可达路径
深搜三部曲
1.确认递归函数参数
首先我们dfs函数一定要存一个图用来遍历的需要存一个目前我们遍历的节点定义为x。
还需要存一个n表示终点我们遍历的时候用来判断当 xn 时候 标明找到了终点。
其实在递归函数的参数 不容易一开始就确定了一般是在写函数体的时候发现缺什么参加就补什么
2.确认终止条件
什么时候我们就找到一条路径了
当目前遍历的节点 为 最后一个节点 n 的时候 就找到了一条 从出发点到终止点的路径。
3.处理目前搜索节点出发的路径
for (int i 1; i n; i) { // 遍历节点x链接的所有节点if (graph[x][i] 1) { // 找到 x链接的节点path.push_back(i); // 遍历到的节点加入到路径中来dfs(graph, i, n); // 进入下一层递归path.pop_back(); // 回溯撤销本节点}
}
import java.util.ArrayList;
import java.util.List;
import java.util.Scanner;public class Main { private static ListList result new ArrayList(); // 收集符合条件的路径 private static List path new ArrayList(); // 1节点到终点的路径private static void dfs(int[][] graph, int x, int n) {// 当前遍历的节点x 到达节点n if (x n) { // 找到符合条件的一条路径result.add(new ArrayList(path));return;}for (int i 1; i n; i) { // 遍历节点x链接的所有节点if (graph[x][i] 1) { // 找到 x链接的节点path.add(i); // 遍历到的节点加入到路径中来dfs(graph, i, n); // 进入下一层递归path.remove(path.size() - 1); // 回溯撤销本节点}}
}public static void main(String[] args) {Scanner scanner new Scanner(System.in);int n scanner.nextInt();int m scanner.nextInt();// 节点编号从1到n所以申请 n1 这么大的数组int[][] graph new int[n 1][n 1];while (m-- 0) {int s scanner.nextInt();int t scanner.nextInt();// 使用邻接矩阵 表示无向图1 表示 s 与 t 是相连的graph[s][t] 1;}path.add(1); // 无论什么路径已经是从1节点出发dfs(graph, 1, n); // 开始遍历// 输出结果if (result.size() 0) {System.out.println(-1);} else {for (ListInteger pa : result) {for (int i 0; i pa.size() - 1; i) {System.out.print(pa.get(i) );}System.out.println(pa.get(pa.size() - 1));}}scanner.close();}
} bfs
广搜的搜索方式就适合于解决两个点之间的最短路径问题。
这一圈一圈的搜索过程是怎么做到的是放在什么容器里才能这样去遍历。
其实我们仅仅需要一个容器能保存我们要遍历过的元素就可以那么用队列还是用栈甚至用数组都是可以的。
用队列的话就是保证每一圈都是一个方向去转例如统一顺时针或者逆时针。
因为队列是先进先出加入元素和弹出元素的顺序是没有改变的。
如果用栈的话就是第一圈顺时针遍历第二圈逆时针遍历第三圈有顺时针遍历。
因为栈是先进后出加入元素和弹出元素的顺序改变了。
那么广搜需要注意 转圈搜索的顺序吗 不需要
所以用队列还是用栈都是可以的但大家都习惯用队列了所以下面的讲解用我也用队列来讲只不过要给大家说清楚并不是非要用队列用栈也可以。 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; // 只要加入队列立刻标记避免重复访问}}}}
