Graph terms and adjacency representations

From trees to general connections

A rooted tree gave each nonroot node one parent and prohibited cycles. A graph is more general: it records vertices and edges between them. A graph can contain a cycle, several routes between the same vertices, or disconnected parts. It does not automatically have a root, parent or left/right child. A traversal may later choose a source and create parent links, but those are outputs of the traversal, not the original graph's definition.

Prerequisites: bounded arrays and matrices, valid indices, C functions, struct records and pointer access to a live record. The earlier binary-tree lesson supplies useful vocabulary; the linked-list lesson distinguishes a logical relation from physical storage order. The needed C syntax is reviewed below. This lesson teaches representation, not BFS, DFS, shortest-path algorithms or complete graph-theory coverage. BFS and DFS follow in separate lessons.

State the graph model before using it

Our runnable program handles a simple undirected, unweighted graph:

• Vertices are distinct labels 0 through n - 1, where 0 <= n <= 6.
• An edge {u,v} joins two different vertices. There are no self-loops and no repeated/parallel edges. “Simple” means these restrictions here.
• Undirected means {u,v} and {v,u} describe the same edge. An edge can be followed in either direction.
• Unweighted means every edge is treated as one step, without a separate cost, distance or duration.

A vertex label is an identifier, not its degree, priority or a distance from a source. Isolated vertices still exist even though no edge touches them. With n = 0, the graph has no vertices or edges; with n = 1, it has one isolated vertex and no edge.

A directed graph instead has arcs u -> v. The reverse arc v -> u is a different possible arc and need not exist. Unless told to ignore direction, traversal follows outgoing arcs. “A can reach B” does not then imply “B can reach A.” We compare directed representation later, but the program deliberately rejects an asymmetric matrix because its contract is undirected.

Neighbors, degree, paths and components

Vertices joined by an edge are adjacent, or neighbors. In this simple undirected model, degree(u) is both the number of incident edges and the number of distinct neighbors of u. An isolated vertex has degree 0. Every edge contributes one to each endpoint's degree, so the sum of degrees is 2m, where m is the edge count.

A walk is a sequence of vertices whose consecutive pairs are edges; vertices may repeat. A path here has no repeated vertices. Its length is the number of edges, not the number of written vertex labels. A cycle in this simple undirected model starts and ends at the same vertex, contains at least three edges, and repeats no other vertex. Moving along one edge and immediately back is a walk, not such a cycle.

A graph is connected if every pair of vertices can be joined by a path. A connected component is a maximal connected set of vertices: all of its vertices connect to each other, and no outside vertex can be added while preserving that property. An isolated vertex forms its own component. A traversal from one source cannot reach another component. These are undirected component definitions; directed strong/weak connectivity needs separate definitions and is outside this lesson.

The number of edges in a shortest unweighted path is a distance. Several paths can have different lengths. Merely listing edges or neighbors does not compute distances or choose a traversal order.

Worked trace 1: one graph, its counts and routes

Let n = 5 and let the five edges be {0,1}, {0,3}, {1,2}, {1,3}, {3,4}. We write each undirected edge once in this set.

The degree sum is 2 + 3 + 1 + 3 + 1 = 10 = 2 x 5. All five vertices are in one component. The sequence 0,1,3,0 is a cycle of length 3. Paths from 0 to 4 include 0,3,4 (two edges) and 0,1,3,4 (three edges). The shorter has distance 2; the existence of the longer path does not change it. BFS will later compute such distances systematically.

This graph is not a tree: it has a cycle. It has no inherent root. Sorting each neighbor list by label is an explicit presentation choice; it does not assert that vertices have numeric priorities or that every traversal must use that order.

Adjacency matrix: one cell per ordered pair

Use A[u][v] = 1 when u and v are adjacent, otherwise 0. The first index is the row vertex; the second is the column vertex. The example's active 5 by 5 matrix is:

The diagonal is zero because self-loops are excluded. The matrix is symmetric: A[u][v] = A[v][u], because an undirected edge appears at both ordered positions. A row sum gives the corresponding degree. Summing every matrix entry counts each edge twice. To count edges once, sum only cells strictly above the diagonal, where u < v, or divide the whole sum by 2.

A cell value 1 means one edge exists, not that the shortest-path distance is one for every other vertex in that row. A[u][v] = 0 says no DIRECT edge; an indirect path may still exist. For example A[0][4] = 0 although 0,3,4 is a path. Matrix rows and columns do not store traversal parents.

Adjacency lists: one neighbor sequence per vertex

Store for each u only the labels of its neighbors. The preceding neighbor table is an adjacency-list representation. “List” describes a sequence of neighbors; it does not require dynamically allocated linked-list nodes. Different implementations use linked nodes, expandable arrays or packed storage.

Our safe small program uses a fixed neighbor row and a degree count per vertex. For vertex u, only neighbor[u][0] through neighbor[u][degree[u]-1] are active. A stored zero outside that prefix is unused storage; it is not an extra neighbor 0. With degree[u] = 0, the list is empty even though a row is allocated. The position k within a neighbor row is not itself a vertex label: neighbor[1][1] = 2 means the second listed neighbor of vertex 1 is vertex 2.

For an undirected edge {u,v}, the lists contain v in u's row AND u in v's row. Thus the total active neighbor entries are 2m. Do not insert the same neighbor twice in a simple graph. The conversion scans v from 0 upward, producing ascending lists reproducibly. A different consistent neighbor order would describe the same edges, although a later traversal's visit order could change.

Complete C11 conversion program

The program validates the matrix, converts it to bounded neighbor rows, prints the lists and counts undirected edges. It does not perform a graph traversal.

#include <stdio.h>

enum { CAP = 6 };

typedef struct {
    int n;
    int adj[CAP][CAP];
} Graph;

typedef struct {
    int degree[CAP];
    int neighbor[CAP][CAP];
} Lists;

int valid_graph(const Graph *g) {
    if (g == NULL || g->n < 0 || g->n > CAP) {
        return 0;
    }
    for (int u = 0; u < g->n; u = u + 1) {
        for (int v = 0; v < g->n; v = v + 1) {
            int x = g->adj[u][v];
            if (x != 0 && x != 1) {
                return 0;
            }
            if (u == v && x != 0) {
                return 0;
            }
            if (x != g->adj[v][u]) {
                return 0;
            }
        }
    }
    return 1;
}

int make_lists(const Graph *g, Lists *out) {
    if (out == NULL || !valid_graph(g)) {
        return 0;
    }
    Lists result = {0};
    for (int u = 0; u < g->n; u = u + 1) {
        for (int v = 0; v < g->n; v = v + 1) {
            if (g->adj[u][v] == 1) {
                int position = result.degree[u];
                result.neighbor[u][position] = v;
                result.degree[u] = position + 1;
            }
        }
    }
    *out = result;
    return 1;
}

int edge_count(const Graph *g) {
    if (!valid_graph(g)) {
        return -1;
    }
    int total = 0;
    for (int u = 0; u < g->n; u = u + 1) {
        for (int v = u + 1; v < g->n; v = v + 1) {
            total = total + g->adj[u][v];
        }
    }
    return total;
}

int main(void) {
    const Graph g = {5, {
        {0, 1, 0, 1, 0, 0},
        {1, 0, 1, 1, 0, 0},
        {0, 1, 0, 0, 0, 0},
        {1, 1, 0, 0, 1, 0},
        {0, 0, 0, 1, 0, 0},
        {0, 0, 0, 0, 0, 0}
    }};
    Lists lists = {0};
    if (!make_lists(&g, &lists)) {
        return 1;
    }
    for (int u = 0; u < g.n; u = u + 1) {
        printf("%d:", u);
        for (int k = 0; k < lists.degree[u]; k = k + 1) {
            printf(" %d", lists.neighbor[u][k]);
        }
        printf("\n");
    }
    printf("edges: %d\n", edge_count(&g));
    return 0;
}

Exact output:

0: 1 3
1: 0 2 3
2: 1
3: 0 1 4
4: 3
edges: 5

C records, input promises and safe boundaries

enum { CAP = 6 }; names an integer constant. Graph contains n followed by a six-by-six int matrix; Lists contains six degree counts followed by six neighbor rows of six slots. Nested braces initialize records and their arrays in declaration order. Lists result = {0} initializes every degree and every neighbor slot to zero, not merely the first element.

&g supplies the address of the live Graph record. const Graph *g receives that address and permits reads through it; g->n means (*g).n. A pointer is passed by value, but following it reaches the original record. Lists *out designates a writable output record; *out = result copies the completed record to it. NULL, available from stdio.h here, denotes no object. The input Graph and output Lists must be distinct, nonoverlapping live initialized objects. NULL is accepted as an error case; dangling pointers or forged addresses cannot be made safe by these checks. No dynamic allocation is involved.

valid_graph first checks the pointer and n, then checks only the active n-by-n square. Every active entry must be 0 or 1, every diagonal entry 0, and symmetric entries equal. Unused rows/columns are initialized storage outside the graph. || short-circuits when an earlier condition is true, preventing access through NULL. && requires both conditions. ! tests for zero. != means not equal; = assigns; == compares. The for loops initialize an index, test a bound before each iteration, and update after the body.

Conversion rejects a bad graph or NULL output before writing anything. It constructs a zero-initialized local result, then copies it to out only on success. Failure returns 0 and preserves a provided live output object field for field. Success returns 1. The input is never changed.

For each vertex, at most n - 1 <= 5 neighbors can occur, because there is no self-loop and each column is examined once. Before each write, position is the number already found, so the largest written position is at most 4 in the six-slot row. This is different from the maximum neighbor LABEL, which may be 5. An empty graph converts successfully with all counts zero; a singleton produces one empty list. edge_count returns -1 on invalid input, or 0 through 15 on a valid graph, so its failure indicator cannot be a legitimate count. It sums only u < v. All index and count arithmetic is bounded and representable as int.

printf's %d prints an int and \n starts a line. main checks conversion status before using the result. The program assumes sequential calls with no concurrent mutation.

Worked trace 2: convert a disconnected graph

Take n = 4 with edges {0,2} and {1,2}; vertex 3 is isolated. Active matrix rows are [0,0,1,0], [0,0,1,0], [1,1,0,0], [0,0,0,0]. Scanning each row from column 0 to 3 produces:

• Row 0: skip 0,1; append label 2 at position 0; skip 3. List [2], degree 1.
• Row 1: list [2], degree 1.
• Row 2: append 0 at position 0 and 1 at position 1. List [0,1], degree 2.
• Row 3: append nothing. List [], degree 0.

The active entry count is four, but the edge count is two. There are two components: {0,1,2} and {3}. Source 0 can reach 1 via 2, even though A[0][1] is zero; it cannot reach 3. Converting every row records the isolated vertex too, but does not itself discover or number components.

Worked trace 3: directed representation is a different contract

For a separate directed graph with arcs 0 -> 1, 0 -> 2 and 2 -> 1, define A[u][v] = 1 for an arc FROM u TO v. Its rows are [0,1,1], [0,0,0], [0,1,0]. Outgoing lists are 0:[1,2], 1:[], 2:[1]. Row sums are outdegrees 2,0,1; column sums are indegrees 0,2,1. Each sum across all vertices equals the three arcs, without division by two.

Vertex 0 reaches 1, but 1 reaches neither 0 nor 2 by outgoing arcs. Do not add reverse entries unless those arcs exist. This matrix is intentionally asymmetric and is NOT accepted by valid_graph above. Supporting directed graphs requires a deliberate contract/validator change, not pretending that symmetry is optional in the undirected program.

Storage and access tradeoffs, with honest bounds

A general n-by-n matrix stores n squared cells, even for few edges. Once indices are valid, testing a specific edge is one cell lookup. Listing all neighbors of u by scanning its row examines n candidate columns.

An ordinary compact adjacency-list representation uses n list descriptors plus neighbor entries: 2m entries for a simple undirected graph, m for directed outgoing lists. Scanning u's already-built list examines degree(u) entries. Searching an unsorted list for one specified neighbor can require examining the whole list; adjacency lists do not automatically provide a constant-time edge lookup.

Our beginner implementation intentionally reserves CAP squared neighbor slots plus CAP counts, just as it reserves CAP squared matrix slots. It does NOT demonstrate the compact list's memory saving. It demonstrates which entries are logically active and how a neighbor sequence represents the same graph. The conversion scans the n-by-n active matrix, and initializing the whole bounded result also touches reserved storage. Formal asymptotic analysis and compact allocation techniques come later.

A precise analogy

Imagine six named stations and direct two-way tracks. The matrix is a checklist for every ordered station pair. A neighbor list is a station's card listing only directly connected stations. An isolated station still needs a row/card. Repeating each two-way track on both endpoint cards does not create two physical tracks. This analogy explains direct adjacency, not travel times or the order a search algorithm chooses; all edges in our model have equal one-step cost.

Key box

• State direction, weights, loops and duplicate-edge rules first.
• Graph vertices need not have a root or one parent. Cycles and disconnected parts are allowed.
• Undirected matrix: symmetric, zero diagonal here, row sum = degree, sum of entries = 2m.
• A missing direct edge does not rule out an indirect path.
• Adjacency lists store neighbor labels; list position and vertex label are different.
• Directed outgoing lists and degree counts follow a different convention.
• Neighbor order is explicit. Representation alone does not compute traversal order or shortest paths.
• The fixed-row demonstration is safe and bounded, but not a compact-memory list implementation.

Try it first, then check

1. Add isolated vertex 5 to the first five-vertex example, leaving all edges unchanged. What changes? Answer: n becomes 6; a zero active row and column and an empty neighbor list are added. Edge count remains 5, degree sum remains 10, and there are now two components.
2. An undirected simple graph has neighbor lists 0:[1], 1:[0,2], 2:[1], 3:[]. Count edges and give a path from 0 to 2. Answer: four neighbor entries represent two edges. Path 0,1,2 has length 2. Vertex 3 is isolated; there is no path from 0 to 3.

Six original practice questions

Choose exactly one option. These original introductory exercises are not previous-year questions, a full mock or complete GATE CS coverage. Use the stated graph model in each question.

1

A simple undirected graph has degrees 2, 3, 1, 3, 1. How many edges does it have?

A. 10 B. 3 C. 5 D. 4

2

In the first worked graph, A[0][4] = 0. Which conclusion is valid?

A. No path can connect 0 to 4. B. There is no direct edge {0,4}; the path 0,3,4 still exists. C. Vertex 4 does not exist. D. The shortest distance from 0 to 4 is zero.

3

For directed arcs 0->1, 0->2 and 2->1, using outgoing adjacency rows, what are vertex 1’s outdegree and indegree?

A. 2 and 0 B. 1 and 1 C. 2 and 2 D. 0 and 2

4

In the first graph’s converted Lists, degree[1] = 3 and neighbor[1] begins [0,2,3]. What does neighbor[1][1] mean?

A. The second listed neighbor of vertex 1 is vertex 2. B. Vertex 1 has a self-loop. C. Vertex 1 has degree 1. D. The distance from 1 to 1 is 2.

5

A simple undirected graph on 0,1,2,3 has only edges {0,2} and {1,2}. Which statement is correct?

A. It has one component because all four labels appear in storage. B. It has three components because 0 and 1 have no direct edge. C. It has two components, {0,1,2} and {3}; vertex 3 has an empty neighbor list. D. Vertex 3 must be deleted because its degree is zero.

6

Which storage statement is correct for the exact C program?

A. Its fixed neighbor rows automatically reserve only 2m integer slots. B. It reserves CAP squared neighbor slots plus CAP counts, although only degree[u] slots per row are active. C. Every zero in an unused row slot is a neighbor named 0. D. An adjacency-list representation always requires malloc and linked nodes.

Worked answers

1: C

A is incorrect: 10 is the sum of degrees, which counts each undirected edge at both endpoints.

B is incorrect: 3 is the maximum degree, not the total edge count.

C is correct: the degree sum is 10, so m = 10/2 = 5.

D is incorrect: n-1 = 4 would be a tree edge count for five vertices, but this graph need not be a tree.

2: B

A is incorrect: adjacency records direct edges, not all reachability.

B is correct: both {0,3} and {3,4} exist, giving a two-edge indirect path.

C is incorrect: n=5 includes vertex labels 0 through 4 regardless of a particular edge.

D is incorrect: this is an adjacency cell, not a distance; the distinct vertices are two edges apart.

3: D

A is incorrect: it reverses incoming and outgoing counts.

B is incorrect: no arc leaves 1, and two different arcs enter it.

C is incorrect: there is no automatic reverse arc in a directed graph.

D is correct: row 1 is all zero; column 1 has ones from vertices 0 and 2.

4: A

A is correct: the first index selects the vertex row; position 1 is its second entry, storing label 2.

B is incorrect: the second index is list position, not the other endpoint label. A self-loop would store label 1, which this graph forbids.

C is incorrect: degree[1], not the neighbor position, gives the count 3.

D is incorrect: neighbor rows store labels, not distances.

5: C

A is incorrect: allocated storage does not create paths.

B is incorrect: path 0,2,1 connects 0 and 1 indirectly.

C is correct: 0,1,2 are connected through 2; isolated 3 forms its own component.

D is incorrect: an isolated vertex is a legitimate graph member.

6: B

A is incorrect: 2m counts active neighbor entries; the fixed arrays reserve capacity even when few edges exist.

B is correct: the implementation uses fixed storage, and degree separates membership from unused cells.

C is incorrect: positions outside the active prefix are not members, regardless of their stored value.

D is incorrect: neighbor sequences can use arrays; this program allocates no dynamic memory.

Next step and scope

Next, use these explicit adjacency rules in BFS and DFS. Their visited state and chosen source determine traversal behavior; the representation alone does not. This original foundation does not change an existing course examination year or claim complete syllabus coverage. Hindi is learning support.