Graph Terminology Vertices Edges Directed Undirected Weighted in DSA C

Mental Model

A graph is a way to connect points (vertices) with lines (edges) that can have directions and weights.

Analogy: Imagine a city map where intersections are points (vertices) and roads are lines (edges). Some roads go one way (directed), some both ways (undirected), and some roads are longer or shorter (weighted).

Vertices: A, B, C, D
Edges:
A -> B (directed)
B ↔ C (undirected)
C -> D (directed, weight 5)

  A -> B
      ↘
       C ↔ D

Weights shown on edges where applicable.

Dry Run Walkthrough

Input: Graph with vertices A, B, C, D; edges: A->B (directed), B↔C (undirected), C->D (directed, weight 5)

Goal: Understand how vertices and edges connect, and how direction and weight affect the graph

Step 1: Identify vertices as points A, B, C, D

Vertices: [A] [B] [C] [D]

Why: Vertices are the main points or nodes in the graph

Step 2: Add directed edge from A to B

A -> B
Vertices: [A] [B] [C] [D]

Why: Directed edge means connection goes only from A to B

Step 3: Add undirected edge between B and C

A -> B ↔ C
Vertices: [A] [B] [C] [D]

Why: Undirected edge means connection goes both ways between B and C

Step 4: Add directed weighted edge from C to D with weight 5

A -> B ↔ C -> D (weight 5)
Vertices: [A] [B] [C] [D]

Why: Weighted edge shows cost or distance; direction shows flow from C to D

Result:

A -> B ↔ C -> D (weight 5)
Vertices: [A] [B] [C] [D]

Annotated Code

DSA C

#include <stdio.h>
#include <stdlib.h>

// Define a structure for an edge
typedef struct Edge {
    char from;
    char to;
    int directed; // 1 if directed, 0 if undirected
    int weight;   // 0 if no weight
    struct Edge* next;
} Edge;

// Define a structure for a graph
typedef struct Graph {
    char vertices[10];
    int vertex_count;
    Edge* edges;
} Graph;

// Function to add an edge to the graph
void add_edge(Graph* g, char from, char to, int directed, int weight) {
    Edge* new_edge = (Edge*)malloc(sizeof(Edge));
    new_edge->from = from;
    new_edge->to = to;
    new_edge->directed = directed;
    new_edge->weight = weight;
    new_edge->next = g->edges;
    g->edges = new_edge;
}

// Function to print the graph
void print_graph(Graph* g) {
    printf("Vertices: ");
    for (int i = 0; i < g->vertex_count; i++) {
        printf("[%c] ", g->vertices[i]);
    }
    printf("\nEdges:\n");
    Edge* current = g->edges;
    while (current != NULL) {
        if (current->directed) {
            if (current->weight > 0) {
                printf("%c -> %c (weight %d)\n", current->from, current->to, current->weight);
            } else {
                printf("%c -> %c\n", current->from, current->to);
            }
        } else {
            if (current->weight > 0) {
                printf("%c <-> %c (weight %d)\n", current->from, current->to, current->weight);
            } else {
                printf("%c <-> %c\n", current->from, current->to);
            }
        }
        current = current->next;
    }
}

int main() {
    Graph g;
    g.vertex_count = 4;
    g.vertices[0] = 'A';
    g.vertices[1] = 'B';
    g.vertices[2] = 'C';
    g.vertices[3] = 'D';
    g.edges = NULL;

    add_edge(&g, 'A', 'B', 1, 0); // directed edge A->B
    add_edge(&g, 'B', 'C', 0, 0); // undirected edge B<->C
    add_edge(&g, 'C', 'D', 1, 5); // directed weighted edge C->D weight 5

    print_graph(&g);
    return 0;
}

Edge* new_edge = (Edge*)malloc(sizeof(Edge));

allocate memory for new edge

new_edge->from = from; new_edge->to = to; new_edge->directed = directed; new_edge->weight = weight;

set edge properties: start, end, direction, weight

new_edge->next = g->edges; g->edges = new_edge;

insert new edge at the front of edge list

while (current != NULL) { ... current = current->next; }

traverse all edges to print them

Output

Vertices: [A] [B] [C] [D] 

Edges:

C -> D (weight 5)

B <-> C

A -> B

Complexity Analysis

Time: O(E) because printing edges requires visiting each edge once

Space: O(V + E) because we store all vertices and edges separately

vs Alternative: Compared to adjacency matrix (O(V^2) space), adjacency list with edges is more space efficient for sparse graphs

Edge Cases

Empty graph with no vertices or edges

Prints no vertices and no edges without error

DSA C

g.vertex_count = 0;

Graph with only one vertex and no edges

Prints single vertex and no edges

DSA C

g.vertex_count = 1;

Edges with zero weight treated as unweighted

Edges print without weight label

DSA C

if (current->weight > 0)

When to Use This Pattern

When a problem involves connecting points with lines that may have directions or costs, recognize it as a graph problem and use graph terminology to describe vertices and edges.

Common Mistakes

Mistake: Confusing directed edges with undirected edges and printing arrows incorrectly
Fix: Check the directed flag before printing arrow direction

Mistake: Ignoring weights and printing all edges the same
Fix: Include weight check and print weight only if greater than zero

Summary

Graphs connect points called vertices with lines called edges that can be directed or undirected and may have weights.

Use graph terminology to describe and solve problems involving networks, maps, or relationships.

The key insight is that edges can have direction and cost, changing how connections work.