哪个网站做ic好,做go kegg的网站,推广网站怎么建,福清市建设工程电子招标网2018版图论基础
图的种类#xff1a;有向图 和 无向图#xff0c;加权有向图#xff0c; 加权无向图
无向图中有几条边连接该节点#xff0c;该节点就有几度。
在有向图中#xff0c;每个节点有出度和入度。出度#xff1a;从该节点出发的边的个数。入度#xff1a;指向该节…图论基础
图的种类有向图 和 无向图加权有向图 加权无向图
无向图中有几条边连接该节点该节点就有几度。
在有向图中每个节点有出度和入度。出度从该节点出发的边的个数。入度指向该节点边的个数。
图的遍历方式
深度优先搜索dfs广度优先搜索bfs 深度优先搜索DFS、广度优先搜索BFS、并查集、拓扑排序、最小生成树系列、最短路算法系列...
深度优先搜索理论基础
dfs是可一个方向去搜不到黄河不回头直到遇到绝境了搜不下去了再换方向换方向的过程就涉及到了回溯。bfs是先把本节点所连接的所有节点遍历一遍走到下一个节点的时候再把连接节点的所有节点遍历一遍搜索方向更像是广度四面八方的搜索过程。
DFS深度优先搜索
往一个方向搜索不到黄河不回头。 从1到6的第一条路径如下 此时我们找到了节点6遇到黄河了是不是应该回头了那么应该再去搜索其他方向了。 路径2撤销了改变了方向走路径3红色线 接着也找到终点6。 那么撤销路径2改为路径3在dfs中其实就是回溯的过程这一点很重要很多录友不理解dfs代码中回溯是用来干什么的
又找到了一条从节点1到节点6的路径又到黄河了此时再回头下图图四中路径4撤销回溯的过程改为路径5。 又找到了一条从节点1到节点6的路径又到黄河了此时再回头下图图五路径6撤销回溯的过程改为路径7路径8 和 路径7路径9 结果发现死路一条都走到了自己走过的节点。 那么节点2所连接路径和节点3所链接的路径 都走过了撤销路径只能向上回退去选择撤销当初节点4的选择也就是撤销路径5改为路径10 。 如图图六 其他节点的过程省略总体来说的两个步骤就是
搜索方向是认准一个方向搜直到碰壁之后再换方向换方向是撤销原路径改为节点链接的下一个路径回溯的过程。
因为dfs搜索向一个方向并且需要回溯所以可以用递归方式来实现。
void dfs(参数) {处理节点dfs(图选择的节点); // 递归回溯撤销处理结果
}
回溯算法其实就是dfs的过程
void dfs(参数) {if (终止条件) {存放结果;return;}for (选择本节点所连接的其他节点) {处理节点;dfs(图选择的节点); // 递归回溯撤销处理结果}
}
深搜三部曲
1. 确定递归函数2. 确认终止条件 3. 处理目前搜索节点出发的路径
98. 所有可达路径
实现这两个图的存储方式邻接矩阵 邻接表
邻接矩阵
vectorvectorint graph(n 1, vectorint(n 1, 0));
// 输入m个边构造方式如下
while (m--) {cin s t;// 使用邻接矩阵 1 表示 节点s 指向 节点tgraph[s][t] 1;
}
邻接表 数组 链表的方式来表示。邻接表是从边的数量来表示图有多少边 才会申请对应大小的链表。
// 节点编号从1到n所以申请 n1 这么大的数组
vectorlistint graph(n 1); // 邻接表list为C里的链表
// 输入m个边构造方式如下
while (m--) {cin s t;// 使用邻接表 表示 s - t 是相连的graph[s].push_back(t);
}
1. 确认递归函数
vectorvectorint result; // 收集符合条件的路径
vectorint path; // 0节点到终点的路径
// x目前遍历的节点
// graph存当前的图
// n终点
void dfs (const vectorvectorint graph, int x, int n) {
2. 确认终止条件
当目前遍历的节点 为 最后一个节点 n 的时候 就找到了一条 从出发点到终止点的路径。
// 当前遍历的节点x 到达节点n
if (x n) { // 找到符合条件的一条路径result.push_back(path);return;
}
3. 处理目前搜索节点出发的路径
for(int i1; in; i){if(graph[x][i] 1) {path.push_back(i);dfs(graph, i, n);path.pop_back(i);}
}
所以本题使用ACM模式写出来就是
#include iostream
#include vector
#include list
using namespace std;
vectorvectorint result;
vectorint path;//void dfs(const vectorvectorint graph, int x, int n){void dfs(const vectorlistint graph, int x, int n){//当前遍历的节点x到达节点nif(xn){result.push_back(path);return;}// for(int i1; in; i){// if(graph[x][i]1){ //找到x链接的节点// path.push_back(i);// dfs(graph, i, n);// path.pop_back();// }// }for(int i:graph[x]){path.push_back(i);dfs(graph, i, n);path.pop_back();}
}
int main(){int n, m, s, t;cinnm;//vectorvectorint graph(n1, vectorint(n1, 0));vectorlistint graph(n1);while(m--){cinst;//graph[s][t] 1;graph[s].push_back(t);}path.push_back(1);//无论什么路径已经是从0节点出发dfs(graph, 1, n);if(result.size()0) cout-1endl;for(const vectorintpa : result){for(int i0; ipa.size()-1; i){coutpa[i] ;}coutpa[pa.size()-1]endl;}
}
797. 所有可能的路径
class Solution {
public:vectorvectorint result;vectorint path;void dfs(vectorvectorint graph, int x, int n){if(xn){result.push_back(path);return;}// for(int i1; in; i){// if(graph[x][i]1){// path.push_back(i);// dfs(graph, i, n);// path.pop_back();// }// }for (auto y : graph[x]) {path.push_back(y);dfs(graph, y, n);path.pop_back();}}vectorvectorint allPathsSourceTarget(vectorvectorint graph) {path.push_back(0);dfs(graph, 0, graph.size()-1);return result;}
};
