Skip to content

Latest commit

 

History

History

11-chapter-Graphs

Folders and files

NameName
Last commit message
Last commit date

parent directory

..
graph.module.js
graph.module.js
 
 
graph.search.js
graph.search.js
 
 
readme.md
readme.md
 
 
test.js
test.js
 
 

readme.md

Graph Data Structure

### Code Examples

Description

There are two main parts of a graph:

  • The vertices (nodes) where the data is stored i.e. the numbers in the image
  • The edges (connections) which connect the nodes i.e. the lines between the numbers in the image

Graphs can be undirected or directed

  • Undirected graph: The relationship exists in both directions.
  • Directed graph: The relationships are based on the direction of the edges. It can be a one way relationship or a two-way relationship, but it must be explicitly stated.

common operations you can perform on graphs:

Additions

  • addNode: adds vertices to your graph
  • addEdge: creates edges between two given vertices in your graph

Removals

  • removeNode: removes vertices from your graph
  • removeEdge: removes edges between two given vertices in your graph

Search

  • contains: checks if your graph contains a given value
  • hasEdge: checks if a connection exists between two given nodes in your graph
  • dfs: Depth First Search (DFS) algorithm traverses a graph in a depthward motion and uses a stack to remember to get the next vertex to start a search, when a dead end occurs in any iteration.
  • bfs: Breadth First Search (BFS) algorithm traverses a graph in a breadthward motion and uses a queue to remember to get the next vertex to start a search, when a dead end occurs in any iteration.

Display

  • showGraph: displays the complete graph
  • showVertex: displays one vertex
  • showVertexs: displays all the vertexs in the graph

In addition to this, graphs can be weighted or unweighted. All this means is that there is some value or cost associated with the edges between the vertices.

Example Use Cases:

  • Electrical Engineering − The concepts of graph theory is used extensively in designing circuit connections. The types or organization of connections are named as topologies. Some examples for topologies are star, bridge, series, and parallel topologies.

  • Computer Science − Graph theory is used for the study of algorithms. For example,

  • Kruskal's Algorithm

  • Prim's Algorithm

  • Dijkstra's Algorithm

  • Computer Network − The relationships among interconnected computers in the network follows the principles of graph theory.

  • Science − The molecular structure and chemical structure of a substance, the DNA structure of an organism, etc., are represented by graphs.

  • Linguistics − The parsing tree of a language and grammar of a language uses graphs.

  • General − Routes between the cities can be represented using graphs. Depicting hierarchical ordered information such as family tree can be used as a special type of graph called tree. Graphs are used to model many different types of real-world systems.

Another example of a real word system that can be modeled by a graph is a consumer market, where vertices represent both institutions (vendors) and consumers.

References