12 Questions
What is a graph in the context of data structures?
A finite set of nodes with edges between nodes
What is the primary difference between a tree and a graph?
Trees are a special case of graphs with no loops
What is a key characteristic of the edges in a tree?
There are always n-1 edges in a tree with n nodes
What type of relationship exists between nodes in a tree?
Parent-child relationships with each node having one parent
What is a common application of graphs?
Social networks and maps
What is a key feature of a graph that distinguishes it from a tree?
Graphs can have cycles and disconnected components
What does each relationship in a graph represent?
Edges between entities x and y
What is an individual data element of a graph called?
Vertex
What is a weighted edge?
An edge with a cost on it
What is a self-loop?
An edge that connects a vertex to itself
What is a connected graph?
A graph with a path between every pair of nodes
What is the indegree of a node?
The number of edges connecting to the node
Study Notes
Definition and Basics of Graphs
- A graph is a non-linear data structure consisting of a finite set of nodes with edges between them.
- A graph G can be formally represented as (V, E), where V is a finite set of nodes, and E is a set of pairs of nodes.
Graph vs. Tree
- A tree is a connected graph with no loops or cycles.
- Graphs can have cycles and disconnected components, while trees are connected with no cycles.
- In a tree, each node (except the root) has exactly one parent, whereas in a graph, nodes can have multiple parents or no parents.
Node and Edge Relationships
- Nodes (or vertices) represent entities such as people, cities, computers, words, etc.
- Edges (x, y) represent relationships between entities x and y, such as distance, friendship, child-parent relationships, etc.
Graph Terminology
- A vertex (or node) is an individual data element of a graph.
- An edge is a connecting link between two vertices and can be undirected, directed, or weighted.
- Undirected edges are bidirectional, while directed edges are unidirectional.
- Weighted edges have a cost or value associated with them.
Edge Types and Graph Properties
- Parallel edges or multiple edges have the same endpoints.
- A self-loop is an edge that connects a node to itself.
- A simple graph has no parallel or self-loop edges.
- Adjacent nodes are connected by an edge.
- A path is a sequence of vertices that connect two nodes in a graph.
Graph Connectivity
- An undirected graph is connected if there is a path between every pair of nodes.
- A disconnected graph is one where there is no path between some pair of nodes.
Indegree and Graph Types
- The indegree of a node is the number of edges incident to it.
- Types of graphs include undirected, directed, complete, and weighted graphs.
Test your understanding of graphs and trees with this quiz. Learn about the differences between graphs and trees, including their structures and characteristics.
Make Your Own Quizzes and Flashcards
Convert your notes into interactive study material.
Get started for free
