首页 > 代码库 > 用邻接矩阵存储的有向图的非递归遍历
用邻接矩阵存储的有向图的非递归遍历
/************************************************** 有向图的非递归遍历, 程序假如图的强联通的 如果不是强联通简单修改即可。 *************************************************/ #include <iostream> #include <cstdio> using namespace std; const int maxsize = 100; typedef struct sqstack { int data[maxsize]; int top; }sqstack; void InitStack(sqstack &s) { s.top = -1; } bool StackEmpty(sqstack s) { if(s.top == -1) return true; else return false; } bool StackFull(sqstack s) { if(s.top == maxsize-1) return true; else return false; } bool Push(sqstack &s, int x) { if(s.top == maxsize-1) return false; s.data[++s.top] = x; return true; } bool Pop(sqstack &s, int &x) { if(s.top == -1) return false; x = s.data[s.top--]; return true; } bool GetTop(sqstack s, int &x) { if(s.top == -1) return false; x = s.data[s.top]; return true; } int mat[maxsize][maxsize]; int n, m; // 图的顶点和边。图的顶点标号从1到n void DFS(int v) { int tmp; bool vis[maxsize]; sqstack s; InitStack(s); memset(vis, false, sizeof(vis)); Push(s, v); vis[v] = true; while(!StackEmpty(s)) { Pop(s, tmp); printf("%d ", tmp); for(int i = 1; i <= n; i++) { if(mat[tmp][i]==1 && !vis[i]) { Push(s, i); vis[i] = true; // marked. } } } } void input_map() { int from, to; memset(mat, 0, sizeof(mat)); printf("请输入总的顶点数和边数:\n"); cin >> n >> m; printf("输入每一条边的起点和终点\n"); for(int i = 0; i < m; i++) { cin >> from >> to; mat[from][to] = 1; } } int main() { input_map(); printf("please input the start point\n"); int start; cin >> start; DFS(start); return 0; } /** Test: 6 8 1 2 1 4 2 3 2 4 3 6 4 5 5 3 6 5 **/
用邻接矩阵存储的有向图的非递归遍历
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。