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

65 阅读 0 评论 43 点赞

我是靠谱客的博主跳跃蚂蚁，最近开发中收集的这篇文章主要介绍基于邻接矩阵的无向图的深度广度遍历实现，觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

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

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

逐个输入