9.42 Let G be a directed graph with N vertices. A vertex s is called a sink if, for every v in V such that s = v, there is an edge (v, s), and there are no edges of the form (s, v). Give an O(N) algorithm to determine whether or not G has a sink, assuming that G is given by its N × N adjacency matrix. - | |
| View Solution | |
| << Back | Next >> |