Definition of the diagram
Graph is composed of a finite non-empty set of vertices and a set of edges between vertices. It is usually represented as: G(V,E), where G represents a graph, V is the set of vertices in graph G, and E is the set of edges in graph G.
Directed graph
Directed edge: If the edge from the vertex Vi to Vj has a direction, this edge is called a directed edge, which also becomes an arc (Arc). It is represented by an ordered <Vi, Vj>. Vi is called the arc tail and Vj is called the arc head.
Disordered diagram
Undirected edge: If the edge between vertices Vi to Vj has no direction, this edge is called an undirected edge (Edge), and is represented by an unordered pair (Vi, Vj).
Simple picture
Simple diagram: In the graph structure, if there is no vertex to its own edge and the same edge does not appear repeatedly, this picture is called a simple diagram.
Picture Class
Indicates a vertex
The first step in creating a graph class is to create a Vertex class to save vertices and edges. This class functions the same as the Node class of linked lists and binary search trees. The Vertex class has two data members: one to identify the vertex and the other to indicate whether it has been accessed. They are named label and was visited respectively.
The code copy is as follows:
function Vertex(label){
this.label = label;
}
We save all vertices in an array, and in the graph class, we can refer to them by their position in the array
Indicates edge
The actual information of the graph is stored on the "edge" because they describe the structure of the graph. A parent node of a binary tree can only have two child nodes, but the structure of the graph is much more flexible. A vertex can have one edge or multiple edges connected to it.
We will use the method of representing edges of the graph to become an adjacency table or an adjacency table array. It will store an array composed of a list of adjacent vertices of vertices
Build a graph
Define the following Graph class:
The code copy is as follows:
function Graph(v){
this.vertices = v;//vertices to the high point
this.edges = 0;
this.adj = [];
for(var i =0;I<this.vertices;++i){
this.adj[i] = [];
this.adj[i].push('');
}
this.addEdge = addEdge;
this.toString = toString;
}
This class records how many edges a graph represents and uses a length and the number of vertices of the graph to record the number of vertices.
The code copy is as follows:
function addEdge(){
this.adj[v].push(w);
this.adj[w].push(v);
this.edges++;
}
Here we use a for loop to add a subarray for each element in the array to store all adjacent vertices and initialize all elements into empty strings.
The traversal of the picture
Depth priority traversal
DepthFirstSearch, also known as DepthFirstSearch, is referred to as DFS for short.
For example, looking for a key in a room, no matter which room you start, you can search for the corners of the room, nightstands, bedside tables, under beds, wardrobes, TV cabinets, etc. one by one, so as not to miss any blind spots. After searching all the drawers and storage cabinets, then searching for the next room.
Depth priority search:
Depth-first search means accessing a vertex that has not been visited, marking it as accessed, and then recursively accessing other vertices that have not been visited in the adjacency table of the initial vertex.
Add an array to the Graph class:
The code copy is as follows:
this.marked = [];//Save the visited vertices
for(var i=0;i<this.vertices;++i){
this.marked[i] = false;//Initialize to false
}
Depth-first search function:
The code copy is as follows:
function dfs(v){
this.marked[v] = true;
//If statement is not necessary here
if(this.adj[v] != undefined){
print("Visited vertex: " + v );
for each(var w in this.adj[v]){
if(!this.marked[w]){
this.dfs(w);
}
}
}
}
Breadth-first search
Broadness-first search (BFS) is a blind search method, with the purpose of systematically expanding and examining all nodes in the graph to find results. In other words, it does not take into account the possible location of the result, and searches the entire picture thoroughly until the result is found.
Breadth-first search starts with the first vertex, and try to access the vertex as close to it as possible, as shown in the following figure:
Its working principle is:
1. First find unreached vertices adjacent to the current vertex and add them to the visited vertices list and queue;
2. Then take out the next vertex v from the graph and add it to the visited vertice list
3. Finally add all unvisited vertices adjacent to v to the queue
The following is the definition of the breadth-first search function:
The code copy is as follows:
function bfs(s){
var queue = [];
this.marked = true;
queue.push(s);//Add to the end of the queue
while(queue.length>0){
var v = queue.shift();//Remove from the team leader
if(v == undefined){
print("Visited vertex: " + v);
}
for each(var w in this.adj[v]){
if(!this.marked[w]){
this.edgeTo[w] = v;
this.marked[w] = true;
queue.push(w);
}
}
}
}
Shortest path
When performing a breadth-first search, the shortest path from one vertex to another connected vertex is automatically found
Determine the path
To find the shortest path, we need to modify the breadth-first search algorithm to record the path from one vertex to another. We need an array to save all edges of the next vertex from one vertex. We name this array edgeTo
The code copy is as follows:
this.edgeTo = [];//Add this line to Graph class
//bfs function
function bfs(s){
var queue = [];
this.marked = true;
queue.push(s);//Add to the end of the queue
while(queue.length>0){
var v = queue.shift();//Remove from the team leader
if(v == undefined){
print("Visited vertex: " + v);
}
for each(var w in this.adj[v]){
if(!this.marked[w]){
this.edgeTo[w] = v;
this.marked[w] = true;
queue.push(w);
}
}
}
}
Topological sorting algorithm
Topological sorting sorts all vertices of a directed graph, so that directed edges point from the front vertex to the back vertex.
The topological sorting algorithm is similar to BFS. The difference is that the topological sorting algorithm does not output the accessed vertices immediately, but instead accesses all adjacent vertices in the current vertex adjacent table. Until this list is exhausted, the current vertex will not be pushed into the stack.
The topological sorting algorithm is split into two functions. The first function is topSort(), which is used to set the sorting process and call a helper function topSortHelper(), and then display the sorted vertex list.
The main work of the topology sorting algorithm is done in the recursive function topSortHelper(), which marks the current vertex as accessed, and then recursively accesses each vertex in the current vertex adjacency table, marking these vertices as accessed. Finally, push the current vertex into the stack.
The code copy is as follows:
//topSort() function
function topSort(){
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] == false){
this.topSortHelper(i, visited,stack);
}
}
for(var i = 0;i<stack.length;i++){
if(stack[i] !=undefined && stack[i] != false){
print(this.vertexList[stack[i]]);
}
}
}
//topSortHelper() function
function topSortHelper(v, visited,stack){
visited[v] = true;
for each(var w in this.adj[v]){
if(!visited[w]){
this.topSortHelper(visited[w], visited,stack);
}
}
stack.push(v);
}