GRAPHS

0.0(0)
studied byStudied by 2 people
0.0(0)
full-widthCall Kai
learnLearn
examPractice Test
spaced repetitionSpaced Repetition
heart puzzleMatch
flashcardsFlashcards
GameKnowt Play
Card Sorting

1/8

flashcard set

Earn XP

Description and Tags

Finals Topic

Study Analytics
Name
Mastery
Learn
Test
Matching
Spaced

No study sessions yet.

9 Terms

1
New cards

Graph

  • Is a non-linear data structure consisting of nodes and edges.

  • A pictorial representation of a set of objects where some pairs of objects are connected by links. The interconnected objects are represented by points termed as vertices, and the links that connect the vertices are called edges

<ul><li><p>Is a non-linear data structure consisting of nodes and edges.</p></li><li><p>A pictorial representation of a set of objects where some pairs of objects are connected by links. The interconnected objects are represented by points termed as vertices, and the links that connect the vertices are called edges</p></li></ul><p></p>
2
New cards

Vertex

  • Each node of the graph is represented as a _

3
New cards

Edge

  • An _ represents a path between two vertices or a line between two vertices

4
New cards

Adjacency

  • Two nodes or vertices are _ if they are connected to each other through an edge

5
New cards

Path

  • Represents a sequence of edges between the two vertices.

6
New cards

Adjacency Matrix

  • It is a 2D array of size V x V where V is the number of vertices in a graph.

  • The _ for the undirected graph is always symmetric/

  • It is also used to represent weighted graphs.

<ul><li><p>It is a 2D array of size V x V where V is the number of vertices in a graph.</p></li><li><p>The _ for the undirected graph is always symmetric/</p></li><li><p>It is also used to represent weighted graphs.</p></li></ul><p></p>
7
New cards

Adjacency List

  • An array of lists is used in the _ type of graph representation. The size of the array is equal to the number of vertices.

<ul><li><p>An array of lists is used in the _ type of graph representation. The size of the array is equal to the number of vertices.</p></li></ul><p></p>
8
New cards

Breadth First Search (BFS)

  • This algorithm is used to search a graph data structure for a node that meets a set of criteria. It starts at the root of the graph and visits all nodes at the current depth level before moving on to the nodes at the next depth level.

  • We divide the vertices into two categories: Visited and Unvisited.

  • Uses a queue data structure for traversal.

<ul><li><p>This algorithm is used to search a graph data structure for a node that meets a set of criteria. It starts at the root of the graph and visits all nodes at the current depth level before moving on to the nodes at the next depth level.</p></li><li><p>We divide the vertices into two categories: Visited and Unvisited.</p></li><li><p>Uses a queue data structure for traversal.</p></li></ul><p></p>
9
New cards

Depth First Search (DFS)

  • It an algorithm for traversing or searching tree or graph data structures. The algorithm starts at the root node (selecting some arbitrary node as the root node in the case of a graph) and explores as far as possible along each branch before backtracking.

  • Uses Stack data structure

<ul><li><p>It an algorithm for traversing or searching tree or graph data structures. The algorithm starts at the root node (selecting some arbitrary node as the root node in the case of a graph) and explores as far as possible along each branch before backtracking.</p></li><li><p>Uses Stack data structure</p></li></ul><p></p>