# Undirected Graph Class

Algorithms# Animated Undirected Graph

## Press "Restart" to draw a new random graph

## What is an Undirected Graph?

Undirected graphs are used to represent connections between points. A simple example would be a graph that represents your "Friends" on FaceBook. All your immediate FaceBook Friends are considered to be a "distance" of 1 link from you. Each one of your Friends has connections to all their Friends, so all their Friends are considered to have a "distance" of 2 links from you.

The above Graph Animation is presented to illustrated how complex the network of connections can be, even for such a small graph. A graph representing the whole FaceBook network of N total members would be huge. The number of all potential connections is 1 * 2 * 3 * ... * (N - 1), also called N factorial (more precisely, it is N - 1 factorial). This value increases with N even faster than exponential growth.

## You Can't Get There From Here?

One of the most common problems in graph theory is determining connectivity. Sometimes there is just no way to get from on node to another. For example, no matter how many levels of connections between successive FaceBook Friends you search, you could never find a connection to me: I don't belong to FaceBook because I think it is evil (just kidding, sort of).

The two most basic Algorithms used to efficiently determine connectivity between "vertices" (points) in a graph are called "Breadth First Search" and "Depth First Search". These algorithms will be illustrated in upcoming articles.

## A Friend of Mine is a Friend of Yours

There are several ways you can store the data representing a graph. The most simple way is to use 2 arrays: one to represent all the vertices, and another to represent all the connections. A connection is also called an "edge" of the graph, which is just the pair of the vertices that are connected.

To solve problems such as determining connectivity, it pays off to do some preprocessing on the graph data in "edge format" (an array of edges just described.) Instead of using a simple list of edges, we store the data for connectivity in terms of array from each vertex. Just like in FaceBook, each member (vertex) has a list (array) of people they are connected to. The lists are symmetric: all your Friends on are in your connection list, and you are in the connection list of each of your Friends.

This way of storing graph data is called "Adjacency" format, since for each vertex, you are storing an array of the the adjacent vertices. The Python code below contains several methods used to construct graphs in Adjacency format from various input files, as well as methods to print out the data. This code is a basic building block for all the graph algorithms to be described in future articles.