Hello everyone.
In this lecture of Data Structure and Algorithm, we’re going to learn Chapter 7 Graph.
First, we’re going to introduce some definition and terms related to the graph and then the ADT.
The graph is a set of nodes and
edges. If there are edges connecting every two
nodes in a graph, we’ll call it complete graph.
Besides complete graph, there is another graph named sparse graph.
There are many node pairs in the graph not being connected by an edge.
If the number of edges in a graph is less than 5% of that of complete graph, we’ll call it sparse graph.
And there is a graph, though it’s not a complete graph, the density of
edges is quite high, that is the number of edges is approximate to that of complete graph, then we’ll
call it dense graph.
In some graph,
the relationship of nodes of edges can be considered as unordered pair.
That is, we don’t need to distinguish edge from v1 to v2 from edge from v2 to v1.
In this situation, the edges are actually bidirectional, that is if there is an edge connecting v1 to v2,
there must be an edge connecting v2 to v1, so we draw edges without
arrows in this graph. This kind of graphs is called undirected graph.
For the directed graph, the relationships of nodes of edges
are ordered. That is if there may be edges connecting v1 to v4,
but may not be edges connecting v4 to v1.
In some situation, we can label the node.
Thus we can refer the nodes
using the labels.
In some situations, the edges are weighted. The weights can mean
the cost from one node to another like the cost of time or price.
In the graph,
degree is a very important concept.
The degree of a node is the number of edges related to it.
For that in the directed graph, the relationships are ordered.
So we can see there are some edges connecting to other nodes from a node. The number of such edges
is the out-degree. It’s also possible that
there are some edges connecting to some node.
The number of such edges is the in-degree.
There is another concept called subgraph. For the graph on the left,
we can see if we extract the blue portion of the graph to form
a subgraph. All the nodes and
related edges are still in the graph.
The path is
a ordered sequence of nodes containing
all the nodes connecting one node to another.
In data structure, we generally only discuss the simple path.
The simple path is a path
in which no nodes appear twice,
except that the start node and terminal node can be the same.
We can see there are
two nodes appear twice in the path
respectively. The nodes in the center
also appear twice. These paths are not simple paths.
The path from vp to vq
is simple path. In the simple path from vp to vq,
the length of the path is equal to the number edges in the path.
If in a simple path,
the start node and terminal node are the same, the path is a cycle.
If there doesn’t exist any cycles in a graph,
we’ll call the graph acyclic graph.
There is a special kind of acyclic graph called directed acyclic graph, or we can call it DAG.
Tree and forest are special cases of DAG.
There exists other kinds of other DAG. The normal DAG is
only required to be directed and acyclic. However, it doesn’t matter if there
is a node connected by several edges. That is,
these nodes are reentrant. But in trees and forests, every node only have
one father, that is there is only one edge pointing to a node, then they are not reentrant.
Let’s have a look at the cycle. For the cycle constructed by
3 nodes, we think it’s correct. But for the cycle constructed by 2 nodes,
if it’s in an undirected graph, we don’t think it’s
a cycle. In fact, we don’t even allow
that there are two edges
connecting the same 2 nodes. We won’t discuss this
in our lecture.
For directed graph, this is a cycle.
That is, there are some cycle in the graph constructed by only 2 nodes.
There is another kind of graph called rooted graph, in this kind of graph,
there is a node which can reach all the nodes in the graph. This node is named root.
Tree is a kind of rooted graphs. How about forest?
For that it contains several trees, we can say it’s a special graph
constructed by several that kind of rooted graphs.
If in the undirected graph,
there is path from v1 to v2 and there must be a
path from v2 to v1. Then we can say v1 and v2 are connected.
And the connected subgraph in the
undirected graph is called connected component.
We can see in the big graph containing these two subgraphs, in the connected component on the left,
all the node pairs are connected.
In the right one, all the node pairs are also connected.
For directed graph, it’s much harder
to be connected. For that if there is a path
from vi to vj, there may not be a graph from vj to vi.
If there are both paths from vi to vj and
vj to vi, we can say the two nodes are
strongly connected.
If all the node pairs in the subgraph is strongly connected.
If we find all the maximal strongly connected subgraphs,
we can get several strongly connected components.
For example, in this big graph, we divide it into 4
strongly connected components. In each component,
all the node pairs are connected, but there is no
strongly connected relationship between each 2 components.
Weighted connected graph is called network. Networks are used in
several applications. Well, let’s see the ADT of graph.
For a data structure, the most important thing is to describe
the properties of nodes and edges. In the ADT of graph, first we should know the
number of nodes and edges.
Moreover, we should know which nodes every node in the graph
is connected to. This kind of connections are established through edges.
Thus we should know all the edges in the graph.
For convenient we should mark every edge.
That is, we should know what the first edge and next edge we can see are from the node.
We record in each edge that what the next edge
connected to the node is.
Then we organize all the edges connected to
this node. That is, we know what the first edge is,
then the next edge, and the next edge of the next edge.
We can save all the edge by such an organization. We can see how to implement it
in the implementation part.
And for such an edge, we should know
what the start node is and the terminal node is.
And also what the weight is.
Here are 2 questions. The first one is
for a node, there may be an edge connecting a node
to itself. This is called loop.
And is it possible that there exists
two edges both connecting a node to the same node other than itself.
This often happens in graph of
webpages. That is, in a webpage,
there may be some webpages linked to other webpages. And
there may be different links
between two webpages. However, we only discuss simple structure in our lecture.
We’ll not discuss the complex situations. You should implement some special processes to handle it.
Thank you all.