`

算法学习 之遍历

    博客分类:
  • c++
 
阅读更多

/********************广度优先遍历算法*******************/

void BFSTraverse(Graph G, Status (*Visit)(int v))
 {  // 按广度优先非递归遍历图G。使用辅助队列Q和访问标志数组visited。
for (v=0; v<G.vexnum; ++v)   visited[v] = FALSE;
InitQueue(Q);     // 置空的辅助队列Q
for ( v=0; v<G.vexnum; ++v )
if (!visited[v])
{  EnQueue(Q, v);                   //入队
visited[u] = TRUE;   Visit(u);    //访问
while (!QueueEmpty(Q))
{  DeQueue(Q, u);              //出队
for ( w=FirstAdjVex(G, u); w!=0; w=NextAdjVex(G, u, w) )
if ( ! visited[w]) 
{  visited[u] = TRUE;   Visit(u);   //访问
EnQueue(Q, w);               //入队
}
}  //while
}  //if
} // BFSTraverse 
// FirstAdjVex(G, u)寻找u的第一个邻接点,并返回其下标位置
// NextAdjVex(G, u, w) w是u的一个邻接点,寻找u的所有邻接点中位于w后面的那一个,并返回其下标位置
 
分享到:
评论
4 楼 sblig 2012-05-22  
用Dijkstra算法求最短路径

#define MAX_VERTEX_NUM  20
void ShortestPath_DIJ(MGraph G,int v1)   //V1是源点
{  //用Dijkstra算法求有向网G的v10顶点到其余顶点的最短路径
 int P[ MAX_VERTEX_NUM] , D[ MAX_VERTEX_NUM];
   int final[ MAX_VERTEX_NUM]; 
   int i,v,w,min,pre;
   for(v=1; v<=G.vexnum; ++v)
   {    //D[ ],final[ ],P[ ]初始化
final[v]=FALSE;  D[v]=G.arcs[v1][v].adj;
      if(D[v]<INFINITY)   P[v]=1;
      else P[v]=0;
    }
    D[v1]=0;  final[v1]=TRUE;  //源点v0相关数组初始化
   for( i=2; i<=G.vexnum; ++i)
    { 
min=INFINITY;   //寻找final[]=0的D[ ]中最小值
       for(w=1; w<=G.vexnum; ++w)  //最小值->min,最小值的下标->v
         if(!final[w] &&D [w]<min)  { v=w; min=D[w];}
       final[v]=TRUE;   //入选
       for(w=1; w<=G.vexnum; ++w) //根据入选的v顶点修改D[ ]及p[ ]
          if(!final[w] && (min+G.arcs[v][w].adj<D[w]))
	       {  D[w]=min+G.arcs[v][w].adj;  P[w]=v;  }
     } //逐渐更新D[ ] 及p[ ]
     for (w=1; w<=G.vexnum; ++w)  //依次输出
     {    printf("%d",w);   pre=P[w];
          if ( pre==0)
             if(w==v1)  printf("    source point \n");
             else       printf("    No Path \n");
          else 
{   while( pre!=v1 ) { printf("<--%d",pre); pre=P[pre];}
	          printf("<--%d **** distance is:%d\n",v0,D[w]);
	       }  //else
     } //for 输出结束
} ShortestPath_DIJ

void ShortestPath_FLOYD(MGraph G,PathMatrix &p[],DistancMatrix D[])
{
for(v=0;v<G.vexnum;v++)
  for(w=0;w<G.vexnum;w++)
{  D[v][w] = G.arcs[v][w]; 
     for(u=0;u<G.vexnum;u++)  P[v][w][u]=FALSE;
     if(D[v][w] < INFINITY) 
{    P[v][w][v] = TRUE;  P[v][w][w] = TRUE;  }
}
for(v=0;v<G.vexnum;v++)
  for(w=0;w<G.vexnum;w++)
    for(u=0;u<G.vexnum;u++)
       if(D[v][u] + D[u][w] < D[v][w])
{   D[v][w] = D[v][u]+D[u][w];
    for(i=0; i<G.vexnum; i++)
      P[v][w][i]= P[v][u][i] || P[u][w][i];
}    
}

 

3 楼 sblig 2012-05-22  
   0  1  2  3  4  5
0   *  6  1  5  *  *
1   6  *  5  *  3  *
2   1  5  *  5  6  4
3   5  *  5  *  *  2
4   *  3  6  *  *  6
5   *  *  4  2  6  *

U 1
到达顶点 V1 V2 V3 V4 V5 V6
经由U中          V1 V1 V1 V1 V1 V1
耗费          0 6 1 5 * *
入选顶点                V3

U 13
到达顶点 V1 V2 V3 V4 V5 V6
经由U中         V1 V3 V1 V1 V3 V3
耗费         0 5 0 5 6 4
入选顶点                                          V6

U 136
到达顶点 V1 V2 V3 V4 V5 V6
经由U中         V1 V3 V1 V6 V3 V3
耗费         0 5 0 2 6 0
入选顶点                         V4

U 1364
到达顶点 V1 V2 V3 V4 V5 V6
经由U中         V1 V3 V1 V6 V3 V3
耗费         0 5 0 0 6 0
入选顶点         V2

U 13642
到达顶点 V1 V2 V3 V4 V5 V6
经由U中         V1 V3 V1 V6 V2 V3
耗费         0 0 0 0 3 0
入选顶点                                        V5

U 136425
到达顶点 V1 V2 V3 V4 V5 V6
完成 经由U中 V1 V3 V1 V6 V2 V3
耗费         0 0 0 0 0 0
入选顶点
2 楼 sblig 2012-05-22  
/****************最小生成树Prim算法******************/

typedef struct
{   VertexType adjvex;
VRType lowcost;
} closedge[MAX_VERTEX_NUM];
void MiniSpanTree_PRIM (MGraph G, VerTexType u)
{
k = LocateVex ( G, u );     // 顶点u为构造生成树的起始点
for ( j=0; j<G.vexnum; ++j )  // 辅助数组初始化
if (j!=k)  closedge[j] = { u, G.arcs[k][j].adj }; 
closedge[k].lowcost = 0;                   // 初始,U={u}
for (i=1; i<G.vexnum; ++i) 
{  //在其余顶点中选择
k = minimum(closedge);        // 求出T的下一个结点(k)
printf(closedge[k].adjvex, G.vexs[k]); // 输出生成树的边
closedge[k].lowcost = 0;             // 第k顶点并入U集
for (j=0; j<G.vexnum; ++j)
if (G.arcs[k][j].adj < closedge[j].lowcost)
{   closedge[j].adjvex=G.vexs[k];
         closedge[j].lowcost=G.arcs[k][j].adj;
};
}
} // MiniSpanTree_PRIM

1 楼 sblig 2012-05-22  
/********************深度优先遍历算法*******************/


//--- 下列算法使用两个的全局变量 ---
Boolean visited[MAX]; // 访问标志数组
Status (* VisitFunc)(int v);      // 函数变量
void DFSTraverse(Graph G, Status (*Visit)(int v)) 
{      // 对图G作深度优先遍历。
VisitFunc = Visit; 
for (v=0; v<G.vexnum; ++v) 
visited[v] = FALSE;                  // 访问标志数组初始化
for (v=0; v<G.vexnum; ++v) 
if (!visited[v]) DFS(G, v);      // 对尚未访问的顶点调用DFS
}
void DFS (Graph G, int v) 
{   // 从顶点v出发递归地深度优先遍历图G。
visited[v] = TRUE;  VisitFunc(v);   //访问第v个顶点
for (w=FirstAdjVex(G, v); w!=0; w=NextAdjVex(G, v, w) )
if (!visited[w]) DFS(G, w); 
// 对v的尚未访问的邻接顶点w递归调用DFS
}
// FirstAdjVex(G, u)寻找u的第一个邻接点,并返回其下标位置
// NextAdjVex(G, u, w) w是u的一个邻接点,寻找u的所有邻接点中位于w后面的那一个,并返回其下标位置


相关推荐

    遍历算法遍历方案及几个算法实现

    遍历算法是计算机科学中处理树形数据结构时的关键操作,它涉及到按照特定顺序访问树中的每一个节点。在二叉树的遍历中,通常有三种主要的遍历方法:前序遍历、中序遍历和后序遍历。这些遍历方式都是基于二叉树的递归...

    中序遍历二叉树非递归算法

    在IT领域,尤其是在数据结构与算法的学习中,中序遍历二叉树的非递归算法是一个关键且实用的知识点。通常,我们首先通过递归来实现二叉树的遍历,但递归方法可能因深度过大导致栈溢出,因此掌握非递归版本的遍历算法...

    建立P131算法6.4并遍历

    在本文中,我们将深入探讨如何建立P131算法6.4,并介绍遍历二叉树的方法。首先,P131算法6.4没有提供具体的细节,但从代码来...理解这些概念和方法对于理解和操作二叉树至关重要,也是数据结构和算法学习中的基础内容。

    树的非递归遍历算法层次遍历与深度遍历C语言源码

    本资源提供了树的非递归遍历算法的C语言源码,包括层次遍历(BFS,Breadth-First Search)和深度遍历(DFS,Depth-First Search)。下面我们将详细探讨这两种遍历方法及其非递归实现。 **层次遍历(BFS)**: 层次...

    汉诺塔问题算法和二叉树遍历的关系

    ### 汉诺塔问题算法和二叉树遍历的关系 #### 一、汉诺塔问题及算法介绍 汉诺塔问题是一个经典的递归问题,它由三个柱子(通常称为A、B、C)和若干个不同大小的圆盘组成。游戏的目标是从一个柱子(比如A)将所有...

    先序遍历的非递归算法

    "先序遍历的非递归算法" 本文将详细介绍二叉树的先序遍历非递归算法,包括其原理、实现代码和相关知识点。 知识点1:二叉树的概念 ...通过学习本文,读者可以更好地理解树遍历算法和非递归算法的原理和实现。

    图的遍历算法 所有遍历算法

    总的来说,掌握图的遍历算法是每个IT从业者必备的技能之一,无论是数据分析、软件开发还是算法设计,都有可能用到这些基础知识。不断练习和深化理解,将使你在处理与图相关的问题时更加得心应手。

    数据结构与算法图的遍历与连通性PPT学习教案.pptx

    数据结构与算法图的遍历与连通性PPT学习教案 本资源摘要信息是关于数据结构与算法图的遍历与连通性PPT学习教案,总共43页,涵盖了图的遍历、深度优先搜索(DFS)和广度优先搜索(BFS)等关键概念。 图的遍历是指从...

    二叉树的创建 遍历 交换子树

    实验的目的在于让学习者掌握二叉树的逻辑结构和不同遍历方式,以及如何使用指针类实现这些操作。通过这个实验,学生可以理解二叉树的基本操作,并加深对二叉链表存储结构的理解。同时,通过编写和调试代码,提高编程...

    树 哈弗曼算法。二叉树遍历的应用。矩阵的相乘

    在IT领域,数据结构是计算机科学中的核心概念之一,它涉及到如何有效地组织和存储数据,以便于高效地访问和操作。在这个压缩包中,我们关注的是三个主要知识点:哈弗曼编码(Huffman Coding)、二叉树遍历以及矩阵...

    二叉树的各种遍历,二叉搜索树的建立,前中序构建二叉树

    总结,二叉树及其遍历是数据结构和算法的基础,理解并掌握它们是成为一名优秀程序员的关键。二叉搜索树则在实际应用中展现出高效性,特别是在需要快速查找和排序的场景。通过学习和实践这些概念,我们可以更好地应对...

    二叉树算法(一种遍历算法)

    上机作业4可能涵盖了设计和实现这三种遍历算法,通过编写程序来演示和验证遍历的结果。在实际操作中,可以使用伪代码、Python、Java或其他编程语言来实现。同时,理解每种遍历方法的逻辑并能够可视化遍历过程,对于...

    基于c的二叉树遍历算法课程设计实验项目+入门级学习+源码和遍历算法介绍

    基于c的二叉树遍历算法课程设计实验项目+入门级学习+源码和遍历算法介绍 项目简介 二叉树遍历算法实现是一个经典的数据结构课程实验项目。该项目旨在通过编程实践,让学生掌握二叉树的前序遍历、中序遍历和后序遍历...

    数据结构与算法学习:图的遍历以及邻接表

    数据结构与算法学习:图的遍历以及邻接表

    数据结构之图的遍历算法

    理解并熟练掌握这两种遍历方法是数据结构和算法学习的重要部分,它们能帮助我们有效地解决复杂的问题,并为高级算法提供基础。 总之,图的遍历是数据结构中的核心内容,C++的实现方式既体现了编程技巧,又展示了对...

    图的遍历的分析与算法设计

    图的遍历是数据结构中的一个重要概念,主要探讨如何系统地访问图中的所有顶点,确保每个顶点至少被访问一次。...无论是对数据结构的学习者还是对算法设计感兴趣的开发者而言,这篇文章都是不可多得的参考资料。

    二叉树遍历(递归算法)

    通过递归算法实现这三种遍历方式,有助于深入理解二叉树的性质和操作,为后续的算法学习和问题解决打下坚实基础。在编程实践中,我们可以根据具体需求选择合适的遍历策略,以高效地处理二叉树结构的数据。

    【C语言】数据结构实验_一元多项式相加_串模式匹配算法_二叉树遍历与路径查找

    在本压缩包中,我们包含了三个C语言编程实验,涵盖了数据结构中的重要概念:一元多项式相加、串模式匹配算法以及二叉树遍历与路径查找。这些实验不仅有助于深入理解C语言的编程技巧,同时对于掌握数据结构的核心原理...

    二叉树的各种遍历的递归算法

    根据给定文件的信息,本文将详细介绍二叉树的前序、中序、后序以及层序遍历的递归算法,并结合代码实例进行说明。 ### 一、二叉树的基本...这些遍历方式是理解和操作二叉树的基础,对于学习数据结构和算法至关重要。

    一个简易的遍历算法的实现

    我们就是不断的掌握着最古老的排序:冒泡等,可是就是在实践的时候往往就是一点用武之地都是没有的,于是我们做的一个小小的东东,就是一个简易的遍历的算法的实现,我们就是在不断的学习的过程里面体味我们的乐趣的...

Global site tag (gtag.js) - Google Analytics