- Node or Vertex
- A fundamental unit of which Graphs are formed.
- Vertices
- The collection of nodes or vertex is called Vertices.
- Edges
- The Relationship between the vertices are called Edges.
- Realtime Example
- A city map can be represented by graph whose vertices are location in the city and whose edges are road between the locations
- Undirected graph
- A graph whose edges are undirected meaning they can traverse in both the directions. For example) A graph of friendship is
undirected graph.
- Watch the edge connecting 2 and 7 in the graph diagram.
- A graph whose edges are undirected meaning they can traverse in both the directions. For example) A graph of friendship is
undirected graph.
- Directed Graph
- A graph whose edges are directed meaning they can traverse only in one direction.
- Watch the edge connecting 1 and 2 in the graph diagram.
- A graph whose edges are directed meaning they can traverse only in one direction.
- Acyclic Graph
- A graph who has no cycles.
- Watch the vertices (1,8), (1,9) and (1,4) in the graph example
- A graph who has no cycles.
- Cyclic Graph
- A graph who has at least one cycle.
- Watch the vertices (2,7), (7,5) and (5,2) in the graph example
- A graph who has at least one cycle.
- Connected Graph(Strongly Connected)
- A graph is connected meaning if one or more edges connecting the given vertices.
- Watch the vertices (2,7), (7,5) and (5,2) in the graph example.
- A graph is connected meaning if one or more edges connecting the given vertices.
- Disconnected Graph(Weakly connected)
- A graph is disconnected meaning if there are connections between the vertices of every pair of vertices.
- Watch the Vertices (6,3) in the graph example is disconnected from the (1,8) vertex.
- A graph is disconnected meaning if there are connections between the vertices of every pair of vertices.
-
Depth First Traversal
- DFT uses Depth First Search approach before traversing the sibling node child node need to traverse.
-
Breadth First Traversal
- BFT uses Breadth First Search approach firstly the sibling node need to be traverse and Secondly, child node need to traverse.
Operation | Complexity |
---|---|
Adding the vertex/Edge | o(v + E) |
Removing the vertex/Edge | o(v + E) |