I've been reading the 3rd edition of [Algorithms][1] by Cormen, Leiserson, Rivest and Stein. For DFS and BFS their algorithm loops through all the vertices first and colors them white.
1) If the color attribute were part of the node/vertex you would have to traverse the graph before you traverse the graph. And if you color every vertex white and your graph is cyclical then you would have an infinite loop.
clarification: CLRS' algorithm for DFS is
for each vertex u 'in' G.V
u.color = WHITE
u.Parent = NIL
time = 0
for each vertex u 'in' G.V
if u.color == WHITE
DFS-VISIT(G.u)
If the u.color is part of the node in the graph how do you actually do that loop? Do you have information on all the nodes stored elsewhere? And if you have an adjacency-list as a linked list with over a billion nodes wouldn't that take too long to iterate through the linked list every time you look for an adjacent vertex?
2) When I thought about storing attributes in an adjacency-matrix or adjacency-list I have a hard time contemplating what that data structure looks like. At least in C I can only make arrays so big. And if I use a linked list then I couldn't index into it. I would have to traverse a potentially huge list to get a vertex attribute. I'm having a hard time thinking of how Facebook would store 1 billion users or Google storing all the addresses for Maps.
3) As a follow up to the Facebook and Google thoughts, assuming that information is stored in a graph, I imagine they don't traverse the entire graph every time somebody searches for an address or person. For example if I enter my address and a destination for directions somehow I would think they find the address and get a pointer to the vertex in the graph that represents my address. From there they would do a BFS or something to calculate my address. They wouldn't start by traversing the whole world map to find my address.
*) I apologize if this isn't the correct way to ask my questions. Really these are just concepts I am having a hard time understanding. Hopefully I have communicated what I am confused by and can get some additional clarification. Thanks!
edit: In reading coding examples of DFS I notice people don't even implement the graph. They implement the adjacency-matrix or list and traverse that. In a tree I may have a struct with a "left" and "right" pointer to its children. While I always assumed the graph nodes would contain links to other nodes (edges) I suppose the nodes could be more simple (just contain the data) and the edges are ONLY stored in the adjacency-matrix or list. Is that a common way to implement graphs?