连通分量转邻接矩阵及16×16邻接矩阵相关技术咨询

Let’s break this down into two clear, actionable parts to help you out.

1. Converting Connected Components to an Adjacency Matrix #

First, quick recap: connected components are groups of nodes where every node in the group is reachable from every other node in the group, with no connections to nodes outside the group. How you convert these to an adjacency matrix depends on what you want the matrix to represent—here are two common scenarios:

Scenario A: Build a matrix where each component is a complete subgraph (clique) #

If you want every node in the same connected component to have a direct edge to every other node in that component (useful for simplifying connectivity analysis), follow these steps:

• Step 1: Initialize an N×N matrix (where N is your total number of nodes) filled with 0s.
• Step 2: For each connected component (e.g., a list like [0,1,2,3]):
  • Loop through every pair of distinct nodes u and v in the component.
  • Set matrix[u][v] = 1 and matrix[v][u] = 1 (skip the second assignment if working with directed graphs, since edges only go one way).
• Step 3: (Optional) If self-loops are allowed, set matrix[u][u] = 1 for each node u (this is rare for connected components unless specified).

Scenario B: Build a component-level adjacency matrix #

If you want to represent the graph at the component level (each matrix node stands for one connected component, edges represent connections between components):

• Step 1: Assign each connected component a unique ID (e.g., Component 0, Component 1, etc.).
• Step 2: Initialize an M×M matrix (where M is the number of connected components) filled with 0s.
• Step 3: For every pair of components C1 and C2:
  • If there’s at least one edge between any node in C1 and any node in C2 in the original graph, set matrix[ID(C1)][ID(C2)] = 1 (and matrix[ID(C2)][ID(C1)] =1 for undirected graphs).

2. Guidance for Your 16×16 Adjacency Matrix #

Looking at your snippet, let’s parse what this matrix represents:

• Node 0 is connected to nodes 1 and 15.
• Nodes 1–8 form a linear chain: node 1 ↔ node 2, node2 ↔ node3, ..., node7 ↔ node8.
• Node8 only connects back to node7.

Assuming the unshown rows (9–14) are all 0s, this is a graph combining a path (0→1→2→...→8) with an extra edge from node0 to node15. Nodes9–14 would be isolated unless you add edges for them.

Here are some common tasks you might want to do with this matrix:

Analyze connectivity #

• To find all connected components, run a BFS or DFS starting from each unvisited node. For your snippet, nodes 0–8 and15 form one component; nodes9–14 are isolated if they have no edges.
• Check if the matrix is symmetric (e.g., row0 has a 1 at column15, so row15 should have a1 at column0) to confirm it’s an undirected graph.

Modify the matrix #

• To add an edge between node9 and node10: set Adjacency[9][10] =1 and Adjacency[10][9] =1.
• To remove the edge between node0 and15: set Adjacency[0][15] =0 and Adjacency[15][0] =0.

Python code example to work with your matrix #

Here’s a quick snippet to initialize your matrix and find connected components:

# Initialize your 16x16 matrix (filling unshown rows with 0s)
adjacency = [
    [0,1,0,0,0,0,0,0,0,0,0,0,0,0,0,1],
    [1,0,1,0,0,0,0,0,0,0,0,0,0,0,0,0],
    [0,1,0,1,0,0,0,0,0,0,0,0,0,0,0,0],
    [0,0,1,0,1,0,0,0,0,0,0,0,0,0,0,0],
    [0,0,0,1,0,1,0,0,0,0,0,0,0,0,0,0],
    [0,0,0,0,1,0,1,0,0,0,0,0,0,0,0,0],
    [0,0,0,0,0,1,0,1,0,0,0,0,0,0,0,0],
    [0,0,0,0,0,0,1,0,1,0,0,0,0,0,0,0],
    [0,0,0,0,0,0,0,1,0,0,0,0,0,0,0,0],
    [0]*16, [0]*16, [0]*16, [0]*16, [0]*16, [0]*16, [0]*16
]

def find_connected_components(adj):
    n = len(adj)
    visited = [False]*n
    components = []
    for i in range(n):
        if not visited[i]:
            queue = [i]
            visited[i] = True
            component = []
            while queue:
                node = queue.pop(0)
                component.append(node)
                for neighbor in range(n):
                    if adj[node][neighbor] ==1 and not visited[neighbor]:
                        visited[neighbor] = True
                        queue.append(neighbor)
            components.append(component)
    return components

print(find_connected_components(adjacency))
# Output: [[0,1,2,3,4,5,6,7,8,15], [9], [10], [11], [12], [13], [14]]

内容的提问来源于stack exchange，提问作者eric lardon