图的创建、遍历及应用

结点类

package ch06;

public class Node {

private Object data; // 存放结点值 private Node next; // 后继结点的引用 // 无参数时的构造函数 public Node() { this(null, null); }

//带一个参数时的构造函数 public Node(Object data) { // 构造值为data的结点 this(data, null); }

//带两个参数时的构造函数 public Node(Object data, Node next) { this.data = data; this.next = next; }

public Object getData() { return data; }

public void setData(Object data) { this.data = data; }

public Node getNext() { return next; }

public void setNext(Node next) { this.next = next; } }

栈的抽象接口类 package ch06;

public interface IStack { public void clear(); public boolean isEmpty(); public int length(); public Object peek(); public void push(Object x) throws Exception; public Object pop(); }

链栈类

package ch06; import ch06.Node;

public class LinkStack implements IStack{ private Node top; //栈顶元素的应用 //将栈置空 public void clear(){ top=null; }

//判断栈是否为空 public boolean isEmpty(){ return top == null; }

//求链栈的长度 public int length(){ Node p = top; int length = 0; while (p!=null){ p=p.getNext(); ++length; } return length; }

//取栈顶元素并返回其值 public Object peek(){ if(!isEmpty()) return top.getData(); else return null; }

//入栈 public void push(Object x){ Node p = new Node(x); p.setNext(top); top = p; }

//出栈 public Object pop(){ if(isEmpty()){ return null; } else{ Node p = top; top = top.getNext(); return p.getData(); } }

//初始化，p指向栈顶元素，length为计数器//从栈顶元素开始向后查找，直到p指向空 // p指向后继结点 //长度增加1 //栈非空 //返回栈顶元素的值 //构造一个新结点 //新结点成为当前的首结点 //p指向被删除的结点（栈顶结点） //修改链指针，使栈顶结点从链栈中移去 //返回栈顶结点的数据域的值

//输出栈中所有数据元素（从栈顶元素到栈底元素） public void display(){ Node p = top; //初始化，p指向栈顶元素 while (p!= null){ //输出所有非空结点的数据元素值 System.out.print((p.getData().toString() + \"\")); p=p.getNext(); //p指针向后移 } } }

队列的抽象接口类 package ch06;

public interface IQueue { public void clear();

public boolean isEmpty(); public int length(); public Object peek();

public void offer(Object x)throws Exception; public Object poll(); }

链队列类 package ch06; import ch06.Node;

public class LinkQueue implements IQueue{ private Node front; private Node rear; //链队列类的构造函数 public LinkQueue(){ front=rear=null; }

//队列置空 public void clear(){ front=rear=null; }

//队列判空 public boolean isEmpty(){ return front==null; }

//求队列的长度 public int length(){ if(!isEmpty()){ Node p=front; int length=0; while(p!=null){ p=p.getNext();

//队首指针 //队尾指针 //队列非空 //指针下移

++length; //计数器+1 } } return length(); }

//取队首元素

public Object peek(){ if(front!=null) //队列非空 return front.getData(); //返回队首结点的数据域值 else return null; }

//入队

public void offer(Object x){ Node p =new Node(x); if(front!=null){ rear.setNext(p); rear=p; } else front=rear=p; }

//出队

public Object poll(){ if(front !=null){ Node p=front; front=front.getNext(); if(p==rear) rear=null; return p.getData(); } else return null;

} }

顶点结点类 package ch06;

public class VNode { private Object data; private ArcNode firstArc; public VNode() { this(null, null); } public VNode(Object data) {

//改变队列尾的位置 //队首结点出列 //被删除的结点是队尾结点时 //返回队首结点的数据域值 //顶点信息 //指向第一条依附于该顶点的弧

this(data, null); } public VNode(Object data, ArcNode firstArc) { this.data = data; this.firstArc = firstArc; } public Object getData() { return data; } public ArcNode getFirstArc() { return firstArc; } public void setData(Object data) { this.data = data; } public void setFirstArc(ArcNode firstArc) { this.firstArc = firstArc; } }

边结点类 package ch06;

public class ArcNode{

private int adjVex; //该弧所指向的顶点位置 private int value; //边或弧的权值 private ArcNode nextArc; //指向下一条弧 public ArcNode() { this(-1,0,null); }

public ArcNode(int adjVex) { this(adjVex,0,null); }

public ArcNode(int adjVex,int value) { this(adjVex,value,null); }

public ArcNode(int adjVex,int value,ArcNode nextArc) { this.value=value; this.adjVex = adjVex;

this.nextArc = nextArc; }

public int getValue(){ return value; }

public ArcNode getNextArc() { return nextArc;

}

public int getAdjVex() { return adjVex; }

public void setAdjVex(int adjVex) { this.adjVex = adjVex; }

public void setValue(int value) { this.value = value; }

public void setNextArc(ArcNode nextArc) { this.nextArc = nextArc; } }

图的类型类 package ch06;

public enum GraphKind { UDN, DN; }

图的抽象类 package ch06;

public interface IGraph{

void createGraph(); int getVexNum(); int getArcNum(); Object getVex(int v) throws Exception; int locateVex(Object vex); int firstAdjVex(int v) throws Exception; int nextAdjVex(int v,int w) throws Exception; }

图的邻接表类 package ch06;

import java.util.Scanner;

public class ALGraph implements IGraph{ private GraphKind kind; private int vexNum,arcNum; private VNode[] vexs; public ALGraph(){ this(null,0,0,null); }

public ALGraph(GraphKind kind,int vexNum,int arcNum,VNode[] vexs){ this.kind=kind;

this.vexNum=vexNum;

this.arcNum=arcNum; this.vexs=vexs; }

//图的创建模块下的子菜单 public void createGraph(){

Scanner sc=new Scanner(System.in);

System.out.println(\"请输入图的类型:1--无向网2--有向网3--退出\"); int kind;

kind =sc.nextInt(); while(kind!=3){ switch(kind){ case 1: System.out.println(\"您选择的是无向网请继续接下来的操作：\"); createUDN(); displayUDN(); break; case 2: System.out.println(\"您选择的是有向网请继续接下来的操作：\"); createDN(); displayDN(); break; default: System.out.println(\"请选择正确的选项!\"); break; }

kind =sc.nextInt(); } }

//创建有向网

private void createDN(){ Scanner sc=new Scanner(System.in); System.out.println(\"请分别输入图的顶点数、图的边数:\"); vexNum=sc.nextInt(); arcNum=sc.nextInt(); vexs = new VNode[vexNum]; System.out.println(\"请分别输入图的各顶点:\"); for(int v=0;vdisplay DN(); }

}

//创建无向网

private void createUDN() { Scanner sc = new Scanner(System.in); System.out.println(\"请分别输入图的顶点数、图的边数:\"); vexNum = sc.nextInt(); arcNum = sc.nextInt(); vexs = new VNode[vexNum]; System.out.println(\"请分别输入图的各个顶点:\"); for (int v = 0; v < vexNum; v++) vexs[v] = new VNode(sc.next()); System.out.println(\"请输入各个边的顶点及其权值:\"); for (int k = 0; k < arcNum; k++) { int v = locateVex(sc.next()); int u = locateVex(sc.next()); int value=sc.nextInt(); addArc(v,u,value); addArc(u,v,value); display UDN(); } }

//输出有向网

public void displayDN(){ System.out.println(\"输入有向网如下:\"); for (int j=0;jfor(ArcNode arc = getVexs()[j].getFirstArc();arc!=null;arc=arc.getNextArc()){ int k =arc.getAdjVex(); int value =arc.getValue(); System.out.println(\"v\"+getVexs()[j].getData()+\"->\"+\"v\"+getVexs()[k].getData() +

\" \"+value);

} }

//输出无向网

public void displayUDN(){ System.out.println(\"输入无向网如下:\"); for (int j=0;jfor(ArcNode arc = getVexs()[j].getFirstArc();arc!=null;arc=arc.getNextArc()){ int k =arc.getAdjVex(); int value =arc.getValue(); if(j\" \"+value);

} }

public void addArc(int v,int u,int value){ //插入边结点 ArcNode arc=new ArcNode(u,value); arc.setNextArc(vexs[v].getFirstArc()); vexs[v].setFirstArc(arc); }

public int getVexNum(){ //返回顶点数 return vexNum; }

public int getArcNum(){ //返回边数 return arcNum; }

public int locateVex(Object vex){ for(int v=0;vpublic VNode[]getVexs(){ return vexs; }

public GraphKind getKind(){ return kind; }

public Object getVex(int v)throws Exception{ if(v<0&&v>=vexNum)

throw new Exception(\"第\"+v+\"个顶点不存在!\"); return vexs[v].getData(); }

//返回v的第一个邻接点，若v没有邻接点，则返回-1，0<=v=vexNum)

throw new Exception(\"第\"+v+\"个顶点不存在!\"); VNode vex=vexs[v];

if(vex.getFirstArc()!=null)

return vex.getFirstArc().getAdjVex(); else

return -1; }

//查找下一个邻接点

public int nextAdjVex(int v,int w)throws Exception{ if(v<0&&v>=vexNum) throw new Exception(\"第\"+v+\"个顶点不存在!\");

VNode vex=vexs[v]; ArcNode arcvw=null;

for(ArcNode arc=vex.getFirstArc();arc!=null;arc=arc.getNextArc()) if(arc.getAdjVex()==w){ arcvw=arc; break; }

if(arcvw!=null&&arcvw.getNextArc()!=null) return arcvw.getNextArc().getAdjVex(); else

return -1; }

//图的创建的主方法

public static void main(String[] args) { ALGraph a = new ALGraph(); a.createGraph(); } }

图的遍历类 package ch06;

import ch06.LinkQueue; class ArcNodei { private int adjVex; // 该弧所指向的顶点位置 private ArcNodei nextArc; // 指向下一条弧 public ArcNodei() { this(-1,null); } public ArcNodei(int adjVex) { this(adjVex, null); } public ArcNodei(int adjVex, ArcNodei nextArc) { this.adjVex = adjVex; this.nextArc = nextArc; } public ArcNodei getNextArc() { return nextArc; } public int getAdjVex() { return adjVex; } public void setAdjVex(int adjVex) { this.adjVex = adjVex; } public void setNextArc(ArcNodei nextArc) {

this.nextArc = nextArc; } }

//图的邻接表存储表示中的顶点结点类 class VNodei {

private Object data;// 顶点信息

private ArcNodei firstArc;// 指向第一条依附于该顶点的弧 public VNodei() { this(null, null); }

public VNodei(Object data) { this(data, null); }

public VNodei(Object data, ArcNodei firstArc) { this.data = data; this.firstArc = firstArc; }

public Object getData() { return data; }

public ArcNodei getFirstArc() { return firstArc; }

public void setData(Object data) { this.data = data; }

public void setFirstArc(ArcNodei firstArc) { this.firstArc = firstArc; } }

//无向图的邻接表类 class AL { private int vexNum, arcNum; // 图的当前顶点数和边数 private VNodei[] vexs; // 顶点 public AL() { this( 0, 0, null); } public AL( int vexNum, int arcNum, VNodei[] vexs) { this.vexNum = vexNum; this.arcNum = arcNum; this.vexs = vexs; }

public int getArcNum() { return arcNum;

}

public void setArcNum(int arcNum) { this.arcNum = arcNum; }

public int getVexNum() { return vexNum; }

public void setVexNum(int vexNum) { this.vexNum = vexNum; }

public VNodei[] getVexs() { return vexs; }

public void setVexs(VNodei[] vexs) { this.vexs = vexs; } // 返回v表示结点的值， 0 <= v < vexNum public Object getVex(int v) throws Exception { if (v < 0 && v >= vexNum) throw new Exception(\"第\" + v + \"个顶点不存在!\"); return vexs[v].getData(); }

// 返回v的第一个邻接点，若v没有邻接点则返回-1， 0 <= v < vexnum public int firstAdjVex(int v) throws Exception { if (v < 0 && v >= vexNum) throw new Exception(\"第\" + v + \"个顶点不存在!\"); VNodei vex = vexs[v]; if (vex.getFirstArc() != null) return vex.getFirstArc().getAdjVex(); else return -1; }

// 返回v相对于w的下一个邻接点，若w是v的最后一个邻接点，则返回-1，其中0

≤v, w= vexNum) throw new Exception(\"第\" + v + \"个顶点不存在!\"); VNodei vex = vexs[v]; ArcNodei arcvw = null; for (ArcNodei arc = vex.getFirstArc(); arc != null; arc = arc.getNextArc()) if (arc.getAdjVex() == w) { arcvw = arc; break; }

if (arcvw != null && arcvw.getNextArc() != null) return arcvw.getNextArc().getAdjVex(); else return -1; }

//邻接表的输出

public void displayAL(){

for (int i=0; iSystem.out.print(vexs[i].getData().toString()+\":\"); ArcNodei p=vexs[i].getFirstArc(); while(p!=null){

System.out.print(p.getAdjVex()+\" \"); p=p.getNextArc(); }

System.out.println(); } }

//图的遍历类

class TraverserAL {

private static boolean[] visited; // 访问标志数组 // 对图G做深度优先遍历

public static void DFSTraverse(AL G) throws Exception { visited = new boolean[G.getVexNum()]; for (int v = 0; v < G.getVexNum(); v++) // 访问标志数组初始化 visited[v] = false; for (int v = 0; v < G.getVexNum(); v++) if (!visited[v])// 对尚未访问的顶点调用DFS DFS(G, v); } // 从第v个顶点出发递归地深度优先遍历图G public static void DFS(AL G, int v) throws Exception { visited[v] = true; System.out.print(G.getVex(v).toString() + \" \"); // 访问第v个顶点 for (int w = G.firstAdjVex(v); w >= 0; w = G.nextAdjVex(v, w)) if (!visited[w]) // 对v的尚未访问的邻接顶点w递归调用DFS DFS(G, w); } public static void BFSTraverse(AL G) throws Exception { //对图G做广度优先遍历 visited = new boolean[G.getVexNum()]; // 访问标志数组 for (int v = 0; v < G.getVexNum(); v++) // 访问标志数组初始化 visited[v] = false; for (int v = 0; v < G.getVexNum(); v++) if (!visited[v]) // v尚未访问 BFS(G, v);

} private static void BFS(AL G, int v) throws Exception { visited[v] = true; System.out.print(G.getVex(v).toString() + \" \"); LinkQueue Q = new LinkQueue(); // 辅助队列Q Q.offer(v);// v入队列 while (!Q.isEmpty()) { int u = (Integer) Q.poll(); // 队头元素出队列并赋值给u for (int w = G.firstAdjVex(u); w >= 0; w = G.nextAdjVex(u, w)) if (!visited[w]) { // w为u的尚未访问的邻接顶点 visited[w] = true; System.out.print(G.getVex(w).toString() + \" \"); Q.offer(w); } } } }

//测试类

public class ergodic{ public static AL generateAL() { //创建无向图的邻接表 ArcNodei v01 = new ArcNodei(1); ArcNodei v02 = new ArcNodei(2, v01); ArcNodei v03 = new ArcNodei(3, v02); VNodei v0 = new VNodei(\"v0\ ArcNodei v10 = new ArcNodei(0); ArcNodei v12 = new ArcNodei(2,v10); ArcNodei v14 = new ArcNodei(4,v12); VNodei v1 = new VNodei(\"v1\ ArcNodei v20 = new ArcNodei(0); ArcNodei v21 = new ArcNodei(1,v20); ArcNodei v23 = new ArcNodei(3,v21); ArcNodei v24 = new ArcNodei(4,v23); VNodei v2 = new VNodei(\"v2\ ArcNodei v30 = new ArcNodei(0); ArcNodei v32 = new ArcNodei(2,v30); ArcNodei v34 = new ArcNodei(4,v32); VNodei v3 = new VNodei(\"v3\ ArcNodei v41 = new ArcNodei(1); ArcNodei v42 = new ArcNodei(2,v41); ArcNodei v43 = new ArcNodei(3,v42); VNodei v4 = new VNodei(\"v4\ VNodei[] vexs = { v0, v1, v2, v3, v4 }; AL G = new AL( 5, 16, vexs); return G;

} public static void main(String[] args) throws Exception { AL G = generateAL(); System.out.print(\"无向图为：\\n\"); G.displayAL(); System.out.print(\"无向图的广度优先遍历序列为：\"); TraverserAL.BFSTraverse(G); System.out.println();

System.out.print(\"无向图的深度优先遍历序列为：\"); TraverserAL.DFSTraverse(G); System.out.println(); } }

汇总类 package all;

import java.util.Scanner; import ch06.ALGraph; import ch06.ergodic; import ch06.CriticalPath; public class all { public static void welcome(){ //主菜单 System.out.println(\" welcome to our system\"); System.out.println(\"***************************\"); System.out.println(\"* 1---图的创建 \"); System.out.println(\"* 2---图的遍历 \"); System.out.println(\"* 3---图的应用 \"); System.out.println(\"* 4---结 束 \"); System.out.println(\"* 5---使用说明 \"); System.out.println(\"***************************\"); }

public static void main(String[] args) throws Exception { Scanner sc = new Scanner(System.in); welcome(); System.out.println(\" 请选择功能: \"); int kind; kind =sc.nextInt(); while(kind!=4){ switch (kind) { case 1: ALGraph.main(null); //调用图的创建的主方法 System.out.println(\"***************************************\"); break ; case 2: ergodic.main(null); //调用图的遍历的主方法

}

}

System.out.println(\"***************************************\"); break ; case 3: CriticalPath.main(null); //调用图的应用主方法 System.out.println(\"***************************************\"); break ;

case 5: //使用说明 System.out.println(\"请通过选择输入1、2、3、4、5来选择相应的功能\\n \" + \" 1为图的创建，你可以实现有向网和无向网的邻接矩阵创建\\n \" + \" 2为图的遍历，可以实现图的深度和广度遍历\\n\" + \" 3为图的应用，可以实现AOE网的关键路径\\n\" + \" 4为结束，可以结束运行\"); System.out.println(\"***************************************\"); break; default: System.out.println(\"请选择正确的选项!\"); break; }

welcome();

System.out.println(\"请选择功能: \"); kind = sc.nextInt(); }