How is an adjacency matrix used to represent a graph?

Question

BlackTom AI · Accepted Answer

An adjacency matrix represents a graph by assigning each vertex to a row and column of an n × n matrix and recording edge presence or weight in the corresponding cell.

1. Relevant knowledge points and concepts
- Graphs have vertices (nodes) and edges (connections).  
- An adjacency matrix for a graph with n vertices is an n × n 2D array (matrix).  
- For an unweighted graph, entry a[i][j] = 1 if there is an edge from vertex i to vertex j, and 0 otherwise. For weighted graphs, a[i][j] holds the weight (or a sentinel like ∞ if no edge).  
- For undirected graphs the matrix is symmetric (a[i][j] = a[j][i]). For directed graphs it may be asymmetric. Diagonal entries represent self-loops.

2. Step-by-step reasoning process
- Label vertices with indices 0..n-1 (or A..).  
- Initialize an n × n 2D array with zeros.  
- For each edge (u,v), set matrix[u][v] = 1 (and matrix[v][u] = 1 if undirected).  
- To check if an edge exists between i and j, read matrix[i][j] in O(1) time.

3. Example with intermediate steps
Graph: vertices A,B,C with edges A–B and B–C (undirected). Map A→0, B→1, C→2. Start with 3×3 zeros:
[ [0,0,0],
  [0,0,0],
  [0,0,0] ]
Process edge A–B: set [0][1]=1 and [1][0]=1:
[ [0,1,0],
  [1,0,0],
  [0,0,0] ]
Process edge B–C: set [1][2]=1 and [2][1]=1:
[ [0,1,0],
  [1,0,1],
  [0,1,0] ]

4. Why the correct answer is correct
This procedure uses a 2D array where each element directly indicates the presence (or weight) of an edge between the pair of nodes, which matches the provided correct option.

5. Why the other options are incorrect
- "A list of lists where each inner list represents edges": describes an adjacency list, not the adjacency matrix.  
- "A single list to represent all edges": insufficient structure to index pairs of vertices; not an adjacency matrix.  
- "A dictionary of nodes": could represent adjacency information (adjacency map) but is not the 2D array structure that an adjacency matrix uses.

6. Conclusion
The correct representation is: "By using a 2D array where each element indicates the presence of an edge between nodes," which matches the provided answer.

How is an adjacency matrix used to represent a graph?单项选择题

类似问题

Using the adjacency matrix representation of a graph, how long does it take (number of checks) to iterate over the vertices adjacent to a vertex v in a graph with V vertices and E edges?

You own a bond that pays $64 in interest annually. The face value is $1,000 and the current market price is $1,021.61. The bond matures in 11 years. What is the yield to maturity?

Which of the following statements is CORRECT?

It will cost $9,600 to acquire an ice cream cart that is expected to produce cash inflows of $3,600 a year for three years. After the three years, the cart is expected to be worthless. What is the payback period?

更多留学生实用工具

智能学习助手

风格化写作助手

论文查重助手

文献引用助手

课堂转译助手

课堂笔记助手

Quiz搜索助手

学校历年真题

智能刷题助手

智能匹配练习

希望你的学习变得更简单