隣接マトリクスに基づく無方向図の深さ広がりを実现しました.
図の作成と深さ広さが遍歴されたコード実装は、隣接行列に基づいており、ここでは無方向図であり、二つの頂点の間に接続があると隣接行列はゼロではなく、接続がないとゼロとなる.
入力マトリックス:0 1 0
0 0 0 1
1 0 0
0 1 0 0
いちいち入力する
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
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 1 0
0 0 0 1
1 0 0
0 1 0 0
いちいち入力する