Graphs worth learning?

    This site uses cookies. By continuing to browse this site, you are agreeing to our Cookie Policy.

    • Graphs worth learning?

      Hey guys,

      I'm still re-implementing the STL containers to make sure I don't have an interview fail on data structures again.

      I've finished all of the containers, but my data structures book ("Data Structures and Algorithms" by Drozdek) has a full chapter on Graphs. I don't see anything equivalent in the STL, and all I remember from my old discrete mathematics class was Euler paths. I didn't immediately see why these would be useful and I've never used them in my previous experience.

      So, is there any point in learning graphs? Have you guys ever used them for anything?
    • My experience has been that graphs tend to be a more obscure data structure. That's not the best way to phrase it, but I can't think of a better wording. What I mean is that most types of data structures (trees, lists, arrays, etc) are used all over the place. In my experience, graphs have VERY specific uses, and their uses tend to be a bit obscure.

      For example, in my physics engine, I use a constraint graph to connect objects together. Each physics body has a list of edges which point to other bodies and what type of constraint they're connected with. What does this allow me to do? Object islanding and sleeping. I can do a depth first search from a given body to find all the other bodies it is directly or indirectly connected to. This forms an "island" which is separate from other physics islands. I can solve the islands independently or put them to sleep if they're not moving around much. This is somewhat of an obscure use for graphs, but a very important one if you're making a 3D physics engine.

      On the flip side of my statement, AI programming uses a ton of graphs. I don't do much AI programming, so my perspective might be different if I did. When I write AI, it is typically just simple state machines, which I could implement as graphs. I don't do this simply because my AIs are really simple.

      Are graphs important for interviews? No idea, probably depends who you're interviewing with. I assume you'd be asked about graphs if it were an AI interview.

      Are graphs important as a data structure? I would say absolutely.