Consider the basic non-recursive DFS algorithm on a graph G=(V,E) (python-like pseudocode below) that uses array-based adjacency lists, a couple of arrays of size V, and a dynamic array stack of size <= V. If I understand correctly, this is a cache oblivious algorithm since no information about the memory configuration is provided. Moreover, even if we suppose that every memory access in this algorithm produces a cache miss (the number of cache misses per line is given in comments), we would still have O(V+E) memory transfers, so I postulate this would be a worst case complexity upper bound under the CO-model. Is this correct?
def dfs(G, s): visited = [False for v in G] # V stack = [s] # 1 nxt = [0 for v in G] # V degree = [len(v) for v in G] # V + E while stack: v = stack.pop(-1) # 1 visited[v] = True # 1 while nxt[v] < degree[v] and visited[G[v][nxt[v]]]: # 6 nxt[v]+=1 # 1 if nxt[v] < lens[v]: # 2 stack.append(v) # 1 stack.append(G[v][nxt[v]]) # 3 def main(): # e.g. dfs order of this graph is 0 1 2 3 # # 0 -> 2 # | \ ^ # | \ | # v v # 3 -> 1 # G = [[1,3,2],,,] dfs(G, 0)