Algorithms review 2 Trees and Graphs

Posted on In

This is a personal notes of algorithms courses

Definition#

A graph G is a pair (V, E), where V is a set of vertices(also called Nodes) and E is a set of Edges connecting the vertices. Graphs can be directed or undirected and weighted or unweighted.(weights are always assigned on the edges)

  • self-loop is an edge that connects to the same vertex twice.
  • mult-edge is a set of two or more edges that have the same two vertices.
  • Simple graph is a graph does not have mult-edges or self-loops
  • In a graph G, if every two vertices of G are connected by a unique path (no circle) <-> G is connected and $V = E + 1$
  • In an undirected simple graph $G = (V, E)$, there are at most $V(V-1)/2$ edges. In short, by using the asymptotic notation,$E = O(v^2)$
  • a graph G is dense if $E=\Omega(v^2)$
  • a graph G is sparse if $E=O(V)$

Graph Traversals#

Graph Traversal means we visiting all versices in a systematic order. Since a graph may contain circle, we need a boolean visited array to mark whether a node has been visited or not. Moreover, there are two ways to represent a graph, either the adjcent matrix or the table.

DFS#

DFS uses a stack data structure or recursive way for backtracking.

  • recursive: 
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    class Solution{
        public void backTracking(int[][] adj) {
            int n = adj.length;
            boolean[] visited = new boolean[n];
            Arrays.fill(visited, false);
            for(int i = 0; i < n; i++) {
                if(!visited[i]) {
                    traversal(i, adj, visited);
                }
            }
        }
        public void traversal(int cur, int[][] adj, boolean visited) {
            visited[cur] = true;
            //visited cur
            for(int i = 0; i < adj[cur].length; i++) {
                if(!visited[i] && adj[i][j] == 1) {
                    traversal(i, adj, visited);
                }
            }
        }
    }
  • Stack 
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    class Solution{
        public void backTracking(int[][] adj) {
            int n = adj.length;
            boolean[] visited = new boolean[n];
            Arrays.fill(visited, false);
            Stack<Integer> stack = new Stack<>();
            for(int i = 0; i < n; i++) {
                if(!visited[i]) {
                    visited[i] = true;
                    //Visit i
                    stack.push(i)
                }
                while(!stack.isEmpty()) {
                    int k = stack.pop();
                    for(int j = 0; j < n; j++) {
                        if(adj[k][j] == 1 && !visited[j]) {
                            visited[j] = true;
                            //visit j
                            stack.push(j);
                            break;
                        }
                    }
                }
            }
        }
    }

BFS#

BFS uses a FIFO queue for book-keeping.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
class Solution{
    public void bfs(int[][] adj) {
        int n = adj.length;
        boolean[] visited = new boolean[n];
        Arrays.fill(visited, false);
        Queue<Integer> queue = new LinkedList<>();
        for(int i = 0; i < n; i++) {
            if(!visited[i]) {
                visited[i] = true;
                //Visit i
                queue.offer(i);
            }
            while(!queue.isEmpty()) {
                int k = queue.poll();
                for(int j = 0; j < n; j++) {
                    if(adj[k][j] == 1 && !visited[j]) {
                        visited[j] = true;
                        //visit j
                        queue.offer(j);
                    }
                }
            }
        }
    }
}

Complexity Analysis#

Please notice that the time complexity is related to the data structure of graph

If a graph stored with adjacent matrix, the time complexity is $O(V^2)$

However, if a graph stored with adjacent list, the time complexity can be lowing to $O(V+E)$;

  1. It visited all the vertices in the connected component;
  2. edges labeled by traversal form a spanning tree of the connected component

Topological Sort#

In a DAG(direct acyclic graph), each vertex represents a task that must be completed and a directed edge$(u,v)$ indicates that task v depends on task u. If we want to find an exist order to complete the tasks. This called topological order or topological sort. There are two ways to get a proper topological order:

1.

    1. select a vertex
    1. run DFS and return vertices that has no undiscorvered leaving edges
    1. run DFS several times(each DFS uses linear time)
    1. We can get verties in reverse order

2.

    1. select a vertex whose indegree = 0
    1. return that vertex and continue search vertexs whose indegree = 0

Planar Graph#

A connected graph is planar if it can be drawn in the plane with edge drawn as a continuous curve such that no two edge cross. A planar graph in addition to vertices and edges also has disjoint faces.

Theorem1.#

(Euler’s formula) If G is a connected plaar graph with V vertices, E edges, and F faces, then
$$V - E + F = 2$$

Theorem2.#

In any simple connected planar graph with at least 3 vertices,
$$E\leq3V-6$$

remaing proof for later :D

Applications#

Example1#

Description#

Finding the longest pat in a DAG with linear time.

Solution#

We use a topological Order to solve that problem. We apply a new attribute to all node which means the longest path from the start point to the current node. If we can find a longer path we update this attribute.
Here is the code:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
Class Solution{
    public void TopologicalOrder(int[][] adj) {
        int n = adj.length;
        int[] indegree = new int[n];
        int[] longestPath = new int[n];
        ArrayList<Integer> res = new ArrayList<>();
        Arrays.fill(indegree, 0);
        Arrays.fill(longestPath, 0);
        for(int i = 0; i < n; i++) {
            for(int j = i; j < n; j++) {
                if(adj[i][j] == 1) indegree[j]++;
            }
        }
        for(int i = 0; i < n; i++) {
            if(indegree[i] == 0) {
                queue.add(i);
            }
        }
        while(!queue.isEmpty()) {
            int j = queue.remove();
            for(int k = 0; k < n; k++) {
                if(adj[j][k] == 1) {
                    indegree[k] -= 1;
                    longestPath[k] = Math.max(longestPath[k], 1 + longestPath[j]);
                    if(indegree[k] == 0) queue.add(k);
                }
            }
        }
    }
}

Reference#

[1] Algorithms in Action, by V. Savvich, First Edition, 2019.