The definition of the figure

  • A graph consists of a set of edges and a set of points,
  • A graph is called a directed graph if its vertices are ordered, and after sorting the vertices in the graph, a flow direction can be drawn
  • If the graph is unordered, it is called an unordered graph
  • A series of vertices in a graph form a path, all of which are joined by edges. The length of a path is expressed by the number of vertices from the first vertex to the last vertex of the path. A path consisting of vertices pointing to itself is called a loop, and the loop has length zero.
  • A loop is a path with at least one edge, and the first vertex of the path is the same as the last vertex. Both digraph and undigraph. A circle with no repeating edges is a simple circle, and a circle with no repeating vertices other than the first and last vertices is called a trivial circle.
  • Vertices are strongly connected if there are paths between them

Use diagrams to model real-world problems

  • Traffic flow
  • Operation system
  • Computer network system

Figure class

If the graph is constructed by tree and binary tree, it will be inefficient as the graph grows

Said the vertices

A class of vertices. Label is the same as identifying vertices. WasVisited indicates whether the vertices have been visited

function Vertex(label, wasVisited) {
        this.label = label
        this.wasVisited = wasVisited
    }
Copy the code

edge

Unlike a binary tree, a vertex can have either one edge or multiple edges. If vertex 2 is connected to 0134, store the 0134 representation at the array index 2.

Adj [2, 2,,1,3,4 [0], 2, 2]Copy the code

Build the figure

function Vertex(label, wasVisited) { this.label = label this.wasVisited = wasVisited } function Graph(v) { this.vertices = v; this.edgs = 0 this.adj = [] for(var i = 0; i< this.vertices; i++) { this.adj[i] = [] this.adj[i].push('') } } Graph.prototype = { addEdge: function(v, w) { this.adj[w].push(v) this.adj[v].push(w) this.edgs ++ }, show: function() { var arr = [] for(var i = 0; i< this.vertices; i++) { arr.push(`${i} ->`) for(var j = 0; j< this.vertices; j++) { if(this.adj[i][j]! =undefined) {arr.push(this.adj[I]+ ")}} arr.push(',')} return arr}} var g = new Graph(5) g.addedge (0,1) G.a ddEdge (0, 2) g.a ddEdge (1, 3) g.a ddEdge (2, 4) g.s how ()Copy the code

Search figure

Determining which vertices can be reached by a given vertex is a basic operation on a graph. Depth first and breadth first can be performed on the diagram

Depth-first search

You start at the vertex of a path, you go back until you get to the last vertex, and then you go back, and you keep going back the surprise path. Until we find the final vertex.

Access an unaccessed vertex, mark it as accessed, recursively access the other unaccessed vertices in the initial vertex’s neighboring table and add a marked array to the class

this.marked = [] for(var i = 0; i< this.vertices; DFS: function(v) {this.marked[v] = true if(this.adj. [v]! Log (' Visited vertex: ${v} ') this. Adj [v].foreach (w => {if(! this.marked[w]) { this.dfs(w) } }) } } function(v) { this.marked[v] = true if(this.adj[v] ! = undefined) { this.adj[v].forEach(w => { if(! this.marked[w]) { this.dfs(w) } }) } }Copy the code

Depth-first thinking:

  • Initialize the marked array
  • Determines whether there are other vertices in the array adjacent to the current vertex
  • Iterates over all the adjacent vertices of this vertex to see if they are marked, if they are not marked then recursive DFS (this vertex)

breadth-first

Start the search at the first vertex and try to access the vertices as close to it as possible.

  • Finds unaccessed vertices adjacent to the current vertex and adds them to the queue of accessed vertices
  • Takes the next vertex V from the graph and adds it to the queue of visited vertices
  • Add all unaccessed vertices adjacent to V to the queue
bfs: function(s) { var queue = [] this.marked[s] = true queue.push(s) while(queue.length > 0) { var v = queue.shift() if(this.adj[v]) { console.log(v) this.adj[v].forEach(w => { if(! this.marked[w]) { this.marked[w] = true queue.push(w) } }) } } }Copy the code

Find the shortest path

The breadth-first algorithm automatically finds the most segway path from one vertex to another adjacent vertex. The shortest path can be obtained by modifying the breadth-first algorithm

To determine the path

The data required to hold all edges from one vertex to the next is called edgeTo. Because we use breadth first, we will encounter an unmarked vertex every time. In addition to marking it, we also add an edge to the vertex that we are exploring in the critical list

bfs: Function (s) {var queue = [] this.marked[s] = true queue.push(s) while(queue.length > 0) {var v = queue.shift() If (this. Adj [v]) {console.log(' Visited vertex: ${v} ')} this. Adj [v].foreach (w => {if(! this.marked[w]) { this.edgeTo[w] = v this.marked[w] = true queue.push(w) } }) } },Copy the code

The helper method pathTo is used to store all vertices that have common edges at a given vertex

pathTo: function(v) { var source = 0 if(! this.hasPathTo(v)) { return undefined } var path = [] for(var i = v; i ! = source; i = this.edgeTo[i]) { path.push(i) } path.push(source) return path }, hasPathTo: function(v) { return this.marked[v] }Copy the code

A topological sort

Topological sorting sorts all vertices of a directed graph so that the directed edges point to the vertices in the front

Topological sorting algorithm

Similar to depth-first search, topological sort accesses all vertices in the adjacent array of the current vertex, and pushes the current vertex onto the stack until the list is exhausted.

Implementation of the algorithm

Complete Graph

function Vertex(label, wasVisited) { this.label = label this.wasVisited = wasVisited } function Graph(v) { this.vertices = v; this.vertexList = [] this.edgs = 0 this.adj = [] this.marked = [] this.edgeTo = [] for(var i = 0; i< this.vertices; i++) { this.adj[i] = [] // this.adj[i].push('') this.marked[i] = false } } Graph.prototype = { addEdge: function(v, w) { this.adj[w].push(v) this.adj[v].push(w) this.edgs ++ }, show: function() { var arr = [] for(var i = 0; i< this.vertices; i++) { arr.push(`${i} ->`) for(var j = 0; j< this.vertices; j++) { if(this.adj[i][j]! =undefined) { arr.push(this.adj[i][j]+ ' ') } } arr.push(',') } return arr.join('') }, dfs: function(v) { this.marked[v] = true if(this.adj[v] ! Log (' Visited vertex: ${v} ') this. Adj [v].foreach (w => {if(! this.marked[w]) { this.dfs(w) } }) } }, bfs: Function (s) {var queue = [] this.marked[s] = true queue.push(s) while(queue.length > 0) {var v = queue.shift() If (this. Adj [v]) {console.log(' Visited vertex: ${v} ')} this. Adj [v].foreach (w => {if(! this.marked[w]) { this.edgeTo[w] = v this.marked[w] = true queue.push(w) } }) } }, pathTo: function(v) { var source = 0 if(! this.hasPathTo(v)) { return undefined } var path = [] for(var i = v; i ! = source; i = this.edgeTo[i]) { path.push(i) } path.push(source) return path }, hasPathTo: function(v) { return this.marked[v] }, topSort: function() { var stack = [] var visited = [] for(var i = 0; i< this.vertices; i++) { visited[i] = false } for(var i = 0; i< this.vertices; i++) { if(! visited[i]) { this.topSortHelper(i, visited, stack) } } for(var i = 0; i< stack.length; i++) { if(stack[i] ! = undefined && stack[i] ! = false) { console.log(this.vertexList[stack[i]]) } } }, topSortHelper: function(v, visited, stack) { visited[v] = true for (const w in this.adj[v]) { if(! visited[w]) { this.topSortHelper(visited[w], visited, Stack)}} stack. Push (v)}} var g = new Graph(5) g.alddge (0,1) g.alddge (0,2) g.alddge (1,3) g.alddge (2,4) g.bfs(0) var vertex = 4 var paths = g.pathTo(vertex) while(paths.length > 0) { console.log(paths.pop()) } g.vertexList = ['cs1', 'cs2', 'data Structures', 'assembly language', 'operate system'] g.show() g.topSort()Copy the code