---------------------------------------------------------------------------------------------------------------------------------
如果以前没怎么写过dfs,一头雾水的
晚上睡不着肝了个->
(15条消息) 彻底搞懂dfs与回溯_lxrrrrrrrr的博客-CSDN博客
希望这里面能说明白哈
目录
问题 A: 将邻接矩阵存储的图转换为邻接表存储的图,附加代码模式
问题 B: 邻接表存储的图转化为邻接矩阵存储的图-附加代码模式
问题 D: 邻接矩阵存储图的DFS-非递归算法(附加代码模式)
问题 G: 邻接矩阵存储图的DFS完成序求解(附加代码模式)
纯纯大模拟
数据同学交python吧
- #include
- using namespace std;
- #define MAX_SIZE 100
- struct Graph{
- int vexNumber;
- string info[MAX_SIZE];
- int adjMatrix[MAX_SIZE][MAX_SIZE];
- };
- struct ArcNode
- {
- int weight;
- int adj;
- ArcNode *nextarc;
- };
- struct VexNode
- {
- string Info;
- ArcNode *firstarc;
- };
- struct linkGraph
- {
- VexNode *vexes;
- int vexnumber;
- };
- int InitGraph(linkGraph &G,int vexnumber)
- {
-
- G.vexes=new VexNode[vexnumber];
- G.vexnumber=vexnumber;
- for(int i=0;i
- {
- G.vexes[i].firstarc=nullptr;
- return 0;
- }
- }
- void InitGraph(linkGraph &G,const Graph& g)
- {
- int n=g.vexNumber;
- int flag[n]={0};
- InitGraph(G,n);
- for(int i=0;i
- {
- G.vexes[i].Info=(char)(i+'a');
- for(int j=0;j
- {
- if(g.adjMatrix[i][j]!=0)
- {ArcNode *p=new ArcNode;
- p->nextarc=G.vexes[i].firstarc;
- G.vexes[i].firstarc=p;
- p->adj=j;}
- }
- }
- }
- int DestroyGraph(linkGraph &G)
- {
- for(int i=0;i
- {
- while(G.vexes[i].firstarc!=nullptr)
- {
- ArcNode *p=G.vexes[i].firstarc;
- G.vexes[i].firstarc=p->nextarc;
- delete p;
- }
- }
- delete[]G.vexes;
- G.vexes=nullptr;
- G.vexnumber=0;
- return 0;
- }
- void PrintGraph(const linkGraph &G){
- for(int i=0;i
- {
- cout<
- ArcNode *p=G.vexes[i].firstarc;
- while(p)
- {
- cout<<" --> "<
adj].Info; - p=p->nextarc;
- }
- cout<<"\n";
- }
- }
python代码:
- n=int(input())
- g=[]
- for i in range(0,n):
- s=input().split()
- g.append(s)
- for i in range(0,n):
- result=ord('a')+i
- result=[chr(result)]
- for j in range(n-1,-1,-1):
- if g[i][j]=='1':
- result.append(chr(ord('a')+j))
- print(' --> '.join(result))
问题 B: 邻接表存储的图转化为邻接矩阵存储的图-附加代码模式
cpp代码:
- #include
- #include
- #include
- using namespace std;
-
- #define size 100;
- struct Graph{
- int vexNumber;
- string info[100];
- int adjMatrix[100][100];
- };//邻接矩阵存储的图
-
- struct ArcNode{
- char weight;//弧上的信息
- int adj;//序号
- ArcNode* nextarc;
- };//弧结点定义
-
- struct VexNode{
- char Info;//顶点信息
- VexNode* nextarc;
- };
-
- struct linkGraph{
- VexNode *vexes;
- int vexnumber;
- int Matrix[100][100];
- };
-
- ArcNode* getArcNode(int adj){
- ArcNode* node=new ArcNode();
- return node;
- }
-
- void InputlinkGraph(linkGraph& lg){
- int n;
- cin>>n;
- lg.vexnumber=n;
- for(int i=0;i
- for(int j=0;j
- lg.Matrix[i][j]=0;
- }
- }
- char str[10];
- while(n--){
- cin>>str;
- char c=str[0];
- for(int i=1;i<strlen(str);i++){
- if(str[i]!='-'){
- lg.Matrix[c-'a'][str[i]-'a']=1;
- }
- }
- }
- return;
- }
-
- void linkGraph2Graph(const linkGraph&lg,Graph& g){
- return;
- }
-
- void printGraph(const Graph&g){
-
- return;
- }
-
- void PrintlinkGraph(linkGraph&g){
- for(int i=0;i
- cout<<(char)('a'+i)<<" ";
- for(int j=g.vexnumber-1;j>=0;j--){
- if(g.Matrix[i][j]==1){
- cout<<"--> ";
- cout<<(char)('a'+j)<<" ";
- }
-
- }cout<
- }
- for(int i=0;i
- for(int j=0;j
- cout<
" "; - }
- cout<
- }
- return;
- }
-
- int DestroylinkGraph(linkGraph&g){
- return 0;
- }
python代码:
- n=int(input())
- v=[]
- g=[]
- for i in range(0,n):
- g.append([0]*n)
- for i in range(0,n):
- v.append(input().split('-'))
- for i in range(0,n):
- begin = v[i][0]
- for j in range(1,len(v[i])):
- ind=ord(v[i][j])-ord('a')
- g[i][ind]=1
- for i in range(0,n):
- print(' --> '.join(v[i]))
- for i in range(0,n):
- print(' '.join(map(str,g[i])))
问题 C: 邻接矩阵存储图的DFS(附加代码模式)
dfs板子
- #include
-
- using namespace std;
-
- #define MAXSIZE 100
-
- // 邻接矩阵存储的图型数据结构
- struct Graph{
- int vexNumber;
- string vexInfo[MAXSIZE];
- int adjMatrix[MAXSIZE][MAXSIZE];
- };
- void DFS(Graph G, int v, int st[]){
- cout<
" "; - st[v] = 1;
- for(int i=0;i
- if(!st[i] && G.adjMatrix[v][i] == 1){
- DFS(G,i,st);
- }
- }
- }
- void DFS(Graph G){
- int st[150];
- memset(st,0,sizeof st);
- for(int i=0;i
- if(!st[i]){
- DFS(G, i , st);
- }
- }
- }
问题 D: 邻接矩阵存储图的DFS-非递归算法(附加代码模式)
- #include
- #include
- #include
- #include
- #include
- using namespace std;
-
- #define MAX_SIZE 100
-
- // 邻接矩阵存储的图
- struct Graph
- {
- int vexNumber;
- string vexInfo[MAX_SIZE];
- int adjMatrix[MAX_SIZE][MAX_SIZE];
- };
-
- // 查找v0的未被访问的邻接点
- int findAdjVex(const Graph& G, int v0, int visited[]){
- for (int i=0;i
- if (G.adjMatrix[v0][i]==1 && !visited[i]) {
- return i;
- }
- }
- return -1;
- }
-
- // 以顶点v0为起点,进行一趟DFS
- string DFS(const Graph& G, int v0, int visited[]){
- string result = G.vexInfo[v0];
- visited[v0] = 1;
- int adj;
- while ((adj = findAdjVex(G, v0, visited)) != -1) {
- result += " ";
- result += DFS(G, adj, visited);
- }
-
- return result;
- }
- // 对整个图进行DFS
- string DFS(const Graph& G){
- string result = "";
- // 第一步:初始化visited数组
- int visited[MAX_SIZE] = { 0 };
- // 第二步:以每个未被遍历的顶点为起点,进行DFS
- for (int i = 0; i < G.vexNumber; ++i) {
- if (!visited[i]) {
- result += DFS(G, i, visited);
- }
- }
- return result;
- }
问题 E: 邻接矩阵存储图的BFS
bfs板子,只不过是邻接矩阵的
- #include
- #define int long long
- #define pb push_back
- #define fer(i,a,b) for(int i=a;i<=b;++i)
- #define der(i,a,b) for(int i=a;i>=b;--i)
- #define all(x) (x).begin(),(x).end()
- #define pll pair
- #define et cout<<'\n'
- #define xx first
- #define yy second
- using namespace std;
- template <typename _Tp>void input(_Tp &x){
- char ch(getchar());bool f(false);while(!isdigit(ch))f|=ch==45,ch=getchar();
- x=ch&15,ch=getchar();while(isdigit(ch))x=x*10+(ch&15),ch=getchar();
- if(f)x=-x;
- }
- template <typename _Tp,typename... Args>void input(_Tp &t,Args &...args){input(t);input(args...);}
- const int N=1e6+10;
- int M[60][60];
- bool st[60];
- int n;
- void bfs(int i){
- queue<int> q;
- q.push(i);
- while(q.size()){
- auto t=q.front();
- q.pop();
- for(int i=0;i
- if(M[t][i]&&!st[i]){
- cout<" ";
- q.push(i);
- st[i]=1;
- }
- }
- }
- }
- signed main()
- {
- cin>>n;
- for(int i=0;i
- for(int j=0;j
- cin>>M[i][j];
- }
- }
- for(int i=0;i
- if(!st[i]){
- st[i]=1;
- cout<' ';
- bfs(i);
- }
- }
- }
问题 F: 案例6-1.2:邻接表存储图的广度优先遍历
这题也注意下排序,然后就是bfs板子了
- #include
- #define int long long
- #define pb push_back
- #define fer(i,a,b) for(int i=a;i<=b;++i)
- #define der(i,a,b) for(int i=a;i>=b;--i)
- #define all(x) (x).begin(),(x).end()
- #define pll pair
- #define et cout<<'\n'
- #define xx first
- #define yy second
- using namespace std;
- template <typename _Tp>void input(_Tp &x){
- char ch(getchar());bool f(false);while(!isdigit(ch))f|=ch==45,ch=getchar();
- x=ch&15,ch=getchar();while(isdigit(ch))x=x*10+(ch&15),ch=getchar();
- if(f)x=-x;
- }
- template <typename _Tp,typename... Args>void input(_Tp &t,Args &...args){input(t);input(args...);}
- const int N=1e6+10;
- vector<int> v[N];
- int vis[N];
- void bfs(int x){
- queue<int>q;
- q.push(x);
- while(q.size()){
- int now=q.front();
- q.pop();
- if(vis[now]==1) continue;
- vis[now]=1;
- cout<
" "; - for(auto t:v[now]){
- if(vis[t]) continue;
- q.push(t);
- }
- }
- }
- signed main(){
- int n,m,x;
- input(n,m,x);
- fer(i,1,m){
- int a,b;
- input(a,b);
- v[a].push_back(b);
- v[b].push_back(a);
- }
- fer(i,0,n-1){
- sort(v[i].begin(),v[i].end());
- }
- bfs(x);
- }
问题 G: 邻接矩阵存储图的DFS完成序求解(附加代码模式)
裸dfs
- #include
- #include
- #include
- #include
- #include
- using namespace std;
-
- #define MAX_SIZE 100
-
- struct Graph
- {
- int vexNumber;
- string vexInfo[MAX_SIZE];
- int adjMatrix[MAX_SIZE][MAX_SIZE];
- };
-
-
- int findAdjVex(const Graph& G, int v0, int visited[]){
- return 0;
- }
-
- string DFS_finished(const Graph &G, int v0, int visited[]){
- string res="";
- visited[v0]=1;
- for(int i=0;i
- if(G.adjMatrix[v0][i]==1&& !visited[i]){
- res+=DFS_finished(G,i,visited);
- }
- }
- res+=(char)(v0+'a');
- return res;
- }
-
- string DFS_finished(const Graph &G){
- string res="";
- int n=G.vexNumber;
- int visited[MAX_SIZE]={};
- for(int i=0;i
- if(!visited[i]) res+=DFS_finished(G,i,visited);
- }
- return res;
- }
问题 H: 案例6-1.1:DFS应用-计算可达城市对
这题数据比较小,相当于dfs板子题了
对于每个点dfs一遍统计答案
这道题的进阶版[JSOI2010]连通数 - 洛谷
原题是要tarjan缩点的,有兴趣的同学可以研究下
- #include
- #define int long long
- #define pb push_back
- #define fer(i,a,b) for(int i=a;i<=b;++i)
- #define der(i,a,b) for(int i=a;i>=b;--i)
- #define all(x) (x).begin(),(x).end()
- #define pll pair
- #define et cout<<'\n'
- #define xx first
- #define yy second
- using namespace std;
- template <typename _Tp>void input(_Tp &x){
- char ch(getchar());bool f(false);while(!isdigit(ch))f|=ch==45,ch=getchar();
- x=ch&15,ch=getchar();while(isdigit(ch))x=x*10+(ch&15),ch=getchar();
- if(f)x=-x;
- }
- template <typename _Tp,typename... Args>void input(_Tp &t,Args &...args){input(t);input(args...);}
- const int N=1e6+10;
- using namespace std;
- vector<int> v[N];
- bool vis[N];
- int m,n;
- int dfs(int x){
- int res=1;
- vis[x]=1;
- for(auto t:v[x]){
- if(!vis[t]){
- res+=dfs(t);
- }
- }
- return res;
- }
- signed main(){
- int ans=0;
- input(n,m);
- int x,y;
- fer(i,1,m){
- input(x,y);
- v[x].pb(y);
- }
- fer(i,1,n){
- memset(vis,0,sizeof vis);
- ans+=dfs(i);
- }
- cout<
- }
问题 I: 案例6-1.3:哥尼斯堡的“七桥问题”
欧拉回路:每条边都要经过一次,并且回到出发点
欧拉回路可以有很多方法求,dfs不是很好写,这里给出一种并查集的求法
不懂并查集可以搜一下
首先一定整张图一定要连通(这好像是废话,但得判断一下,也就是ans==1的部分)
(在并查集中,有几个fa[i]=i,证明有几个连通块,没听过可以了解一下)
其次,所有点的度必须为偶数(度:无向图中一个点连有几条边度就是几)
因为欧拉回路既然是回路就得一来一回,奇数肯定不行
满足这俩条件就是有欧拉回路
- #include
- #define int long long
- #define pb push_back
- #define fer(i,a,b) for(int i=a;i<=b;++i)
- #define der(i,a,b) for(int i=a;i>=b;--i)
- #define all(x) (x).begin(),(x).end()
- #define pll pair
- #define et cout<<'\n'
- #define xx first
- #define yy second
- using namespace std;
- template <typename _Tp>void input(_Tp &x){
- char ch(getchar());bool f(false);while(!isdigit(ch))f|=ch==45,ch=getchar();
- x=ch&15,ch=getchar();while(isdigit(ch))x=x*10+(ch&15),ch=getchar();
- if(f)x=-x;
- }
- template <typename _Tp,typename... Args>void input(_Tp &t,Args &...args){input(t);input(args...);}
- const int N=1e6+10;
- int fa[N];
- int find(int x){
- if(fa[x]!=x) fa[x]=find(fa[x]);
- return fa[x];
- }
- int w[N];
- signed main()
- {
- int n,m;
- fer(i,0,1000) fa[i]=i;
- input(n,m);
- while(m--)
- {
- int a,b;
- input(a,b);
- if(find(a)!=find(b)){
- fa[find(a)]=find(b);
- }
- w[a]++;
- w[b]++;
- }
- int ans=0;
- int flag=1;
- fer(i,1,n)
- {
- if(w[i]%2!=0){
- flag=0;
- }
- if(fa[i]==i){
- ans++;
- }
- }
- if(ans!=1){
- flag=0;
- }
- if(flag){
- cout<<"1"<<'\n';
- }
- else{
- cout<<"0"<<'\n';
- }
- }
问题 J: 案例6-1.4:地下迷宫探索
这题注意dfs的时候排下序
我们只要从起点dfs一遍,如果还有没到过的点,说明不是连通图,在输出一个0
- #include
- #define int long long
- #define pb push_back
- #define fer(i,a,b) for(int i=a;i<=b;++i)
- #define der(i,a,b) for(int i=a;i>=b;--i)
- #define all(x) (x).begin(),(x).end()
- #define pll pair
- #define et cout<<'\n'
- #define xx first
- #define yy second
- using namespace std;
- template <typename _Tp>void input(_Tp &x){
- char ch(getchar());bool f(false);while(!isdigit(ch))f|=ch==45,ch=getchar();
- x=ch&15,ch=getchar();while(isdigit(ch))x=x*10+(ch&15),ch=getchar();
- if(f)x=-x;
- }
- template <typename _Tp,typename... Args>void input(_Tp &t,Args &...args){input(t);input(args...);}
- const int N=1e4+10;
- int n,m,st;
- vector<int >v[N];
- stack<int>s;
- bool vis[N];
- void dfs(int k)
- {
- vis[k]=1;
- sort(v[k].begin(),v[k].end());
- for(auto t:v[k]){
- if(!vis[t]){
- s.push(k);
- cout<
" "; - dfs(t);
- }
- }
- if(k!=st)
- {
- cout<
top()<<' '; - s.pop();
- }
- }
- signed main()
- {
- input(n,m,st);
- fer(i,1,m)
- {
- int a,b;
- input(a,b);
- v[a].push_back(b);
- v[b].push_back(a);
- }
- cout<
" "; - dfs(st);
- fer(i,1,n)
- {
- if(!vis[i])
- {
- cout<<0;
- break;
- }
- }
- }
问题 K: 基础实验6-2.3:拯救007
可以dfs也可以bfs,这里给出其中一种bfs的写法
我们把所有鳄鱼根据距离排序,然后开始跳,用遍历到的每一只鳄鱼更新其他鳄鱼的dist值
直至可以跳出或不能再跳
- #include
- #define int long long
- #define pb push_back
- #define fer(i,a,b) for(int i=a;i<=b;++i)
- #define der(i,a,b) for(int i=a;i>=b;--i)
- #define all(x) (x).begin(),(x).end()
- #define pll pair
- #define et cout<<'\n'
- #define xx first
- #define yy second
- using namespace std;
- template <typename _Tp>void input(_Tp &x){
- char ch(getchar());bool f(false);while(!isdigit(ch))f|=ch==45,ch=getchar();
- x=ch&15,ch=getchar();while(isdigit(ch))x=x*10+(ch&15),ch=getchar();
- if(f)x=-x;
- }
- template <typename _Tp,typename... Args>void input(_Tp &t,Args &...args){input(t);input(args...);}
- const int N=1e5+10;
- int n,r;
- int dist[N];
- const int INF=0x3f3f3f3f;
- struct Node{
- int x,y;
- double dis;
- };
- Node node[N];
- bool cmp(Node &a,Node &b){
- return a.dis
- }
- void bfs(){
- queue<int> q;
- for(int i=0;i
- if(node[i].dis>7.5&&node[i].dis<=7.5+r){
- q.push(i);
- dist[i]=1;
- }
- }
- while(q.size()){
- int u=q.front();
- q.pop();
- double nex=min(50-abs(node[u].x),50-abs(node[u].y));
- if(nex<=r){
- dist[n]=dist[u]+1;
- break;
- }
- for(int i=0;i
- if(dist[i]==INF){
- double next=sqrt((node[i].x-node[u].x)*(node[i].x-node[u].x)+(node[i].y-node[u].y)*(node[i].y-node[u].y));
- if(next<=r){
- dist[i]=dist[u]+1;
- q.push(i);
- }
- }
- }
- }
- }
- signed main(){
- fer(i,0,105) dist[i]=INF;
- input(n,r);
- if(r>=43){
- cout<<"Yes"<<'\n';
- return 0;
- }
- fer(i,0,n-1){
- input(node[i].x,node[i].y);
- node[i].dis=sqrt(node[i].x*node[i].x+node[i].y*node[i].y);
- }
- sort(node,node+n,cmp);
- bfs();
- if(dist[n]!=INF){
- cout<<"Yes"<<'\n';
- }
- else{
- cout<<"No"<<'\n';
- }
-
- }
-
相关阅读:
JS中的闭包
使用YOLOv5-C3模块识别图像天气 - P8
全面解读 AWS Private 5G 的革新理念
Unity 性能优化Shader分析处理函数:ShaderUtil.GetShaderGlobalKeywords用法
AtCoder abc 136
iOS 那些不为人知的bug: Error Domain=NSCocoaErrorDomain Code=3840
【云服务器 ECS 实战】云服务器新手指南(配置+使用详解)
Ajax 实战
Web前端开发与低代码开发——现状分析与未来发展
《八》QSplitter拆分器以及QDockWidget窗口详解
-
原文地址:https://blog.csdn.net/m0_61735576/article/details/127810290