| 漏洞检测 |
| 隐藏捆绑 |
图的深度优先搜索和广度优先搜索算法、最小生成树两种算法 --C++实现(2)
测试代码：#include graph.h#include graph_mtx.h#define VERTEX_SIZE 4int main(){graph_gm.insert_vertex(A);gm.insert_vertex(B);gm.insert_vertex(C);gm.insert_vertex(D);gm.insert_vertex(E);gm.inser
测试代码：
#include &graph.h&
#include &graph_mtx.h&
#define VERTEX_SIZE 4
int main()
gm.insert_vertex('A');
gm.insert_vertex('B');
gm.insert_vertex('C');
gm.insert_vertex('D');
gm.insert_vertex('E');
gm.insert_vertex('F');
gm.insert_edge('A', 'B', 6);
gm.insert_edge('A', 'C', 1);
gm.insert_edge('A', 'D', 5);
gm.insert_edge('B', 'C', 5);
gm.insert_edge('B', 'E', 3);
gm.insert_edge('C', 'D', 5);
gm.insert_edge('C', 'F', 4);
gm.insert_edge('D', 'F', 2);
gm.insert_edge('E', 'F', 6);
gm.insert_edge('C', 'E', 6);
gm.print_graph();
cout && &depth_first traverse:& &&
gm.depth_first('A');
cout && &broad_first traverse:& &&
gm.broad_first('A');
cout && &min_spantree_kruskal :& &&
gm.min_spantree_kruskal();
cout && &min_spantree_prim :& &&
gm.min_spantree_prim('A');
测试结果：
(责任编辑：幽灵学院)
------分隔线----------------------------
Note：Mutex是Windows中用于对线程控制的互斥量。意思是只能...
1 inline函数简介inline函数是由inline关键字来定义，引入in...
网上有很多对于STL空间配置器源码的剖析，之所以这么多人去...
在C++中，库的地位是非常高的。C++之父 Bjarne Stroustrup先...
类的6个默认的成员函数包括：构造函数、析构函数、拷贝构造...
#include#pragma comment(lib, dbghelp.lib)LONG WINAPI Top...
工作日：9:00-21:00
周　六：9:00-18:00
&&扫一扫关注幽灵学院Posts - 98,
Articles - 0,
Comments - 324
男，程序员，关注 c++，欢迎技术探讨，平时看书，写博客。
09:23 by 捣乱小子, ... 阅读,
写在最前面的
两种图的遍历算法在其他图的算法当中都有应用，并且是基本的图论算法。
广度优先搜索
广度优先搜索（BFS），可以被形象的描述为&浅尝辄止&，具体一点就是每个顶点只访问它的邻接节点（如果它的邻接节点没有被访问）并且记录这个邻接节点，当访问完它的邻接节点之后就结束这个顶点的访问。
广度优先用到了&先进先出&队列，通过这个队列来存储第一次发现的节点，以便下一次的处理；而对于再次发现的节点，我们不予理会&&不放入队列，因为再次发现的节点：
无非是已经处理完的了；
或者是存储在队列中尚未处理的。
《算法导轮》对两种搜索都采用了很聪明的做法，用白色WHITE来标志未发现的节点，用灰色GRAY来标志第一次被发现的节点，用黑色BLACK来标志第二次被发现的节点。
于是有了：
for each vertex v in V[G]
status[v] = WHITE
/******其他初始化******/
status[s] = GRAY //s是原点
入队(q,s);
while q非空
t = 出队(q);
for each vertex v in Adj[t] //与t邻接的点
if status[v] = WHITE //只对未访问的操作
status[v] = GRAY //标记为第一次访问
/******其他操作******/
status[t] = BLACK //此点已经处理完了
导轮还在上面伪代码的&其他&中加入了访问长度和父节点的操作。此举可以算出，从源点到其他顶点路径的最少步数和它的具体路径。
关于广度优先搜索的一个简单应用：
假如有问题，每个村庄之间都通过桥来联通，先给出村庄的图，问村庄A到村庄B最少要通过多少座桥？这个问题可以很容易的转化为上面的BFS问题。
深度优先搜索
深度优先搜索（DFS），可以被形象的描述为&打破沙锅问到底&，具体一点就是访问一个顶点之后，我继而访问它的下一个邻接的顶点，如此往复，直到当前顶点一被访问或者它不存在邻接的顶点。
同样，算法导论采用了&聪明的做法&，用三种颜色来标记三种状态。但这三种状态不同于广度优先搜索：
WHITE 未访问顶点
GRAY 一条深度搜索路径上的顶点，即被发现时
BLACK 此顶点的邻接顶点被全部访问完之后&&结束访问次顶点
for each vertex v in V(G)
status[v] = WHITE
/******其他初始化******/
for each vertex v in V(G)
if(status[v]==WHITE)
DFS-VISIT(v)
DFS-VISIT(v)
status[v] = GRAY
for each vertex t in Adj(v)
if status[t] = WHITE
DFS-VISIT(t)
/******其他操作******/
status[v] = BLACK
通过给DFS搜索过程中给每一个顶点加时间戳，就可以实现拓扑排序了。实现拓扑排序需要：
对于每一个顶点，都有两个时间戳，分别这样来定义：
在一顶点刚被发现的时候，标记此顶点的第一个时间戳；
在结束此顶点的访问的时候，标记此顶点的第二个时间戳。时间戳可以用简单的123456来标记，只要能区分大小就行。
因此，你会发现，越早发现的点，他的第一个时间戳会越小，但是他的第二个时间戳会越大。&
两个算法都是O(V+E)，在用到的时候适当选取。在使用白灰黑标志的时候，突然明白了如何用深度优先搜索来判断有向图中是否存在环。
深度优先和广度优先各有各的优缺点:
广优的话，占内存多，能找到最优解，必须遍历所有分枝. 广优的一个应用就是迪科斯彻单元最短路径算法.
深优的话，占内存少，能找到最优解（一定条件下），但能很快找到接近解（优点），可能不必遍历所有分枝（也就是速度快）, 深优的一个应用就是连连看游戏.
在更多的情况下，深优是比较好的方案。C++ 深度优先搜索 生成全排列排列如何用深度优先搜索（DFS）生成全排列?求代码和每句的详解
#include&cstdio&#include&iostream&using&namespace&int&a[1000],v[1000],n;void&print(){&&for&(int&i=1;i&=n;i++)&printf(&%d&&,a[i]);&//将每位输出&&&puts(&&);&//换行&}void&DFS(int&dep){&&if&(dep==n)&print();&//如果搜到一个结果输出&&&dep++;&//查找当前要处理位&&&for&(int&i=1;i&=n;i++)&{&//枚举当前位&&&&if&(v[i])&&//如果这个数之前被选过就跳过&&&&v[i]=1;&//选中当前位&&&&a[dep]=i;//将当前位存入数组&&&&DFS(dep);//搜索下一位&&&&v[i]=0;//取消选中当前位&&&}}int&main(){&&scanf(&%d&,&n);&//读入&&DFS(0);&//深搜&&system(&pause&);&//暂停(查看结果)&}
为您推荐：
其他类似问题
扫描下载二维码（c语言）有关acm深度优先搜索的问题 help！_百度知道查看:735|回复：5
其实是作业题。别说我懒，我是初学，而且找了几个晚上相关信息，都找不到解决方法，主要是DFS书上都是2个参数，这里有3个，而且题目意思不明。
发帖求教。
试实现邻接矩阵存储图的深度优先遍历。
函数接口定义：void DFS( MGraph Graph, Vertex V, void (*Visit)(Vertex) );
其中MGraph是邻接矩阵存储的图，定义如下：
typedef struct GNode *PtrToGN
struct GNode{& &
int Nv;&&/* 顶点数 */& &
int Ne;&&/* 边数& &*/& &
WeightType G[MaxVertexNum][MaxVertexNum]; /* 邻接矩阵 */
typedef PtrToGNode MG /* 以邻接矩阵存储的图类型 */
函数DFS应从第V个顶点出发递归地深度优先遍历图Graph，遍历时用裁判定义的函数Visit访问每个顶点。当访问邻接点时，要求按序号递增的顺序。题目保证V是图中的合法顶点。
裁判测试程序样例：
#include &stdio.h&
typedef enum {false, true}
#define MaxVertexNum 10&&/* 最大顶点数设为10 */
#define INFINITY 65535& &/* ∞设为双字节无符号整数的最大值65535*/
typedef int V& && &/* 用顶点下标表示顶点,为整型 */
typedef int WeightT&&/* 边的权值设为整型 */
typedef struct GNode *PtrToGN
struct GNode{& &
int Nv;&&/* 顶点数 */& &
int Ne;&&/* 边数& &*/& &
WeightType G[MaxVertexNum][MaxVertexNum]; /* 邻接矩阵 */
typedef PtrToGNode MG /* 以邻接矩阵存储的图类型 */
bool Visited[MaxVertexNum]; /* 顶点的访问标记 */
MGraph CreateGraph(); /* 创建图并且将Visited初始化为false；裁判实现，细节不表 */
void Visit( Vertex V )
printf(& %d&, V);
void DFS( MGraph Graph, Vertex V, void (*Visit)(Vertex) );
int main()
MGraph G;& &
Vertex V;& &
G = CreateGraph();& &
scanf(&%d&, &V);& &
printf(&DFS from %d:&, V);& &
DFS(G, V, Visit);& &
}/* 你的代码将被嵌在这里 ++需要我写函数++*/
输入样例：给定图如下
输出样例：
DFS from 5: 5 1 3 0 2 4 6求解。
我的理解是补全void DFS( MGraph Graph, Vertex V, void (*Visit)(Vertex) );这个函数的方法，但一直编译错误。
本帖最后由 imhere 于
23:30 编辑
这里是sql server板块。
引用:原帖由 oswica 于
08:58 发表
这里是sql server板块。 您发表的主题被执行管理操作
& && &&&惊艳了青春
& && &&& 07:36
& & 这是由论坛系统自动发送的通知短消息。
& & 以下您所发表的主题被 惊艳了青春 执行 移动 操作。
& & 主题: 关于 邻接矩阵存储图的深度优先遍历-求教
& & 发表时间:
& & 原论坛: 待审核
& & 目标论坛: SQL Server论坛
& & 操作理由: 内容整合
& & 如果您对本管理操作有异议，请与我取得联系。
被人为移动过来了，不知道出于什么原因，我已申述了需要移回C++
引用:原帖由 imhere 于
09:10 发表
您发表的主题被执行管理操作
& && &&&惊艳了青春
& && &&& 07:36
& & 这是由论坛系统自动发送的通知短消息。
& & 以下您所发表的主题被 惊艳了青春 执行 移动 操作。
& & 主题: 关于 邻接矩阵存储图 ... 抱歉，已帮您移动到C++板块了！
Exchange 2013 MCSE | Microsoft MVP,Office Servers and Services
社区官方Exchange技术群:
问题解决与否,欢迎大家反馈一下,也是对回答者认可&肯定，谢谢！
请高手指定下 谢谢