Chapter 7 Flashcards
is a non-linear data structure consisting of vertices and edges.
Graph
the fundamental units of the graph
Vertices
drawn or used to connect two nodes of the graph.
Edges
A graph is known as a __ if there are no edges in the graph.
null graph
Graph having only a single vertex, it is also the smallest graph possible
Trivial Graph
The graph in which from one node we can visit any other node in the graph is known as a
Connected Graph
The graph in which at least one node is not reachable from a node is known as a
Disconnected Graph
The graph in which the degree of every vertex is equal to K is called
Regular Graph
The graph in which from each node there is an edge to each other node.
Complete Graph
The graph in which the graph is a cycle in itself, the degree of each vertex is 2.
Cycle Graph
A graph containing at least one cycle is known
Cyclic Graph
A Directed Graph that does not contain any cycle.
Directed Acyclic Graph
A graph in which vertex can be divided into two sets such that vertex in each set does not contain any edge between them.
Bipartite Graph
A graph in which the edges are already specified with suitable weight
Weighted Graph
the restricted types of graphs, just with some more rules.
Trees
Two ways to store a graph:
Adjacency Matrix
Adjacency List
can be used to represent the interactions between players on a team, such as passes, shots, and tackles
Graph data structures
Can be used to represent the topology of computer networks, such as the connections between routers and switches.
Graphs
are used to represent the connections between different places in a transportation network, such as roads and airports
Graphs
real-life applications of graph
1.Neural Networks
2.Compilers
3.Robot planning
used to search a graph data structure for a node that meets a set of criteria.
TheBreadth First Search (BFS)algorithm
similar toDepth First Traversal of a tree.The only catch here is, that, unlike trees, graphs may contain cycles (a node may be visited twice).
Depth First Traversal (or DFS)for a graph
an algorithm for traversing or searching tree or graph data structures.
Depth-first search
A graph has a cycle if and only if we see a back edge during DFS
Detecting cycle in a graph
