数据结构练习程序 喜欢ヅ旅行 2022-08-18 11:36 104阅读 0赞 今天朋友托我写一份程序,大二本科生的数据结构课程实验。要是以前的话,肯定先要定义图的邻接表结构,图的输入输出操作,图的遍历,写了很多代码。但是现在也仅仅越简洁越实用越好,这可能是由于时过境迁,人的心境也就变了。 问题描述:图的路径遍历要比结点遍历具有更为广泛的应用。写一个路径遍历算法,求出从结点L到结点I中途不过结点K的所有简单路径。(图的存储结构没有要求) ![这里写图片描述][20151214160845575] /* ============================================== * Simple path * Author:WinCoder@qq.com * 2015.12.14 */ #include <iostream> #include <queue> #include <stack> using namespace std; typedef struct { char data[13]; int matrix[13][13]; }Graph; Graph g = { { 'A','B','C','D','E','F','G','H','I','J','K','L','M'}, { { 0,1,1,0,0,1,0,0,0,0,0,1,0}, { 1,0,1,1,0,0,1,1,0,0,0,0,1}, { 1,1,0,0,0,0,0,0,0,0,0,0,0}, { 0,1,0,0,1,0,0,0,0,0,0,0,0}, { 0,0,0,1,0,0,0,0,0,0,0,0,0}, { 1,0,0,0,0,0,0,0,0,0,0,0,0}, { 0,1,0,0,0,0,0,1,1,0,1,0,0}, { 0,1,0,0,0,0,1,0,0,0,1,0,0}, { 0,0,0,0,0,0,1,0,0,0,0,0,0}, { 0,0,0,0,0,0,0,0,0,0,0,1,1}, { 0,0,0,0,0,0,0,1,0,1,0,0,0}, { 1,0,0,0,0,0,0,0,0,1,0,0,1}, { 0,1,0,0,0,0,0,0,0,1,0,1,0} } }; deque<int> path; //i是出发,j是目标,k是不经过节点 void dfs(Graph g,int i,int j,int k) { if(i == k || (path.end()!=find(path.begin(),path.end(),i))) return; path.push_back(i); if(i == j) { cout<<"Simple path: "; for(int n = 0;n< path.size(); n++) { cout<<g.data[path[n]]<<" "; } cout<<endl; path.pop_back(); return; } for(int n = 0;n<13;n++) { if(g.matrix[i][n] == 1) { dfs(g,n,j,k); } } path.pop_back(); } int main() { dfs(g,11,8,10); getchar(); } 运行结果是只有8条简单路径,简单路径是指没有回路的路径。 ![这里写图片描述][20151214160958521] [20151214160845575]: /images/20220731/b9322c57a7754b3fb9a0f30c36e8d41a.png [20151214160958521]: /images/20220731/4d0adf3452c0470a9714bd8d0ab37636.png
还没有评论,来说两句吧...