Graph Bandwidth Greedy

Problem

Build a vertex ordering with a Cuthill-McKee style BFS and measure its bandwidth.

Start from the smallest-index minimum-degree node. Add nodes in BFS order, pushing each node's unvisited neighbors sorted by degree then index. The bandwidth is the largest absolute difference between the positions of an edge's endpoints. Return [order, bandwidth]. edges is a list of [u, v] pairs.

Hint

Good orderings place connected nodes close together, keeping the bandwidth small.

Test cases

case 1

in: [4,[[0,1],[1,2],[2,3]]]

expected: [[0,1,2,3],1]

case 2

in: [4,[[0,1],[0,2],[0,3]]]

expected: [[1,0,2,3],2]

case 3

in: [4,[[0,1],[1,2],[2,3],[3,0]]]

expected: [[0,1,3,2],2]

case 4

in: [5,[[0,1],[1,2],[2,3],[3,4]]]

expected: [[0,1,2,3,4],1]

Starter codePython

def greedy_bandwidth(n, edges):
    # Your code here
    pass

4 test cases · run your code against them in the editor