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

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

邻接表,无向图,深度、广度遍历,测试通过

基本构建图的邻接表结构以及深度广度遍历

public class ALGraph {
	AdjList[] vertices;
	int vexNum;
	int arcNum;
	boolean[] visited;
	public ALGraph(int vexNum,int arcNum){
		this.vexNum = vexNum;
		this.arcNum = arcNum;
	}
	//建立有vexNum个结点arcNum条边的无向图的邻接表存储结构
	public void createAlGraph(){
		vertices = new AdjList[vexNum];
		Scanner in1 = new Scanner(System.in);
		visited = new boolean[vexNum];
		for(int i=0;i<vexNum;i++ ){
			//输入顶点的信息
			System.out.print("please input the info of vex");

vertices[i] = new AdjList(in1.next(),null);
		}
		//输入边的信息
		Scanner in2 = new Scanner(System.in);
		for(int k=0;k<arcNum;k++){
			System.out.print("please input the info of arc one:");
			int i=in2.nextInt();
			System.out.print("please input the info of arc two:");
			int j=in2.nextInt();//顶点ij之间存在边,我们要把这条边链上
			//将j链接到i上,由于是无向图,同时将i也链接到j上
			ArcNode nodei = new ArcNode(j,null);
		    ArcNode p = vertices[i].firstArc;
		    if(p==null){
		            vertices[i].firstArc = nodei;
		            nodei.nextarc = null;
		    }
		    else{
		    	while(p.nextarc!=null)
		    		p=p.nextarc;
		    	p.nextarc = nodei;
		    	 nodei.nextarc = null;
		    }
			ArcNode nodej = new ArcNode(i,null);
			p = vertices[j].firstArc;
			if(p==null){
				 vertices[j].firstArc = nodej;
				 nodej.nextarc = null;
		    }
		    else{
		    	while(p.nextarc!=null)
		    		p=p.nextarc;
		    	p.nextarc = nodej;
		    	 nodej.nextarc = null;
		    }
			
		}
	}
	public void visit(AdjList v){
		if(v!=null){System.out.print(MessageFormat.format("结点值为{0}:",v.data));
		System.out.println();
		}
		
	}
	 public void dFS(int k){
		
		if(!visited[k]){
			visit(vertices[k]);
			visited[k]=true;
			for(ArcNode p= vertices[k].firstArc;p!=null;p=p.nextarc){
				int w = p.adjvex;
				if(!visited[w]){
					dFS(w);
				}
			}
			
		}
		
	}
	public void dFSTrave(){
		System.out.print(vexNum);
		for(int i=0;i<vexNum;i++){
			visited[i] = false;
			
		}
		for(int j=0;j<vexNum;j++){
			if(!visited[j]){
				dFS(j);
			}
		}
	}
	public void bFSTrave(){
		
		for(int j=0;j<vexNum;j++){
			visited[j] = false;
		}
		Queue queue = new Queue(100);
		for(int i=0;i<vexNum;i++){
			if(!visited[i]){
				visit(vertices[i]);
				visited[i]=true;
				queue.EnQueue(queue, i);
				while(!queue.isEmpty(queue)){
					int w = queue.DeQueue(queue);
					ArcNode p = vertices[w].firstArc;
					while(p!=null){
						if(p!=null){
							int k = p.adjvex;
							if(!visited[k]){
								visit(vertices[k]);
								visited[k] = true;
								queue.EnQueue(queue, k);
							}
						}
						
						p=p.nextarc;
					}
				}
				
			}
		}
		
	}
	

}

队列结构,主要是用来辅助广度遍历

public class Queue {
	private static int maxSize=100;
	private int[] data;
	private int front;
	private int rear;
	
	public static int getMaxSize() {
		return maxSize;
	}
	public static void setMaxSize(int maxSize) {
		Queue.maxSize = maxSize;
	}
	public int[] getData() {
		return data;
	}
	public void setData(int[] 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 int[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,int node){
		
		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 int DeQueue(Queue q){
		if(isEmpty(q)){
			System.out.print("该队列为空");
			return 0;
			
		}
		else{
			int node = q.data[q.front];
			q.front = (q.front+1)%maxSize;
			return node;
		}
		
	}
	

}

基本存储结构

public class ArcNode {
	public int adjvex;
	public ArcNode nextarc;
	public ArcNode(int adjvex,ArcNode nextarc){
		this.adjvex = adjvex;
		this.nextarc = nextarc;
		
		
	}
	public ArcNode(int adjvex){
		this.adjvex = adjvex;
	}
	

}
public class AdjList {
	public String data;
/*	public ArcNode node;*/
	public ArcNode firstArc;
	public AdjList(String data,ArcNode firstArc){
		this.data = data;
/*		this.node = new ArcNode(Integer.parseInt(data));*/
		this.firstArc = firstArc;
	}

}

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

我来说两句

0 条评论
登录 后参与评论

相关文章

  • 贪心算法举例分析

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

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

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

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

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

    张凝可
  • 一步一步学Linq to sql(八):继承与关系

    1.首先定义的是Topic实体基类,然后两个子类的继承,NewTopic--主题帖,Reply--回复帖。 2.Topic类上的特性,下面先来看一下特性类

    aehyok
  • 轻松又酷炫地实现弹幕效果——手把手教学

    更多代码,请查看我的github:https://github.com/shuaijia/JsPlayer ,喜欢的话就给个star!^_^

    蜻蜓队长
  • 23种设计模式详解(四)

    顾名思义,装饰模式就是给一个对象增加一些新的功能,而且是动态的,要求装饰对象和被装饰对象实现同一个接口,装饰对象持有被装饰对象的实例。

    南风
  • Spring Boot Async异步执行任务

    异步调用就是不用等待结果的返回就执行后面的逻辑,同步调用则需要等带结果再执行后面的逻辑。

    猿天地
  • 23种设计模式详解(四)

    南风
  • Android registerActivityLifecycleCallbacks 使用

    使用这个类,我们可以很方便的监听到 Activity 的状态,从而可以判断 APP 是否在前台或者后台等。

    IT大飞说
  • Java 基础知识点(必知必会其二)

       1.如何将数字输出为每三位逗号分隔的格式,例如“1,234,467”?    1 package com.Gxjun.problem; 2 3 i...

    Gxjun

扫码关注云+社区

领取腾讯云代金券