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

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

阅读更多
经常要用到,放到这里备用!!
//邻接矩阵实现图的广搜和深搜
import java.util.*;

public class Graph {

	private int[][] G;//邻接矩阵
	private int k;//顶点数目
	private boolean[] visited;//判断顶点是否被访问过
	
        public Graph(int k,int[][] G){
           this.k=k;
           this.G=G;
           visited = new boolean[k];         
        }

	public static void main(String[] args) {
	  Scanner sc = new Scanner(System.in);
          int k;
          k = sc.nextInt(); //顶点数(顶点为0,1,2,...k-1)
          int m=sc.nextInt();//边数
         
         //构建邻接矩阵
          int[][] G = new int[k][k];
          for (int i = 0; i <m; i++) {
            int u = sc.nextInt();
            int v = sc.nextInt();
            G[u][v] = 1;
            G[v][u] = 1;//无向图的对称
	 }
          Graph g=new Graph(k,G);
          g.bfs(0);
        // g.dfs(0);
         System.out.println();
       }
     
	//广搜
   private void bfs(int v) {
     //队列用来保存被访问节点的分支节点
     Queue<Integer> que = new LinkedList<Integer>();
     que.offer(v);
     while (!que.isEmpty()) {
      v = que.poll();
      System.out.print(v+" ");
      visited[v] = true;
      //将被访问节点的分支节点加入到队列中
      for (int i = 0; i < k; i++) {
       if (G[v][i] == 1 && !visited[i]) {
          que.add(i);
          visited[i] = true;
       }
      }
     }
   }

   //深搜
   private  void dfs(int v) {
     visited[v] = true; 
      System.out.print(v+" ");
      for (int i = 0; i <k; i++) {
        //递归调用搜索没有被访问过的当前节点的下一个节点(邻接点)
        if (G[v][i] == 1 && !visited[i])
          dfs(i);
      }
   }

}


C:\java>java Graph
6
10
0 1
0 2
0 3
1 2
1 4
2 4
2 5
2 3
3 5
4 5
0 1 2 3 4 5

源码:
  • 大小: 5.3 KB
分享到:
评论

相关推荐

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

    本文将深入探讨如何使用Java实现图的邻接矩阵以及如何在该数据结构上执行广度优先搜索(BFS)。 **邻接矩阵** 邻接矩阵是一种二维数组,它用来表示图中顶点之间的连接。如果图是无向的,邻接矩阵是对称的;如果图...

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

    本篇将详细介绍如何使用Java实现基于邻接表的图的广度优先搜索(BFS)和深度优先搜索(DFS),并提供相关代码模板。 **一、邻接表的概念** 邻接表是一种空间效率高的图数据结构,它为每个顶点维护一个列表,列表中...

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

    这个应用程序演示了如何使用Java实现图的邻接矩阵和深度优先搜索的基本概念。 总结一下,这个话题涵盖了以下关键知识点: 1. 图的邻接矩阵表示法:使用二维数组存储图中节点的关系。 2. Java中实现邻接矩阵:创建一...

    图的遍历(邻接矩阵、邻接链表建图,深搜、广搜遍历,生成最小生成树)

    在这个课程设计中,我们将深入探讨“图的遍历”这一主题,它包括了如何使用邻接矩阵和邻接链表来构建图,以及如何通过深度优先搜索(DFS)和广度优先搜索(BFS)遍历图,最后还将学习Prim算法和Kruskal算法来生成...

    邻接矩阵实现图

    邻接矩阵实现图

    实现图的邻接矩阵和邻接表存储

    在编程中,有多种方法来存储图,其中两种常用的方法是邻接矩阵和邻接表。这两种方法各有优缺点,适用于不同类型的图和不同的操作需求。 邻接矩阵是一种二维数组,其中的每个元素代表两个顶点之间是否存在边。如果...

    代码 有向图关联矩阵和邻接矩阵的相互转换算法代码

    代码 有向图关联矩阵和邻接矩阵的相互转换算法代码代码 有向图关联矩阵和邻接矩阵的相互转换算法代码代码 有向图关联矩阵和邻接矩阵的相互转换算法代码代码 有向图关联矩阵和邻接矩阵的相互转换算法代码代码 有向图...

    类模板无向图邻接矩阵和深度及广度优先搜索遍历

    在这个主题中,我们将深入探讨如何使用类模板实现无向图的邻接矩阵表示法,以及如何通过深度优先搜索(DFS)和广度优先搜索(BFS)遍历这样的图。 首先,让我们理解邻接矩阵的概念。邻接矩阵是一个二维数组,其中的...

    图的邻接矩阵

    9. 图的邻接矩阵的实现:图的邻接矩阵可以使用C语言、Java语言、Python语言等多种编程语言来实现。 10. 图的邻接矩阵的常见错误:图的邻接矩阵的实现中,常见的错误包括矩阵越界、边的权值错误等。

    无向图的邻接矩阵存储及输出

    通过邻接矩阵来存储和操作无向图是一种直观且高效的方法,特别是在处理稠密图时。本文介绍的代码示例提供了从创建无向图到输出邻接矩阵的完整过程,有助于理解无向图的邻接矩阵表示方法及其应用。在实际编程中,选择...

    C++通过邻接矩阵实现图.zip

    本篇将深入探讨如何利用C++通过邻接矩阵实现图,并涵盖图的一些基本操作,如添加和删除顶点、添加和删除边,以及两种常用的图遍历算法——深度优先搜索(DFS)和广度优先搜索(BFS)。此外,还将涉及单源最短路径...

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

    图是数据结构中的一种重要...综上所述,`createadjlist.cpp`和`creatematix.cpp`文件分别实现了图的邻接表和邻接矩阵存储,为理解和操作图提供基础。通过阅读和理解这些代码,你可以更好地掌握这两种重要的图数据结构。

    图的邻接矩阵和邻接表实现

    本文将详细探讨图的两种常见存储方式——邻接矩阵和邻接表,以及基于这两种数据结构的深度搜索(DFS)、广度搜索(BFS)和Dijkstra最短路径算法。 首先,邻接矩阵是一种二维数组,用于表示图中所有节点之间的连接...

    数据结构C语言版_图的邻接矩阵存储表示和实现

    ### 数据结构C语言版_图的邻接矩阵存储表示和实现 #### 1. 图的邻接矩阵存储表示概述 图是一种重要的非线性数据结构,由顶点集和边集组成,用数学符号表示为 G = (V, E),其中 V 是顶点集合,E 是边集合。在计算机...

    graph_malab实现邻接矩阵画图_

    在MATLAB中,邻接矩阵是表示图结构的一种常见方式,尤其在图形理论、网络分析和数据可视化领域中。本文将深入探讨如何使用MATLAB来实现邻接矩阵的画图功能,以帮助我们直观地理解图的结构。 首先,邻接矩阵是一个二...

    邻接矩阵,邻接表实现图的创建,遍历(DFS,BFS)

    本文将深入探讨如何使用邻接矩阵和邻接表这两种方法来创建图,并实现深度优先搜索(DFS)和广度优先搜索(BFS)算法。 首先,我们来看邻接矩阵。邻接矩阵是一个二维数组,其中的元素代表图中节点之间的连接状态。...

    深度优先搜索 邻接矩阵邻接表

    本话题将详细讲解如何利用邻接矩阵和邻接表这两种数据结构来实现DFS,并通过实例验证算法的正确性。 首先,我们需要理解邻接矩阵和邻接表的概念: 1. **邻接矩阵**:邻接矩阵是用二维数组来表示图的邻接关系,其中...

    根据邻接矩阵绘制矩阵网络图Matlab程序

    `gplot`函数是专门用于根据矩阵数据绘制网络图的,它可以接受邻接矩阵和节点坐标作为输入参数。 在描述中提到的“根据节点活跃度自动分级”,这意味着我们需要对节点进行权重分配或聚类,以展示节点在图中的相对...

    代码 无向图关联矩阵和邻接矩阵的相互转换算法代码

    代码 无向图关联矩阵和邻接矩阵的相互转换算法代码代码 无向图关联矩阵和邻接矩阵的相互转换算法代码代码 无向图关联矩阵和邻接矩阵的相互转换算法代码代码 无向图关联矩阵和邻接矩阵的相互转换算法代码代码 无向图...

Global site tag (gtag.js) - Google Analytics