A graph is a collection of nodes called vertices, and the connections between them, called edges.
is yet another data structure that you can use to store information. Unlike trees
, which have a strict hierarchical
structure, graphs are more flexible.
Topics covered in this snack-sized chapter:
A graph can be implemented by linked list or array.
When the edges in a graph have a direction, the graph is called a directed graph or digraph, and the edges are called directed edges or arcs.
The number of edges with one endpoint on a given vertex is called that vertex's degree.
In a directed graph, the number of edges that point to a given vertex is called its in-degree, and the number that point from it is called it’s out-degree.
Often, we may want to be able to distinguish between different nodes and edges.
An undirected graph can easily be implemented as a directed graph by adding edges between connected vertices in both directions.
In a directed graph, the edges point from one vertex to another, while in an undirected graph, they merely connect two vertices.
A representation can often be simplified if it is only being used for undirected graphs.
We may also want to associate some cost or weight to the traversal of an edge.
When we add this information, the graph is called weighted.
An example of a weighted graph would be the distance between the capitals of a set of countries.
Directed and undirected graphs may both be weighted.
The operations on a weighted graph are the same with addition of a weight parameter during edge creation.
There are essentially 5 ways of representing a graph:
Usually the first step in representing a graph is to map the nodes to a set of contiguous integers.
(0, |V|-1) is the most convenient in C programs - other, more flexible, languages allow you greater choice! The mapping can be performed using any type of search structure: binary trees, m-way trees, hash tables, etc.
Adjacency lists are lists of nodes that are connected to a given node. For each node, a linked list of nodes connected to it can be set up.
Adding an edge to a graph will generate two entries in adjacency lists - one in the lists for each of its extremities.
Having mapped the vertices to integers, one simple representation for the graph uses an adjacency matrix.
Using a |V| x |V| matrix of booleans, we set aij
= true if an edge connects i and j.
Edges can be undirected, in which case if aij
= true, then aji
= true also, or directed, in which aij
! = aji
, unless there are two edges, one in either direction, between i and j.
The diagonal elements, aii
, may be either ignored or, in cases such as state machines, where the presence or absence of a connection from a node to itself is relevant, set to true or false as required.
When space is a problem, bit maps can be used for the adjacency matrix.
In this case, an ADT for the adjacency matrix improves the clarity of your code immensely by hiding the bit twiddling that this space saving requires!
In undirected graphs, only one half of the matrix needs to be stored, but you will need to calculate the element addresses explicitly yourself.
Again an ADT can hide this complexity from a user! If the graph is dense, i.e. most of the nodes are connected by edges, and then the O (|V|2) cost of initializing an adjacency matrix is matched by the cost of inputting and setting the edges.
However, if the graph is sparse, i.e. |E| is closer to |V|, and then an adjacency list representation may be more efficient.
This structure is more flexible than adjacency list, but requires little more source code to implement it, and to use it.
Each vertex has list of pointers to edges to which it is incident.
Advantage of this is that two vertices that are adjacent to this edge share the same instance of edge, so when you want to manipulate with edge data, for example flow or cost, you only change data in one object.
You also modify neighbor function to make your graph directed, or mixed. Imagine how easy it would be to change the orientation of the edge with this data structure.
It’s an ordinary and directed graph.
In graph theory, the incidence matrix of an undirected graph G is a p × q matrix [bij] where p and q are the number of vertices and edges respectively, such that bij = 1 if the vertex vi and edge xj are incident and 0 otherwise.