C语言实现图的遍历之深度优先搜索实例
更新时间:2020年4月25日 17:40 点击:2005
DFS(Depth-First-Search)深度优先搜索算法是图的遍历算法中非常常见的一类算法。分享给大家供大家参考。具体方法如下:
#include <iostream> #include <algorithm> #include <iterator> using namespace std; #define MAX_VERTEX_NUM 10 struct Node { int adjvex; struct Node *next; int info; }; typedef struct VNode { char data; Node *first; }VNode, AdjList[MAX_VERTEX_NUM]; struct Graph { AdjList vertices; int vexnum, arcnum; }; int visited[MAX_VERTEX_NUM]; int locateVex(Graph G, char u) { int i; for (i = 0; i < G.vexnum; i++) { if (u == G.vertices[i].data) return i; } if (i == G.vexnum) { printf("Error u!\n"); exit(1); } return 0; } void createGraph(Graph &G) { int i, j, k, w; char v1, v2, enter; Node *p; printf("input vexnum & arcnum:\n"); scanf("%d", &G.vexnum); scanf("%d", &G.arcnum); printf("input vertices:\n"); for (i = 0; i < G.vexnum; i++) { scanf("%c%c", &enter, &G.vertices[i].data); G.vertices[i].first = NULL; } printf("input Arcs(v1, v2, w):\n"); for (k = 0; k < G.arcnum; k++) { scanf("%c%c", &enter, &v1); scanf("%c%c", &enter, &v2); scanf("%d", &w); i = locateVex(G, v1); j = locateVex(G, v2); p = (Node *)malloc(sizeof(Node)); p->adjvex = j; p->info = w; p->next = G.vertices[i].first; G.vertices[i].first = p; } } void DFS(Graph &G, int v) { Node *p; printf("%c", G.vertices[v].data); visited[v] = 1; p = G.vertices[v].first; while (p) { if (!visited[p->adjvex]) DFS(G, p->adjvex); p = p->next; } } void DFSTranverse(Graph &G) { for (int v = 0; v < G.vexnum; v++) visited[v] = 0; for (int v = 0; v < G.vexnum; v++) { if (!visited[v]) DFS(G, v); } } int main() { Graph G; createGraph(G); DFSTranverse(G); }
再换一种方式来写DFS。具体代码如下:
#include <iostream> #include <string> using namespace std; #define MAXLEN 10 struct Node { int data; Node *next; }; struct Link { int count; string name; Node *head; }; struct Graph { Link link[MAXLEN]; int vexnum; int arcnum; }; int findIndex(Graph &G, string name) { int index = -1; for (int i = 0; i < G.vexnum; i++) { if (G.link[i].name == name) { index = i; break; } } if (index == -1) cout << "error" << endl; return index; } void constructGraph(Graph &G) { cout << "construct graph yooo" << endl; cout << "enter vexnum" << endl; cin >> G.vexnum; string array[] = {"v1", "v2", "v3", "v4", "v5", "v6", "v7", "v8"}; const int size = sizeof array / sizeof *array; for (int i = 0; i < G.vexnum; i++) { G.link[i].name = array[i]; G.link[i].head = NULL; } string leftName; string rightName; cout << "enter a pair" << endl; cin >> leftName >> rightName; while (leftName != "end" && rightName != "end") { int leftIndex = findIndex(G, leftName); int rightIndex = findIndex(G, rightName); Node *node = new Node; node->data = rightIndex; node->next = NULL; node->next = G.link[leftIndex].head; G.link[leftIndex].head = node; cout << "enter a pair" << endl; cin >> leftName >> rightName; } } bool flag[MAXLEN]; void DFSTranverse(Graph &G, int num) { cout << G.link[num].name << " "; flag[num] = true; Node *head = G.link[num].head; while (head != NULL) { int index = head->data; if (!flag[index]) DFSTranverse(G, index); head = head->next; } } void main() { Graph G; constructGraph(G); for (int i = 0; i < MAXLEN; i++) flag[i] = false; DFSTranverse(G, 0); }
DFS的迭代遍历算法如下:
void DFS(Graph &G) { stack<int> istack; istack.push(0); cout << G.link[0].name << " "; flag[0] = true; while (!istack.empty()) { int index = istack.top(); Node *head = G.link[index].head; while (head != NULL && flag[head->data] == true) head = head->next; if (head != NULL) { index = head->data; if (!flag[index]) { cout << G.link[index].name << " "; flag[index] = true; istack.push(index); } } else istack.pop(); } }
感性的朋友可以测试运行一下本文实例代码以加深印象,相信本文所述对大家C程序算法设计的有一定的借鉴价值。
相关文章
- 这篇文章主要为大家详细介绍了C语言实现放烟花的程序,有音乐播放,文中示例代码介绍的非常详细,具有一定的参考价值,感兴趣的小伙伴们可以参考一下...2021-02-23
- 本篇文章主要介绍C语言中char的知识,并附有代码实例,以便大家在学习的时候更好的理解,有需要的可以看一下...2020-04-25
- 这篇文章主要介绍了matplotlib绘制正余弦曲线图的实现,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参考学习价值,需要的朋友们下面随着小编来一起学习学习吧...2021-02-22
- 这篇文章主要介绍了matplotlib bar()实现百分比堆积柱状图,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参考学习价值,需要的朋友们下面随着小编来一起学习学习吧...2021-02-24
- 这篇文章主要介绍了详解如何将c语言文件打包成exe可执行程序,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参考学习价值,需要的朋友们下面随着小编来一起学习学习吧...2021-02-25
- 这篇文章主要介绍了解决echarts 一条柱状图显示两个值,类似进度条的问题,具有很好的参考价值,希望对大家有所帮助。一起跟随小编过来看看吧...2020-07-20
- 这篇文章主要介绍了R语言基本画图函数与多图多线的用法,具有很好的参考价值,希望对大家有所帮助。一起跟随小编过来看看吧...2021-05-06
- overlay就是在地图上以另外一种形式浮现在地图上,常见的地图覆盖物为这三种类型,如:popup 弹窗、label标注信息、text文本信息等,接下来跟随小编看下openlayers6之地图覆盖物overlay详解,一起看看吧...2021-09-15
- 采用CSS覆盖的方法就可以了,但是官方是不允许这么做的...2013-10-13
- 本篇文章是对GDI+简单绘图的绘图知识进行了详细的分析介绍,需要的朋友参考下...2020-06-25
- 下面小编就为大家带来一篇js遍历json的key和value的实例。小编觉得挺不错的,现在就分享给大家,也给大家做个参考。一起跟随小编过来看看吧...2017-01-26
JavaScript中的数组遍历forEach()与map()方法以及兼容写法介绍
下面小编就为大家带来一篇JavaScript中的数组遍历forEach()与map()方法以及兼容写法介绍。小编觉得挺不错的,现在分享给大家,也给大家做个参考。一起跟随小编过来看看吧...2016-05-20- 这篇文章主要介绍了如何使用JavaScript实现“无缝滚动 自动播放”轮播图效果,本文通过实例代码给大家介绍的非常详细,对大家的学习或工作具有一定的参考借鉴价值,需要的朋友可以参考下...2020-08-20
- 这篇文章主要介绍了vue+高德地图实现地图搜索及点击定位操作,具有很好的参考价值,希望对大家有所帮助。一起跟随小编过来看看吧...2020-09-09
详解pandas.DataFrame.plot() 画图函数
这篇文章主要介绍了详解pandas.DataFrame.plot()画图函数,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参考学习价值,需要的朋友们下面随着小编来一起学习学习吧...2020-06-15- 这篇文章主要介绍了React使用高德地图的实现示例(react-amap),文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参考学习价值,需要的朋友们下面随着小编来一起学习学习吧...2021-04-18
- free函数是释放之前某一次malloc函数申请的空间,而且只是释放空间,并不改变指针的值。下面我们就来详细探讨下...2020-04-25
jQuery遍历DOM的父级元素、子级元素和同级元素的方法总结
借助jQuery我们可以轻松地堆DOM元素进行向上、向下遍历以及同级的遍历,本文我们即来整理jQuery遍历DOM的父级元素、子级元素和同级元素的方法总结:...2016-07-25- 这篇文章主要介绍了如何用c# 实现实时曲线图,文中讲解非常细致,代码帮助大家更好参考和学习,感兴趣的朋友可以了解下...2020-11-03
- 这篇文章主要介绍了C语言中计算正弦的相关函数总结,包括正弦和双曲线正弦以及反正弦的函数,需要的朋友可以参考下...2020-04-25