`
128kj
  • 浏览: 604270 次
  • 来自: ...
社区版块
存档分类
最新评论

图的邻接矩阵实现及广度优先搜索(JAVA)

    博客分类:
阅读更多


import java.util.Queue;
import java.util.ArrayDeque;

// 顶点类
   
class Vertex
   {
   public char label;   
   public boolean wasVisited;//顶点是否被访问过的标志

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

   } 

 //图的邻接矩阵表示实现
class Graph
   {
   private final int MAX_VERTS = 20;
   private Vertex vertexList[]; // 顶点数组
   private int adjMat[][];      // 邻接矩阵
   private int nVerts;          // 当前的顶点数
   private Queue<Integer> theQueue;

   public Graph()            
      {
      vertexList = new Vertex[MAX_VERTS];                               
      adjMat = new int[MAX_VERTS][MAX_VERTS];
      nVerts = 0;
      for(int j=0; j<MAX_VERTS; j++)    
         for(int k=0; k<MAX_VERTS; k++)  
            adjMat[j][k] = 0;
      theQueue = new ArrayDeque<Integer>();
      }  

  //往图中加一个顶点
   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()                   
      {                               
      vertexList[0].wasVisited = true; //从第一个顶点开始搜索,并标记
      displayVertex(0);                // display it
      theQueue.offer(0);              // 进队列
      int v2;

      while( !theQueue.isEmpty() )    
         {
         int v1 = theQueue.poll();   // 队列头元素出队列
         // 直到它没有未被访问的邻接点
         while( (v2=getAdjUnvisitedVertex(v1)) != -1 )
            {                                
            vertexList[v2].wasVisited = true;  // 标记已被访问过
            displayVertex(v2);                 // display it
            theQueue.offer(v2);               // 进队
            }  
         }  

      for(int j=0; j<nVerts; j++)           
         vertexList[j].wasVisited = false;
      }  

   // 返回v的一个未被访问过的邻接顶点,如果v的所有邻接点都访问过,返回-1
   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;
      }  

   }  

public 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();
      }  
   } 

运行结果:
Visits: ABDCE
下载源码:
  • 大小: 24 KB
分享到:
评论
1 楼 w222124 2013-10-08  
如果代码第49行注释掉,则图就变成有向图了

相关推荐

    基于java数据结构实验基于邻接矩阵和邻接表的深度广度优先遍历图.pdf

    实验的目的包括掌握图的相关概念、掌握用邻接矩阵和邻接表的方法描述图的存储结构、掌握图的深度优先搜索和广度优先搜索遍历的方法及其计算机的实现。 实验的内容包括使用邻接矩阵、邻接表作为图的存储结构建立一个...

    邻接矩阵实现图的广搜和深搜(java模板)

    本文将深入探讨如何使用邻接矩阵来实现图的广度优先搜索(BFS)和深度优先搜索(DFS),并提供一个Java模板。 首先,我们需要理解邻接矩阵的概念。邻接矩阵是一个二维数组,其中的元素表示图中节点之间的连接。如果...

    图数据结构以及深度优先和广度优先算法java实现

    在Java中,我们可以使用邻接矩阵或邻接表来实现图数据结构。 **邻接矩阵** 是一种二维数组,其中的元素表示对应顶点之间是否存在边。如果图是无向的,矩阵是对称的;如果是有向的,则可能不对称。对于稀疏图(边的...

    邻接矩阵和邻接表存储的图的遍历

    本主题将深入探讨两种常见的图存储方式——邻接矩阵和邻接表,以及如何在这两种存储方式下实现深度优先遍历(DFS)和广度优先遍历(BFS)。 首先,邻接矩阵是一种直观的图表示方法,它使用二维数组来存储图中每个...

    数据结构邻接矩阵 Graph

    - **图的遍历**:深度优先搜索(DFS)和广度优先搜索(BFS)是常见的图遍历算法,它们可以基于邻接矩阵实现。 - **图的应用**:图被广泛应用于网络路由、社交网络、推荐系统、生物信息学等领域。 通过研究"数据...

    有向图的邻接矩阵.。。

    4. **遍历**:邻接矩阵便于进行深度优先搜索(DFS)和广度优先搜索(BFS)。DFS可以从矩阵中沿着非零元素向下搜索,BFS可以通过队列来逐层访问矩阵的行或列。 5. **操作效率**:虽然邻接矩阵方便查询任意两个节点之间...

    数据结构图的邻接矩阵,邻接表存储表示,图的深度优先搜索遍历,广度优先搜索遍历

    本主题将深入探讨图的两种常见存储方式——邻接矩阵和邻接表,以及如何进行深度优先搜索(DFS)和广度优先搜索(BFS)遍历。 **邻接矩阵**是一种直观且简单的图存储方法。对于一个有n个顶点的图,邻接矩阵是一个n×...

    图的邻接矩阵表示实验

    1)实现图的邻接矩阵和邻接表存储结构; 2)完成基于邻接矩阵的深度优先搜索遍历及广度优先搜索遍历; 3)实现从键盘输入任意一对顶点,求出顶点间的最短路径。

    图的邻接表存储及遍历(JAVA)

    相比于邻接矩阵,邻接表在处理稀疏图(边的数量远小于顶点数量的平方)时更节省空间。邻接表的主要优点是它可以根据边的连接关系动态地添加和删除,且遍历效率较高。 二、邻接表的实现 在Java中,我们可以使用...

    数据结构 图(邻接矩阵) java图形界面 实现

    6. **GraphGui.java**:这是项目中的主要源代码文件,很可能包含了图的类定义,邻接矩阵的实现,以及GUI组件的布局和事件监听。文件可能包括以下功能: - 初始化图和邻接矩阵 - 添加和删除顶点 - 显示和更新GUI以...

    java使用邻接表对图进行深度和广度优先遍历

    在这个Java程序中,我们将探讨如何使用邻接表来实现图的深度优先遍历(DFS)和广度优先遍历(BFS)。邻接表是图数据结构的一种有效实现方式,尤其对于稀疏图(边的数量远小于节点数量的平方)来说,它比邻接矩阵更加...

    java实现广度优先搜索算法(BFS)

    在上述示例代码中,我们通过邻接矩阵表示图。graph是一个二维数组,其中graph[i][j]表示顶点i和j之间是否存在边。 算法的关键是使用队列来进行遍历。我们从指定的起始顶点开始,并将其入队,并将其标记为已访问。...

    Graph-Theory:有向加权图的实现,以及使用广度优先搜索在有向图中找到最短路径,并使用Dikstra和Bellman Ford算法在加权图中找到最短路径

    加权图(邻接表)遍历广度优先搜索深度优先搜索最短路径广度优先搜索最短路径(有向图) Dikstra的最短路径(加权图) 贝尔曼·福特的最短路径(加权图) 优化的Bellman Ford的最短路径(加权图)Java实作有向图...

    数据结构-图的应用(邻接矩阵、邻接多重表)

    对任意给定的图(顶点数不小于20,边数不少于30,图的类型可以是有向图、无向图、有向网、无向网),能够输入图的顶点和边(或弧)的信息,并存储到相应存储结构(邻接矩阵、邻接表、十字链表、邻接多重表,任选其中...

    图的几种常用算法(广度/深度优先搜索,最小生成树,弗洛伊德,拓扑排序....)java实现,简单易懂。

    本资源包含了一些图算法的Java实现,包括但不限于广度优先搜索(BFS)、深度优先搜索(DFS)、最小生成树(Minimum Spanning Tree, MST)、弗洛伊德算法(Floyd-Warshall)以及拓扑排序。下面将详细介绍这些算法及其...

    JAVA实现求矩阵表示的无向图的欧拉通路、回路及欧拉图判定

    4. **寻找欧拉回路**:对于欧拉图,可以使用深度优先搜索(DFS)或广度优先搜索(BFS)策略遍历图。每次访问一个节点时,都要沿着一条未访问过的边移动,直到所有边都被走过一次。记录路径,当返回到起点时,找到的路径...

    图的广度优先遍历

    为了实现BFS,首先我们需要创建一个数据结构来存储图,如邻接矩阵或邻接表。然后,使用一个队列(先进先出)来存储待访问的节点。初始时,将起始状态入队。接着,进入一个循环,每次从队列头部取出一个节点,访问它...

    图的深度和广度遍历(Java实现)

    本篇将详细讲解如何使用Java实现图的深度优先遍历(DFS, Depth-First Search)和广度优先遍历(BFS, Breadth-First Search)。 1. **深度优先遍历(DFS)**: - DFS 是一种递归策略,它沿着某条路径深入到图的深处...

Global site tag (gtag.js) - Google Analytics