图的创建、遍历及应用.doc

结点类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 IStackprivate Node top; /栈顶元素的应用 /将栈置空public void clear() top=null; /判断栈是否为空public boolean isEmpty()return top = null; /求链栈的长度public int length()Node p = top; /初始化，p指向栈顶元素，length为计数器int length = 0;while (p!=null) /从栈顶元素开始向后查找，直到p指向空p=p.getNext(); / p指向后继结点+length; /长度增加1return length; /取栈顶元素并返回其值public Object peek()if(!isEmpty() /栈非空return top.getData(); /返回栈顶元素的值elsereturn null; /入栈public void push(Object x)Node p = new Node(x); /构造一个新结点p.setNext(top);top = p; /新结点成为当前的首结点 /出栈public Object pop()if(isEmpty()return null;elseNode p = top; /p指向被删除的结点（栈顶结点）top = top.getNext(); /修改链指针，使栈顶结点从链栈中移去return p.getData(); /返回栈顶结点的数据域的值 /输出栈中所有数据元素（从栈顶元素到栈底元素）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 IQueueprivate 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(); /返回队首结点的数据域值elsereturn null;/入队public void offer(Object x)Node p =new Node(x);if(front!=null)rear.setNext(p);rear=p; /改变队列尾的位置elsefront=rear=p;/出队public Object poll()if(front !=null)Node p=front;front=front.getNext(); /队首结点出列if(p=rear) /被删除的结点是队尾结点时rear=null;return p.getData(); /返回队首结点的数据域值 elsereturn 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 IGraphvoid 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 VNodevexNum; System.out.println(请分别输入图的各顶点:); for(int v=0;vvexNum;v+) vexsv = new VNode(sc.next(); System.out.println(请输入各边的顶点及其权值:); for(int k=0;karcNum;k+) int v=locateVex(sc.next(); int u=locateVex(sc.next(); int value=sc.nextInt(); addArc(v,u,value); display DN(); /创建无向网 private void createUDN() Scanner sc = new Scanner(System.in);System.out.println(请分别输入图的顶点数、图的边数:);vexNum = sc.nextInt();arcNum = sc.nextInt();vexs = new VNodevexNum;System.out.println(请分别输入图的各个顶点:);for (int v = 0; v vexNum; v+)vexsv = 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;j+v+getVexs()k.getData() + +value); /输出无向网 public void displayUDN() System.out.println(输入无向网如下:);for (int j=0;jgetVexNum();j+) for(ArcNode arc = getVexs()j.getFirstArc();arc!=null;arc=arc.getNextArc() int k =arc.getAdjVex(); int value =arc.getValue(); if(jk) System.out.println(v+getVexs()j.getData()+-+ v+getVexs()k.getData() + +value); public void addArc(int v,int u,int value) /插入边结点 ArcNode arc=new ArcNode(u,value); arc.setNextArc(vexsv.getFirstArc(); vexsv.setFirstArc(arc); public int getVexNum() /返回顶点数 return vexNum; public int getArcNum() /返回边数 return arcNum; public int locateVex(Object vex) for(int v=0;vvexNum;v+) if(vexsv.getData().equals(vex) return v; return -1; public VNodegetVexs() return vexs; public GraphKind getKind() return kind; public Object getVex(int v)throws Exception if(v=vexNum) throw new Exception(第+v+个顶点不存在!); return vexsv.getData(); /返回v的第一个邻接点，若v没有邻接点，则返回-1，0=vvexNum public int firstAdjVex(int v)throws Exception if(v=vexNum) throw new Exception(第+v+个顶点不存在!); VNode vex=vexsv; if(vex.getFirstArc()!=null) return vex.getFirstArc().getAdjVex(); else return -1; /查找下一个邻接点 public int nextAdjVex(int v,int w)throws Exception if(v=vexNum) throw new Exception(第+v+个顶点不存在!); VNode vex=vexsv; 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 vexNumpublic Object getVex(int v) throws Exception if (v = vexNum)throw new Exception(第 + v + 个顶点不存在!);return vexsv.getData(); / 返回v的第一个邻接点，若v没有邻接点则返回-1， 0 = v vexnumpublic int firstAdjVex(int v) throws Exception if (v = vexNum)throw new Exception(第 + v + 个顶点不存在!);VNodei vex = vexsv;if (vex.getFirstArc() != null)return vex.getFirstArc().getAdjVex();elsereturn -1; / 返回v相对于w的下一个邻接点，若w是v的最后一个邻接点，则返回-1，其中0v, wvexNumpublic int nextAdjVex(int v, int w) throws Exception if (v = vexNum)throw new Exception(第 + v + 个顶点不存在!);VNodei vex = vexsv;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();elsereturn -1;/邻接表的输出 public void displayAL() for (int i=0; ivexs.length;i+) System.out.print(vexsi.getData().toString()+:); ArcNodei p=vexsi.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 booleanG.getVexNum(); for (int v = 0; v G.getVexNum(); v+) / 访问标志数组初始化visitedv = false;for (int v = 0; v = 0; w = G.nextAdjVex(v, w)if (!visitedw) / 对v的尚未访问的邻接顶点w递归调用DFSDFS(G, w);public static void BFSTraverse(AL G) throws Exception /对图G做广度优先遍历visited = new booleanG.getVexNum(); / 访问标志数组for (int v = 0; v G.getVexNum(); v+) / 访问标志数组初始化visitedv = false;for (int v = 0; v = 0; w = G.nextAdjVex(u, w)if (!visitedw) / w为u的尚未访问的邻接顶点visitedw = true;System.out.print(G.getVex(w).toString() + );Q.offer(w);/测试类public class ergodicpublic 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, v03); ArcNodei v10 = new ArcNodei(0); ArcNodei v12 = new ArcNodei(2,v10); ArcNodei v14 = new ArcNodei(4,v12);VNodei v1 = new VNodei(v1, v14); 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, v24); ArcNodei v30 = new ArcNodei(0); ArcNodei v32 = new ArcNodei(2,v30); ArcNodei v34 = new ArcNodei(4,v32); VNodei v3 = new VNodei(v3, v34); ArcNodei v41 = new ArcNodei(1); ArcNodei v42 = new ArcNodei(2,v41); ArcNodei v43 = new ArcNodei(3,v42);VNodei v4 = new VNodei(v4, v43);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)