After reading this article, you can try to solve the following problems:

797. All possible paths (Medium)

Readers often ask me “graph” this kind of data structure, because our public number what data structure and algorithm have written, but did not specifically introduce “graph”.

In fact, in the frame thinking of learning data structure and algorithm, it was said that although graph can play more algorithms and solve more complex problems, the essence of the graph can be considered as an extension of multi-fork tree.

There are few graph-related questions in the written interview, and even if there are, most of them are simple traversal questions, which can basically completely copy the traversal of multi-fork trees.

In terms of minimum spanning tree, Dijkstra, network flow, they’re great, of course, but in terms of the written algorithm, the cost of learning is high but the benefit is low, there’s no cost performance, so it’s better to brush up on dynamic programming, really.

So, this article still uphold the style of our number, only talk about “picture” the most practical, from our closest part, let you have an intuitive understanding of the picture in your heart.

Diagram logical structure and concrete implementation

A graph is made up of nodes and edges, and the logical structure is as follows:

What is “logical structure”? That is to say, for the sake of study, we abstracted the graph like this.

According to this logical structure, we can consider the implementation of each node as follows:

/ / class Vertex {int id; Vertex[] neighbors; }Copy the code

Are you familiar with this implementation? It is almost exactly the same as the multi-fork tree node we talked about earlier:

/* Class TreeNode {int val; TreeNode[] children; }Copy the code

So the graph really doesn’t have any depth, it’s just a higher level multi-fork tree.

However, the above implementation is “logical”. In fact, we rarely use this Vertex class to implement graphs. Instead, we use the commonly known adjacency list and adjacency matrix.

For example, here’s the picture:

The storage of adjacency list and adjacency matrix is as follows:

Adjacency lists are pretty straightforward. I store the neighbors of each node X in a list, and then I associate x with the list, so that I can find all of its neighbors from a node X.

The adjacency matrix is a two-dimensional Boolean array, which we call matrix. If nodes x and y are connected, then matrix[x][y] is set to true. If you want to find the neighbor of node X, scan the matrix[x][..] Will do.

So why are there two ways to store graphs? It must be because they have their strengths and weaknesses.

For adjacency lists, the advantage is that they take up less space.

If you look at the adjacency matrix and there are so many empty places, you need more storage.

However, adjacency lists cannot quickly determine whether two nodes are adjacent.

For example, if I want to determine whether node 1 is adjacent to node 3, I’m going to look for the presence of node 3 in the neighbor list corresponding to node 1. But for adjacency matrix, it is simple, just look at matrix[1][3], high efficiency.

So, which way to implement a diagram depends on the situation.

Okay, so this is all you need to be able to read for a graph.

Then you may ask that the model of our graph is only directed and undirected graphs, not weighted graphs, undirected graphs, etc…

In fact, these more complex models are derived from this simplest diagram.

How to realize directed weighted graph? It’s simple:

If it’s an adjacency list, we don’t just store all the neighbors of a node X, we store the weights of x to each of the neighbors, and then we have a weighted digraph, right?

If the matrix[x][y] is not a Boolean, but an int, 0 means no connection, and the other values are weights, then it becomes a weighted directed graph.

How to implement undirected graph? Also very simple, the so-called “undirected”, is not the same as “two-way”?

Matrix [x][y] and matrix[y][x] are both true; Adjacency lists are similar operations.

Put the above techniques together and you get an undirected weighted graph…

Well, that’s enough for the basic introduction to graphs, and now you should have a pretty good idea of what to do with any random graphs.

Let’s look at the problem all data structures have: traversal.

Graph traversal

How does the graph traverse? Again, the traversal framework for multi-fork trees is as follows:

Void traverse(TreeNode root) {if (root == null) return; for (TreeNode child : root.children) traverse(child); }Copy the code

The big difference between a graph and a multi-fork tree is that a graph can have loops, you can start at one node of the graph, you can go all the way back to that node.

Therefore, if the graph contains rings, the traversal framework needs a Visited array to assist:

Graph graph; boolean[] visited; / / void traverse(Graph Graph, int s) {if (visited[s]) return; // s visited[s] = true; for (TreeNode neighbor : graph.neighbors(s)) traverse(neighbor); S visited[s] = false; }Copy the code

Okay, so when you look at this framework, does it remind you of the backtracking framework in the core of the backtracking algorithm?

The operation of the visited array is similar to that of the backtracking algorithm. The difference lies in the position. The “making” and “unselecting” of the backtracking algorithm are inside the for loop, while the operation of the Visited array is outside the for loop.

The only difference between the inside and outside of the for loop is the processing of the root node.

For example, the following two types of multi-fork tree traversal:

void traverse(TreeNode root) { if (root == null) return; System.out.println("enter: " + root.val); for (TreeNode child : root.children) { traverse(child); } System.out.println("leave: " + root.val); } void traverse(TreeNode root) { if (root == null) return; for (TreeNode child : root.children) { System.out.println("enter: " + child.val); traverse(child); System.out.println("leave: " + child.val); }}Copy the code

The former will correctly print the entry and exit information of all nodes, while the latter will only print the entry and exit information of the whole root node.

Why does the backtracking algorithm framework use the latter? Because the backtracking algorithm doesn’t focus on nodes, it focuses on branches, and if you look at the graph in the backtracking algorithm’s core pattern, it can ignore the root node.

Obviously, for the traversal of the “graph” here, we should put the operation of visited outside the for loop, otherwise the traversal of the starting point will be missed.

Of course, the visited array is needed only when the directed graph contains rings. If it does not contain rings, even the Visited array is omitted, which is basically the traversal of the multi-branch tree.

The subject practice

Let’s look at question 797 “All possible paths”, the function signature is as follows:

List<List<Integer>> allPathsSourceTarget(int[][] graph);

Copy the code

They input a directed acyclic graph with n nodes labeled 0, 1, 2… , n-1, please calculate all the paths from node 0 to node n-1.

Graph [I] stores all the neighboring nodes of node I.

For example, graph = [[1,2],[3],[3],[]] represents the following graph:

The algorithm should return [[0,1,3],[0,2,3]], all paths from 0 to 3.

The solution is very simple, take 0 as the starting point to traverse the graph, and record the paths traversed at the same time, when traversed to the end, the path can be recorded.

Since the input graph is acyclic, we do not need the assistance of visited array, and directly apply the graph traversal framework:

List<List<Integer>> res = new LinkedList<>(); public List<List<Integer>> allPathsSourceTarget(int[][] graph) { LinkedList<Integer> path = new LinkedList<>(); traverse(graph, 0, path); return res; Void traverse(int[][] graph, int s, LinkedList<Integer> path) {// Add node s to path.addlast (s); int n = graph.length; If (s == n-1) {// add(new LinkedList<>(path)); path.removeLast(); return; } // recurse each adjacent node for (int v: graph[s]) {traverse(graph, v, path); } // Remove the node from the path s path.removelast (); }Copy the code

The problem was solved.

To sum up, the main ways of storing graphs are adjacency lists and adjacency matrices, which can be used to store any fancy graph.

In the written exam, the algorithm most frequently examined is graph traversal, which is very similar to the traversal framework of multi-fork trees.

Of course, there are many other interesting algorithms for graphs, such as binary graph determination, loop detection (compiler loop reference detection is a similar algorithm), and so on.

View more quality algorithm articles click here, hand with your brush force buckle, committed to the algorithm to speak clearly! My algorithm tutorial has received 90K star, welcome to like!