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

```public class ALGraph {
int vexNum;
int arcNum;
boolean[] visited;
public ALGraph(int vexNum,int arcNum){
this.vexNum = vexNum;
this.arcNum = arcNum;
}
//建立有vexNum个结点arcNum条边的无向图的邻接表存储结构
public void createAlGraph(){
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");

}
//输入边的信息
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;
}

}
}
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){
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){
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 ArcNode nextarc;
this.nextarc = nextarc;

}
}

}
public String data;
/*	public ArcNode node;*/
public 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 版权协议，转载请附上原文出处链接和本声明。

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

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

• 23种设计模式详解（四）

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

• Spring Boot Async异步执行任务

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

• Android registerActivityLifecycleCallbacks 使用

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

• Java 基础知识点（必知必会其二）

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