Todai Entrance Exam: Subject 2013 – Problem 3

(1)

Skip.

(2)

The adjacency matrix representation uses 36 memory units. The adjacency list representation uses 20 memory units. Therefore, the adjacency matrix representation uses more memory space than the list representation.

(3)

Let E be the set of edges. The adjacency matrix representation uses N^{2} memory units while the adjacency list representation uses 2|E| - N memory units. So when |E| = \frac{1}{2}(N^{2} + N), both representations require the same size of memory space.

How can we tell if a directed graph is weakly connected based on the number of edges?

(4)

Skip.

(5)

Traverse(Graph G)

  • foreach v \in V { v.setMark(UNVISITED) }
  • foreach v \in V {
    • if (v.getMark() == UNVISITED)
      • if DFS(G, v) == 1
        • break
  • }

DFS(Graph G, Vertex v)

  • v.setMark(VISITED)
  • foreach (v, w) \in E {
    • if (w.getMark() == UNVISITED)
      • if DFS(G, w) == 1
        • return 1
    • else
      • return 1
  • }
  • return 0

GetCycle(Graph G)

  • C = {}
  • foreach v \in V {
    • if (v.getMark() == VISITED)
      • C = C \cup \{ v \}
  • }
  • return C

And in the main program:

  • Traverse(G)
  • GetCycle(G)

Facebooktwittergoogle_plusredditpinterestlinkedinmail

Leave a Reply

Your email address will not be published. Required fields are marked *