Graph – Basic concept

Relative articles

1. Graph – Basic concept (You're reading now!)
2. Graph – Shortest path algorithm
3. Graph – Spanning Tree

Content

1. What is graph?
2. Why graph is so important?
3. Types of graph
4. Walking through the graph
5. Summary
6. Reference

What is graph?

Graph is the relationship between each nodes. For example:

On Facebook which indicated by the lines between us. So all of us is the vertexs in graph and the lines are edges. To be more precisly, Graph is a Data Structure form by the set of vertexs and edges.

Why graph is so important?

Let's discuss the following problems:

---

1. Friends Suggestion
   Suppose FB wants to recommend Justin's Friends to Alex, then the number of edges should be crossed equals to 2. One of the edges is connenct Justin and Alex and the other one is that connect Justin and his friends.

---

2. Products Suggestion
   Once Justin browse a product on Shopee, Shopee will make an edge from that product to Justin. Therefore, the suggestion that Justin will notice next time should be the prouducts that connect to the last product Justin saw before.

---

3. Network Connection
   Given the specific IP address, Justin wanted to access some special Japan websites. However, Justin didn't directly connect to that server. Therefore, there should be a path (a set of edges) that formed a method to connect to that website.

---

With the real life examples above, we can deal with plenty of problems through graph theoroy(algorithm).

Types of graph

• Undirected graph

There are no direction for each edges.

• Directed graph (digraph)

Each edges has specific direction

• Weighted graph

Each edge has its own weight

• cycle graph

There exist at least a cycle in digraph or undirected graph

a->b->c form a cycle, but c->b->a doesn't.

Both a-b-c or c-b-a form cycles.

• DAG (Directed Acyclic graph)

Approaches to represent the graph

1. Adjancency matrix
   Using 2 dimension matrix to show the graph. If two vertex are connected, the value in matrix is 1, otherwise, 0.

• Undirected graph

$$Matrix=\left\{\begin{array}{cccc}0& 0& 1& 1\\ 0& 0& 1& 0\\ 1& 1& 0& 1\\ 1& 0& 1& 0\end{array}\right\}$$

• Digraph

$$Matrix=\left\{\begin{array}{cccc}0& 0& 0& 0\\ 0& 0& 1& 0\\ 1& 0& 0& 0\\ 1& 0& 1& 0\end{array}\right\}$$

---

2. Adjancency linked list
   Using a 1D matrix to store the vertex and using Linked list to show the connection with other vertex.

• Undirected graph

• Digraph

---

3. Edges container

Using container to store both vertexs and edges

// Class for edges
template <typename T>
class edge {
  // Start node and end node
  T start, end;
  
  // Add weight for weighted graph
  int weight
}

int main() {
  // Container to store both edges and vertex
  std::vector<edge<T> > edges;
  std::vector<int> vertexs;
  ...
}

Walking through the graph

In this example, I will use adjacency matrix to represent the graph

int graph = [[0, 0, 1, 1],
             [0, 0, 1, 0],
             [1, 1, 0, 1],
             [1, 0, 1, 0]];

---

• DFS

Go as deep as one node can!

For example, we start from node a.

We then explore other node connected to node a. Next node is c. Change our position from a to c.

Check the node connected to c. The first node we would encounter was a, however, a had already been visited. Therefore, we move next to b.

Check the node connected to b. There are no avaliable nodes for b because a had been already visited. Move back to c

Visit node d.

Alredy visited c and a. No node to visit from d. Move back to c.

No more node to visit from c. Move back to a.

No more node to visit from a. Stop program. The order is:

a c b d

Notice that we were passing through the graph not drawing the graph. We don't have to show every edges in the graph.

Code:

void DFS(int graph[][4], int start) {
  // Array to check visited
  static int visited[4] = {0};
  
  // Set visited and print out
  visited[start] = 1;
  std::cout << start << " ";
  
  // Check for connected edges
  for (int i = 0; i < 4; ++i) {
  
    // if not visited and has the connection then move to that node
    if (graph[start][i] == 1 && !visited[i]) {
      DFS(graph, graph[start][i]);
    }
    
  }
}

---

• BFS

See as much as one node can!

For example, we start from node a.

Next, check all the connected edges from a. Node c will be encountered first. Instead of moving to node c, we save it in queue and still stay at node a.

Visit node d and save it into queue.

The nodes connected to a had already been visited. Pop out c from queue.

Continue visiting other nodes connect to c.

Finish node c. Pop out d

Finish node d. Pop out b.

Finish node b. Also, queue is empty. Stop program. The order is:

a c d b

Code:

void BFS(int graph[][4], int start) {
  // queue for saving the visited node 
  std::queue<int> node;
  
  // Array for checking visited
  int visited[4] = {0};
  
  // Push the start node into queue
  node.push(start);
  
  // Start passing through the graph
  while (!node.empty()) {
  
    // Get the node from queue
    int current_node = node.front(); node.pop();
    
    // Print out the node
    std::cout << current_node << " ";
    
    // Check the connected edges
    for (int i = 0; i < 4; ++i) {
    
      // if not visited and has the connection then push to queue
      if (graph[current_node][i] == 1 && !visited[i]) {
        node.push(graph[current_node][i]);
      }
      
    }
    
  }
  
  std::cout << std::endl;
}

Summary

So far, we have introduced the basic concept of graph. We introduced the types of graph, how can we express the graph using different structures and how to pass through the graph. In next article, we're going to discuss how can we find the shortest path.

Reference

1. 培養與鍛鍊程式設計的邏輯腦 第二版

Contribution

• Thanks @JoyceFang1213 for checking the misspells.