Graph Terminology Vertices Edges Directed Undirected Weighted in DSA Java - Deep Dive

Overview - Graph Terminology Vertices Edges Directed Undirected Weighted

What is it?

A graph is a way to show connections between things. The things are called vertices or nodes, and the connections between them are called edges. Edges can have directions, meaning they go one way, or be undirected, meaning they go both ways. Sometimes edges have weights, which are numbers showing how strong or costly the connection is.

Why it matters

Graphs help us understand and solve many real-world problems like finding the shortest path on a map, social network connections, or scheduling tasks. Without graphs, it would be hard to model and analyze these relationships clearly and efficiently.

Where it fits

Before learning graphs, you should know basic data structures like arrays and lists. After this, you can learn graph algorithms like searching, shortest paths, and spanning trees.

Mental Model

Core Idea

A graph is a collection of points (vertices) connected by lines (edges) that can have direction and weight to represent relationships.

Think of it like...

Imagine a city map where intersections are vertices and roads are edges. Some roads are one-way (directed), some two-way (undirected), and some roads take longer to travel (weighted).

Graph Structure:

Vertices (Nodes): V1, V2, V3, ...
Edges (Connections):
  V1 --- V2 (undirected)
  V2 -> V3 (directed)
  V3 --5--> V1 (weighted edge with weight 5)

Representation:
  V1
 /  \
V2 -> V3

Edges can be arrows (directed) or lines (undirected).

Build-Up - 6 Steps

1

Foundation

Understanding Vertices and Edges

Concept: Introduce the basic parts of a graph: vertices (points) and edges (connections).

Vertices are the objects or points in a graph. Edges are the lines that connect these points. For example, in a social network, people are vertices and friendships are edges. Edges can connect any two vertices.

Result

You can identify vertices and edges in any graph and understand that edges link vertices.

Knowing vertices and edges is the foundation for all graph concepts because they define what a graph is.

2

Foundation

Directed vs Undirected Edges

Concept: Learn the difference between edges that have direction and those that don't.

An undirected edge means the connection goes both ways, like a two-way street. A directed edge means the connection goes only one way, like a one-way street. For example, a Twitter follow is directed (you follow someone, but they may not follow back), while a Facebook friendship is undirected (both are friends).

Result

You can tell if a graph is directed or undirected by looking at its edges.

Understanding direction helps you know how information or flow moves in a graph.

3

Intermediate

Weighted Edges and Their Meaning

🤔Before reading on: do you think weights on edges always represent distance? Commit to your answer.

Concept: Edges can have weights, which are numbers that show cost, distance, or strength of the connection.

A weighted edge has a number attached to it. This number can mean different things depending on the problem: distance between cities, cost of a flight, or strength of a friendship. For example, a road between two cities might have a weight of 10 miles.

Result

You can interpret and use weights to find shortest paths or cheapest routes in graphs.

Knowing weights lets you solve real problems where connections are not equal.

4

Intermediate

Representing Graphs in Code

🤔Before reading on: do you think adjacency lists or adjacency matrices use less memory for sparse graphs? Commit to your answer.

Concept: Graphs can be stored in different ways in a program, mainly adjacency lists or adjacency matrices.

An adjacency list stores for each vertex a list of connected vertices. It is memory efficient for graphs with few edges. An adjacency matrix is a 2D array where each cell shows if an edge exists between two vertices. It uses more memory but allows quick edge checks.

Result

You can choose the right graph representation based on the graph size and density.

Understanding storage helps write efficient graph algorithms.

5

Advanced

Directed Weighted Graphs in Practice

🤔Before reading on: do you think a directed weighted graph can have cycles with negative total weight? Commit to your answer.

Concept: Combining direction and weights creates complex graphs used in many applications like routing and scheduling.

A directed weighted graph has edges with direction and weights. This allows modeling one-way roads with distances or costs. Some algorithms handle these graphs to find shortest paths, even with negative weights, but negative cycles cause problems.

Result

You can model and analyze complex networks with direction and cost, preparing for advanced algorithms.

Knowing how direction and weights interact is key to understanding graph algorithm challenges.

6

Expert

Edge Cases and Graph Terminology Nuances

🤔Before reading on: do you think a graph can have multiple edges between the same two vertices? Commit to your answer.

Concept: Explore special cases like multigraphs, loops, and terminology variations in graphs.

Some graphs allow multiple edges between the same vertices (multigraphs) or edges from a vertex to itself (loops). Terminology can vary: vertices are also called nodes, edges called arcs in directed graphs. Understanding these helps read and write precise graph definitions.

Result

You can recognize and handle special graph types and terminology in advanced contexts.

Knowing these nuances prevents confusion and errors in complex graph problems.

Under the Hood

Internally, a graph is stored as data structures like arrays, lists, or matrices. Vertices are stored as elements, and edges as links or entries between these elements. Directed edges store direction by linking from one vertex to another specifically. Weighted edges store numbers alongside these links. This structure allows algorithms to traverse and analyze connections efficiently.

Why designed this way?

Graphs were designed to model relationships naturally found in many fields like math, computer science, and social sciences. Direction and weights add realism to these models, allowing more precise representation of real-world problems. Alternatives like trees or simple lists cannot capture complex connections as flexibly.

Graph Internal Structure:

Vertices: [V1, V2, V3, ...]

Adjacency List:
V1 -> [(V2, weight), (V3, weight)]
V2 -> [(V3, weight)]
V3 -> []

Adjacency Matrix:
    V1 V2 V3
V1 [ 0  5  2 ]
V2 [ 0  0  3 ]
V3 [ 0  0  0 ]

Edges store direction by position and weights by values.

Myth Busters - 4 Common Misconceptions

Quick: do you think all graphs must have edges connecting every vertex to every other vertex? Commit yes or no.

Common Belief: Graphs always connect every vertex to every other vertex.

Reality: Graphs can be sparse, with many vertices having few or no edges connecting them.

Why it matters: Assuming full connectivity leads to inefficient algorithms and wrong assumptions about graph properties.

Quick: do you think weights on edges must always be positive? Commit yes or no.

Common Belief: Edge weights are always positive numbers.

Reality: Weights can be zero or negative, especially in problems like financial modeling or shortest path with penalties.

Why it matters: Ignoring negative weights can cause algorithms to fail or give incorrect results.

Quick: do you think directed graphs cannot have cycles? Commit yes or no.

Common Belief: Directed graphs never have cycles.

Reality: Directed graphs can have cycles, where following edges leads back to the starting vertex.

Why it matters: Misunderstanding cycles affects algorithm choice, especially in scheduling and dependency resolution.

Quick: do you think weighted edges always represent physical distance? Commit yes or no.

Common Belief: Weights on edges always mean physical distance.

Reality: Weights can represent any cost, time, capacity, or strength, not just distance.

Why it matters: Limiting weights to distance restricts problem modeling and solution approaches.

Expert Zone

1

Some graph algorithms behave differently on directed vs undirected graphs, so knowing the graph type deeply affects algorithm design.

2

Weighted graphs with negative cycles require special algorithms like Bellman-Ford; otherwise, shortest path calculations can be incorrect or infinite.

3

Multigraphs and loops complicate graph traversal and require careful handling in data structures and algorithms.

When NOT to use

Graphs are not ideal when relationships are strictly hierarchical (trees are better) or when data is linear or tabular without complex connections. For very large dense graphs, specialized data structures or approximations may be needed instead of simple adjacency lists or matrices.

Production Patterns

Graphs are used in routing systems (GPS navigation), social network analysis (friend recommendations), dependency management (build systems), and recommendation engines. Professionals often combine graph representations with algorithms like BFS, DFS, Dijkstra, and PageRank to solve real problems.

Connections

Tree Data Structure

A tree is a special type of graph with no cycles and a hierarchical structure.

Understanding graphs helps grasp trees as simpler graphs, clarifying traversal and hierarchy concepts.

Network Theory (Sociology)

Graphs model social networks where vertices are people and edges are relationships.

Knowing graph terminology aids in analyzing social structures, influence, and connectivity in human networks.

Transportation Systems

Graphs represent routes and connections in transportation, with weights as distances or costs.

Graph concepts directly apply to optimizing travel, logistics, and scheduling in real-world transport.

Common Pitfalls

#1 Confusing directed and undirected edges leads to wrong graph modeling.

Wrong approach:

Representing a one-way street as an undirected edge, allowing travel both ways.

Correct approach:

Represent the one-way street as a directed edge from start to end vertex only.

Root cause:

Misunderstanding edge direction causes incorrect graph behavior and algorithm results.

#2 Ignoring edge weights when they matter causes wrong shortest path calculations.

Wrong approach:

Using unweighted shortest path algorithms on weighted graphs, treating all edges equally.

Correct approach:

Use algorithms like Dijkstra that consider edge weights to find correct shortest paths.

Root cause:

Not recognizing the importance of weights leads to oversimplified and incorrect solutions.

#3 Using adjacency matrix for very large sparse graphs wastes memory and slows performance.

Wrong approach:

Storing a graph with millions of vertices and few edges in a large 2D matrix.

Correct approach:

Use adjacency lists to store only existing edges efficiently.

Root cause:

Not matching graph representation to graph density causes inefficiency.

Key Takeaways

Graphs are made of vertices (points) connected by edges (lines) that can be directed or undirected and may have weights.

Direction on edges shows one-way or two-way connections, which changes how information flows in the graph.

Weights on edges represent costs or distances, enabling more realistic problem modeling.

Choosing the right graph representation (adjacency list or matrix) depends on graph size and density.

Understanding graph terminology and nuances is essential for applying graph algorithms correctly in real-world problems.

Practice

1. Which of the following best describes a vertex in a graph?

easy

A. A point or node where edges meet

B. A line connecting two vertices

C. A graph with no edges

D. A graph that has weights on edges

Solution

1. Step 1: Understand the definition of vertex

   A vertex is a fundamental unit in a graph representing a point or node.

2. Step 2: Differentiate vertex from edges and graph types

   Edges connect vertices; weights and graph types describe edges or the whole graph, not vertices.

3. Final Answer:

   A point or node where edges meet -> Option A

4. Quick Check:

   Vertex = point/node [OK]

Hint: Vertices are points/nodes, edges are connections [OK]

Common Mistakes:

• Confusing edges with vertices
• Thinking weights define vertices
• Mixing graph types with vertex definition

2. Which of the following is the correct way to declare an undirected weighted graph using adjacency list in Java?

easy

A. Map graph = new HashMap<>();

B. Map graph = new TreeMap<>();

C. Map>> graph = new TreeSet<>();

D. Map>> graph = new HashMap<>();

Solution

1. Step 1: Identify data structure for weighted edges

   Weighted edges need to store both neighbor and weight, so Pair is used.

2. Step 2: Choose correct map and list types

   HashMap with List of pairs is standard for adjacency list of weighted graphs.

3. Final Answer:

   Map>> graph = new HashMap<>(); -> Option D

4. Quick Check:

   Weighted graph uses Pair for edges [OK]

Hint: Weighted edges need pairs: neighbor and weight [OK]

Common Mistakes:

• Using List<Integer> for weighted edges
• Using TreeSet instead of List for adjacency
• Confusing Map types for graph

3. Consider the following Java code snippet for a directed graph:

Map graph = new HashMap<>();
graph.put(1, Arrays.asList(2, 3));
graph.put(2, Arrays.asList(3));
graph.put(3, Arrays.asList());
System.out.println(graph.get(1));

What will be the output?

medium

A. null

B. [1, 2, 3]

C. [2, 3]

D. []

Solution

1. Step 1: Check what is stored for key 1

   Key 1 maps to list containing 2 and 3.

2. Step 2: Print the list for key 1

   Printing graph.get(1) outputs the list [2, 3].

3. Final Answer:

   [2, 3] -> Option C

4. Quick Check:

   graph.get(1) = [2, 3] [OK]

Hint: Print adjacency list for key to see neighbors [OK]

Common Mistakes:

• Expecting all vertices in output
• Confusing keys and values
• Assuming empty list prints null

4. The following code attempts to add an edge to an undirected graph represented by adjacency list. What is the bug?

void addEdge(Map graph, int u, int v) {
    graph.get(u).add(v);
}

medium

A. It adds edge only from u to v, missing v to u

B. It uses get() instead of put() to add edge

C. It should use a Set instead of List for adjacency

D. It should clear the adjacency list before adding

Solution

1. Step 1: Understand undirected graph edge addition

   Undirected edges must be added both ways: u to v and v to u.

2. Step 2: Analyze given code

   Code adds edge only from u to v, missing the reverse edge.

3. Final Answer:

   It adds edge only from u to v, missing v to u -> Option A

4. Quick Check:

   Undirected edges need both directions [OK]

Hint: Undirected edges require adding both directions [OK]

Common Mistakes:

• Adding edge only one way in undirected graph
• Confusing get() and put() usage
• Clearing adjacency list mistakenly

5. You have a weighted directed graph represented as:

Map>> graph = new HashMap<>();
graph.put(1, Arrays.asList(new Pair<>(2, 5), new Pair<>(3, 10)));
graph.put(2, Arrays.asList(new Pair<>(3, 2)));
graph.put(3, Arrays.asList());

How would you find the total weight of edges going out from vertex 1?

hard

A. Sum weights 10 + 2 = 12

B. Sum weights 5 + 10 = 15

C. Sum weights 5 + 2 = 7

D. Count edges: 2

Solution

1. Step 1: Identify edges from vertex 1

   Edges from 1 go to 2 with weight 5, and to 3 with weight 10.

2. Step 2: Sum the weights of these edges

   Total weight = 5 + 10 = 15.

3. Final Answer:

   Sum weights 5 + 10 = 15 -> Option B

4. Quick Check:

   Total outgoing weight from 1 = 15 [OK]

Hint: Add weights of all edges from the vertex [OK]

Common Mistakes:

• Adding weights from wrong vertices
• Counting edges instead of summing weights
• Mixing weights of different edges