Final answer:
To find a vertex with in-degree 0 in an adjacency matrix, check each column for all zeros, with an O(n^2) running time. For an adjacency list, count appearances across lists and find any vertex not present; this takes O(n + m) time.
Step-by-step explanation:
Finding a Vertex with In-degree 0 in an Adjacency Matrix
To find a vertex with an in-degree of 0 in a directed graph represented by an adjacency matrix, you must examine each column to check if the column has all zeros, which would indicate no incoming edges. Here is a pseudo-code algorithm for this purpose:
function findVertexWithZeroInDegree(adjMatrix):
for j in range(0, n):
zeroInDegree = true
for i in range(0, n):
if adjMatrix[i][j] != 0:
zeroInDegree = false
break
if zeroInDegree:
return j
return -1
The asymptotic running time of this algorithm is O(n^2), as it involves checking all n rows of each of the n columns.
Finding a Vertex with In-degree 0 in an Adjacency List
When the graph is represented as an adjacency list, you need to count the number of times each vertex appears across all lists to find the in-degree. For a vertex to have in-degree 0, it must not appear in any list. Here is the pseudo-code:
function findVertexWithZeroInDegree(adjList):
inDegree = [0] * n
for each list in adjList:
for vertex in list:
inDegree[vertex] += 1
for i in range(0, n):
if inDegree[i] == 0:
return i
return -1
The asymptotic running time for this algorithm is O(n + m), because you traverse each edge exactly once to build the in-degree array, and then traverse the in-degree array of size n.