如何从节点边权列表生成邻接矩阵？

Got it, let's walk through how to convert your edge list into an adjacency matrix. This approach works efficiently even for large datasets, and I'll use Python since it's straightforward for this kind of data manipulation.

Step-by-Step Breakdown #

• Extract Unique Nodes: First, we need to gather all distinct nodes from your edge list. Sorting them is optional but makes the matrix easier to read and consistent.
• Map Nodes to Indices: Create a dictionary to map each node name to a numerical index—this lets us quickly find where each node sits in the matrix.
• Initialize the Matrix: Create an n×n matrix (where n is the number of unique nodes) with a default value (usually 0 for no connection, or float('inf') if you want to represent unreachable nodes).
• Populate Weights: Iterate through each edge in your list, use the index mapping to place the weight in the correct position. If your graph is undirected (edges work both ways), don't forget to fill both symmetric positions.

Example Code #

# Your edge list (scaled example; works for full-size list too)
edge_list = [['10', '20', 2], ['10', '21', 2], ['10', '1', 2], ['10', '0', 3],
             ['1', '20', 3], ['1', '21', 3], ['1', '1', 3], ['1', '0', 0]]

# 1. Get all unique nodes and sort for consistency
nodes = sorted({node for edge in edge_list for node in edge[:2]})
num_nodes = len(nodes)

# 2. Create node-to-index mapping
node_index = {node: idx for idx, node in enumerate(nodes)}

# 3. Initialize adjacency matrix (default to 0; use float('inf') for unreachable)
adj_matrix = [[0]*num_nodes for _ in range(num_nodes)]

# 4. Fill the matrix with edge weights
for u, v, weight in edge_list:
    u_idx = node_index[u]
    v_idx = node_index[v]
    adj_matrix[u_idx][v_idx] = weight
    # Uncomment this line if your graph is undirected (bidirectional edges)
    # adj_matrix[v_idx][u_idx] = weight

# Optional: Print with node labels for clarity
print("Nodes:", nodes)
print("\nAdjacency Matrix:")
for row in adj_matrix:
    print(row)

Key Notes #

• Handling Large Data: Using sets to extract nodes is O(m) time (m = number of edges), which is efficient even for huge lists. The matrix initialization is O(n²), which is standard for adjacency matrices.
• Default Value Choice: Use 0 if a weight of 0 means "no edge" (but be careful if your edges can have 0 weight—then use float('inf') instead).
• Node Types: This code works for string or numeric node names, no changes needed.

内容的提问来源于stack exchange，提问作者Favites Test