免费的行情软件网站下载免费,苏州城乡和住房建设局网站首页,如何创建个人网站英语作文,无锡网站制作哪家好0x01 实验目的
掌握无向图的创建、遍历方法。
0x02 实验内容
创建图类#xff0c;存储结构使用邻接矩阵。输入图的节点数n(小于10个)、边数m#xff0c;节点分别用1-n代表。采用“起始节点#xff0c;终止节点#xff0c;权值”输入图的m条边#xff0c;创建图。输出从…0x01 实验目的
掌握无向图的创建、遍历方法。
0x02 实验内容
创建图类存储结构使用邻接矩阵。输入图的节点数n(小于10个)、边数m节点分别用1-n代表。采用“起始节点终止节点权值”输入图的m条边创建图。输出从节点1开始的BFS广度遍历在遍历过程中如果从一个节点出发有多个可以选择的节点则优先选择编号较小的节点。输出从节点1开始的DFS深度遍历在遍历过程中如果从一个节点出发有多个可以选择的节点则优先选择编号较小的节点。输出从第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 *[n1];for(int i 1; i n; i) {a[i] new int[n1];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;queueint q;reach[v] label;q.push(v);while(!q.empty()) {int w q.front();q.pop();if(flag false) {flag true;coutw;} 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) {queueint 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) {coutv;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;}}}最短路径起点到终点
我的思路是
首先用宽度优先搜索判断是否能够到达终点看是否被到达标记标记到不能的话直接return 0然后用深度优先搜索必须用带“恢复”的因为此时我们要遍历全部的路径求他们的权重比较而不只是遵循该规则的路径 – 如果从一个节点出发有多个可以选择的节点则优先选择编号较小的节点寻找每一条从起点到终点的路径然后比较它们的权重取最小值最后返回。
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) {queueint 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输出
12354
12345
1000x04 完整代码
#includebits/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 *[n1];for(int i 1; i n; i) {a[i] new int[n1];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;queueint q;reach[v] label;q.push(v);while(!q.empty()) {int w q.front();q.pop();if(flag false) {flag true;coutw;} 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) {coutv;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) {queueint 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() {coutInputendl;string n ,m ;string S;cinS;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;cins;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));}coutOutputendl;g.BFS(1,arr,2);coutendl;g.DFS(1,brr,2);coutendl;//让第0组权重无限大其他就都会比他小了crr[0] 10000000;int ans g.pathLength(1);coutansendl;coutEnd;return 0;
}
