这是一个关于图的练习题。
给定一个有n个点和m条边的无向图G,以及一个整数k,设计一个O(m+n)算法,找出G的最大诱导子图H,满足H中每个顶点的度≥k,或者证明不存在这样的图。 图G的诱导子图F = (U, R) 是指由G的一个子集U构成的子图,并且包含U中所有在G中相邻的点之间的边R。
我的初始想法如下:
首先,这个练习实际上要求我们找到所有度数大于或等于k的顶点S,然后删除S中没有与其他顶点相连的顶点。然后经过筛选的S就是H,其中所有顶点的度数都≥k,它们之间的边为R。
此外,它要求O(m+n),因此我认为需要使用BFS或DFS。但我卡住了。
在BFS中,我可以知道一个顶点的度数。但是一旦我得到v(一个顶点)的度数,除了其父节点之外,我不知道其他相邻的顶点。但如果父节点的度数不≥k,则无法将v排除,因为它仍可能与其他顶点相连。
有什么提示吗?
编辑:
根据@Michael J. Barber的答案,我实现了代码并将关键方法public Graph kCore(Graph g, int k)
更新在此处。请问我的实现正确吗?它是O(m+n)吗?
class EdgeNode {
EdgeNode next;
int y;
}
public class Graph {
public EdgeNode[] edges;
public int numVertices;
public boolean directed;
public Graph(int _numVertices, boolean _directed) {
numVertices = _numVertices;
directed = _directed;
edges = new EdgeNode[numVertices];
}
public void insertEdge(int x, int y) {
insertEdge(x, y, directed);
}
public void insertEdge(int x, int y, boolean _directed) {
EdgeNode edge = new EdgeNode();
edge.y = y;
edge.next = edges[x];
edges[x] = edge;
if (!_directed)
insertEdge(y, x, true);
}
public Graph kCore(Graph g, int k) {
int[] degree = new int[g.numVertices];
boolean[] deleted = new boolean[g.numVertices];
int numDeleted = 0;
updateAllDegree(g, degree);// get all degree info for every vertex
for (int i = 0;i < g.numVertices;i++) {
**if (!deleted[i] && degree[i] < k) {
deleteVertex(p.y, deleted, g);
}**
}
//Construct the kCore subgraph
Graph h = new Graph(g.numVertices - numDeleted, false);
for (int i = 0;i < g.numVertices;i++) {
if (!deleted[i]) {
EdgeNode p = g[i];
while(p!=null) {
if (!deleted[p.y])
h.insertEdge(i, p.y, true); // I just insert the good edge as directed, because i->p.y is inserted and later p.y->i will be inserted too in this loop.
p = p.next;
}
}
}
}
return h;
}
**private void deleteVertex(int i, boolean[] deleted, Graph g) {
deleted[i] = true;
EdgeNode p = g[i];
while(p!=null) {
if (!deleted[p.y] && degree[p.y] < k)
deleteVertex(p.y, deleted, g);
p = p.next;
}
}**
private void updateAllDegree(Graph g, int[] degree) {
for(int i = 0;i < g.numVertices;i++) {
EdgeNode p = g[i];
while(p!=null) {
degree[i] += 1;
p = p.next;
}
}
}
}
->}