`

图的遍历(广度和深度)

    博客分类:
  • java
阅读更多
//深度优先遍历****************************************************
 class Graph1 {  //以邻接矩阵存储的图类
	
 protected int n;      //图的节点个数
 protected int mat[][];   // 二维数组存储图的邻接矩阵
 protected int visited[]; //访问标记数组
 
	 public Graph1(int m1[][]){
		 n = m1.length;
		 mat = new int [n][n];
		 System.arraycopy(m1, 0, mat, 0, n);  //System类方法,复制数组
		 visited= new int [n];
	 }
	 public Graph1(){
	 }
 public void depthFirstSearch(){  //图的深度优先遍历
	 System.out.println("深度优先遍历Depth first search:");
	 for(int k=1;k<=n;k++){
		 depthfs(k);
		 System.out.println();
		 unvisited();
	 }
	 }
	private void unvisited() {
	 int i;
		for(i = 0;i<visited.length;i++){
			visited[i]=0;
		}
	}
	private void depthfs(int k) {    //从节点k开始的深度优先遍历
		 int i,j=0;
		 System.out.print(" v"+k+"->");
		 i = k - 1;
		 visited[i]=1;
		 while(j<n){
			 if(mat[i][j]==1 && visited[j]==0){
				 depthfs(j+1);
			 }else {
				 j++;
			 }
		 }
	}
}
 public class testGraph1{
	public static void main(String ag[]){
		int mat[][]= {{0,1,0,0},{0,0,1,1},{0,0,0,0},{1,0,1,0}};
		Graph1 g1 = new Graph1(mat);
		g1.depthFirstSearch();
	}
}

//广度优先遍历*****************************************************
public class OnelinkNode {      //单向链表的节点结构
   public int data;
   public OnelinkNode next;
   public OnelinkNode(int k){   //构造值为k的节点
	   data = k;
	   next = null;
   }
   public OnelinkNode(){
	   this(0);
   }  
}

public class Graph2 extends Graph1 {             //以邻接表存储的图类
   OnelinkNode table[];                //图的邻接表
   
   public Graph2(int mat[][]){               //以邻接矩阵的形式建立图的邻接表
	 n = mat.length;                // 继承Graph1类的成员
	 table  = new OnelinkNode[n+1];           //建立节点表,多一个元素
	 OnelinkNode p = null,  q;
	 int i ,j ;
	 for(i = 1; i<= n;i++){                    //table[0]不用   节点序号i与table中的 下标一致
		 table[i] = new  OnelinkNode(i);          //创建i在节点表中的元素
		 p = table[i];   //建立节点i的出边表
		 for(j = 1; j<=n;j++){      //查找与i相邻的其他节点j
			 if(mat[i-1][j-1]==1){
				 q = new OnelinkNode(j);
				 p.next = q;
				  p = q;
			 }
		 }
		 visited = new int [n +1];
	 }
   }
   public Graph2(){}
   
   public void output(){
	   OnelinkNode p;
	   System.out.println("邻接表table:");
	   for(int i=0;i<table.length;i++){
		   System.out.print("table["+i+"]=");
		   if(table[i]!=null){
			   System.out.print("v"+table[i].data);
			   p = table[i].next;
			   while(p != null){
				   System.out.print("->v"+p.data);
				   p = p.next;
			   }
		   }
		   System.out.println(" null");
	   }
	   
   }

   
  /* public void depthfs(int k){
	   int i , j = 0;
	   OnelinkNode p ;
	   System.out.print("  v" +k+" ->");
	   i = k;
	   visited[i]=1;
	   if(table[i]!=null){
		   p = table[i].next;
		   while(p !=null){
			   j = p.data;
			   if(visited[j]==0){
				   depthfs(j);
			   }else{
			   p = table[i].next;
			   }
		   }
	   }
   }
   */
   public static void main(String args[]){
	   int mat[][]=  {{0,1,0,0},{0,0,1,1},{0,0,0,0},{1,0,1,0}};  
	   Graph2 g2 = new Graph2(mat);                    //现在的g2已经是一个邻接表了不是邻接矩阵了
	   g2.output();
	   
	   
   }
}
//邻接表table:
//table[0]= null
//table[1]=v1->2->4 null
//table[2]=v2->1->3->4 null
//table[3]=v3->2->4 null
//table[4]=v4->1->2->3 null



分享到:
评论

相关推荐

    图的深度优先遍历和广度优先遍历算法

    "图的深度优先遍历和广度优先遍历算法" 图的深度遍历和广度遍历是两个重要的算法,这也是我们理解并掌握图这一数据结构的基础。通过此程序算法可以进一步掌握图的构造以及遍历的相关知识。 图的深度优先遍历算法 ...

    邻接表深度遍历和广度遍历.h

    邻接表深度遍历和广度遍历 邻接表深度遍历和广度遍历 邻接表深度遍历和广度遍历 邻接表深度遍历和广度遍历

    图的遍历---深度和广度

    图的遍历---深度和广度 图的遍历---深度和广度 图的遍历---深度和广度 图的遍历---深度和广度 图的遍历---深度和广度 图的遍历---深度和广度 图的遍历---深度和广度

    图的遍历:深度优先、广度优先

    在邻接矩阵的存储结构下,实现图的深度优先遍历和广度优先遍历。

    无向图建立、深度优先遍历和广度优先遍历实现算法[借鉴].pdf

    无向图建立、深度优先遍历和广度优先遍历实现算法 本文将详细介绍无向图的建立、深度优先遍历和广度优先遍历的实现算法。这些算法是数据结构中非常重要的内容,掌握它们对后续学习和应用非常重要。 一、无向图的...

    图 深度遍历 广度遍历 基本操作

    在这个主题中,我们将深入探讨图的深度遍历(Depth-First Search, DFS)和广度遍历(Breadth-First Search, BFS)这两种遍历算法,以及它们在数据结构基本实验中的应用。 **1. 图的基本概念** 图由顶点(Vertex)...

    图的遍历 广度优先和深度优先

    图的遍历 广度优先和深度优先 采用vc++编写iostream输入和输出

    图的遍历演示(深度遍历和广度遍历)

    很多涉及图上操作的算法都是以图的遍历操作为基础的、是写一个程序,演示在连通的无向图上访问全部节点的操作。

    图的创立数据结构对其进行深度优先遍历和广度优先遍历

    在本文中,我们将深入探讨图的数据结构以及如何对图进行深度优先遍历(DFS)和广度优先遍历(BFS)。首先,我们要理解图的基本概念。图是一种数据结构,用于表示对象之间的关系,其中的对象称为顶点或节点,而它们...

    邻接矩阵表示法深度遍历和广度遍历.h

    邻接矩阵表示法深度遍历和广度遍历 邻接矩阵表示法深度遍历和广度遍历 邻接矩阵表示法深度遍历和广度遍历 邻接矩阵表示法深度遍历和广度遍历

    二叉树深度遍历广度遍历

    总之,掌握二叉树的深度遍历和广度遍历是理解和应用数据结构的关键。通过学习这些基本操作,可以更好地解决实际问题,例如在搜索、排序、图论等领域。在实际编程中,理解并灵活运用这些方法,能够提高代码的效率和...

    二叉树广度和深度优先遍历

    二叉树广度和深度优先遍历,通过递归算法实现二叉树的建立,利用递归算法实现深度优先遍历,使用队列实现广度优先遍历

    图的深度遍历和广度遍历

    图的深度遍历和广度遍历是图论中的两种基本搜索策略,它们在计算机科学中有着广泛的应用,尤其是在算法设计、数据结构处理、网络路由等领域。本篇实验报告将详细探讨这两种遍历方法,并提供C语言实现的源代码。 ...

    pptjoin 深度遍历 广度遍历

    "pptjoin 深度遍历 广度遍历"这一主题聚焦于两种不同的遍历策略:深度优先搜索(DFS)和广度优先搜索(BFS)。这些方法在解决各种问题时具有广泛的应用,例如网络爬虫、查找最短路径、判断连通性等。 深度优先搜索...

    建立图的邻接矩阵或邻接表存储并在此基础上实现图的深度优先遍历和广度优先遍历.doc

    "建立图的邻接矩阵或邻接表存储并在此基础上实现图的深度优先遍历和广度优先遍历" 本文档主要介绍了图的存储方式,包括邻接矩阵和邻接表两种存储方法,并在此基础上实现了图的深度优先遍历和广度优先遍历。 一、图...

    图的遍历,包括深度优先和广度优先遍历

    在这个主题下,我们将深入探讨深度优先遍历(DFS, Depth First Search)和广度优先遍历(BFS, Breadth First Search),以及在树结构中常见的先序、中序和后序遍历。这些遍历方法各有其特点,适用于不同的问题场景。...

    图的深度优先遍历和广度优先遍历

    图的深度优先遍历和广度优先遍历

    深度优先遍历与广度优先遍历

    图的遍历可以分为两类:深度优先遍历和广度优先遍历。这两种方法不仅适用于无向图,也适用于有向图。 #### 深度优先遍历 深度优先遍历是一种递归的遍历策略,它遵循“尽可能深入”的原则,尽可能地沿着图的一条边...

    图的深度和广度遍历算法

    通过算法实现图的深度优先遍历和广度优先遍历

    基于C++的图的深度遍历和广度遍历

    本教程将深入讲解基于C++实现的图的深度遍历(DFS, Depth First Search)和广度遍历(BFS, Breadth First Search)。 深度优先搜索是一种用于遍历或搜索树或图的算法。在C++中,我们可以使用递归或栈来实现DFS。...

Global site tag (gtag.js) - Google Analytics