Graph

[YuezhenQin]

Graph terminology

1. Edges of a node can either be directed or undirected. Directed edges mean that you can only traverse in one direction. Undirected edges mean that you can traverse in both directions.

   In binary trees, the edges were directed. Binary trees are directed graphs. You can't access a node's parent, only its children. Once you move to a child, you can't move back.

2. Another important term is connected component. A connected component of a graph is a group of nodes that are connected by edges.

3. A node can have any number of edges connected to it. Nodes that are connected by an edge are called neighbors. The number of edges that can be used to reach the node is the node's indegree. The number of edges that can be used to leave the node is the node's outdegree.

   In binary trees, all nodes except the root had an indegree of 1 (due to their parent). All nodes have an outdegree of 0, 1, or 2. An outdegree of 0 means that it is a leaf. Specific to trees, we used the parent/child terms instead of "neighbors".

4. A graph can be either cyclic or acyclic. Cyclic means that the graph has a cycle, acyclic means that it doesn't.

[YuezhenQin]

Code differences between LinkedLists, Trees and Graphs

An important thing to understand is that with LinkedLists (ListNode) and Trees (TreeNode), you are literally given objects in memory that contain data and pointers. With Graphs, the graph doesn't literally exist in memory.

In fact, only the "idea" of the graph exists. The input will give you some information about it, and it's up to you to figure out how to represent and traverse the graph with code.

First input format: array of edges (边的集合) [[x1,y1], [x2,y2], [x3,y3], ...]

In this input format, the input will be a 2D array. Each element of the array will be in the form [x, y], which indicates that there is an edge between vertices x and y.

Before starting the traversal, we can pre-process the input so that we can easily find all neighbors of any given node. Ideally, you want a data structure where you can give node as an argument and be returned a list of neighbors. The easiest way to accomplish this is using a hash map.

Second input format: adjacency list (邻接表: 出度边的集合)

In an adjacency list, the nodes will be numbered from 0 to n - 1. The input will be a 2D integer array, let's call it graph. graph[i] will be a list of all the outgoing edges from the i^th node.

Third input format: adjacency list (邻接矩阵: 出度边的集合)

Once again, the nodes will be numbered from 0 to n - 1. You will be given a 2D matrix of size n x n, let's call it graph. If graph[i][j] == 1, that means there is an outgoing edge from node i to node j.

[YuezhenQin]

Graph, DFS

[YuezhenQin]

Graph, BFS

Like with trees, in many graph problems, it doesn't really matter if you use DFS or BFS, and there are rarely scenarios where DFS performs better than BFS - people just choose DFS because it's faster/cleaner to implement, especially recursively.

But, there are some problems where using BFS is clearly better than using DFS. In trees, this was the case when we were concerned with tree levels. In graphs, it is mostly the case when you are asked to find the shortest path.