java 图的深度优先和广度优先搜索以及关键路径

《java 图的深度优先和广度优先搜索以及关键路径》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、package数据结构.图的邻接表法;/*思路(这是一个无向图)：*1、从命令行接收增加节点数把它放在一个一维数组中*2、增加边数，同时找这个边是否在图中，若在，就构造邻接表*/importjava.util.ArrayList;importjava.util.Scanner;importjava.util.Stack;classArcNode{//表结点intinfo;//该弧相关信息的指针intadjvex;//邻接点域ArcNodenext;//指向下一条弧的指针publicArcNode(intadjvex,intinfo){//构造函数this.adjvex=adjvex;th

2、is.info=info;this.next=null;}}classVNode{//头结点intdata;//顶点信息（如数据等）ArcNodefirstarc;//指向第一条依附该顶点的边的弧指针publicVNode(intdata){//构造函数this.data=data;this.firstarc=null;}}classALGraph{ArrayListvertces=newArrayList();//存放图顶点信息的数组intvexnum;//图的当前顶点数intarcnum;//图的弧数publicALGraph(){//构造函数this.a

3、rcnum=0;this.vexnum=0;}}publicclassALGraphMain{ALGraphg=newALGraph();LinkQueueq=newLinkQueue();//广度优先搜索栈LinkStacklinkStack=newLinkStack();//拓扑排序顶点栈LinkStacklinkStackT=newLinkStack();//T为拓扑序列顶点栈LinkStacklinkStackS=newLinkStack();//S为零入度顶点栈ArrayListvisitedDFS=newArrayList();//深度优先

4、访问标志数组ArrayListvisitedBFS=newArrayList();//广度优先访问标志数组ArrayListindegree=newArrayList();//存放顶点入度的数组ArrayListindegreeCritical=newArrayList();//存放关键路径的顶点入度的数组ArrayListearly=newArrayList();//顶点最早开始时间数组ArrayListlast=newArr

5、ayList();//顶点最晚开始时间数组voidadd_vex(){//增加节点数System.out.println("输入无向图的顶点数");Scannerscanner=newScanner(System.in);g.vexnum=scanner.nextInt();System.out.println("输入顶点信息：");for(inti=0;i

6、p;ArcNodetemp;ArcNodetemp1;System.out.println("输入有向边数");Scannerscanner=newScanner(System.in);g.arcnum=scanner.nextInt();intv1;intv2;intlength;for(intk=0;k

7、v1=scanner.nextInt();v2=scanner.nextInt();length=scanner.nextInt();inti=LocateVex(v1);//查找i,j的位置intj=LocateVex(v2);intnum=(Integer)indegree.get(j)+1;indegree.set(j,num);//入度加1this.indegreeCritical.set(j,num);s=newArcNo