Graph Terminology Vertices Edges Directed Undirected Weighted in DSA Go - 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. The connections between them are called edges. Edges can have directions (directed) or not (undirected), and they can have values (weights) that show how strong or costly the connection is.

Why it matters

Graphs help us understand and solve many real-world problems like maps, social networks, and computer networks. Without graphs, it would be hard to model relationships and paths between objects clearly and efficiently.

Where it fits

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

Mental Model

Core Idea

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

Think of it like...

Imagine a city map where intersections are vertices and roads are edges. Some roads go one way (directed), some go both ways (undirected), and some roads are longer or have tolls (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), and numbers show weights.

Build-Up - 7 Steps

1

Foundation

Understanding Vertices as Points

Concept: Vertices are the basic units or points in a graph representing objects or entities.

Think of vertices as dots or points. Each vertex can represent anything like a city, a person, or a webpage. In code, vertices can be numbers, strings, or objects that identify these points.

Result

You can identify and list all the points in a graph clearly.

Understanding vertices as distinct points helps you see the graph as a set of objects before worrying about how they connect.

2

Foundation

Edges Connect Vertices

Concept: Edges are the links or lines that connect two vertices, showing a relationship or path.

Edges connect two vertices. For example, an edge between vertex A and vertex B means there is a connection or relationship between them. Edges can be drawn as lines or arrows.

Result

You can visualize how points in a graph relate or connect to each other.

Seeing edges as connections clarifies how the graph models relationships, not just isolated points.

3

Intermediate

Directed Edges Show One-Way Connections

🤔Before reading on: do you think a directed edge means you can travel both ways or only one way? Commit to your answer.

Concept: Directed edges have a direction, meaning the connection goes from one vertex to another but not necessarily back.

A directed edge is like a one-way street. If there is a directed edge from vertex A to vertex B, you can go from A to B but not from B to A unless there is another edge going back.

Result

You understand that some connections in graphs have direction, affecting how you can move or flow through the graph.

Knowing direction changes how you traverse or analyze graphs, important for tasks like finding routes or dependencies.

4

Intermediate

Undirected Edges Show Two-Way Connections

🤔Before reading on: do you think undirected edges allow movement both ways or just one? Commit to your answer.

Concept: Undirected edges connect vertices without direction, meaning the connection works both ways.

An undirected edge is like a two-way street. If vertex A and vertex B are connected by an undirected edge, you can go from A to B and from B to A freely.

Result

You can model mutual relationships or connections where direction does not matter.

Recognizing undirected edges helps in problems where relationships are symmetric, like friendships or roads without one-way rules.

5

Intermediate

Weighted Edges Add Value to Connections

🤔Before reading on: do you think weights on edges represent strength, cost, or something else? Commit to your answer.

Concept: Weighted edges carry a number that shows the cost, distance, or strength of the connection between vertices.

Weights can represent things like distance between cities, cost of travel, or strength of a relationship. For example, an edge with weight 5 means it costs 5 units to travel that edge.

Result

You can model real-world scenarios where connections have different importance or cost.

Understanding weights allows you to solve optimization problems like shortest path or cheapest route.

6

Advanced

Combining Directed, Undirected, and Weighted Edges

🤔Before reading on: can a graph have both directed and undirected edges at the same time? Commit to your answer.

Concept: Graphs can mix directed, undirected, and weighted edges to model complex relationships.

Some graphs have only directed edges, some only undirected, and some mix both. Weights can be added to any edge type. This flexibility lets graphs represent many real-world systems like social networks, road maps, or workflows.

Result

You can design graphs that fit complex problems by choosing edge types and weights appropriately.

Knowing how to combine edge types and weights lets you tailor graphs to specific needs and understand their behavior deeply.

7

Expert

Graph Terminology in Go Data Structures

🤔Before reading on: do you think Go's built-in types directly support graphs or do you need custom structures? Commit to your answer.

Concept: Implementing graphs in Go requires custom data structures using slices, maps, and structs to represent vertices and edges with direction and weights.

In Go, vertices can be keys in a map, and edges can be stored as adjacency lists with structs holding destination and weight. Directed edges are represented by one-way entries, undirected by two-way entries. Weighted edges include a weight field. Example: ```go type Edge struct { To int Weight int } type Graph map[int][]Edge // Add directed edge func (g Graph) AddEdge(from, to, weight int) { g[from] = append(g[from], Edge{To: to, Weight: weight}) } // For undirected, add both ways func (g Graph) AddUndirectedEdge(a, b, weight int) { g.AddEdge(a, b, weight) g.AddEdge(b, a, weight) } ``` This structure supports all graph types and weights.

Result

You can build flexible graph representations in Go that handle vertices, edges, directions, and weights.

Understanding how to represent graph terminology in code bridges theory and practice, enabling real applications.

Under the Hood

Graphs are stored in memory as collections of vertices and edges. Vertices are often keys or indexes, and edges are stored as lists or matrices. Directed edges are stored as one-way links, while undirected edges are stored as two-way links. Weighted edges store extra data with each connection. This structure allows efficient traversal and querying.

Why designed this way?

Graphs evolved to model relationships naturally. Directed edges capture asymmetric relations like dependencies, while undirected edges model symmetric relations like friendships. Weights add realism by quantifying connections. This design balances simplicity and expressiveness.

Graph Internal Structure:

┌─────────┐       ┌─────────────┐
│ Vertex  │──────▶│ Edge List   │
│ (ID)    │       │ (To, Weight)│
└─────────┘       └─────────────┘
    ▲                  ▲
    │                  │
    │                  └─ Directed or undirected edges stored here
    │
  Collection of vertices

Edges stored as adjacency lists:
Vertex 1: [(2, 5), (3, 0)]
Vertex 2: [(3, 2)]

Directed edges mean only one direction stored.
Undirected edges stored twice (both directions).

Myth Busters - 4 Common Misconceptions

Quick: Does an undirected edge mean you must store it twice internally? Commit yes or no.

Common Belief: Undirected edges are stored only once because they connect two vertices equally.

Reality: Undirected edges are usually stored twice internally, once for each vertex's adjacency list, to allow easy traversal from either vertex.

Why it matters: If you store undirected edges only once, traversals from one vertex may miss connections, causing incorrect graph algorithms.

Quick: Do weighted edges always mean distance? Commit yes or no.

Common Belief: Weights on edges always represent physical distance between vertices.

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

Why it matters: Assuming weights always mean distance limits the graph's use and can cause wrong interpretations in algorithms.

Quick: Can a graph have both directed and undirected edges at the same time? Commit yes or no.

Common Belief: Graphs must be either fully directed or fully undirected, not both mixed.

Reality: Graphs can mix directed and undirected edges to model complex relationships.

Why it matters: Believing graphs can't mix edge types limits modeling power and understanding of real-world systems.

Quick: Does a vertex have to be a number? Commit yes or no.

Common Belief: Vertices must be numbers or integers to work in graphs.

Reality: Vertices can be any unique identifier like strings, objects, or custom types.

Why it matters: Limiting vertices to numbers restricts graph flexibility and real-world applicability.

Expert Zone

1

Weighted edges can be negative, but this requires special algorithms to handle cycles and shortest paths correctly.

2

In some graphs, edges can have multiple attributes (multi-weighted), requiring complex data structures beyond simple weights.

3

The choice between adjacency list and adjacency matrix representations affects performance and memory, especially for sparse vs dense graphs.

When NOT to use

Graphs are not ideal when relationships are simple or linear, where arrays or trees suffice. For very large graphs with millions of vertices, specialized graph databases or streaming algorithms are better than in-memory structures.

Production Patterns

In production, graphs are used in recommendation systems, routing engines, social network analysis, and dependency resolution. Efficient storage uses adjacency lists with hash maps for fast lookups. Weighted directed graphs model workflows and cost optimizations.

Connections

Tree Data Structure

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

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

Network Routing Protocols

Routing protocols use weighted directed graphs to find best paths in networks.

Knowing graph terminology aids understanding how routers decide paths based on edge weights and directions.

Social Network Analysis (Sociology)

Graphs model social relationships, with vertices as people and edges as interactions.

Graph concepts help analyze social structures, influence, and community detection in sociology.

Common Pitfalls

#1 Confusing directed and undirected edges leads to wrong traversal results.

Wrong approach:

Treating all edges as undirected in a directed graph traversal, e.g., visiting neighbors without checking edge direction.

Correct approach:

Check edge direction before traversal, only follow edges from source to destination in directed graphs.

Root cause:

Misunderstanding that directed edges allow movement only one way, causing incorrect graph exploration.

#2 Ignoring weights when calculating shortest paths causes wrong answers.

Wrong approach:

Using simple breadth-first search on weighted graphs without considering edge weights.

Correct approach:

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

Root cause:

Assuming all edges have equal cost, which is false in weighted graphs.

#3 Storing undirected edges only once causes incomplete adjacency lists.

Wrong approach:

Adding an undirected edge only to one vertex's adjacency list.

Correct approach:

Add the undirected edge to both vertices' adjacency lists.

Root cause:

Not realizing undirected edges must be represented in both directions for correct traversal.

Key Takeaways

Graphs consist of vertices (points) connected by edges (lines) that can be directed or undirected.

Directed edges have a one-way connection, while undirected edges allow two-way movement.

Weighted edges carry values representing cost, distance, or strength, adding realism to graph models.

Graphs can mix directed, undirected, and weighted edges to represent complex relationships.

Implementing graphs in code requires careful structure to handle vertices, edges, directions, and weights efficiently.

Practice

1. In a graph, what do we call the points or nodes where edges meet?

easy

A. Paths

B. Edges

C. Weights

D. Vertices

Solution

1. Step 1: Understand graph components

   A graph consists of points called nodes and connections called edges.

2. Step 2: Identify the term for nodes

   The points or nodes where edges meet are called vertices.

3. Final Answer:

   Vertices -> Option D

4. Quick Check:

   Nodes = Vertices [OK]

Hint: Remember: nodes = vertices, connections = edges [OK]

Common Mistakes:

• Confusing edges with vertices
• Thinking weights are nodes
• Mixing paths with vertices

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

easy

A. graph := make(map[int][]int)

B. graph := make([][]int, 0)

C. graph := make(map[int]int)

D. graph := make([]int, 0)

Solution

1. Step 1: Understand adjacency list representation

   An adjacency list uses a map from a vertex to a list of connected vertices.

2. Step 2: Choose correct Go syntax

   Using map[int][]int creates a map from int to slice of ints, perfect for adjacency list.

3. Final Answer:

   graph := make(map[int][]int) -> Option A

4. Quick Check:

   Map of int to slice[int] = adjacency list [OK]

Hint: Adjacency list = map from node to list of nodes [OK]

Common Mistakes:

• Using map[int]int which stores single int, not list
• Using slice of slices without map for keys
• Using slice of ints which can't map nodes

3. What will be the output of the following Go code snippet representing a weighted directed graph adjacency list?

graph := map[int]map[int]int{
  1: {2: 5, 3: 10},
  2: {3: 2},
  3: {},
}
fmt.Println(graph[1][3])

medium

A. 2

B. 5

C. 10

D. 0

Solution

1. Step 1: Understand graph structure

   graph[1] is a map with keys 2 and 3, values 5 and 10 respectively.

2. Step 2: Access graph[1][3]

   graph[1][3] accesses the weight from vertex 1 to 3, which is 10.

3. Final Answer:

   10 -> Option C

4. Quick Check:

   Weight from 1 to 3 = 10 [OK]

Hint: Access nested map keys for weights: graph[from][to] [OK]

Common Mistakes:

• Confusing weight 5 (edge 1->2) with 1->3
• Assuming 0 means no edge but 3 has empty map
• Mixing up keys and values in nested maps

4. Identify the error in this Go code snippet for adding an edge to an undirected graph adjacency list:

func addEdge(graph map[int][]int, u, v int) {
  graph[u] = append(graph[u], v)
  graph[v] = append(graph[u], v)
}

medium

A. Appending v to graph[u] twice

B. Appending v to graph[v] incorrectly

C. Missing initialization of graph map

D. Using wrong data type for graph

Solution

1. Step 1: Analyze append statements

   First append adds v to graph[u], correct for edge u->v.

2. Step 2: Check second append

   Second append incorrectly appends v to graph[u] again instead of graph[v].

3. Final Answer:

   Appending v to graph[v] incorrectly -> Option B

4. Quick Check:

   Second append should be graph[v] = append(graph[v], u) [OK]

Hint: For undirected, append u to v's list and v to u's list [OK]

Common Mistakes:

• Appending to wrong slice variable
• Forgetting to append both directions
• Not initializing map slices before append

5. Given a weighted undirected graph represented as a map[int]map[int]int in Go, how can you ensure that adding an edge between two vertices u and v with weight w updates both directions correctly?

hard

A. graph[u][v] = w; graph[v][u] = w

B. graph[u][v] = w only

C. graph[v][u] = w only

D. graph[u][v] = w; graph[u][v] = w

Solution

1. Step 1: Understand undirected graph edge representation

   In undirected graphs, edges go both ways, so weights must be stored both ways.

2. Step 2: Update both directions in map

   Assign weight w to graph[u][v] and graph[v][u] to reflect undirected edge.

3. Final Answer:

   graph[u][v] = w; graph[v][u] = w -> Option A

4. Quick Check:

   Both directions updated = undirected edge [OK]

Hint: Update both graph[u][v] and graph[v][u] for undirected edges [OK]

Common Mistakes:

• Updating only one direction
• Assigning weight twice to same direction
• Confusing directed and undirected edge updates