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

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

2、jvex = adjvex;this.info = info;this.next = null;class VNode / 头结点int data; / 顶点信息（如数据等）ArcNode firstarc; / 指向第一条依附该顶点的边的弧指针public VNode(int data) / 构造函数this.data = data;this.firstarc = null;class ALGraph ArrayList vertces = new ArrayList(); / 存放图顶点信息的数组int vexnum;/ 图的当前顶点数int arcnum;/ 图的弧数public ALG

3、raph() / 构造函数this.arcnum = 0;this.vexnum = 0;public class ALGraphMain ALGraph g = new ALGraph();LinkQueue q = new LinkQueue(); / 广度优先搜索栈LinkStack linkStack = new LinkStack(); / 拓扑排序顶点栈LinkStack linkStackT = new LinkStack(); / T 为拓扑序列顶点栈LinkStack linkStackS = new LinkStack(); / S 为零入度顶点栈ArrayList vis

4、itedDFS = new ArrayList(); / 深度优先访问标志数组ArrayList visitedBFS = new ArrayList(); / 广度优先访问标志数组ArrayList indegree = new ArrayList(); / 存放顶点入度的数组ArrayList indegreeCritical = new ArrayList(); / 存放关键路径的顶点入度的数组ArrayList early = new ArrayList(); / 顶点最早开始时间数组ArrayList last = new ArrayList(); / 顶点最晚开始时间数组void

5、add_vex() / 增加节点数System.out.println(“输入无向图的顶点数“);Scanner scanner = new Scanner(System.in);g.vexnum = scanner.nextInt();System.out.println(“输入顶点信息：“);for (int i = 0; i = g.vexnum)return -1;return i;void CreatUDN() add_vex(); / 增加顶点数add_arc(); / 增加边数/* 思路：先输出当前顶点，如果下一条邻接顶点不为空，则输出 */void printAdjList()

6、 / 输出邻接表int i;ArcNode p;System.out.println(“编号t 顶点t 邻点编号“);for (i = 0; i = 0; w = NextAdjvex(this.g.vertces.get(v).data, this.g.vertces.get(w).data) if (this.visitedDFS.get(w) = false) DFS(w);/* 基本实现思想 （1）顶点 v 入队列。 （2）当队列非空时则继续执行，否则算法结束。 （3）出队列取得队头顶点 v；访问顶点 v 并标记顶点 v 已被访问。* （4）查找顶点 v 的第一个邻接顶点 w。 （5）

7、若 v 的邻接顶点 w 未被访问过的，则 w 入队列。* （6）继续查找顶点 v 的另一个新的邻接顶点 w，转到步骤（ 5） 。 直到顶点 v 的所有未被访问过的邻接点处理完。转到步骤（2） 。* 广度优先遍历图是以顶点 v 为起始点，由近至远，依次访问和 v 有路径相通而且路径长度为 1，2，的顶点。* 为了使“先被访问顶点的邻接点”先于“后被访问顶点的邻接点”被访问，需设置队列存储访问的顶点。* * 伪代码 （1）初始化队列 Q；visitedn=0； （2）访问顶点 v；visitedv=1 ；顶点v 入队列 Q； （3）* while（队列 Q 非空） v=队列 Q 的对头元素出队；

8、w=顶点 v 的第一个邻接点； while（w 存在） 如果 w 未访问，则访问顶点 w；* visitedw=1； 顶点 w 入队列 Q； w=顶点 v 的下一个邻接点。*/private void BFS() / 广度优先搜索int u;for (int i = 0; i = 0; w = NextAdjvex(this.g.vertces.get(u).data,this.g.vertces.get(w).data)if (this.visitedBFS.get(w) = false) / 如果 w 顶点未被访问，则w 顶点入队列this.visitedBFS.set(w, true);

9、System.out.print(g.vertces.get(w).data + “ “);q.EnQueue(w); / w 顶点入队列private void FindInDegree() / 输出入度数for (int i = 0; i this.early.get(k) / 求最早发生时间this.early.set(k, this.early.get(j) + p.info);if (count g.vexnum) / 如果入栈顶点数小于图的顶点数，则图中有环路return false; else return true;private void CriticalPath() / 关

10、键路径ArcNode p;int k;int ee; / 每条弧的最早开始时间int el; / 每条弧的最晚开始时间if (!TopologicalOrder() System.out.println(“图中有环路“);for (int i = 0; i g.vexnum; i+) /初始化最晚开始时间this.last.add(this.early.get(g.vexnum - 1);System.out.print(“输出最早开始时间:“);for (int i = 0; i g.vexnum; i+) System.out.print(early.get(i) + “ “);Syste

11、m.out.println();while (!linkStackT.IsEmpty() / 出栈求最晚开始时间int j = linkStackT.Pop();for (p = g.vertces.get(j).firstarc; p != null; p = p.next) k = p.adjvex;if (last.get(k) - p.info last.get(j) / 活动最晚开始时间last.set(j, last.get(k) - p.info); / for/ whileSystem.out.print(“输出最晚开始时间:“);for (int i = 0; i g.vex

12、num; i+) System.out.print(last.get(i) + “ “);System.out.println();for (int i = 0; i g.vexnum; i+) / 求 ee 和 el 以及关键路径for (p = g.vertces.get(i).firstarc; p != null; p = p.next) k = p.adjvex;ee = early.get(i);el = last.get(k) - p.info;if (ee = el) / 若某条弧满足条件 ee=el，则为关键活动。System.out.println(g.vertces.ge

13、t(i).data + “到“+ g.vertces.get(k).data + “长度为:“ + p.info+ “ 发生时间为:“ + ee);/ forpublic static void main(String args) ALGraphMain agp = new ALGraphMain();agp.CreatUDN();agp.printAdjList();System.out.print(“图的深度优先遍历为：“);agp.DFSTraverse();System.out.println();System.out.print(“图的广度优先遍历为：“);agp.BFS();System.out.println();System.out.print(“各顶点入度为：“);agp.FindInDegree();System.out.println();System.out.print(“图的拓扑排序为：“);agp.TopologicalSort();System.out.println();System.out.println(“图的关键路径为：“);agp.CriticalPath();System.out.println();