Teaching Kids Programming – Introduction to Graph Data Structure

Teaching Kids Programming: Videos on Data Structures and Algorithms

We have so far learned the basic data structures:

• Teaching Kids Programming – Linked List Data Structure
• Teaching Kids Programming – Introduction to Queue Data Structure and Examples
• Teaching Kids Programming – Introduction to Heap and Priority Queue
• Teaching Kids Programming – Introduction to Trees, Binary Trees, Perfect Binary Trees, and BFS.
• Teaching Kids Programming – Reversing a List using Stack

It is time to take a look at the Graph Data Structure. In theory, a tree is also a Graph (special case). Two trees (disjoint) are also graphs (sometimes they are called forest). A linked list is also a graph.

So, a graph consists of Vertices (V) and Edges (E). Each edge can have a weight or not. If it is weighted, we call it a weighted graph otherwise it is unweigted.

Edges in the Graph G can also have directions. If the edges are directed, we call the Graph directed Graph, otherwise it is undirected Graph.

For number of incoming edges, we call it the incoming degree, and for number of outgoing edges for a vertex, we call it the outgoing degree.

A complete Graph is a graph that each vertice contains all possible edges to other vertices. An empty Graph is basically an empty set of G(V, E).

A Connected Graph is a Graph that each vertice is connected from or connected to any other vertices and Dis-connected graph is otherwise.

Storing the Graph using Adjacent Matrix

We can use the 2 dimesnional array to store the Vertices and Edges: for example

1
2
3
4
5

G = [
  [0, 1, 0], # edges from vertex 0
  [1, 0, 1], # edges from vertex 1
  [0, 1, 0]  # edges from vertex 2
]

G = [
  [0, 1, 0], # edges from vertex 0
  [1, 0, 1], # edges from vertex 1
  [0, 1, 0]  # edges from vertex 2
]

which represents the following Graph:

1

(0) <--> (1) <--> (2)

(0) <--> (1) <--> (2)

This data structure can be used to store weighted, unweights, directed and undirected Graphs.

Storing the Graph using Adjacent Linked List

If the edge number is small compared to vertice number, the above data structure is not space efficient, we can store, however, the Graph using the below Adjacent Linked List data structure:

1
2
3
4
5

G = {
  "A": ["B"],
  "B": ["A", "C"],
  "C": ["B"]
}

G = {
  "A": ["B"],
  "B": ["A", "C"],
  "C": ["B"]
}

This represents the following Graph:

1

(A) <--> (B) <--> (C)

(A) <--> (B) <--> (C)

We can also store the weights by using the tuples:

1
2
3
4
5

G = {
  "A": [("B", 1)],
  "B": [("A", 2), ("C", 3)],
  "C": [("B", 4)]
}

G = {
  "A": [("B", 1)],
  "B": [("A", 2), ("C", 3)],
  "C": [("B", 4)]
}

We can also change slightly to use the dictionary/hash map to store the edges as well:

1
2
3
4
5

G = {
  "A": {"B": 1},
  "B": {"A": 2, "C": 3},
  "C": {"B": 4}
}

G = {
  "A": {"B": 1},
  "B": {"A": 2, "C": 3},
  "C": {"B": 4}
}

Algorithm-wise, we can perform Depth First Search, or Breadth First Search Algorithms on it e.g. to find the shortest distance etc.

–EOF (The Ultimate Computing & Technology Blog)