Graph Terminology Vertices Edges Directed Undirected Weighted in DSA C - Build from Scratch

Graph Terminology: Vertices, Edges, Directed, Undirected, Weighted

📖 Scenario: Imagine you are organizing a small network of cities connected by roads. Each city is a point (called a vertex), and each road connecting two cities is a line (called an edge). Some roads allow travel in both directions (undirected), while others only allow one-way travel (directed). Also, roads have distances (weights) showing how far apart the cities are.

🎯 Goal: You will create a simple graph representation using arrays to list cities (vertices) and roads (edges). You will mark if roads are one-way or two-way and include distances. This will help you understand basic graph terms like vertices, edges, directed, undirected, and weighted.

📋 What You'll Learn

Create an array of city names called vertices with 4 exact cities.

Create an array of edges called edges where each edge has a start city index, end city index, and distance.

Add a variable is_directed to indicate if the roads are one-way (1) or two-way (0).

Write a loop to print all edges with city names, direction, and distance.

💡 Why This Matters

🌍 Real World

Graphs are used to model networks like roads, social connections, and computer networks.

💼 Career

Understanding graph basics is important for software roles involving data structures, algorithms, and network programming.

1

Create the list of cities (vertices)

Create a char* array called vertices with these exact city names: "A", "B", "C", "D".

DSA C

char* vertices[] = {"A", "B", "C", "D"};
// Your code here

Hint

Think of vertices as the list of city names.

2

Create the list of roads (edges)

Create a 2D integer array called edges with these exact rows: {0, 1, 5}, {1, 2, 3}, {2, 3, 4}, {3, 0, 2}. Each row means start city index, end city index, and distance.

DSA C

char* vertices[] = {"A", "B", "C", "D"};
int edges[][3] = {
    {0, 1, 5},
    {1, 2, 3},
    {2, 3, 4},
    {3, 0, 2}
};
// Your code here

Hint

Each edge connects two cities by their indexes and has a distance.

3

Add direction information

Create an integer variable called is_directed and set it to 1 to mean roads are one-way (directed).

DSA C

char* vertices[] = {"A", "B", "C", "D"};
int edges[][3] = {
    {0, 1, 5},
    {1, 2, 3},
    {2, 3, 4},
    {3, 0, 2}
};
int is_directed = 1;
// Your code here

Hint

Use 1 for directed roads and 0 for undirected.

4

Print all roads with details

Write a for loop using i from 0 to 3 to print each edge in this format: "A -> B : 5" if is_directed is 1, or "A -- B : 5" if is_directed is 0. Use printf and the vertices and edges arrays.

DSA C

char* vertices[] = {"A", "B", "C", "D"};
int edges[][3] = {
    {0, 1, 5},
    {1, 2, 3},
    {2, 3, 4},
    {3, 0, 2}
};
int is_directed = 1;

for (int i = 0; i < 4; i++) {
    // Your code here
}

Hint

Use printf inside the loop to show each road with arrow or dash based on direction.

Practice

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

easy

A. A point or node representing an entity in the graph

B. A connection between two nodes

C. A path that starts and ends at the same node

D. A graph with no edges

Solution

1. Step 1: Understand the definition of vertex

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

2. Step 2: Differentiate vertex from edges and other terms

   Edges connect vertices; paths and graph types are different concepts.

3. Final Answer:

   A point or node representing an entity in the graph -> Option A

4. Quick Check:

   Vertex = node/entity [OK]

Hint: Vertices are the points or nodes in a graph [OK]

Common Mistakes:

• Confusing vertices with edges
• Thinking vertices are paths
• Mixing vertex with graph types

2. Which of the following is the correct way to represent a weighted edge from vertex u to vertex v with weight 5 in C struct?

easy

A. struct Edge { int u, v; }; struct Weight { int w; };

B. struct Edge { int u; int v; }; int weight = 5;

C. struct Edge { int u; int v; int weight; };

D. struct Edge { int u; int v; };

Solution

1. Step 1: Identify the correct struct fields for weighted edge

   A weighted edge needs source vertex, destination vertex, and weight as fields.

2. Step 2: Check struct syntax correctness

   struct Edge { int u; int v; int weight; }; correctly declares all three fields in one struct.

3. Final Answer:

   struct Edge { int u; int v; int weight; }; -> Option C

4. Quick Check:

   Weighted edge struct = u, v, weight [OK]

Hint: Weighted edges need u, v, and weight fields in one struct [OK]

Common Mistakes:

• Separating weight outside the edge struct
• Incorrect field order causing confusion
• Missing weight field

3. What is the output of the following code snippet that prints edges of a directed weighted graph?

typedef struct { int u; int v; int weight; } Edge;
Edge edges[] = { {0, 1, 10}, {1, 2, 20}, {2, 0, 30} };
int n = 3;
for (int i = 0; i < n; i++) {
    printf("%d -> %d (weight %d)\n", edges[i].u, edges[i].v, edges[i].weight);
}

medium

A. 0 -> 1 (weight 10)
1 -> 2 (weight 30)
2 -> 0 (weight 20)

B. 0 -> 1 (weight 10)
1 -> 2 (weight 20)
2 -> 0 (weight 30)

C. 0 -> 1 (weight 30)
1 -> 2 (weight 20)
2 -> 0 (weight 10)

D. 1 -> 0 (weight 10)
2 -> 1 (weight 20)
0 -> 2 (weight 30)

Solution

1. Step 1: Read the edges array values

   Edges are: (0,1,10), (1,2,20), (2,0,30).

2. Step 2: Trace the loop printing each edge

   Loop prints each edge in order with format "u -> v (weight w)".

3. Final Answer:

   0 -> 1 (weight 10) 1 -> 2 (weight 20) 2 -> 0 (weight 30) -> Option B

4. Quick Check:

   Print edges as stored = 0 -> 1 (weight 10) 1 -> 2 (weight 20) 2 -> 0 (weight 30) [OK]

Hint: Print edges in array order with their weights [OK]

Common Mistakes:

• Reversing u and v in print
• Mixing up weights between edges
• Printing edges in wrong order

4. Identify the error in this code snippet that tries to create an undirected graph edge list:

typedef struct { int u; int v; } Edge;
Edge edges[2];
edges[0].u = 0; edges[0].v = 1;
edges[1].u = 1; edges[1].v = 0;
// Print edges
for (int i = 0; i <= 2; i++) {
    printf("Edge from %d to %d\n", edges[i].u, edges[i].v);
}

medium

A. Edge direction is incorrect for undirected graph

B. Edges should have weight field

C. Edges array size should be 1, not 2

D. Loop condition should be i < 2, not i <= 2

Solution

1. Step 1: Check array size and loop bounds

   Edges array has size 2, valid indices are 0 and 1.

2. Step 2: Identify loop error

   Loop runs from i=0 to i=2 inclusive, which accesses edges[2] (out of bounds).

3. Final Answer:

   Loop condition should be i < 2, not i <= 2 -> Option D

4. Quick Check:

   Array size 2 means max index 1 [OK]

Hint: Loop index must be less than array size [OK]

Common Mistakes:

• Using <= instead of < in loop
• Assuming edges need weight for undirected
• Confusing edge direction in undirected graphs

5. You have a weighted undirected graph with vertices 0, 1, 2 and edges:
(0,1,4), (1,2,6), (0,2,5)
How many edges will be stored if you represent this graph using an edge list storing each edge only once?

medium

A. 3

B. 6

C. 2

D. 1

Solution

1. Step 1: Understand undirected edge storage

   In undirected graphs, each edge connects two vertices without direction, so store only one entry per edge.

2. Step 2: Count unique edges given

   Edges are (0,1), (1,2), (0,2) -- total 3 unique edges.

3. Final Answer:

   3 -> Option A

4. Quick Check:

   Undirected edges stored once = 3 [OK]

Hint: Undirected edges stored once, count unique pairs [OK]

Common Mistakes:

• Counting each edge twice
• Confusing directed with undirected storage
• Ignoring weights when counting edges