DFS 数据结构 C++语言实现 图的深度优先遍历 |
您所在的位置：网站首页 › 地图历史记录怎么删除 › DFS 数据结构 C++语言实现 图的深度优先遍历 |
DFS 数据结构 C++语言实现 图的深度优先遍历
|
1.DFS图解 图的深度优先遍历
1.1 基本定义：
设初始时，图中所有顶点未曾被访问过： ● 从图中某个顶点 v 出发，访问此顶点； ● 依次从 v 的未被访问的邻接点出发深度优先遍历图，直至图中所有和顶点 v 有路径相通的顶点都被访问到； ● 如果此时图中还有尚未访问的顶点，则另选一个尚未访问的顶点作起始点，重复上述过程，直至图中所有顶点都被访问到为止。 1.2 举例说明如：下图从V0出发，可以得到一个深度优先遍历序列为{ V0 ,V1 ,V3 ,V7 ,V4 ,V2 ,V5 ,V6 }。
2.基本存储结构补充 1.1 边结点、头结点、邻接表、图的基本存储结构 typedef enum{DG,DN,UDG,UDN} GraphKind; /*有向图，有向网，无向图，无向网*/ /*边结点类型*/ typedef struct ENode { int adjvex; struct ENode *nextarc; int weight; }ENode; typedef int VexType; /*头结点类型*/ typedef struct VNode { VexType vex; ENode *firstarc; }VNode, AdjList[MAXVEX]; /*邻接表类型定义*/ /*邻接表存储的图的类型定义*/ typedef struct { AdjList vertices; /*用邻接表存储顶点集合及边集合*/ int vexnum,edgenum; GraphKind kind; }ALGraph; 3. 主程序（main process） int main() { ALGraph g; CreateUDG_ALG(g); /*创建邻接表存储的无向图*/ DFSTraverse(g); /*深度优先遍历*/ return 0; }CreateUDG_ALG(g) 函数主要是去创建无向图的邻接表，这里不再赘述，详见： http://t.csdn.cn/sFZ46 下面我们主要讲解一下DFSTraverse(g)函数的实现过程 4.深度遍历函数 DFSTraverse(g)实现 void DFSTraverse(ALGraph g)/*深度优先遍历以邻接表存储的图g*/ { int i; for(i=0;iadjvex);/*如果没有访问过就继续递归进行一个访问*/ } else { pn=pn->nextarc;/*通过这一个边结点能访问的点已经访问完了，无路可走了，回到原点继续下一个边结点的访问*/ } } } |
【本文地址】
公司简介
联系我们
今日新闻 |
点击排行 |
|
推荐新闻 |
图片新闻 |
|
专题文章 |