15% off all plans & roadmaps Use code
See plansOpening your learning path
Progress is saved as you study.
A graph is a set of vertices joined by edges. A vertex is one item, and an edge is one connection between two items. In an undirected graph, a vertex's degree counts the edge ends that touch it, and the graph is connected only when every vertex is reachable from one chosen vertex.
| Parts | Vertices V and edges E |
|---|---|
| Edge types | Undirected A-B, directed A->B, weighted (A-B labeled 7) |
| Degree | Number of incident edge ends; a self-loop adds 2 |
| Connected | Every vertex is reachable from one chosen vertex |
| Time and space | O(V + E) time to build neighbors and degrees and test connectivity, O(V) auxiliary space |
No prerequisites are required.
A graph describes a collection of named items and the connections between them.
For example, an undirected edge between A and B can be written as A-B. The order does not matter: A-B and B-A describe the same undirected connection.
The lesson uses an undirected, unweighted graph first. Directed and weighted graphs appear later.
For graph vocabulary and undirected-graph scope, see Undirected Graphs.
Use this graph throughout the lesson:
A, B, C, D, EA-B, A-C, B-D, C-DE has no edges.The lesson graph: edges A-B, A-C, B-D and C-D connect A, B, C and D, while E has no edges. N(A) = {B, C}, deg(A) = 2, and E is isolated with deg(E) = 0.
Write the graph as sets:
Do not infer edges from where vertices are drawn. Only the listed edges belong to the graph.
A vertex connected directly by an edge is a neighbor, also called an adjacent vertex.
For A:
The degree of a vertex in an undirected graph is the number of incident edge ends. Count how many edge ends touch that vertex.
Two edges touch A: A-B and A-C. Therefore:
Vertex E has no incident edges, so it is an isolated vertex:
Start from the stated vertices and edges.
| State | What we know |
|---|---|
| State 0 | Vertex set is {A,B,C,D,E}; edge set is {A-B,A-C,B-D,C-D}. |
| State 1 | Neighbors are N(A)={B,C}, N(B)={A,D}, N(C)={A,D}, N(D)={B,C}, N(E)={}. |
| State 2 | Degrees are deg(A)=2, deg(B)=2, deg(C)=2, deg(D)=2, deg(E)=0. |
| State 3 | A-B-C-D form reachable connections, but E cannot be reached from A. |
| State 4 | Classify the input as undirected, unweighted, disconnected, with no self-loops or parallel edges. |
Build State 1 one edge at a time.
Read A-B.
B to A's neighbors.A to B's neighbors.1N(A) = {B}
2N(B) = {A}Read A-C.
C to A's neighbors.A to C's neighbors.1N(A) = {B, C}
2N(B) = {A}
3N(C) = {A}Read B-D.
1N(B) = {A, D}
2N(D) = {B}Read C-D.
1N(C) = {A, D}
2N(D) = {B, C}No listed edge contains E.
1N(E) = {}Count each neighbor list for this graph. The counts produce State 2.
A path is a sequence of vertices where consecutive vertices share an edge. For example:
is a path because A-B and B-D are edges.
Starting at A, we can reach B, C, and then D. We cannot reach E, because no edge leads to it. Therefore the graph is disconnected.
An undirected graph is connected when every vertex can be reached from one chosen vertex through edges.
An edge can have direction or weight.
A-B is undirected. It connects both ways.A->B is directed. It goes from A to B; it does not also create B->A.A-B labeled 7 is weighted. The edge has weight 7.Graphs can also contain these features when their model permits them:
A-A.A-B.Look at one undirected edge, u-v.
Once that edge has been recorded correctly:
u appears among v's neighbors.v appears among u's neighbors.The relationship must remain true after every edge we process.
The invariant is:
For every undirected edge
u-v,uis a neighbor ofvandvis a neighbor ofu. A vertex's degree counts incident edge ends, so a self-loop contributes two to undirected degree.
A self-loop needs careful handling. For A-A, both ends of the edge touch A.
A is adjacent to itself.deg(A).Parallel edges are counted separately when they are permitted. Two occurrences of A-B give two incident edge ends at A and two at B.
Suppose the input is a vertex list and an undirected edge list.
To compute every neighbor list and degree:
0.u-v once.v as a neighbor of u.u as a neighbor of v.1.For a self-loop u-u, steps 4 and 5 both affect u, and step 6 increases degree[u] twice. That matches the degree definition.
To determine connectivity:
For the example, beginning at A reaches A, B, C, and D, but not E.
DESCRIBE_UNDIRECTED_GRAPH does not mutate the input vertex list or edge list.
The neighbor lists preserve edge-list order. A later caller may sort those lists if its output contract requires sorted neighbors.
1procedure DESCRIBE_UNDIRECTED_GRAPH(vertices, edges) -> (neighbors, degree, connected)
2 input:
3 vertices: nonempty list of distinct vertex labels
4 edges: list of undirected endpoint pairs (u, v);
5 every endpoint must appear in vertices
6 returns:
7 neighbors: map from each vertex to its list of incident neighbors
8 degree: map from each vertex to its undirected degree
9 connected: true exactly when every vertex is reachable
10 from vertices[0]
11 mutation:
12 does not modify vertices or edges
13
14 neighbors <- empty map
15 degree <- empty map
16
17 for each vertex u in vertices do
18 neighbors[u] <- empty list
19 degree[u] <- 0
20
21 for each edge (u, v) in edges do
22 append v to neighbors[u]
23 append u to neighbors[v]
24 degree[u] <- degree[u] + 1
25 degree[v] <- degree[v] + 1
26
27 start <- vertices[0]
28 reached <- set containing start
29 worklist <- stack containing start
30
31 while worklist is not empty do
32 u <- pop worklist
33
34 for each v in neighbors[u] do
35 if v is not in reached then
36 add v to reached
37 push v onto worklist
38
39 connected <- (size of reached = size of vertices)
40 return (neighbors, degree, connected)Helper contracts used here:
append x to list adds x at the end of that list.push adds one item to the stack.pop removes and returns one item from the stack.reached is a set, so adding a vertex already present does not create a second copy.Use:
1vertices = [A, B, C, D, E]
2edges = [(A, B), (A, C), (B, D), (C, D)]After the first for each vertex loop:
| Vertex | neighbors | degree |
|---|---|---|
| A | [] | 0 |
| B | [] | 0 |
| C | [] | 0 |
| D | [] | 0 |
| E | [] | 0 |
Read (A, B).
1neighbors[A] = [B]
2neighbors[B] = [A]
3degree[A] = 1
4degree[B] = 1Read (A, C).
1neighbors[A] = [B, C]
2neighbors[C] = [A]
3degree[A] = 2
4degree[C] = 1Read (B, D).
1neighbors[B] = [A, D]
2neighbors[D] = [B]
3degree[B] = 2
4degree[D] = 1Read (C, D).
1neighbors[C] = [A, D]
2neighbors[D] = [B, C]
3degree[C] = 2
4degree[D] = 2E was not part of any edge, so it remains:
1neighbors[E] = []
2degree[E] = 0The state matches States 1 and 2.
Set:
1start = A
2reached = {A}
3worklist = [A]Pop A.
1u = A
2worklist = []Inspect neighbors[A] = [B, C].
B is not reached. Add and push it.C is not reached. Add and push it.1reached = {A, B, C}
2worklist = [B, C]Pop C.
1u = C
2worklist = [B]Inspect neighbors[C] = [A, D].
A is already reached. Do nothing.D is not reached. Add and push it.1reached = {A, B, C, D}
2worklist = [B, D]Pop D.
1u = D
2worklist = [B]Inspect neighbors[D] = [B, C].
B is already reached.C is already reached.1reached = {A, B, C, D}
2worklist = [B]Pop B.
1u = B
2worklist = []Inspect neighbors[B] = [A, D].
A is already reached.D is already reached.The worklist is now empty.
1size(reached) = 4
2size(vertices) = 5
3connected = falseE was never reached, so the graph is disconnected.
Consider the edge-processing loop first.
Before reading any edges:
0.No processed edge exists yet, so the symmetric-adjacency rule is true vacuously. The degree counters correctly describe zero processed incident edge ends.
Assume the rule is true after some number of edges.
Now process one undirected edge u-v.
v to neighbors[u].u to neighbors[v].The newly processed edge is recorded symmetrically.
The algorithm also increases degree[u] and degree[v] once each. Each ordinary edge contributes one incident end to each endpoint. If u and v are the same vertex, both increments apply to that one vertex, so a self-loop contributes two.
Previously processed edges are unchanged. The rule remains true.
The loop processes every listed edge exactly once. By the invariant, all listed undirected edges are represented symmetrically, and every degree counter equals the number of incident edge ends. Therefore the returned neighbor lists and degrees are correct.
For connectivity, reached begins with the chosen start vertex. Whenever the algorithm sees an edge from a reached vertex to an unreached neighbor, it adds that neighbor. Every marked vertex has a path from the start.
When the worklist becomes empty, every neighbor of every reached vertex has been inspected. If an unreached vertex had a path from the start, the first unreached vertex on that path would have been discovered from a reached predecessor. That is impossible at termination. Therefore reached contains exactly the vertices reachable from the start.
The final size comparison is true exactly when every vertex is reachable, which is the required connectedness test for this undirected graph.
For degree computation from an edge list:
So computing all undirected degrees takes:
time.
The degree-counter array or map holds one counter for each vertex:
auxiliary space.
The input graph is not counted as auxiliary space.
The connectivity portion uses a reached set and worklist that can each hold up to vertices. It examines neighbor-list entries created from the edge list. In an undirected graph, the lists contain two entries per ordinary edge, so the traversal performs work and uses auxiliary space.
Incorrect assumption: “Vertices drawn near each other must be connected.”
Exposing input:
1V = {A, B}
2E = {}Wrong result: Report A-B because A and B appear close in a drawing.
Correction: Use only explicit edges from the drawing or edge list. Here, both vertices are isolated.
Incorrect assumption: A->B also creates B->A.
Exposing input:
1directed edge: A->BWrong result: List A as an outgoing neighbor of B.
Correction: Preserve the arrow. A has an outgoing connection to B; B does not have an outgoing connection to A.
Incorrect assumption: “A graph containing isolated E is invalid for traversal.”
Exposing input:
1V = {A, B, E}
2E = {A-B}Wrong result: Reject the graph instead of describing it.
Correction: E is valid. Its neighbor list is empty and its degree is 0. Its presence makes the graph disconnected.
Incorrect assumption: “If some vertices form a cycle, the graph is connected.”
Exposing input:
1V = {A, B, C, D}
2E = {A-B, B-C, C-A}Wrong result: Report connected because A-B-C-A is a cycle.
Correction: Start at A. You reach A, B, and C, but never D. Every vertex must be reachable.
Incorrect update for edge (A, A):
1degree[A] <- degree[A] + 1Exposing input:
1V = {A}
2E = {A-A}Wrong result: degree[A] = 1.
Correction: A loop has two incident edge ends at A, so increment the degree twice. The correct degree is 2.
| Input | Expected result |
|---|---|
V={A}, E={} | One-vertex graph; connected under the usual reachability definition; degree(A)=0. |
V={A,B}, E={} | Disconnected; both vertices are isolated. |
Directed edge A->B | A has an outgoing connection to B; B does not have one to A. |
Undirected self-loop A-A | A is adjacent to itself; the loop contributes two to undirected degree. |
Two listed edges A-B and A-B | Identify parallel edges if the graph model permits them. |
Executable objective: Given a JSON vertex list and edge list for an undirected graph, return each vertex's sorted neighbor list and degree, and report whether every vertex is reachable from the first vertex.
The practice contract tests that you:
1def describe(vertices, edges):
2 neighbors = {v: [] for v in vertices}
3 degree = {v: 0 for v in vertices}
4 for u, v in edges:
5 neighbors[u].append(v)
6 neighbors[v].append(u)
7 degree[u] += 1 # a self-loop (u == v) hits this twice
8 degree[v] += 1
9 start = vertices[0]
10 reached = {start}
11 stack = [start]
12 while stack:
13 u = stack.pop()
14 for v in neighbors[u]:
15 if v not in reached:
16 reached.add(v)
17 stack.append(v)
18 return neighbors, degree, len(reached) == len(vertices)
19
20vertices = ["A", "B", "C", "D", "E"]
21edges = [("A", "B"), ("A", "C"), ("B", "D"), ("C", "D")]
22neighbors, degree, connected = describe(vertices, edges)
23for v in vertices:
24 print(f"{v}: [{', '.join(neighbors[v])}] deg {degree[v]}")
25print("connected:", "true" if connected else "false")1import java.util.*;
2
3public class Main {
4 public static void main(String[] args) {
5 String[] vertices = {"A", "B", "C", "D", "E"};
6 String[][] edges = {{"A", "B"}, {"A", "C"}, {"B", "D"}, {"C", "D"}};
7
8 Map<String, List<String>> neighbors = new LinkedHashMap<>();
9 Map<String, Integer> degree = new LinkedHashMap<>();
10 for (String v : vertices) {
11 neighbors.put(v, new ArrayList<>());
12 degree.put(v, 0);
13 }
14 for (String[] e : edges) {
15 neighbors.get(e[0]).add(e[1]);
16 neighbors.get(e[1]).add(e[0]);
17 degree.merge(e[0], 1, Integer::sum); // a self-loop hits this twice
18 degree.merge(e[1], 1, Integer::sum);
19 }
20
21 Set<String> reached = new HashSet<>();
22 Deque<String> stack = new ArrayDeque<>();
23 reached.add(vertices[0]);
24 stack.push(vertices[0]);
25 while (!stack.isEmpty()) {
26 String u = stack.pop();
27 for (String v : neighbors.get(u)) {
28 if (reached.add(v)) stack.push(v);
29 }
30 }
31
32 for (String v : vertices) {
33 System.out.println(v + ": " + neighbors.get(v) + " deg " + degree.get(v));
34 }
35 System.out.println("connected: " + (reached.size() == vertices.length));
36 }
37}1#include <iostream>
2#include <map>
3#include <set>
4#include <string>
5#include <vector>
6using namespace std;
7
8int main() {
9 vector<string> vertices = {"A", "B", "C", "D", "E"};
10 vector<pair<string, string>> edges = {{"A", "B"}, {"A", "C"}, {"B", "D"}, {"C", "D"}};
11
12 map<string, vector<string>> neighbors;
13 map<string, int> degree;
14 for (const string& v : vertices) {
15 neighbors[v];
16 degree[v] = 0;
17 }
18 for (const auto& e : edges) {
19 neighbors[e.first].push_back(e.second);
20 neighbors[e.second].push_back(e.first);
21 degree[e.first]++; // a self-loop hits this twice
22 degree[e.second]++;
23 }
24
25 set<string> reached = {vertices[0]};
26 vector<string> stack = {vertices[0]};
27 while (!stack.empty()) {
28 string u = stack.back();
29 stack.pop_back();
30 for (const string& v : neighbors[u]) {
31 if (reached.insert(v).second) stack.push_back(v);
32 }
33 }
34
35 for (const string& v : vertices) {
36 cout << v << ": [";
37 for (size_t i = 0; i < neighbors[v].size(); i++) cout << (i ? ", " : "") << neighbors[v][i];
38 cout << "] deg " << degree[v] << "\n";
39 }
40 cout << "connected: " << (reached.size() == vertices.size() ? "true" : "false") << endl;
41}1const vertices = ['A', 'B', 'C', 'D', 'E'];
2const edges = [['A', 'B'], ['A', 'C'], ['B', 'D'], ['C', 'D']];
3
4const neighbors = new Map(vertices.map((v) => [v, []]));
5const degree = new Map(vertices.map((v) => [v, 0]));
6for (const [u, v] of edges) {
7 neighbors.get(u).push(v);
8 neighbors.get(v).push(u);
9 degree.set(u, degree.get(u) + 1); // a self-loop hits this twice
10 degree.set(v, degree.get(v) + 1);
11}
12
13const reached = new Set([vertices[0]]);
14const stack = [vertices[0]];
15while (stack.length > 0) {
16 const u = stack.pop();
17 for (const v of neighbors.get(u)) {
18 if (!reached.has(v)) {
19 reached.add(v);
20 stack.push(v);
21 }
22 }
23}
24
25for (const v of vertices) {
26 console.log(`${v}: [${neighbors.get(v).join(', ')}] deg ${degree.get(v)}`);
27}
28console.log(`connected: ${reached.size === vertices.length}`);It is a set of edges in a connected, weighted, undirected graph that links every vertex with no cycle and the smallest total weight. This lesson does not build one. The weighted graph lesson covers the edge weights it relies on.
Undirected, directed and weighted. An undirected edge A-B works both ways, a directed edge A->B goes one way only, and a weighted edge carries a number such as 7. A graph can also have self-loops or parallel edges when its model permits them.
Keep a map from each vertex to a list of neighbors. For each undirected edge u-v, add v to u's list and u to v's list. The program above does this with a LinkedHashMap of ArrayLists in O(V + E) time.
In a connected graph every vertex is reachable from one chosen vertex. In the example, A reaches B, C and D but never E, so the graph is disconnected. A cycle among some vertices does not make the whole graph connected.
Twice, in an undirected graph. Both ends of the edge A-A touch A, so degree(A) is 2. Counting it once is a common bug.