18

What are graphs, in computer science, and what are they used for? In laymen's terms preferably.

I have read the definition on Wikipedia:

In computer science, a graph is an abstract data type that is meant to implement the graph and hypergraph concepts from mathematics.

A graph data structure consists of a finite (and possibly mutable) set of ordered pairs, called edges or arcs, of certain entities called nodes or vertices. As in mathematics, an edge (x,y) is said to point or go from x to y. The nodes may be part of the graph structure, or may be external entities represented by integer indices or references.

but I'm looking for a less formal, easier to understand definition.

Improve this question
4
  • Do you mean graphs the data structure?
    – System Down
    Commented Oct 9, 2012 at 0:26
  • 1
    Yes, sorry. Graphs as described here en.wikipedia.org/wiki/Graph_(abstract_data_type) , only I'm looking for a less formal, easier to understand definition.
    – ConditionRacer
    Commented Oct 9, 2012 at 0:28
  • @Justin984 Wikipedia links with parentheses (and there are so many of them) don't work, the parentheses don't play well with the Markdown format for links. Now, for future reference please add any clarifications to your question in the question itself, not in comments, they aren't that visible and it's easy to miss them. I'll edit your above comment in the question...
    – yannis
    Commented Oct 9, 2012 at 1:46
  • @Justin984 Also note that Computer Science Stack Exchange might be a bit more appropriate for questions like this one than Programmers. Don't get me wrong, the question is perfectly on topic here, and it got great answers, but it wouldn't hurt if you checked out a community that's a bit more focused on core computer science concepts than we are (don't post the same question in multiple sites though, if you happen to post it in the wrong site, we can move it to the right one automatically).
    – yannis
    Commented Oct 9, 2012 at 1:50

4 Answers 4

Reset to default
28

A perfect layman's example might be Facebook. The network of you, your friends, and their friends etc, are collectively refered to as the social graph.

In this "graph" the people are considered nodes of the graph and the edges are friendship links.

In Facebook friend is a bidirectional relationship (A is B's Friend => B is A's friend) so the graph is an Undirected Graph. A network like Google+ or Twitter would be considered a Directed Graph since the direction of the relationship has meaning here.

All of these graphs are refered to as cyclic graphs, as the relationships between nodes can form cycles. A Family Tree, on the other hand, is a special kind of graph which, among other things, is Acyclic since there cannot be cycles in family tree relatioship. (It is technically called a Directed Acyclic Graph (DAG) since its both directed and acyclic)

This should cover all of the basic jargon involving graphs, so now you should be able to follow the rest of the material in the field.

Improve this answer
8
  • 1
    Can't believe it didn't occur to me that it's called the facebook graph api. Good example!
    – ConditionRacer
    Commented Oct 9, 2012 at 1:32
  • 4
    Family tree not cyclic? It shouldn't be, but it unfortunately is...
    – Marjan Venema
    Commented Oct 9, 2012 at 6:03
  • 1
    @MarjanVenema, the family tree is cyclic? (It's a directed graph, so the direction is important in determining cycles, and presumably step relationships don't really count.)
    – huon
    Commented Oct 9, 2012 at 9:25
  • @dbaupp: I have no desire to go into details here, so I'll just mention one word: incest.
    – Marjan Venema
    Commented Oct 9, 2012 at 10:03
  • 5
    @MarjanVenema, you're missing my point. A cycle in a directed graph is a pattern like A -> B -> C -> A (i.e. a circle of arrows), incest just gives A -> B -> C and A -> D -> C (i.e. a diamond). A cycle in a family tree needs time travel.
    – huon
    Commented Oct 9, 2012 at 10:06
16

Graphs are one of the most important mathematical concepts used in computer science.

You've seen graphs many times over. Imagine that you are taking a plane flight from one city to another. You'll inevitably find a nice glossy magazine from the airline in the seat pocket in front of you. Near the back of that magazine you can almost always find a map that depicts the cities serviced by that airline represented as circles, with the flights that connect those cities represented as curved lines. That's a graph! The cities, represented as circles, are the nodes of this graph and the flights, represented as curved lines, are the edges. Graphs are just things with nodes and edges that connect nodes.

You can embellish those simple graphs in various ways. You don't want to see just a bunch of circles and lines when you're looking at that map. Those cities have names. Labeling those cities results in labeled graph. (You can also label the edges, e.g., flight 1234.) Computer science often associates data with the nodes, sometimes with the edges, but that's just an extension of the label. It's still a labeled graph. Another embellishment results if you can fly directly from city A to city B, but not from city B to city A. An obvious way to portray this is to put an arrow on the line that connects the cities to depict this one-way relationship. Now you have a directed graph.

Linked lists, trees, state transition diagrams, and lots of other computer science data structures are all examples of graphs. It is a very powerful concept.

Improve this answer
1
  • I'd actually extend that example to note that all entities described in your example could be depicted as vertices in a graph (city, plane, magazine, map, etc), the map itself just being a single vertex.
    – Demian Brecht
    Commented Oct 9, 2012 at 5:41
14

A better question would be "What aren't graphs used for?". Computer Science is, in many respects, the study of Graphs.

A graph, in laymen's terms, is a collection of arbitrary abstract objects called "nodes" or "vertices" that represent points of connection. They are then connected via "paths" or "edges". The abstract data type "Graph" is an implementation of the mathematical "Graph". So basically you have nodes and edges as your fields and various operations you can perform on them. You can, for instance, add a new node to the graph's collection (this could be a list or an array or some other structure depending on the language). You could then link that node to existing nodes. Operations would also be include traversing the graph, checking whether two nodes share an edge (are connected), retrieving values from nodes or edges, and the deletion of nodes or edges from the graph.

As far as utilization goes, Graphs are used all over the place. Networking makes particularly heavy use of them but they are found in Artificial Intelligence, Data Mining, Game Development, Geoinformatics, and a host of other disciplines. In formal Computer Science, they see even more use, namely as a way of representing state.

Effectively anything that you can represent as a set of connections can be represented as a graph and implemented via that ADT in some form.

Here's an example graphic I made:

Graph Example

Improve this answer
4

A graph is just a collection of objects connected together by lines called vertices.

The term "graph" is an abstraction and generalization of many data structures used in software development. Linked lists, binary trees and AST's are all graphs.

Basically, any collection of objects that has pointers that associate the objects with each other is a graph. Once you have a graph, you can apply the principles of graph theory to it, to solve certain problems.

Improve this answer

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.