个有向图采用邻接表存储结构,边结点类定义如下: public class Edge{ public int adj; //邻接点在顶点表中的下标 public Edge next; 74133220935 顶点结点类定义如下: public class Vex{ public Object data; public Edge first; 22093 3322093 图的类定义为: public class Graph ( private Vex vex; //顶点表 private int vn; //顶点个数 注:初始化空栈用new Stack0, 顶点序号v入栈用stack中的push(√方法,出栈Stack中的pop0方 法,返回值为出栈的顶点序号,判|断栈是否为空用Stack中的isEmp ty0方法。 用Java编写拓扑排序函数booleaan topoSort(Object] a)如下5,其中排序结果(顶点的data域的 值)写入a数组,函数返回值为true表示成功,为false表示存在环
时间: 2023-11-27 15:55:05 浏览: 76
有向图的邻接表表示(c/c ++语言)
4星 · 用户满意度95%
以下是用Java编写的拓扑排序函数:
```
public boolean topoSort(Object[] a) {
int[] inDegree = new int[vn]; // 存储每个顶点的入度
Stack<Integer> stack = new Stack<>(); // 存储入度为0的顶点的序号
// 统计每个顶点的入度
for (int i = 0; i < vn; i++) {
Edge edge = vex[i].first;
while (edge != null) {
inDegree[edge.adj]++;
edge = edge.next;
}
}
// 将入度为0的顶点入栈
for (int i = 0; i < vn; i++) {
if (inDegree[i] == 0) {
stack.push(i);
}
}
int index = 0; // a数组的下标
while (!stack.isEmpty()) {
int v = stack.pop(); // 取出入度为0的顶点
a[index++] = vex[v].data; // 将该顶点的data域的值存入a数组中
// 将与该顶点相邻的顶点的入度减1,并将入度变为0的顶点入栈
Edge edge = vex[v].first;
while (edge != null) {
int adj = edge.adj;
inDegree[adj]--;
if (inDegree[adj] == 0) {
stack.push(adj);
}
edge = edge.next;
}
}
// 判断是否存在环
if (index != vn) {
return false;
} else {
return true;
}
}
```
首先,初始化一个数组inDegree,存储每个顶点的入度。然后,遍历整个邻接表,统计每个顶点的入度。接着,将入度为0的顶点的序号入栈。循环中,每次取出入度为0的顶点,将该顶点的data域的值存入a数组中,并将与该顶点相邻的顶点的入度减1,若有顶点的入度变为0,将其入栈。最后,判断a数组中的元素个数是否等于顶点个数vn,若相等,则拓扑排序成功,返回true,否则,存在环,返回false。
阅读全文