当前位置： 首页 > article >正文

实验8 图的操作

article 2024/11/17 13:23:34

0x01 实验目的

掌握无向图的创建、遍历方法。

0x02 实验内容

  1. 创建图类，存储结构使用邻接矩阵。
  2. 输入图的节点数n(小于10个)、边数m，节点分别用1-n代表。
  3. 采用“起始节点，终止节点，权值”输入图的m条边，创建图。
  4. 输出从节点1开始的BFS广度遍历，在遍历过程中，如果从一个节点出发有多个可以选择的节点，则优先选择编号较小的节点。
  5. 输出从节点1开始的DFS深度遍历，在遍历过程中，如果从一个节点出发有多个可以选择的节点，则优先选择编号较小的节点。
  6. 输出从第1节点到最后一个节点（即第n个节点）最短路径的长度，如果没有路经，输出0。

0x03 实验过程分析

建立Class-graph

  • node：点数
  • edge：边数
  • noEdge：无边的标识
  • a：二维数组（指针形式的创建过程）二维数组的值代表权重
class graph {
	public:
		graph(int n, int e) {
			node = n;
			edge = e;
			a = new int *[n+1];
			for(int i = 1; i <= n; i++) {
				a[i] = new int[n+1];
				for(int j = 1; j <= n; j++) {
					a[i][j] = noEdge;
				}
			}
		}
	private:
		int node;
		int edge;
		int ** a;
		int noEdge = 0;
};

插入边操作

因为是无向图，所以边是相互的。

        void insertEdge(int start, int end, int weight) {
			a[start][end] = weight;
			a[end][start] = weight;
        }

广度优先搜索

用队列，因为要求输出逗号，所以写的比较复杂。

		void BFS(int v, int reach[], int label) {
			bool flag = false;
			queue<int> q;
			reach[v] = label;
			q.push(v);
			while(!q.empty()) {
				int w = q.front();
				q.pop();
				if(flag == false) {
					flag = true;
					cout<<w;
				} else cout<<","<<w;
				for(int i = 1; i <= node; i++) {
					if(a[w][i] != 0 && reach[i] != label) {
						q.push(i);
						reach[i] = label;
					}
				}
			}
		}

简化后：无输出。

  • v：搜索的起点
  • reach：存储该点是否到达过
  • label：到达后的标记
		void BFS(int v, int reach[], int label) {
			queue<int> q;
			reach[v] = label;
			q.push(v);
			while(!q.empty()) {
				int w = q.front();
				q.pop();
				for(int i = 1; i <= node; i++) {
				    //当有这条边&没到达过才会将其入队
					if(a[w][i] != 0 && reach[i] != label) {
						q.push(i);
						reach[i] = label;
					}
				}
			}
		}

深度优先搜索

用堆栈，递归调用的思想。

		void DFS(int v, int reach[], int label) {
			reach[v] = label;
			if(fl == false) {
				cout<<v;
				fl = true;
			} else {
				cout<<","<<v;
			}
			for(int i = 1; i <= node; i++) {
				if(a[v][i] != 0 && reach[i] != label) {
					DFS(i,reach,label);
				}
			}
		}

同样，简化后代码：

  • v：搜索的起点
  • reach：存储该点是否到达过
  • label：到达后的标记

因为要求从小的数开始输出，所以没有“恢复”

		void DFS(int v, int reach[], int label) {
			reach[v] = label;
			for(int i = 1; i <= node; i++) {
				if(a[v][i] != 0 && reach[i] != label) {
					DFS(i,reach,label);
				}
			}
		}

加上“恢复”：

void DFS(int v, int reach[], int label) {
			reach[v] = label;
			for(int i = 1; i <= node; i++) {
				if(a[v][i] != 0 && reach[i] != label) {
					DFS(i,reach,label);
					reach[i] = 0;
				}
			}
		}

最短路径（起点到终点）

我的思路是：

  1. 首先，用宽度优先搜索，判断是否能够到达终点（看是否被到达标记标记到），不能的话，直接return 0；
  2. 然后，用深度优先搜索（必须用带“恢复”的，因为此时我们要遍历全部的路径，求他们的权重比较，而不只是遵循该规则的路径 – 如果从一个节点出发有多个可以选择的节点，则优先选择编号较小的节点），寻找每一条从起点到终点的路径，然后比较它们的权重，取最小值，最后返回。
int pathLength(int start) {
			int reach[100] = {0};
			int rea[100] = {0};
			bfs(1,reach,2);
			if(reach[node] != 2) return 0;
			else {
				dfs(1,rea,2,0);
				return crr[0];
			}
		}
		void dfs(int v, int reach[], int label, int weight) {
			reach[1] = label;
			for(int i = 1; i <= node; i++) {
				if(a[v][i] != 0 && reach[i] != label) {
					weight += a[v][i];
					//到达终点就退出
					if(i == node) {
					    //与之前的权重比较，小就保留，大就舍弃
						if(weight < crr[0]) crr[0] = weight;
						return;
					} else {
						reach[i] = label;
						dfs(i,reach,label,weight);
						reach[i] = 0;
						//一定要减掉，不仅要恢复标记，还要恢复权重，否则结果会偏大
						weight -= a[v][i];
					}
				}
			}
		}
		void bfs(int v, int reach[], int label) {
			queue<int> q;
			reach[v] = label;
			q.push(v);
			while(!q.empty()) {
				int w = q.front();
				q.pop();
				for(int i = 1; i <= node; i++) {
					if(a[w][i] != 0 && reach[i] != label) {
						q.push(i);
						reach[i] = label;
					}
				}
			}
		}

输入处理

输入全都是字符串，属实是绷不住了，处理麻烦死了 。
直接看下面完整代码叭。。

在这贴一组测试数据

输入
5,8
1,2,10
1,3,50
1,5,100
2,3,200
2,4,30
3,4,290
3,5,250
4,5,280
输出
1，2，3，5，4
1，2，3，4，5
100

0x04 完整代码

#include<bits/stdc++.h>
using namespace std;
const int M = 100;
int arr[M];
int brr[M];
int crr[M];
int path[M];
bool fl = false;
class graph {
	public:
		graph(int n, int e) {
			node = n;
			edge = e;
			a = new int *[n+1];
			for(int i = 1; i <= n; i++) {
				a[i] = new int[n+1];
				for(int j = 1; j <= n; j++) {
					a[i][j] = noEdge;
				}
			}
		}
		void insertEdge(int start, int end, int weight) {
			a[start][end] = weight;
			a[end][start] = weight;
		}
		void BFS(int v, int reach[], int label) {
			bool flag = false;
			queue<int> q;
			reach[v] = label;
			q.push(v);
			while(!q.empty()) {
				int w = q.front();
				q.pop();
				if(flag == false) {
					flag = true;
					cout<<w;
				} else cout<<","<<w;
				for(int i = 1; i <= node; i++) {
					if(a[w][i] != 0 && reach[i] != label) {
						q.push(i);
						reach[i] = label;
					}
				}
			}
		}
		void DFS(int v, int reach[], int label) {
			reach[v] = label;
			if(fl == false) {
				cout<<v;
				fl = true;
			} else {
				cout<<","<<v;
			}
			for(int i = 1; i <= node; i++) {
				if(a[v][i] != 0 && reach[i] != label) {
					DFS(i,reach,label);
				}
			}
		}
		int pathLength(int start) {
			int reach[100] = {0};
			int rea[100] = {0};
			bfs(1,reach,2);
			if(reach[node] != 2) return 0;
			else {
				dfs(1,rea,2,0);
				return crr[0];
			}
		}
		void dfs(int v, int reach[], int label, int weight) {
			reach[1] = label;
			for(int i = 1; i <= node; i++) {
				if(a[v][i] != 0 && reach[i] != label) {
					weight += a[v][i];
					if(i == node) {
						if(weight < crr[0]) crr[0] = weight;
						return;
					} else {
						reach[i] = label;
						dfs(i,reach,label,weight);
						reach[i] = 0;
						weight -= a[v][i];
					}
				}
			}
		}
		void bfs(int v, int reach[], int label) {
			queue<int> q;
			reach[v] = label;
			q.push(v);
			while(!q.empty()) {
				int w = q.front();
				q.pop();
				for(int i = 1; i <= node; i++) {
					if(a[w][i] != 0 && reach[i] != label) {
						q.push(i);
						reach[i] = label;
					}
				}
			}
		}
	private:
		int node;
		int edge;
		int ** a;
		int noEdge = 0;
};
int main() {
	cout<<"Input"<<endl;
	string n = "",m = "";
	string S;
	cin>>S;
	int temp;
	for(int i = 0; i < S.length(); i++) {
		if(S.at(i) == ',') {
			temp = i;
			break;
		}
	}
	for(int p = 0; p < temp; p++) {
		n += S.at(p);
	}
	for(int p = temp + 1; p < S.length(); p++) {
		m += S.at(p);
	}
	int num1 = stoi(n);
	int num2 = stoi(m); 
	graph g(num1,num2);
	for(int i = 0; i < num2; i++) {
		string s;
		cin>>s;
		int fir = 0;
		int sec = 0;
		for(int j = 0; j < s.length(); j++) {
			if(s.at(j) == ',' && fir == 0) fir = j;
			else if(s.at(j) == ',' && fir != 0) {
				sec = j;
				break;
			}
		}
		string s1 = "";
		string s2 = "";
		string s3 = "";
		for(int p = 0; p < fir; p++) {
			s1 += s.at(p);
		}
		for(int q = fir + 1; q < sec; q++) {
			s2 += s.at(q);
		}
		for(int o = sec + 1; o < s.length(); o++) {
			s3 += s.at(o);
		}
		g.insertEdge(stoi(s1), stoi(s2), stoi(s3));
	}
	cout<<"Output"<<endl;
	g.BFS(1,arr,2);
	cout<<endl;
	g.DFS(1,brr,2);
	cout<<endl;
	//让第0组权重无限大，其他就都会比他小了（
	crr[0] = 10000000;
	int ans = g.pathLength(1);
	cout<<ans<<endl;
	cout<<"End";
	return 0;
}

http://www.kler.cn/a/154658.html

相关文章：

  • RHCE的学习（20）
  • [Python学习日记-67] 封装
  • 论文 | On Second Thought, Let’s Not Think Step by Step!
  • 直接映射缓存配置
  • 民事诉讼中，火灾事故认定书并非不可推翻，其证明力弱于鉴定意见
  • 基于STM32的智能家居安防系统设计
  • LangChain（0.0.339）官方文档四：Prompts下——prompt templates的存储、加载、组合和部分格式化
  • 肖sir__mysql之单表练习题2__(2)
  • 吉利展厅 | 透明OLED拼接2x2：科技与艺术的完美融合
  • 西南科技大学模拟电子技术实验四（集成运算放大器的线性应用）预习报告
  • Java Web——动态Web开发核心-Servlet
  • TA-Lib学习研究笔记（八）——Momentum Indicators 中
  • TLS、对称/非对称加密、CA认证
  • Zabbix HA高可用集群搭建
  • Node.js 事件循环：定时任务、延迟任务和 I/O 事件的艺术
  • 编程实战：类C语法的编译型脚本解释器（五）
  • HarmonyOS——解决本地模拟器无法选择设备的问题
  • 编程实战：类C语法的编译型脚本解释器（三）
  • 2312skia,15vulkan及技巧
  • Go语言实现深度学习的正向传播和反向传播
  • 深入理解Servlet(上)
  • 深度学习记录--计算图(前向后向传播)
  • 最新AI智能写作回答系统源码 附完整的搭建教程
  • java学习part29线程通信
  • 锐捷EWEB网管系统 RCE漏洞复现
  • oracle sql相关语法