---
tags: Data structure and algorithm
---
# Graph -- Basic concept
## Relative articles
1. [Graph -- Basic concept](https://hackmd.io/@Justin123/graph1) (You're reading now!)
2. [Graph -- Shortest path algorithm](https://hackmd.io/@Justin123/graph2)
3. [Graph – Spanning Tree](https://hackmd.io/@Justin123/graph3)
## 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:
```graphviz
graph test {
// title
labelloc="t";
label = "Facebook Social Network\n\n";
rankdir=LR;
Justin -- Katie;
Justin -- Joyce;
Justin -- Alex;
Joyce -- Katie
Joyce -- Alex;
Katie -- Alex;
}
```
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.
```graphviz
graph test {
// title
labelloc="t";
label = "Undirected graph\n\n";
rankdir=LR;
a -- b;
b -- c;
b -- d;
d -- a;
e -- a;
e -- d;
}
```
* Directed graph (digraph)
> Each edges has specific direction
```graphviz
digraph test {
// title
labelloc="t";
label = "Directed graph\n\n";
rankdir=LR;
a -> b;
b -> c;
b -> d;
d -> a;
a -> e;
e -> d;
}
```
* Weighted graph
> Each edge has its own weight
```graphviz
graph test {
// title
labelloc="t";
label = "Weighted graph\n\n";
rankdir=LR;
a -- b [ label = "2" ]
b -- c [ label = "5" ]
b -- d [ label = "1" ]
d -- a [ label = "3" ]
e -- a [ label = "6" ]
e -- d [ label = "4" ]
}
```
* cycle graph
> There exist at least a cycle in digraph or undirected graph
```graphviz
digraph test {
// title
labelloc="t";
label = "Directed cyclic graph\n\n";
rankdir=LR;
a -> b;
b -> c;
c -> a
}
```
**<center>a->b->c form a cycle, but c->b->a doesn't.</center>**
```graphviz
graph test {
// title
labelloc="t";
label = "Undirected cyclic graph\n\n";
rankdir=LR;
a -- b;
b -- c;
c -- a
}
```
**<center>Both a-b-c or c-b-a form cycles.</center>**
* DAG (Directed Acyclic graph)
```graphviz
digraph test {
// title
labelloc="t";
label = "DAG\n\n";
rankdir=LR;
a -> b;
a -> d;
a -> c;
b -> c;
b -> d;
c -> d;
}
```
## 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
```graphviz
graph test {
rankdir=LR;
b -- c;
c -- a;
d -- a;
d -- c;
}
```
$$Matrix=
\left\{
\begin{matrix}
0 & 0 & 1 & 1 \\
0 & 0 & 1 & 0 \\
1 & 1 & 0 & 1 \\
1 & 0 & 1 & 0 \\
\end{matrix}
\right\}
$$
* Digraph
```graphviz
digraph test {
rankdir=LR;
b -> c;
c -> a;
d -> a;
d -> c;
}
```
$$Matrix=
\left\{
\begin{matrix}
0 & 0 & 0 & 0 \\
0 & 0 & 1 & 0 \\
1 & 0 & 0 & 0 \\
1 & 0 & 1 & 0 \\
\end{matrix}
\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
```graphviz
graph test {
rankdir=LR;
b -- c;
c -- a;
d -- a;
d -- c;
}
```
```graphviz
digraph g {
rankdir=LR
edge[arrowsize=1.0, arrowhead=vee]
node[shape=record fontsize=20];
list [label = "<a> a|<b> b|<c> c|<d> d", height=3];
nodea [label = "{c | d}"]
nodeb [label = "{c}"]
nodec [label = "{a | b | d}"]
noded [label = "{a | c}"]
list:a -> nodea
list:b -> nodeb
list:c -> nodec
list:d -> noded
}
```
* Digraph
```graphviz
digraph test {
rankdir=LR;
b -> c;
c -> a;
d -> a;
d -> c;
}
```
```graphviz
digraph g {
rankdir=LR
edge[arrowsize=1.0, arrowhead=vee]
node[shape = record, fontsize=20];
list [label = "<a> a | <b> b | <c> c | <d> d", height=3];
nodeb [label = "{c}"]
nodec [label = "{a}"]
noded [label = "{a | c}"]
list:b -> nodeb
list:c -> nodec
list:d -> noded
}
```
---
3. **Edges container**
> Using container to store both vertexs and edges
```cpp=
// 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;
...
}
```
```graphviz
digraph g {
node[shape=record, fontsize=20];
label = "\nContainer for vertexs"
list_vertexs [label = "vertex1 | vertex2 | vertex3 | ..."]
}
```
```graphviz
digraph g {
node[shape=record, fontsize=20];
label = "\nContainer for edges"
list_edges [label = "edges1 | edges2 | edges3 | ..."];
}
```
## Walking through the graph
```graphviz
graph test {
labelloc = "t"
label = "Example graph\n\n"
rankdir=LR;
b -- c;
c -- a;
d -- a;
d -- c;
}
```
In this example, I will use adjacency matrix to represent the graph
```cpp=
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**.
```graphviz
graph test {
labelloc = "t"
label = "First step\n\n"
rankdir=LR;
a [ color="red" ]
}
```
We then explore other node connected to node **a**. Next node is **c**. Change our position from **a** to **c**.
```graphviz
graph test {
labelloc = "t"
label = "Second step\n\n"
rankdir=LR;
c [ color="red" ]
a -- 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**.
```graphviz
graph test {
labelloc = "t"
label = "Third step\n\n"
rankdir=LR;
b [ color="red" ]
a -- c;
c -- b;
}
```
Check the node connected to **b**. There are no avaliable nodes for **b** because **a** had been already visited. Move back to **c**
```graphviz
graph test {
labelloc = "t"
label = "Fourth step\n\n"
rankdir=LR;
c [ color="red" ]
a -- c;
c -- b;
}
```
Visit node **d**.
```graphviz
graph test {
labelloc = "t"
label = "Fifth step\n\n"
rankdir=LR;
d [ color="red" ]
a -- c;
c -- b;
c -- d;
}
```
Alredy visited **c** and **a**. No node to visit from **d**. Move back to **c**.
```graphviz
graph test {
labelloc = "t"
label = "Sixth step\n\n"
rankdir=LR;
c [ color="red" ]
a -- c;
c -- b;
c -- d;
}
```
No more node to visit from **c**. Move back to **a**.
```graphviz
graph test {
labelloc = "t"
label = "Seventh step\n\n"
rankdir=LR;
a [ color="red" ]
a -- c;
c -- b;
c -- d;
}
```
No more node to visit from **a**. Stop program. The order is:
```cpp
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:
```cpp=
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**.
```graphviz
graph test {
labelloc = "t";
label = "First step\n\n";
rankdir=LR;
a [ color="red" ]
}
```
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**.
```graphviz
digraph g {
node[shape=record, fontsize=20];
labelloc = "t";
label = "Queue for saving visited node\n";
list_vertexs [label = "c"];
}
```
```graphviz
graph test {
labelloc = "t";
label = "Second step\n\n";
rankdir=LR;
a [ color="red" ]
a -- c
}
```
Visit node **d** and save it into queue.
```graphviz
digraph g {
node[shape=record, fontsize=20];
labelloc = "t";
label = "Queue for saving visited node\n\n";
list_vertexs [label = "c | d"]
}
```
```graphviz
graph test {
labelloc = "t";
label = "Third step\n\n";
rankdir=LR;
a [ color="red" ]
a -- c
a -- d
}
```
The nodes connected to **a** had already been visited. Pop out **c** from queue.
```graphviz
digraph g {
node[shape=record, fontsize=20];
labelloc = "t";
label = "Queue for saving visited node\n\n";
list_vertexs [label = "d"]
}
```
```graphviz
graph test {
labelloc = "t";
label = "Fourth step\n\n";
rankdir=LR;
c [ color="red" ]
a -- c
a -- d
}
```
Continue visiting other nodes connect to **c**.
```graphviz
digraph g {
node[shape=record, fontsize=20];
labelloc = "t";
label = "Queue for saving visited node\n\n";
list_vertexs [label = "d | b"]
}
```
```graphviz
graph test {
labelloc = "t";
label = "Fifth step\n\n";
rankdir=LR;
c [ color="red" ]
a -- c;
a -- d;
c -- b;
}
```
Finish node **c**. Pop out **d**
```graphviz
digraph g {
node[shape=record, fontsize=20];
labelloc = "t";
label = "Queue for saving visited node\n\n";
list_vertexs [label = "b"]
}
```
```graphviz
graph test {
labelloc = "t";
label = "Sixth step\n\n";
rankdir=LR;
a -- c;
a -- d;
d [ color="red" ]
c -- b;
}
```
Finish node **d**. Pop out **b**.
```graphviz
digraph g {
node[shape=record, fontsize=20];
labelloc = "t";
label = "Queue for saving visited node\n\n"
list_vertexs [label = ""]
}
```
```graphviz
graph test {
labelloc = "t";
label = "Seventh step\n\n";
rankdir=LR;
a -- c;
a -- d;
c -- b;
b [ color="red" ]
}
```
Finish node **b**. Also, queue is empty. Stop program. The order is:
```cpp
a c d b
```
Code:
```cpp=
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. [培養與鍛鍊程式設計的邏輯腦 第二版](https://www.books.com.tw/products/0010616945?gclid=Cj0KCQjwoub3BRC6ARIsABGhnyamNtOnA0U1z3yzZeFonqM2HT7jnj1WZcRX8ArR1_KwV3YEgkkkPlIaAlCZEALw_wcB)
## Contribution
* Thanks @JoyceFang1213 for checking the misspells.
Sign in with Wallet
Connect another wallet