专栏首页技术圈基于邻接矩阵的无向图的深度广度遍历实现

基于邻接矩阵的无向图的深度广度遍历实现

图的创建及深度广度遍历的代码实现,基于的是邻接矩阵,图这里是无向图,并且两个顶点之间有连接则邻接矩阵非零,如果没有连接则为零

public class Graph {
	//图的邻接矩阵形式
	private int[][] edges;
	private int num;//图的结点数量
	private boolean[] visited ;//结点是否被访问过
	private Vertex[] vertex ;
	private int pre;//用来记录前一个访问的结点
	public Graph(){
		
	}
	public void createGraph(){
		Scanner in = new Scanner(System.in);
		System.out.print("please input the info:");
		String str = in.next();
		String[] temp = str.split(",");
		System.out.print(temp.length);
		this.num = temp.length;
		System.out.print(num);
		visited = new boolean[num];
		vertex = new Vertex[num];
		for(int i=0;i<num;i++){
			Vertex v = new Vertex(i,temp[i]);
			vertex[i]=v;
			visit(vertex[i]);
			System.out.println();
		}
		edges = new int[num][num];
		for(int i=0;i<num;i++){
		
			for(int j=0;j<num;j++){
				Scanner in1 = new Scanner(System.in);
				System.out.print("input the value:");
				int k = in1.nextInt();
				/* System.out.print(k);*/
				edges[i][j] =k;
			}
		}
		
	}
	public void visit(Vertex v){
		if(v!=null){System.out.print(MessageFormat.format("结点序号为{0},结点信息为{1}", v.no,v.info));
		System.out.println();
		}
		
	}
	public void dFS(int i){
		visit(vertex[i]);
		visited[i]=true;
		for(int j=i+1;j<num;j++){
			if(!visited[j]&&edges[i][j]!=0){
				dFS(j);
			}
		}
	}
	public void dFSTrave(){
		//深度遍历是在邻接矩阵的基础上进行的
		for(int i=0;i<num;i++){
			visited[i]=false;//默认情况下所有顶点是没有被访问过的
		}
		
			for(int i=0;i<num;i++){
				if(!visited[i]){//还需要考虑一个条件就是必须可达
					
					dFS(i);
					
				}
			}
			
		
		
		
	}
	//广度遍历则需要使用数据结构队列
	public void bFSTrave(){
		for(int i=0;i<num;i++){
			visited[i]=false;//默认情况下所有顶点是没有被访问过的
		}
		Vertex v=null;
		Queue queue = new Queue(100);
		for(int i=0;i<num;i++){
			if(!visited[i]){
				
				visit(vertex[i]);
				visited[i]=true;
				//访问完成后入队
				queue.EnQueue(queue, vertex[i]);
				while(!queue.isEmpty(queue)){
					v = queue.DeQueue(queue);
					if(v!=null){
						int k = v.no;
						for(int j=k+1;j<num;j++){
							if(!visited[j]&&edges[k][j]!=0){
								visit(vertex[j]);
								visited[j]=true;
								
								queue.EnQueue(queue, vertex[j]);
							}
					}
					
					}
				}
			}
		}
		
	}
	

}
public class Vertex {
	//图的顶点信息
  public	int no;//顶点的标号
  public String info;//顶点的信息
  public Vertex(int i,String info){
	  this.no = i;
	  this.info = info;
  }
	

}
public class Queue {
	private static int maxSize=100;
	private Vertex[] data;
	private int front;
	private int rear;
	
	public static int getMaxSize() {
		return maxSize;
	}
	public static void setMaxSize(int maxSize) {
		Queue.maxSize = maxSize;
	}
	public Vertex[] getData() {
		return data;
	}
	public void setData(Vertex[] data) {
		this.data = data;
	}
	public int getFront() {
		return front;
	}
	public void setFront(int front) {
		this.front = front;
	}
	public int getRear() {
		return rear;
	}
	public void setRear(int rear) {
		this.rear = rear;
	}
	public 	Queue(int maxSize){
		data = new Vertex[maxSize];
		front = 0;
		rear = 0;
		
	}
	public static boolean isEmpty(Queue q){
		if (q.front==q.rear){
			return true;
		}
		else return false;
		
	}
	public static void EnQueue(Queue q,Vertex node){
		System.out.print(maxSize);
		if((q.rear+1)%maxSize==q.front){
			System.out.print("队列已经满了");
			return;
			
		}else{
			q.data[q.rear]=node;
			q.rear =( q.rear+1)%maxSize;
		}
		
	}
	public static Vertex DeQueue(Queue q){
		if(isEmpty(q)){
			System.out.print("该队列为空");
			return null;
			
		}
		else{
			Vertex node = q.data[q.front];
			q.front = (q.front+1)%maxSize;
			return node;
		}
		
	}
	

}
public class Client_Graph {

	/**
	 * @param args
	 */
	public static void main(String[] args) {
		Graph graph = new Graph();
		graph.createGraph();
		graph.dFSTrave();
		graph.bFSTrave();
		

	}

}

输入格式为:a,b,c,d代表四个个顶点

输入矩阵:0 0 1 0

0 0 1 1

1 1 0 0

0 1 0 0

逐个输入

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • 基于分治和DP的算法设计

    发现下面的策略都是比较糟糕的,这里提及一下分治和动态规划的区别,动态规划避免了分治方法的重复计算,下面的基本上是用了最朴素的动态规划方案,接下来会用自底向上的方...

    张凝可
  • 常用的递归算法

    版权声明:本文为博主原创文章,遵循 CC 4.0 by-sa 版权协议,转载请附上原文出处链接和本声明。

    张凝可
  • 面试题目集(一)

    版权声明:本文为博主原创文章,遵循 CC 4.0 by-sa 版权协议,转载请附上原文出处链接和本声明。

    张凝可
  • 编程题7-12答案

    三哥
  • 设计模式二十四章经之策略模式

    我就是马云飞
  • Android中View跟随手指滑动效果的实例代码

    本文讲述了Android中View跟随手指滑动效果的实例代码。分享给大家供大家参考,具体如下:

    砸漏
  • Android利用ViewDragHelper轻松实现拼图游戏的示例

    最近一段时间看了一些介绍ViewDragHelper的博客,感觉这是一个处理手势滑动的神奇,看完以后就想做点东西练练手,于是就做了这个Android拼图小游戏。

    砸漏
  • 剑指offer(01-15题)优化题解

    思路: 选定一个维度(行或列)先找到需要查找的元素所在的行(列),再从该行(列)找到该元素的该元素具体的列(行)位置。复杂度O(n)。

    bigsai
  • 事件系统的设计方法

    事件功能用过段时间,像用户登入登出,充值,完成任务等非常的方便,有时间看看源码学习,设计的时候比较复杂,但完成后使用很简单,选了创建角色事件走遍流程,下面是JA...

    深雾
  • 2018年海淀区青少年程序设计思维挑战活动普及组详细答案

    海天一树

扫码关注云+社区

领取腾讯云代金券