`
lighter
  • 浏览: 500206 次
  • 性别: Icon_minigender_1
  • 来自: 广州
社区版块
存档分类
最新评论

无向图的广度搜索实例

阅读更多
说明一下:下边的例子就是<Java数据结构和算法>书的一个例子,并非我所写的,这一本书我觉得是最好 的一本java数据结构的入门书籍.现在把这一个例子记录在blog上,当作温习一下啦。

无向图的广度搜索的规则有如下:

规则1、访问下一个未来访问的邻接点(如果存在),这个顶点必须是当前顶点的邻接点,标点它,并把它插入到队列中。

规则2、如果因为已经没有未访顶点而不能执行规则1,那么从队列取一个顶点(如果存在),并使其成为当前的顶点。

规则3、如果因为队列为空而不能执行规则2,则搜索结束。

下面是实例的代码:

class Queue
   {
   private final int SIZE = 20;
   private int[] queArray;
   private int front;
   private int rear;

   public Queue()            // constructor
      {
      queArray = new int[SIZE];
      front = 0;
      rear = -1;
      }

   public void insert(int j) // put item at rear of queue
      {
      if(rear == SIZE-1)
         rear = -1;
      queArray[++rear] = j;
      }

   public int remove()       // take item from front of queue
      {
      int temp = queArray[front++];
      if(front == SIZE)
         front = 0;
      return temp;
      }

   public boolean isEmpty()  // true if queue is empty
      {
      return ( rear+1==front || (front+SIZE-1==rear) );
      }

   }  // end class Queue

class Vertex
   {
   public char label;        // label (e.g. 'A')
   public boolean wasVisited;

   public Vertex(char lab)   // constructor
      {
      label = lab;
      wasVisited = false;
      }

   }  // end class Vertex
/*Graph类的bfs()方法和dfs()方法类似的,只是用队列代替了栈,嵌套的循环代替了单层 *循环。外层循环等待队列为空,而内层循环依次寻找当前顶点的未访问邻接点。
**/
class Graph
   {
   private final int MAX_VERTS = 20;
   private Vertex vertexList[]; // list of vertices
   private int adjMat[][];      // adjacency matrix
   private int nVerts;          // current number of vertices
   private Queue theQueue;

   public Graph()               // constructor
      {
      vertexList = new Vertex[MAX_VERTS];
                                          // adjacency matrix
      adjMat = new int[MAX_VERTS][MAX_VERTS];
      nVerts = 0;
      for(int j=0; j<MAX_VERTS; j++)      // set adjacency
         for(int k=0; k<MAX_VERTS; k++)   //    matrix to 0
            adjMat[j][k] = 0;
      theQueue = new Queue();
      }  // end constructor

   public void addVertex(char lab)
      {
      vertexList[nVerts++] = new Vertex(lab);
      }

   public void addEdge(int start, int end)
      {
      adjMat[start][end] = 1;
      adjMat[end][start] = 1;
      }

   public void displayVertex(int v)
      {
      System.out.print(vertexList[v].label);
      }

   //核心代码
   public void bfs()                   // breadth-first search
      {                                // begin at vertex 0
      vertexList[0].wasVisited = true; // mark it
      displayVertex(0);                // display it
      theQueue.insert(0);              // insert at tail
      int v2;

      while( !theQueue.isEmpty() )     // until queue empty,
         {
         int v1 = theQueue.remove();   // remove vertex at head
         // until it has no unvisited neighbors
         while( (v2=getAdjUnvisitedVertex(v1)) != -1 )
            {                                  // get one,
            vertexList[v2].wasVisited = true;  // mark it
            displayVertex(v2);                 // display it
            theQueue.insert(v2);               // insert it
            }   // end while
         }  // end while(queue not empty)

      // queue is empty, so we're done
      for(int j=0; j<nVerts; j++)             // reset flags
         vertexList[j].wasVisited = false;
      }  // end bfs()

   // returns an unvisited vertex adj to v
   public int getAdjUnvisitedVertex(int v)
      {
      for(int j=0; j<nVerts; j++)
         if(adjMat[v][j]==1 && vertexList[j].wasVisited==false)
            return j;
      return -1;
      }  // end getAdjUnvisitedVertex()

   }  // end class Graph

class BFSApp
   {
   public static void main(String[] args)
      {
      Graph theGraph = new Graph();
      theGraph.addVertex('A');    // 0  (start for bfs)
      theGraph.addVertex('B');    // 1
      theGraph.addVertex('C');    // 2
      theGraph.addVertex('D');    // 3
      theGraph.addVertex('E');    // 4

      theGraph.addEdge(0, 1);     // AB
      theGraph.addEdge(1, 2);     // BC
      theGraph.addEdge(0, 3);     // AD
      theGraph.addEdge(3, 4);     // DE

      System.out.print("Visits: ");
      theGraph.bfs();             // breadth-first search
      System.out.println();
      }  // end main()
   }  // end class BFSApp
分享到:
评论
1 楼 ricky_love 2006-12-27  
支持一下

相关推荐

    无向图的应用用C语言描述

    无向图的课设,有程序和报告,内容有邻接矩阵建立无向图、邻接矩阵遍历、广度优先搜索遍历、深度优先搜索遍历、(最小生成树普里姆(Prim)算法)、单源最短路径(地杰斯特拉(Dijkstra)算法),程序打开即可运行。

    图的广度优先遍历

    对于有向图和无向图,BFS的执行方式基本相同,区别在于邻接节点的定义。在无向图中,两个节点之间有一条边,那么它们相互为邻接节点。而在有向图中,只有当存在一条从节点A到节点B的边,节点B才是节点A的邻接节点。 ...

    图 拓扑排序 深度搜索 广度搜索 最小生成树

    最后,**最小生成树(MST)** 是一个无向图中边的子集,它包含了图中的所有节点,并且任何两个节点之间都有路径相连,同时这个子集的总权重是最小的。求解MST是图论中的经典问题,常见算法包括Prim的贪心算法和...

    VC 有向无环图操作实例.rar

    在有向图中,每个边都有明确的方向,从一个节点指向另一个节点。 3. **DAG类(DAG Class)**:DAG类管理所有节点和边,提供添加、删除节点和边的方法。它还可能包含用于执行特定操作,如拓扑排序和最短路径计算的...

    acm程序设计竞赛广度搜索BFS实例

    在ACM程序设计竞赛中,广度优先搜索(Breadth-First Search,简称BFS)是一种常用的图遍历算法,常用于解决许多问题,如最短路径、判断连通性等。本压缩包文件“BFS”包含了作者在参与ACM竞赛时总结的一些BFS实例...

    广度优先搜索学习五例之一

    在寻找最小生成树时,可以使用BFS来解决如Prim算法的简化版本,尤其是在加权无向图中。 总结,广度优先搜索是一种重要的图论算法,广泛应用于寻找最短路径、遍历结构等问题。通过上述五个实例,我们可以更好地理解...

    2015北大ACM-ICPC暑期课(广度优先搜索)

    - **拓扑排序**:在有向无环图(DAG)中,BFS可以进行拓扑排序,确定节点的先后顺序。 - **判断连通性**:通过BFS遍历所有节点,可判断图是否连通。 在实际编程中,BFS的实现需要特别注意空间效率,因为可能会有大量...

    广度优先遍历,深度优先遍历实例代码

    DFS在有向图和无向图中都能使用,但不保证找到最短路径。在某些问题,如判断图是否连通、查找有向图中的环等,DFS是非常有效的。 在提供的文件列表中,我们可以看到`Graph.cpp`, `Node.cpp`, `Path.cpp`, 和 `Main....

    广度优先搜索学习五例之二(JAVA)

    - **拓扑排序**:在无环有向图中,BFS可以用于执行拓扑排序。 - **层次遍历**:在树结构中,BFS可以按层级顺序访问所有节点,例如在二叉树中进行层次遍历。 5. **Java实现**: 在Java中,我们可以使用`java.util...

    基于邻接数组(邻接矩阵)无向图实现代码(C/C++)_下载无需积分

    2. `main.cpp`: 这是程序的主入口,可能会创建一个无向图实例,调用`func.cpp`中的函数进行图的操作,并打印结果或者进行其他处理。 3. `UD_Graph_Structure.h`: 这是一个头文件,很可能定义了无向图的数据结构,...

    深度优先搜索和广度优先搜索

    - **有向图与无向图**:如果图中的每条边都具有明确的方向,则该图称为有向图;反之,若图中边无方向,则称为无向图。 - **简单图与多重图**:简单图要求任意两条边的起点和终点不能完全相同,并且每条边必须连接...

    c语言 turbo C编译通过 无向图非递归遍历 数据结构

    定义了一个函数`creatgraph`用于创建一个无向图实例,并初始化顶点和边。用户需要输入边的信息来构建图。 ```c void creatgraph(Graph *g, int n) { // 初始化顶点 for (int i = 1; i ; i++) { g-&gt;V[i] = i; } ...

    广度优先搜索学习五例之三

    通常,BFS的学习案例会包括经典问题,如寻找二叉树的层次遍历、社交网络中的朋友查找、有向图或无向图的最短路径等。 【标签】"源码 工具"表明这篇内容可能会包含实际的Java代码实现,并可能提供了一些实用工具或...

    图的数据结构深搜/广搜

    3. 测试用例,用于验证算法的正确性,可能包括有向图、无向图、有向网(带权有向图)和无向网(带权无向图)的实例。 4. 可能还包含输入输出处理,用于读取图的结构信息并打印搜索结果。 在实际应用中,DFS和BFS各...

    C++实现图的邻接表存储和广度优先遍历实例分析

    示例:建立如图所示的无向图 由上图知,该图有5个顶点,分别为a,b,c,d,e,有6条边. 示例输入(按照这个格式输入): 5 6 abcde 0 1 0 2 0 3 2 3 2 4 1 4 输入结束(此行不必输入) 注:0 1表示该图的第0个顶点和第1...

    广度优先搜索解决迷宫问题_迷宫问题_

    在迷宫问题中,我们把迷宫看作一个有向图,每个可通行的单元格是一个节点,相邻的可通行单元格之间有边相连。 BFS算法的步骤如下: 1. 将起点放入一个队列。 2. 创建一个集合(或者用一个二维数组)来跟踪已经访问...

    广度优先搜索算法分析

    此外,对于有向图中的强连通分量和拓扑排序等问题,BFS也有其独特的优势。 学习BFS时,建议结合实际问题进行练习,例如构建自己的图数据结构,实现BFS算法并进行调试,这样可以更深入地理解和掌握这种算法。同时,...

    数学建模 图论 课件 最小生成树 广度和深度搜索

    在一个加权无向图中,最小生成树是一棵树形子图,包含了原图的所有顶点,且所有边的权重之和是最小的。常见的算法有Prim算法和Kruskal算法,它们分别通过贪心策略和并查集数据结构寻找最小生成树。 **广度优先搜索...

    数据结构实例教程(C语言版):第7章 图的结构分析与应用.ppt

    根据边是否有方向,图可以分为无向图和有向图。无向图中的边没有方向,而有向图中的边具有明确的方向。例如,无向完全图中任意两个顶点之间都有边相连,而有向完全图则包含方向相反的两条边。 图的术语包括度...

Global site tag (gtag.js) - Google Analytics