java - 构建图形数组

Question

我正在尝试实现一个有向图。我能够让我的大部分方法正常工作，但停留在 inEdge 和 outEdge 方法上。我知道这两种方法如何工作以及我应该返回什么数据，但问题是这些方法要求返回一个数组。所以，问题是我无法理解如何构建图形数组。基本上 outEdge 方法的答案是“return list[a];”但它不起作用，因为需要数组。我尝试制作一个数组，但它导致了一些问题，希望有人可以提供帮助。

public class Graph {

/** Constructs a graph with the given number of nodes, and no 
 * edges.
 * 
 * @param nodes Number of nodes in the graph
 */
Graph(int nodes) {

   this.nodes = nodes;
   this.edges = 0;
   list = new LinkedList[nodes];

for (int i = 0; i < nodes; i++){
    list[i] = new LinkedList<>();
}
}

/** Returns an array of all the nodes adjacent to a.
 * A node b is adjacent to a if there is an edge a → b in the graph.
 * If a is not a valid node, should return an empty array.
 * 
 * Complexity: O(E) (but you can do better)
 * @param a Source node
 * @return  Array of all nodes adjacent to a
 */
int[] outEdges(int a) {

    int[] tempresult = new int[nodes];
    int outs = 0;


    for (int i =0;i< nodes;i++){
        list[a].contains()= tempresult[outs];
        outs++;
    }

    int[] result = new int[outs];

    for (int i = 0 ;i<outs;i++){
        tempresult[outs] = result[i]; 
    }
    return result;
}

/** Returns an array of all the nodes that b is adjacent to.
 * b is adjacent to some node a if there exists an edge a → b.
 * If b is not a valid node, should return an empty array.
 * 
 * Complexity: O(N + E)
 * @param b Destination node
 * @return  Array of all nodes that b is adjacent to.
 */
int[] inEdges(int b) {

   LinkedList<Integer> edges = new LinkedList<>();
   for (int j = 0; j < n; j++)
   if (list[j].contains(b)) edges.add(j);
   return edges;
    }

////////////测试文件

  static AdjListGraph g_line;       // 9 edges, straight line
  static AdjListGraph g_cycle;      // 10 edges, cycle
  static AdjListGraph g_complete;   // Complete graph with 10 nodes
  static AdjListGraph g_discrete;   // Graph with 10 nodes, no edges
  static AdjListGraph g_example;    // The example graph I always use

public AdjListGraphTest() {
}

@BeforeClass
public static void setUpClass() {
    g_line = new AdjListGraph(10);
    g_cycle = new AdjListGraph(10);
    g_complete = new AdjListGraph(10);
    g_discrete = new AdjListGraph(10);
    g_example = new AdjListGraph(10);

    for(int i = 0; i < 9; ++i) {
        g_line.addEdge(i, i+1);
        g_cycle.addEdge(i, i+1);
    }
    g_cycle.addEdge(9, 0);

    for(int a = 0; a < 10; ++a)
        for(int b = 0; b < 10; ++b)
            g_complete.addEdge(a, b);

    // No edges in g_discrete

    g_example.addEdge(0,2);
    g_example.addEdge(2,1);
    g_example.addEdge(1,0);
    g_example.addEdge(3,1);
    g_example.addEdge(3,2);
    g_example.addEdge(3,4);
    g_example.addEdge(4,5);
    g_example.addEdge(4,7);
    g_example.addEdge(5,6);
    g_example.addEdge(6,5);
    g_example.addEdge(7,3);
    g_example.addEdge(8,7);
    g_example.addEdge(8,9);
    g_example.addEdge(9,7);
}
 /**
 * Test of outEdges method, of class Graph.
 */
@Test
public void testOutEdges() {
    System.out.println("outEdges");

    for(int i = 0; i < 9; ++i) {
        int[] es = g_line.outEdges(i);
        assertEquals(es.length, 1);
        assertEquals(es[0], i+1);

        es = g_cycle.outEdges(i);
        assertEquals(es.length, 1);
        assertEquals(es[0], i + 1);            
    }

    assertEquals(g_line.outEdges(9).length, 0);
    assertEquals(g_cycle.outEdges(9).length, 1);
    assertEquals(g_cycle.outEdges(9)[0], 0);

    for(int a = 0; a < 10; ++a) {
        int[] es = g_complete.outEdges(a);
        assertEquals(es.length, 9);

        assertEquals(g_discrete.outEdges(a).length, 0);

        for(int b = 0; b < 10; ++b) {
            if(a != b)
                assertTrue(Arrays.binarySearch(es, b) >= 0);
            else if (a == b) {
                assertFalse(Arrays.binarySearch(g_example.outEdges(a), b) >= 0);
            }
        }
    }

    for(int a = 0; a < 10; ++a)
        for(int b = 0; b < 10; ++b) {
            if(a != b && g_example.adjacent(a, b))
                assertTrue(Arrays.binarySearch(g_example.outEdges(a), b) >= 0);
            else if(a == b)
                assertFalse(Arrays.binarySearch(g_example.outEdges(a), b) >= 0);
        }                
}

/**
 * Test of inEdges method, of class Graph.
 */
@Test
public void testInEdges() {
    System.out.println("inEdges");

    for (int i = 1; i < 10; ++i) {
        int[] es = g_line.inEdges(i);
        assertEquals("only one in-edge to " + i, es.length, 1);
        assertEquals("in-edge to " + i + " comes from " + es[0] + ", should come from " + (i-1) + ";", 
                i - 1, es[0]);

        es = g_cycle.inEdges(i);
        assertEquals(es.length, 1);
        assertEquals(es[0], i - 1);
    }

    assertEquals(g_line.inEdges(0).length, 0);
    assertEquals(g_cycle.inEdges(0).length, 1);
    assertEquals(g_cycle.inEdges(0)[0], 9);

    for (int a = 0; a < 10; ++a) {
        int[] es = g_complete.inEdges(a);
        assertEquals(es.length, 9);

        assertEquals(g_discrete.inEdges(a).length, 0);

        for (int b = 0; b < 10; ++b) {
            if (a != b) {
                assertTrue(Arrays.binarySearch(es, b) >= 0);
            } else if (a == b) {
                assertFalse(Arrays.binarySearch(g_example.inEdges(a), b) >= 0);
            }
        }
    }

    for (int a = 0; a < 10; ++a) {
        for (int b = 0; b < 10; ++b) {
            if (a != b && g_example.adjacent(a, b)) {
                assertTrue(Arrays.binarySearch(g_example.inEdges(b), a) >= 0);
            } else if (a == b) {
                assertFalse(Arrays.binarySearch(g_example.inEdges(b), a) >= 0);
            }
        }
    }
}

在 inEdge 方法中，我刚刚编写了在普通 linkedList 中执行的代码。当我理解了如何构建图数组后，方法的实现就会很容易。

Answer 1

假设 i 的值是图表中的节点
从您的方法outEdges:
修改此:

 for (int i =0;i< nodes;i++){
            list[a].contains()= tempresult[outs];
            outs++;
        }

至

 List<Integer> resultList = new ArrayList<>();

    for (int i = 0; i < nodes; i++){   
              //a is input node 
            if(list.get(a).contains(i))
                resultList.add(i);
        }
    //returns int[]
    return resultList.stream().mapToInt(e -> e).toArray();

希望这有帮助。