一个数据结构（java版）问题?分别对以邻接矩阵和邻接表存储的有向图,实现下列操作（1）求图中的边数（2）求各顶点的入度和出度（3）判断任意两个顶点之间是否存在一条路径,若有给出

Question

一个数据结构（java版）问题?
分别对以邻接矩阵和邻接表存储的有向图,实现下列操作
（1）求图中的边数
（2）求各顶点的入度和出度
（3） 判断任意两个顶点之间是否存在一条路径,若有给出路径长度

Answer 1

我这个写的很简单,对于G=(V,E),各个顶点是以从1~V的连续数字来表示的,存数邻接表采用的是一个2维数组：
import java.util.*;
public class test {
public static void main(String [] args) {
// 以邻接表数组初始化有向图
digraph dg = new digraph(
new int[]{1,2,3},
new int[]{2,3},
new int[]{3,4},
new int[]{4,2,5},
new int[]{5,2}
);
dg.adjListPresent();
dg.adjMatrixPresent();
System.out.println("Edges: " + dg.getEdges());
System.out.print("In-Degree:\t");
for(int t : dg.getAdjHeads()) // 输出每个顶点的入度
System.out.print(t + "=" + dg.getInDegree(t) + " ");
System.out.println();
System.out.print("Out-Degree:\t");
for(int t : dg.getAdjHeads()) // 输出每个顶点的出度
System.out.print(t + "=" + dg.getOutDegree(t) + " ");
System.out.println();
dg.searchPath(1, 5);
}
}
// 有向图类
class digraph {
int [][] g;
int edges;
int heads;
public digraph(int[]...a){
int i = 0;
edges = 0;
heads = a.length;
g = new int[heads][];
for(int[] e : a) {
g[i++] = e;
edges += e.length - 1;
}
}
// 邻接表
public void adjListPresent() {
System.out.println("AdjList:");
for(int e[] : g) {
for(int i = 0; i < e.length; ++i)
System.out.print(e[i]+(i == e.length-1 ? "" : "->"));
System.out.println();
}
}