package curriculumProject;//非连通图的深度优先搜索遍历和广度优先搜索遍历import linearList.Queue.SeqQueue; //顺序循环队列类public abstract class AbstractGraph<E> implements GGraph<E>//抽象图类{public abstract int vertexCount(); //返回顶点数，方法由子类实现public abstract E get(int i); //返回顶点vi的数据域public abstract int getFirstNeighbor(int i); //返回顶点vi的第一个邻接顶点的序号public abstract int getNextNeighbor(int i, int j); //返回vi在vj 后的下一个邻接顶点的序号// public abstract AbstractGraph prim();public void DFSTraverse(int v) //从顶点v出发对非连通图的一次深度优先搜索遍历{boolean[] visited = new boolean[vertexCount()]; //访问标记数组，元素初值为false，表示未被访问int i=v;do{if (!visited[i]) //若顶点vi未被访问{System.out.print("{ ");depthfs(i, visited); //从顶点vi出发的一次深度优先搜索遍历System.out.print("} ");}i = (i+1) % vertexCount(); //在其他连通分量中寻找未被访问顶点} while (i!=v);System.out.println();}private void depthfs(int v, boolean[] visited) //从顶点v开始发的一次深度优先搜索遍历{ //遍历一个连通分量System.out.print(this.get(v)+" "); //访问该顶点visited[v] = true; //置已访问标记int w = getFirstNeighbor(v); //获得第一个邻接顶点while (w!=-1) //若存在邻接顶点{if(!visited[w]) //若邻接顶点w未被访问depthfs(w, visited); //从w出发的深度优先搜索遍历，递归调用w = getNextNeighbor(v, w); //返回v在w后的下一个邻接顶点的序号}}public void BFSTraverse(int v) //从顶点v出发对非连通图进行一次广度优先搜索遍历{boolean[] visited = new boolean[vertexCount()]; //访问标记数组int i=v;do{if (!visited[i]) //若顶点vi未被访问{System.out.print("{ ");breadthfs(i, visited); //从顶点vi出发的广度优先搜索遍历System.out.print("} ");}i = (i+1) % vertexCount(); //在其他连通分量中寻找未被访问顶点} while (i!=v);System.out.println();}private void breadthfs(int v, boolean[] visited) //从顶点v出发的广度优先搜索遍历{ //遍历一个连通分量System.out.print(this.get(v)+" ");visited[v] = true;SeqQueue<Integer> que = new SeqQueue<Integer>(vertexCount()); //创建顺序队列que.enqueue(new Integer(v)); //访问过的顶点v的序号入队while (!que.isEmpty()) //当队列不空时循环{v = que.dequeue().intValue(); //出队int w = getFirstNeighbor(v); //获得顶点v的第一个邻接顶点序号while (w!=-1) //当邻接顶点存在时循环{if (!visited[w]) //若该顶点未访问过{System.out.print(this.get(w)+" "); //访问顶点visited[w] = true;que.enqueue(new Integer(w)); //访问过的顶点w的序号入队}w = getNextNeighbor(v, w); //返回v在w后的下一个邻接顶点的序号}}}}package curriculumProject;//图的邻接表import dataStructure.linearList.SeqList; //顺序表类import linearList.linkedList.SortedHSLinkedList; //排序的带头结点的单链表类//public class AdjListGraph<E> implements GGraph<E> //邻接表表示的图类public class AdjListGraph<E> extends AbstractGraph<E> implements GGraph<E> //邻接表表示的图类{protected SeqList<Vertex<E>> vertexlist; //顶点表public AdjListGraph(int n) //构造方法，n指定顶点数{this.vertexlist = new SeqList<Vertex<E>>(n);}public AdjListGraph(E[] vertices, Edge[] edges) //以顶点集合和边集合构造一个图{this(vertices.length);for (int i=0; i<vertices.length; i++)insertVertex(vertices[i]); //插入一个顶点for (int j=0; j<edges.length; j++)insertEdge(edges[j]); //插入一条边}public int vertexCount() //返回顶点数{return this.vertexlist.length();}public E get(int i) //返回顶点vi的数据元素{return this.vertexlist.get(i).data;}public boolean insertVertex(E vertex) //插入一个顶点，若插入成功，返回true{return this.vertexlist.add(new Vertex<E>(vertex)); //在顺序表最后插入一个元素}public boolean insertEdge(int i, int j) //插入一条权值为weight 的边〈vi,vj〉{if (i>=0 && i<vertexCount() && j>=0 && j<vertexCount() && i!=j){//SortedHSLinkedList<Edge> slink = new SortedHSLinkedList<Edge>();SortedHSLinkedList slink = this.vertexlist.get(i).adjlink;// slink = this.vertexlist.get(i).adjlink;// System.out.println(this.vertexlist.get(i));return slink.add(new Edge(i,j));//在第i条单链表最后增加边结点}return false;}public boolean insertEdge(Edge edge) //插入一条边{if (edge!=null)return insertEdge(edge.start, edge.dest);return false;}public String toString() //获得图的顶点集合和邻接表{String str= "顶点集合："+vertexlist.toString()+"\n";str += "出边表：\n "; //+edgeCount+"条边\n";for (int i=0; i<vertexCount(); i++)str += this.vertexlist.get(i).adjlink.toString()+"\n"; //遍历第i条单链表return str;}public boolean removeEdge(int i, int j) //删除边〈vi,vj〉，i、j指定顶点序号{if (i>=0 && i<vertexCount() && j>=0 && j<vertexCount() && i!=j){SortedHSLinkedList slink = this.vertexlist.get(i).adjlink; //获得第i条边单链表return slink.remove(new Edge(i,j));}return false;}public boolean removeVertex(int v) //删除序号为v的顶点及其关联的边{ //若删除成功，返回trueint n=vertexCount(); //删除之前的顶点数if (v>=0 && v<n){SortedHSLinkedList<Edge> slink =this.vertexlist.get(v).adjlink; //获得欲删除的第v条边单链表int i=0;Edge edge = slink.get(i);while (edge!=null){this.removeEdge(edge.dest, edge.start); //删除对称的边i++;edge = slink.get(i);}this.vertexlist.remove(v); //删除顺序表的第i个元素，顶点数已减一for (i=0; i<n-1; i++) //未删除的边结点更改某些顶点序号{slink = this.vertexlist.get(i).adjlink; //获得第i条边单链表int j=0;edge = slink.get(j);while (edge!=null){if (edge.start>v)edge.start--; //顶点序号减一if (edge.dest>v)edge.dest--;j++;edge = slink.get(j);}}return true;}return false;}public int getFirstNeighbor(int v) //返回顶点v的第一个邻接顶点的序号{ //若不存在第一个邻接顶点，则返回-1return getNextNeighbor(v, -1);}public int getNextNeighbor(int v, int w) //返回v在w后的下一个邻接顶点的序号{ //若不存在下一个邻接顶点，则返回-1if (v>=0 && v<vertexCount() && w>=-1 && w<vertexCount()){SortedHSLinkedList<Edge> slink = this.vertexlist.get(v).adjlink; //获得第v条边单链表Edge edge = slink.get(0); //返回单链表的第一个结点表示的边int i=0;while (edge!=null) //寻找下一个邻接顶点{if (edge.dest>w)return edge.dest; //返回下一个邻接顶点的序号i++;edge = slink.get(i); //返回单链表的第一个结点表示的边}}return -1;}}package curriculumProject;//带权图的边类public class Edge implements Comparable<Edge> //带权值的边类{public int start; //边的起点序号public int dest; //边的终点序号//public int weight; //边的权值public Edge(int start, int dest){this.start = start;this.dest = dest;//this.weight = weight;}public String toString(){return "("+start+","+dest+")";}public int compareTo(Edge e) //约定两条边比较大小的规则{if (this.start!=e.start)return this.start - e.start;elsereturn this.dest - e.dest;}}package curriculumProject;//图接口public interface GGraph<E> //图接口{int vertexCount(); //返回顶点数E get(int i); //返回顶点vi的数据元素boolean insertVertex(E vertex); //插入一个顶点boolean insertEdge(int i, int j); //插入一条权值为weight的边〈vi,vj〉boolean removeVertex(int v); //删除序号为v的顶点及其关联的边boolean removeEdge(int i, int j); //删除边〈vi,vj〉int getFirstNeighbor(int v); //返回顶点v 的第一个邻接顶点的序号int getNextNeighbor(int v, int w); //返回v在w 后的下一个邻接顶点的序号}package curriculumProject;import java.util.*;import linearList.Queue.SeqQueue;;public class Graph_Main2 {/*** @param args*/int bian;// 定义边数HashSet array = new HashSet();// 定义一个集合保存顶点的值ArrayList list2 = new ArrayList();// 保存优先关系顶点的值ArrayList listrudu = new ArrayList();// 保存顶点的入度ArrayList result = new ArrayList();// 保存拓扑排序的结果ArrayList credit2 = new ArrayList();// 保存学分信息ArrayList credit3 = new ArrayList();// 保存学分信息int[][] relation;// 保存输入优先关系的所有值int[][] c_relation;Scanner scanner = new Scanner(System.in);public void input() {System.out.println("请输入课程总数,按回车确认");Scanner reader=new Scanner(System.in);int Input=reader.nextInt();System.out.println("请依次输入各个课程的学分:");int[] credit = new int[Input];for(int i = 0; i < Input; i++){credit[i] = reader.nextInt();credit2.add(credit[i]);}String[] vertices = new String[Input];for (int n = 0; n < Input; n++) {if (n < 9) {vertices[n] = "C0" + (n + 1);} else {vertices[n] = "C" + (n + 1);}}Scanner reader2=new Scanner(System.in);System.out.println("请输入课程之间的关系总和，即有多少条边？,按回车确认");bian = reader2.nextInt();relation = new int[bian][2];List<Edge> list = new ArrayList<Edge>();System.out.println("比如：C01是C02的先修课，则输入01 02");for (int i = 0; i < bian; i++) {System.out.print("请输入第" + (i + 1) + "条边的优先关系");for (int j = 0; j < 2; j++) {relation[i][j] = reader.nextInt();}list.add(new Edge(relation[i][0],relation[i][1]));}Edge[] edges = list.toArray(new Edge[0]);AdjListGraph<String> graph = new AdjListGraph<String>(vertices,edges);System.out.println("带权有向图，"+graph.toString());System.out.println("深度优先搜索遍历");for(int i=0;i<graph.vertexCount();i++){graph.DFSTraverse(i);}System.out.println("广度优先搜索遍历");for(int i=0;i<graph.vertexCount();i++){graph.BFSTraverse(i);}}public void sort() {for (int i = 0; i < bian; i++) {for (int j = 0; j < 2; j++) {array.add(relation[i][j]);}}Iterator iter = array.iterator();while (iter.hasNext()) {Object s = iter.next();list2.add(s);// 将各顶点的值保存在list里，方便后面查找入度时使用}int count = 0;// 定义一个记入度的计数器for (int i = 0; i < list2.size(); i++) {for (int j = 0; j < bian; j++) {if (list2.get(i).equals(relation[j][1])) {count++;}}listrudu.add(list2.get(i));listrudu.add(count);count = 0;}System.out.println();boolean flag = true;while (flag) {int check = 0;// 检查有没有入度为0for (int i = 0; i < listrudu.size(); i = i + 2) {if (listrudu.get((i + 1)).equals(0)) {result.add(listrudu.get(i));// for(int j=0;j<result.size();j++){// credit3.add(credit2.get(j)); // }//credit3.add(credit2.get(i));for (int j = 0; j < list2.size(); j++) {if (listrudu.get(i).equals(list2.get(j))) {for (int j2 = 0; j2 < bian; j2++) {if (list2.get(j).equals(relation[j2][0])) {relation[j2][1] = -9999;// 如果这个前驱是要被删除的话，那么把他的后继改值}}list2.remove(j);}}} else {check++;}}if (check == listrudu.size()/2) {System.out.println("课程关系输入错误，有环,无法排序");flag = false;}int count1 = 0;// 定义一个记入度的计数器for (int i = 0; i < list2.size(); i++) {for (int j = 0; j < bian; j++) {if (list2.get(i).equals(relation[j][1])) {count1++;}}listrudu.add(list2.get(i));listrudu.add(count1);count1 = 0;}if (list2.size() == 0) {System.out.println("存在拓扑排序");flag = false;}}// while循环结束}public void print() {* 这个for循环的作用是：因为我上面做的是根据listrudu来找的，* 所以它每进行一次循环就把前面的入度为0的值再保存了一遍，其实最后的结果是最后一次循环所得的值，打印的时候要把前面重复的去掉*/for (int i = result.size() - 1; i >= 0; i--) {for (int j = 0; j < i; j++) {if (result.get(j).equals(result.get(i))) {result.remove(j);}}}for (int i = 0; i < result.size(); i++) {System.out.print(result.get(i) + "-->");}System.out.println();System.out.println();System.out.println("请输入你的总学期数");Scanner reader3=new Scanner(System.in);int term = reader3.nextInt();System.out.println("请输入学期学分上线");int sum_credit = reader3.nextInt();System.out.println("如果要使课程均匀分布在各个学期，则为：");int sum=0;int sum2=0;for (int i = 0; i < result.size(); i++) {for(int j=0;j<result.size();j=j+2){Object res2 = result.get(j);Integer r2 = Integer.parseInt(res2.toString());Object obj = credit2.get(r2-1);Integer a = Integer.parseInt(obj.toString());sum += a;j=j+2;break;}double value = (double)credit2.size()/(double)term;int value2=0;if(value<=1.0)value=1.0;if((int)value==value)value2=(int)value;elsevalue2 = (int)value+1;if((i+1)%(value2)==0){System.out.print(result.get(i) + "-->");System.out.println();}else{if(sum<=sum_credit){for(int j3=0;j3<result.size();j3=j3+2){Object res = result.get(j3);Integer r = Integer.parseInt(res.toString());Object obj2 = credit2.get(r-1);Integer a2 = Integer.parseInt(obj2.toString());sum += a2;break;}if(sum<=sum_credit)System.out.print(result.get(i) + "-->");//System.out.print(result.get(i) + "-->");else{sum = 0;System.out.print(result.get(i) + "-->");}}else{System.out.println();sum = 0;System.out.print(result.get(i) + "-->");}}}System.out.println();System.out.println();System.out.println("如果要使课程分布在前几个学期，则为：");int j_=0;int j=0;for (int i = 0; i < result.size(); i++) {//for(int j=0;j<result.size();j=j+2){Object res4 = result.get(j);Integer r4 = Integer.parseInt(res4.toString());Object obj4 = credit2.get(r4-1);Integer a4 = Integer.parseInt(obj4.toString());sum += a4;j=j+1;//break;//}if(sum<=sum_credit){//for(int j=0;j<result.size();j=j+2){Object res3 = result.get(j_);Integer r3 = Integer.parseInt(res3.toString());Object obj3 = credit2.get(r3-1);Integer a3 = Integer.parseInt(obj3.toString());sum += a3;j_=j_+1;if(sum<=sum_credit)System.out.print(result.get(i) + "-->"); // if(sum<=sum_credit&&)// System.out.print(result.get(i) + "-->");else{sum = 0;System.out.print(result.get(i) + "-->");}}else{System.out.print(result.get(i) + "-->");System.out.println();sum = 0;}// if(sum<=sum_credit){// System.out.print(result.get(i) + "-->"); // }else{// System.out.println();// sum = 0;// System.out.print(result.get(i) + "-->"); // }}}public static void main(String[] args) {// TODO Auto-generated method stubGraph_Main2 s = new Graph_Main2();s.input();s.sort();s.print();}}package curriculumProject;import linearList.linkedList.SortedHSLinkedList; //排序的带头结点的单链表类public class Vertex<E> //顶点表{public E data; //顶点数据域public SortedHSLinkedList<Edge> adjlink; //该顶点的边单链表public Vertex(E data, SortedHSLinkedList<Edge> adjlink){this.data = data;this.adjlink = adjlink;}public Vertex(E data){this(data, new SortedHSLinkedList<Edge>()); //构造结点时创建空单链表}public String toString(){return this.data.toString();}。