Hello,
Welcome back to Data Structures and Algorithms. We will continue learn chapter 7, Graph. We will discuss storage of graph in this lecture.
Graph is a presentation of nodes and edges between nodes.
Thus we can naturally represent it with a matrix.
Elements of the matrix stand for whether an edge
exists. If an edge exists,
the corresponding element in matrix is 1, or 0 if not exists.
Then, we successfully represent a graph with adjacent matrix. It consumes O(n^2) storage space.
Space consummation is only related to number of nodes,
no matter the graph is dense or sparse.
Let's see an example of an adjacent matrix for a directed graph.
This element in the matrix
presenting the edge from v3 to v0.
Let's see a weighted undirected graph.
For this graph, we modify value of elements(0,1) in matrix
to weight of edges if edges exist.
Because this is an undirected graph,
The adjacent matrix is a symmetric matrix
We realize adjacent matrix with
two dimensional array. Notice that
each elements in the two-dimensional array
represents for an edge with information of
start of the edge, end of the edge and weight of the edge.
For sparse graph, there are a lot of 0 in the matrix
If we need to find out all non-zero elements, or say all edges
We need to scan all elements.
This is a loop in loop, consume much of time.
There are only a few non-zero elements in sparse matrix
We can save a lot of time if we can organize all edges in some way and save space as well.
Let's look at Adjacency List.
Adjacency List contains edges
with information of nodes of edges
We can link all edges and form such a structure.
This structure saves time and space.
Let's look into detail.
For a node in the list, it contains data of
First edge of it and a pointer point to next edge
connecting to this node
All edges in one list start from a same node.
Let's look at a example for Adjacency List of undirected graph
There are 5 edges in this undirected graph
Every edge connects to two nodes and will present in
two lists of the two nodes respectively. We need to be careful for that
if we need to modify an edge of an undirected graph
we have to modify two nodes in the adjacency list
respectively. The two nodes represents for a same edge and thus
we need to maintain consistency.
Let's look at this weighted graph
We add weight as a data field of node in
Adjacency List
For directed graph
adjacency list organized by "from" node
That is, nodes in edges in a list
can be reached by the edges from
node for which the list represents.
Information in the adjacency list is accomplished. For convenience, we may need to
to organize Adjacency List by "to" node.
We call it "to" edge Adjacent List.
Space consummation is related to
number of nodes-n and number of edges-e.
for undirected graph, each edges is stored twice
such that it needs n+2e space.
For directed graph, this is n+e.
If graph is sparse, e << n^2
we save a lot of time by using Adjacency List
And also make operation efficient.
If we need "to" and "from" information together
we can organize it together by
such a orthogonal list.
Its a combination of two kinds of adjacency list.
Every item in the list contains
several information field.
From point, To point and next item
in "from" list and "to" list
This two dimensional structure
represents for a graph structure
organized by "from" information and
"to" information.
every item in the list contains 5 field.
From point, To point, weight and
next item in same row
and next item in same column
This can be applied Orthogonal list
To realize sudoku.
Here are questions for you
If we need to represent a complex graph with self-loop and multi edges
how to modify structures we introduced to satisfy such diamond?