• 北京化工大学数据结构2022/11/10作业 题解


    ---------------------------------------------------------------------------------------------------------------------------------

    如果以前没怎么写过dfs,一头雾水的

    晚上睡不着肝了个->

    (15条消息) 彻底搞懂dfs与回溯_lxrrrrrrrr的博客-CSDN博客

    希望这里面能说明白哈

    目录

    问题 A: 将邻接矩阵存储的图转换为邻接表存储的图,附加代码模式

    cpp代码:

    python代码:

    问题 B: 邻接表存储的图转化为邻接矩阵存储的图-附加代码模式

    cpp代码:

    python代码:

    问题 C: 邻接矩阵存储图的DFS(附加代码模式)

    问题 D: 邻接矩阵存储图的DFS-非递归算法(附加代码模式)

    问题 E: 邻接矩阵存储图的BFS

    问题 F: 案例6-1.2:邻接表存储图的广度优先遍历

    问题 G: 邻接矩阵存储图的DFS完成序求解(附加代码模式)

    问题 H: 案例6-1.1:DFS应用-计算可达城市对

    问题 I: 案例6-1.3:哥尼斯堡的“七桥问题”

    问题 J: 案例6-1.4:地下迷宫探索

    问题 K: 基础实验6-2.3:拯救007


    问题 A: 将邻接矩阵存储的图转换为邻接表存储的图,附加代码模式

    纯纯大模拟

    数据同学交python吧

    cpp代码:

    1. #include
    2. using namespace std;
    3. #define MAX_SIZE 100
    4. struct Graph{
    5. int vexNumber;
    6. string info[MAX_SIZE];
    7. int adjMatrix[MAX_SIZE][MAX_SIZE];
    8. };
    9. struct ArcNode
    10. {
    11. int weight;
    12. int adj;
    13. ArcNode *nextarc;
    14. };
    15. struct VexNode
    16. {
    17. string Info;
    18. ArcNode *firstarc;
    19. };
    20. struct linkGraph
    21. {
    22. VexNode *vexes;
    23. int vexnumber;
    24. };
    25. int InitGraph(linkGraph &G,int vexnumber)
    26. {
    27. G.vexes=new VexNode[vexnumber];
    28. G.vexnumber=vexnumber;
    29. for(int i=0;i
    30. {
    31. G.vexes[i].firstarc=nullptr;
    32. return 0;
    33. }
    34. }
    35. void InitGraph(linkGraph &G,const Graph& g)
    36. {
    37. int n=g.vexNumber;
    38. int flag[n]={0};
    39. InitGraph(G,n);
    40. for(int i=0;i
    41. {
    42. G.vexes[i].Info=(char)(i+'a');
    43. for(int j=0;j
    44. {
    45. if(g.adjMatrix[i][j]!=0)
    46. {ArcNode *p=new ArcNode;
    47. p->nextarc=G.vexes[i].firstarc;
    48. G.vexes[i].firstarc=p;
    49. p->adj=j;}
    50. }
    51. }
    52. }
    53. int DestroyGraph(linkGraph &G)
    54. {
    55. for(int i=0;i
    56. {
    57. while(G.vexes[i].firstarc!=nullptr)
    58. {
    59. ArcNode *p=G.vexes[i].firstarc;
    60. G.vexes[i].firstarc=p->nextarc;
    61. delete p;
    62. }
    63. }
    64. delete[]G.vexes;
    65. G.vexes=nullptr;
    66. G.vexnumber=0;
    67. return 0;
    68. }
    69. void PrintGraph(const linkGraph &G){
    70. for(int i=0;i
    71. {
    72. cout<
    73. ArcNode *p=G.vexes[i].firstarc;
    74. while(p)
    75. {
    76. cout<<" --> "<adj].Info;
    77. p=p->nextarc;
    78. }
    79. cout<<"\n";
    80. }
    81. }

    python代码:

    1. n=int(input())
    2. g=[]
    3. for i in range(0,n):
    4. s=input().split()
    5. g.append(s)
    6. for i in range(0,n):
    7. result=ord('a')+i
    8. result=[chr(result)]
    9. for j in range(n-1,-1,-1):
    10. if g[i][j]=='1':
    11. result.append(chr(ord('a')+j))
    12. print(' --> '.join(result))

    问题 B: 邻接表存储的图转化为邻接矩阵存储的图-附加代码模式

    cpp代码:

    1. #include
    2. #include
    3. #include
    4. using namespace std;
    5. #define size 100;
    6. struct Graph{
    7. int vexNumber;
    8. string info[100];
    9. int adjMatrix[100][100];
    10. };//邻接矩阵存储的图
    11. struct ArcNode{
    12. char weight;//弧上的信息
    13. int adj;//序号
    14. ArcNode* nextarc;
    15. };//弧结点定义
    16. struct VexNode{
    17. char Info;//顶点信息
    18. VexNode* nextarc;
    19. };
    20. struct linkGraph{
    21. VexNode *vexes;
    22. int vexnumber;
    23. int Matrix[100][100];
    24. };
    25. ArcNode* getArcNode(int adj){
    26. ArcNode* node=new ArcNode();
    27. return node;
    28. }
    29. void InputlinkGraph(linkGraph& lg){
    30. int n;
    31. cin>>n;
    32. lg.vexnumber=n;
    33. for(int i=0;i
    34. for(int j=0;j
    35. lg.Matrix[i][j]=0;
    36. }
    37. }
    38. char str[10];
    39. while(n--){
    40. cin>>str;
    41. char c=str[0];
    42. for(int i=1;i<strlen(str);i++){
    43. if(str[i]!='-'){
    44. lg.Matrix[c-'a'][str[i]-'a']=1;
    45. }
    46. }
    47. }
    48. return;
    49. }
    50. void linkGraph2Graph(const linkGraph&lg,Graph& g){
    51. return;
    52. }
    53. void printGraph(const Graph&g){
    54. return;
    55. }
    56. void PrintlinkGraph(linkGraph&g){
    57. for(int i=0;i
    58. cout<<(char)('a'+i)<<" ";
    59. for(int j=g.vexnumber-1;j>=0;j--){
    60. if(g.Matrix[i][j]==1){
    61. cout<<"--> ";
    62. cout<<(char)('a'+j)<<" ";
    63. }
    64. }cout<
    65. }
    66. for(int i=0;i
    67. for(int j=0;j
    68. cout<" ";
    69. }
    70. cout<
    71. }
    72. return;
    73. }
    74. int DestroylinkGraph(linkGraph&g){
    75. return 0;
    76. }

    python代码:

    1. n=int(input())
    2. v=[]
    3. g=[]
    4. for i in range(0,n):
    5. g.append([0]*n)
    6. for i in range(0,n):
    7. v.append(input().split('-'))
    8. for i in range(0,n):
    9. begin = v[i][0]
    10. for j in range(1,len(v[i])):
    11. ind=ord(v[i][j])-ord('a')
    12. g[i][ind]=1
    13. for i in range(0,n):
    14. print(' --> '.join(v[i]))
    15. for i in range(0,n):
    16. print(' '.join(map(str,g[i])))

    问题 C: 邻接矩阵存储图的DFS(附加代码模式)

    dfs板子

    1. #include
    2. using namespace std;
    3. #define MAXSIZE 100
    4. // 邻接矩阵存储的图型数据结构
    5. struct Graph{
    6. int vexNumber;
    7. string vexInfo[MAXSIZE];
    8. int adjMatrix[MAXSIZE][MAXSIZE];
    9. };
    10. void DFS(Graph G, int v, int st[]){
    11. cout<" ";
    12. st[v] = 1;
    13. for(int i=0;i
    14. if(!st[i] && G.adjMatrix[v][i] == 1){
    15. DFS(G,i,st);
    16. }
    17. }
    18. }
    19. void DFS(Graph G){
    20. int st[150];
    21. memset(st,0,sizeof st);
    22. for(int i=0;i
    23. if(!st[i]){
    24. DFS(G, i , st);
    25. }
    26. }
    27. }

    问题 D: 邻接矩阵存储图的DFS-非递归算法(附加代码模式)

    1. #include
    2. #include
    3. #include
    4. #include
    5. #include
    6. using namespace std;
    7. #define MAX_SIZE 100
    8. // 邻接矩阵存储的图
    9. struct Graph
    10. {
    11. int vexNumber;
    12. string vexInfo[MAX_SIZE];
    13. int adjMatrix[MAX_SIZE][MAX_SIZE];
    14. };
    15. // 查找v0的未被访问的邻接点
    16. int findAdjVex(const Graph& G, int v0, int visited[]){
    17. for (int i=0;i
    18. if (G.adjMatrix[v0][i]==1 && !visited[i]) {
    19. return i;
    20. }
    21. }
    22. return -1;
    23. }
    24. // 以顶点v0为起点,进行一趟DFS
    25. string DFS(const Graph& G, int v0, int visited[]){
    26. string result = G.vexInfo[v0];
    27. visited[v0] = 1;
    28. int adj;
    29. while ((adj = findAdjVex(G, v0, visited)) != -1) {
    30. result += " ";
    31. result += DFS(G, adj, visited);
    32. }
    33. return result;
    34. }
    35. // 对整个图进行DFS
    36. string DFS(const Graph& G){
    37. string result = "";
    38. // 第一步:初始化visited数组
    39. int visited[MAX_SIZE] = { 0 };
    40. // 第二步:以每个未被遍历的顶点为起点,进行DFS
    41. for (int i = 0; i < G.vexNumber; ++i) {
    42. if (!visited[i]) {
    43. result += DFS(G, i, visited);
    44. }
    45. }
    46. return result;
    47. }

    问题 E: 邻接矩阵存储图的BFS

    bfs板子,只不过是邻接矩阵的

    1. #include
    2. #define int long long
    3. #define pb push_back
    4. #define fer(i,a,b) for(int i=a;i<=b;++i)
    5. #define der(i,a,b) for(int i=a;i>=b;--i)
    6. #define all(x) (x).begin(),(x).end()
    7. #define pll pair
    8. #define et cout<<'\n'
    9. #define xx first
    10. #define yy second
    11. using namespace std;
    12. template <typename _Tp>void input(_Tp &x){
    13. char ch(getchar());bool f(false);while(!isdigit(ch))f|=ch==45,ch=getchar();
    14. x=ch&15,ch=getchar();while(isdigit(ch))x=x*10+(ch&15),ch=getchar();
    15. if(f)x=-x;
    16. }
    17. template <typename _Tp,typename... Args>void input(_Tp &t,Args &...args){input(t);input(args...);}
    18. const int N=1e6+10;
    19. int M[60][60];
    20. bool st[60];
    21. int n;
    22. void bfs(int i){
    23. queue<int> q;
    24. q.push(i);
    25. while(q.size()){
    26. auto t=q.front();
    27. q.pop();
    28. for(int i=0;i
    29. if(M[t][i]&&!st[i]){
    30. cout<" ";
    31. q.push(i);
    32. st[i]=1;
    33. }
    34. }
    35. }
    36. }
    37. signed main()
    38. {
    39. cin>>n;
    40. for(int i=0;i
    41. for(int j=0;j
    42. cin>>M[i][j];
    43. }
    44. }
    45. for(int i=0;i
    46. if(!st[i]){
    47. st[i]=1;
    48. cout<' ';
    49. bfs(i);
    50. }
    51. }
    52. }

    问题 F: 案例6-1.2:邻接表存储图的广度优先遍历

    这题也注意下排序,然后就是bfs板子了

    1. #include
    2. #define int long long
    3. #define pb push_back
    4. #define fer(i,a,b) for(int i=a;i<=b;++i)
    5. #define der(i,a,b) for(int i=a;i>=b;--i)
    6. #define all(x) (x).begin(),(x).end()
    7. #define pll pair
    8. #define et cout<<'\n'
    9. #define xx first
    10. #define yy second
    11. using namespace std;
    12. template <typename _Tp>void input(_Tp &x){
    13. char ch(getchar());bool f(false);while(!isdigit(ch))f|=ch==45,ch=getchar();
    14. x=ch&15,ch=getchar();while(isdigit(ch))x=x*10+(ch&15),ch=getchar();
    15. if(f)x=-x;
    16. }
    17. template <typename _Tp,typename... Args>void input(_Tp &t,Args &...args){input(t);input(args...);}
    18. const int N=1e6+10;
    19. vector<int> v[N];
    20. int vis[N];
    21. void bfs(int x){
    22. queue<int>q;
    23. q.push(x);
    24. while(q.size()){
    25. int now=q.front();
    26. q.pop();
    27. if(vis[now]==1) continue;
    28. vis[now]=1;
    29. cout<" ";
    30. for(auto t:v[now]){
    31. if(vis[t]) continue;
    32. q.push(t);
    33. }
    34. }
    35. }
    36. signed main(){
    37. int n,m,x;
    38. input(n,m,x);
    39. fer(i,1,m){
    40. int a,b;
    41. input(a,b);
    42. v[a].push_back(b);
    43. v[b].push_back(a);
    44. }
    45. fer(i,0,n-1){
    46. sort(v[i].begin(),v[i].end());
    47. }
    48. bfs(x);
    49. }

    问题 G: 邻接矩阵存储图的DFS完成序求解(附加代码模式)

    裸dfs

    1. #include
    2. #include
    3. #include
    4. #include
    5. #include
    6. using namespace std;
    7. #define MAX_SIZE 100
    8. struct Graph
    9. {
    10. int vexNumber;
    11. string vexInfo[MAX_SIZE];
    12. int adjMatrix[MAX_SIZE][MAX_SIZE];
    13. };
    14. int findAdjVex(const Graph& G, int v0, int visited[]){
    15. return 0;
    16. }
    17. string DFS_finished(const Graph &G, int v0, int visited[]){
    18. string res="";
    19. visited[v0]=1;
    20. for(int i=0;i
    21. if(G.adjMatrix[v0][i]==1&& !visited[i]){
    22. res+=DFS_finished(G,i,visited);
    23. }
    24. }
    25. res+=(char)(v0+'a');
    26. return res;
    27. }
    28. string DFS_finished(const Graph &G){
    29. string res="";
    30. int n=G.vexNumber;
    31. int visited[MAX_SIZE]={};
    32. for(int i=0;i
    33. if(!visited[i]) res+=DFS_finished(G,i,visited);
    34. }
    35. return res;
    36. }

    问题 H: 案例6-1.1:DFS应用-计算可达城市对

    这题数据比较小,相当于dfs板子题了

    对于每个点dfs一遍统计答案

    这道题的进阶版[JSOI2010]连通数 - 洛谷

    原题是要tarjan缩点的,有兴趣的同学可以研究下

    1. #include
    2. #define int long long
    3. #define pb push_back
    4. #define fer(i,a,b) for(int i=a;i<=b;++i)
    5. #define der(i,a,b) for(int i=a;i>=b;--i)
    6. #define all(x) (x).begin(),(x).end()
    7. #define pll pair
    8. #define et cout<<'\n'
    9. #define xx first
    10. #define yy second
    11. using namespace std;
    12. template <typename _Tp>void input(_Tp &x){
    13. char ch(getchar());bool f(false);while(!isdigit(ch))f|=ch==45,ch=getchar();
    14. x=ch&15,ch=getchar();while(isdigit(ch))x=x*10+(ch&15),ch=getchar();
    15. if(f)x=-x;
    16. }
    17. template <typename _Tp,typename... Args>void input(_Tp &t,Args &...args){input(t);input(args...);}
    18. const int N=1e6+10;
    19. using namespace std;
    20. vector<int> v[N];
    21. bool vis[N];
    22. int m,n;
    23. int dfs(int x){
    24. int res=1;
    25. vis[x]=1;
    26. for(auto t:v[x]){
    27. if(!vis[t]){
    28. res+=dfs(t);
    29. }
    30. }
    31. return res;
    32. }
    33. signed main(){
    34. int ans=0;
    35. input(n,m);
    36. int x,y;
    37. fer(i,1,m){
    38. input(x,y);
    39. v[x].pb(y);
    40. }
    41. fer(i,1,n){
    42. memset(vis,0,sizeof vis);
    43. ans+=dfs(i);
    44. }
    45. cout<
    46. }

    问题 I: 案例6-1.3:哥尼斯堡的“七桥问题”

    欧拉回路:每条边都要经过一次,并且回到出发点

    欧拉回路可以有很多方法求,dfs不是很好写,这里给出一种并查集的求法

    不懂并查集可以搜一下

    首先一定整张图一定要连通(这好像是废话,但得判断一下,也就是ans==1的部分)

    (在并查集中,有几个fa[i]=i,证明有几个连通块,没听过可以了解一下)

    其次,所有点的度必须为偶数(度:无向图中一个点连有几条边度就是几)

    因为欧拉回路既然是回路就得一来一回,奇数肯定不行

    满足这俩条件就是有欧拉回路

    1. #include
    2. #define int long long
    3. #define pb push_back
    4. #define fer(i,a,b) for(int i=a;i<=b;++i)
    5. #define der(i,a,b) for(int i=a;i>=b;--i)
    6. #define all(x) (x).begin(),(x).end()
    7. #define pll pair
    8. #define et cout<<'\n'
    9. #define xx first
    10. #define yy second
    11. using namespace std;
    12. template <typename _Tp>void input(_Tp &x){
    13. char ch(getchar());bool f(false);while(!isdigit(ch))f|=ch==45,ch=getchar();
    14. x=ch&15,ch=getchar();while(isdigit(ch))x=x*10+(ch&15),ch=getchar();
    15. if(f)x=-x;
    16. }
    17. template <typename _Tp,typename... Args>void input(_Tp &t,Args &...args){input(t);input(args...);}
    18. const int N=1e6+10;
    19. int fa[N];
    20. int find(int x){
    21. if(fa[x]!=x) fa[x]=find(fa[x]);
    22. return fa[x];
    23. }
    24. int w[N];
    25. signed main()
    26. {
    27. int n,m;
    28. fer(i,0,1000) fa[i]=i;
    29. input(n,m);
    30. while(m--)
    31. {
    32. int a,b;
    33. input(a,b);
    34. if(find(a)!=find(b)){
    35. fa[find(a)]=find(b);
    36. }
    37. w[a]++;
    38. w[b]++;
    39. }
    40. int ans=0;
    41. int flag=1;
    42. fer(i,1,n)
    43. {
    44. if(w[i]%2!=0){
    45. flag=0;
    46. }
    47. if(fa[i]==i){
    48. ans++;
    49. }
    50. }
    51. if(ans!=1){
    52. flag=0;
    53. }
    54. if(flag){
    55. cout<<"1"<<'\n';
    56. }
    57. else{
    58. cout<<"0"<<'\n';
    59. }
    60. }

    问题 J: 案例6-1.4:地下迷宫探索

    这题注意dfs的时候排下序

    我们只要从起点dfs一遍,如果还有没到过的点,说明不是连通图,在输出一个0

    1. #include
    2. #define int long long
    3. #define pb push_back
    4. #define fer(i,a,b) for(int i=a;i<=b;++i)
    5. #define der(i,a,b) for(int i=a;i>=b;--i)
    6. #define all(x) (x).begin(),(x).end()
    7. #define pll pair
    8. #define et cout<<'\n'
    9. #define xx first
    10. #define yy second
    11. using namespace std;
    12. template <typename _Tp>void input(_Tp &x){
    13. char ch(getchar());bool f(false);while(!isdigit(ch))f|=ch==45,ch=getchar();
    14. x=ch&15,ch=getchar();while(isdigit(ch))x=x*10+(ch&15),ch=getchar();
    15. if(f)x=-x;
    16. }
    17. template <typename _Tp,typename... Args>void input(_Tp &t,Args &...args){input(t);input(args...);}
    18. const int N=1e4+10;
    19. int n,m,st;
    20. vector<int >v[N];
    21. stack<int>s;
    22. bool vis[N];
    23. void dfs(int k)
    24. {
    25. vis[k]=1;
    26. sort(v[k].begin(),v[k].end());
    27. for(auto t:v[k]){
    28. if(!vis[t]){
    29. s.push(k);
    30. cout<" ";
    31. dfs(t);
    32. }
    33. }
    34. if(k!=st)
    35. {
    36. cout<top()<<' ';
    37. s.pop();
    38. }
    39. }
    40. signed main()
    41. {
    42. input(n,m,st);
    43. fer(i,1,m)
    44. {
    45. int a,b;
    46. input(a,b);
    47. v[a].push_back(b);
    48. v[b].push_back(a);
    49. }
    50. cout<" ";
    51. dfs(st);
    52. fer(i,1,n)
    53. {
    54. if(!vis[i])
    55. {
    56. cout<<0;
    57. break;
    58. }
    59. }
    60. }

    问题 K: 基础实验6-2.3:拯救007

    可以dfs也可以bfs,这里给出其中一种bfs的写法

    我们把所有鳄鱼根据距离排序,然后开始跳,用遍历到的每一只鳄鱼更新其他鳄鱼的dist值

    直至可以跳出或不能再跳

    1. #include
    2. #define int long long
    3. #define pb push_back
    4. #define fer(i,a,b) for(int i=a;i<=b;++i)
    5. #define der(i,a,b) for(int i=a;i>=b;--i)
    6. #define all(x) (x).begin(),(x).end()
    7. #define pll pair
    8. #define et cout<<'\n'
    9. #define xx first
    10. #define yy second
    11. using namespace std;
    12. template <typename _Tp>void input(_Tp &x){
    13. char ch(getchar());bool f(false);while(!isdigit(ch))f|=ch==45,ch=getchar();
    14. x=ch&15,ch=getchar();while(isdigit(ch))x=x*10+(ch&15),ch=getchar();
    15. if(f)x=-x;
    16. }
    17. template <typename _Tp,typename... Args>void input(_Tp &t,Args &...args){input(t);input(args...);}
    18. const int N=1e5+10;
    19. int n,r;
    20. int dist[N];
    21. const int INF=0x3f3f3f3f;
    22. struct Node{
    23. int x,y;
    24. double dis;
    25. };
    26. Node node[N];
    27. bool cmp(Node &a,Node &b){
    28. return a.dis
    29. }
    30. void bfs(){
    31. queue<int> q;
    32. for(int i=0;i
    33. if(node[i].dis>7.5&&node[i].dis<=7.5+r){
    34. q.push(i);
    35. dist[i]=1;
    36. }
    37. }
    38. while(q.size()){
    39. int u=q.front();
    40. q.pop();
    41. double nex=min(50-abs(node[u].x),50-abs(node[u].y));
    42. if(nex<=r){
    43. dist[n]=dist[u]+1;
    44. break;
    45. }
    46. for(int i=0;i
    47. if(dist[i]==INF){
    48. 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));
    49. if(next<=r){
    50. dist[i]=dist[u]+1;
    51. q.push(i);
    52. }
    53. }
    54. }
    55. }
    56. }
    57. signed main(){
    58. fer(i,0,105) dist[i]=INF;
    59. input(n,r);
    60. if(r>=43){
    61. cout<<"Yes"<<'\n';
    62. return 0;
    63. }
    64. fer(i,0,n-1){
    65. input(node[i].x,node[i].y);
    66. node[i].dis=sqrt(node[i].x*node[i].x+node[i].y*node[i].y);
    67. }
    68. sort(node,node+n,cmp);
    69. bfs();
    70. if(dist[n]!=INF){
    71. cout<<"Yes"<<'\n';
    72. }
    73. else{
    74. cout<<"No"<<'\n';
    75. }
    76. }

  • 相关阅读:
    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