1. Why diagrams

  1. We learned about linear tables and trees

  2. Linear tables are limited to a direct precursor and a direct successor

  3. A tree can only have one direct precursor, the parent node

  4. When we need to represent many-to-many relationships, we use graphs here.

2. Illustration of the graph

A graph is a data structure in which a node can have zero or more adjacent elements. The connection between two nodes is called an edge. Nodes can also be called vertices.

3. Common concepts of graphs

  1. Vertex (vertex)

  2. Side (edge)

  3. The path

  4. Undirected graph

  1. Directed graph

  2. Weighted graph

There are two ways of graph representation: two-dimensional array representation (adjacency matrix); Linked list representation (adjacency list).

4. Adjacency matrix

An adjacency matrix is a matrix that represents adjacent relationships between vertices in a graph. For a graph with n vertices, row and col represent 1…. N points.

5. Adjacency list

  1. Adjacency matrix needs to allocate space of n edges for each vertex. In fact, many sides do not exist, which will cause certain loss of space.

  2. An adjacency list implementation only cares about edges that exist, not edges that don’t. So there’s no wasted space. Adjacency lists are arrays plus linked lists

6. Implement the following structure

(1) Store vertex String using ArrayList

(2) Save matrix int[][] edges

public class Graph {

	private ArrayList<String> vertexList; // Store the vertex set
	private int[][] edges; // Store the adjacent node matrix corresponding to the graph
	private int numOfEdges; // Indicates the number of edges
	// Define an array Boolean [] that records whether a node is accessed
	private boolean[] isVisited;
    
    // Insert node
	public void insertVertex(String vertex) {
		vertexList.add(vertex);
	}
	
	/** * add edge *@paramV1 refers to the subscript of A point even if the vertex is "A"-"B" "A"->0 "B"->1 *@paramThe second vertex of v2 is subscript star@param* / weight
	public void insertEdge(int v1, int v2, int weight) { edges[v1][v2] = weight; edges[v2][v1] = weight; numOfEdges++; }}Copy the code

7. Depth-first traversal of the graph

The so-called graph traversal is the access to nodes. There are so many nodes in a graph, and there’s a strategy for how to traverse those nodes,

Generally, there are two access policies:

  • (1) Depth-first traversal
  • (2) breadth-first traversal

7.1 Basic idea of depth-first traversal

    1. Depth-first traversal starts from the initial access node, which may have multiple adjacent nodes. The strategy of depth-first traversal is access first

    The first adjacency is accessed, and the first adjacency is accessed using the accessed adjacency as the initial node, which can be interpreted as:

    Each time, the first adjacent node of the current node is accessed first after the current node is accessed.

    1. As we can see, the access strategy is to preferentially dig deep vertically, rather than horizontally access all the adjacent nodes of a node.
    1. Obviously, depth-first search is a recursive process

7.2 Steps of depth-first traversal algorithm

  1. Access the initial node V and mark node V as visited.

  2. Find the first adjacent node w of v.

  3. If w exists, continue with 4. If w does not exist, go back to step 1 and continue from the next node of v.

  4. If w is not accessed, perform depth-first traversal recursion on W (that is, treat W as another V and proceed to step 123).

  5. Find the next adjacent node of the W adjacent node of node V, go to Step 3.

7.3 Code Implementation

	// Depth-first traversal algorithm
	// I is 0 the first time
	private void dfs(boolean[] isVisited, int i) {
		// First we access the node, output
		System.out.print(getValueByIndex(i) + "- >");
		// Set the node to already accessed
		isVisited[i] = true;
		// find the first adjacent node w of node I
		int w = getFirstNeighbor(i);
		while(w ! = -1) {/ / instructions
			if(! isVisited[w]) { dfs(isVisited, w); }// if node w has already been accessedw = getNextNeighbor(i, w); }}// Perform an overload on DFS to traverse all of our nodes and DFS
	public void dfs(a) {
		isVisited = new boolean[vertexList.size()];
		// do DFS on all nodes
		for(int i = 0; i < getNumOfVertex(); i++) {
			if(! isVisited[i]) { dfs(isVisited, i); }}}Return the number of nodes
	public int getNumOfVertex(a) {
		return vertexList.size();
	}

Copy the code

8. Breadth-first traversal of the graph

8.1 Basic idea of breadth-first traversal

    1. Broad First Search of graphs.
    1. Similar to a hierarchical search process, breadth-first traversal requires a queue to maintain the order of nodes visited so that their neighbors can be accessed in that order

8.2 Steps of the breadth-first traversal algorithm

    1. Access the initial node v and mark node V as visited.
    1. Node V is queued
    1. When the queue is not empty, the execution continues, otherwise the algorithm ends.
    1. Out of the queue, get the queue head node u.
    1. Find the first adjacent node w of u.
    1. If the adjacent node W of node U does not exist, go to Step 3. Otherwise, the loop performs the following three steps:

    • 6.1 If node W has not been accessed, node W is accessed and marked as accessed.

    • 6.2 Node W is queued

    • 6.3 Searching for the next adjacent node W of node U after ADJACENT node W, go to Step 6.

8.3 Code Implementation

	
	// Breadth-first traversal of a node
	private void bfs(boolean[] isVisited, int i) {
		int u ; // the header of the queue corresponds to the subscript
		int w ; // adjacency node w
		// queue to record the order in which nodes are accessed
		LinkedList queue = new LinkedList();
		// Access node, output node information
		System.out.print(getValueByIndex(i) + "= >");
		// Mark as visited
		isVisited[i] = true;
		// queue the node
		queue.addLast(i);
		
		while( !queue.isEmpty()) {
			// Retrieve the header subscript of the queue
			u = (Integer)queue.removeFirst();
			// get the subscript w of the first adjacent node
			w = getFirstNeighbor(u);
			while(w ! = -1) {/ / find
				// Whether it has been accessed
				if(! isVisited[w]) { System.out.print(getValueByIndex(w) +"= >");
					// The tag has been accessed
					isVisited[w] = true;
					/ / team
					queue.addLast(w);
				}
				// use u as the starting point to find the next neighbor after w
				w = getNextNeighbor(u, w); // Reflect our breadth first}}}// Run the breadth-first search through all nodes
	public void bfs(a) {
		isVisited = new boolean[vertexList.size()];
		for(int i = 0; i < getNumOfVertex(); i++) {
			if(! isVisited[i]) { bfs(isVisited, i); }}}Copy the code

9. Depth first vs. breadth first