图算法

1 BFS

def BFS(G<V,E>, s) {
新建:队列Q
    前驱数组 pred[]
    距离数组 dist[]
    颜色数组 celor[]
    // 初始化
    for(u in V) {
        color[u] = white;
        pred[u] = NULL;
        dist[u] = INF;
    }
    color[s] = gray;
    dist[s] = 0;
    Q.add(s);
    while(Q != empty) {
        u = Q.pop();
        for(v in G中u相邻的点) {
        	if(color[v] == white) {
                color[v] = gray;
                pred[v] = u;
                dist[v] = dist[u] + 1;
                Q.add(v);
            }
        }
        color[u] = black;
    }
}

时间复杂度为：\(O(|V| + |E|)\)

2 DFS

def DFS_visit(G, u){
    color[u] = gray;
    time = time + 1;
    d[u] = time;
    for(w in G中u相邻的点) {
        pred[w] = u;
        DFS_visit(G, w);
    }
    color[u] = black;
    time = time + 1;
    f[u] = time;
}


def DFS(G){
 	新建:
    	color[]
        pred[]
    	发现时刻 d[]
        完成时刻 f[]
    for(u in V) {
        color[u] = white;
        pred[u] = NULL;
    }
    time = 0;
    for(u in V) {
        if(color[u] == white) {
			DFS_visit(G,u)
        }
    }
}

时间复杂度\(O(|V| + |E|)\)

树边、后向边、括号化定理、白色路径定理

3 环路检测

有向图存在环路 等价于 搜索时出现后向边

使用dfs判断即可，在每次看到一个点的时候，先看看它是不是灰色，是灰色说明返回true

4 拓扑排序

输入有向无环图(DAG图): G

//topo排序BFS版本
def TopoBFS(G){
    初始化队列Q
    for(v in V) {
        if(v的入度为0) {
        	Q.add(v);
        }
    }
    while(Q != empty) {
        u = Q.pop();
        print(u);
        for(w in G中于u相邻的点) {
            w的入度--;
            if (w的入度为0) {
            	Q.add(w);
            }
        }
    }
}

// topo排序DFS版本
def DFS_visit(G, u){
    color[u] = gray;
    for(w in G中u相邻的点) {
        L = DFS_visit(G, w);
    }
    color[u] = black;
	向L的结尾追加一个u; //因为u是最后完成的
    return L;
}


def DFS(G){
 	新建:
    	color[]
    for(u in V) {
        color[u] = white;
    }
    for(u in V) {
        if(color[u] == white) {
			L1 = DFS_visit(G,u)
        	向L的结尾追加L1;
        }
    }
    return L;
}

def TopoDFS(G){
    L = DFS(G);
    return L的逆序;
}

5 强连通分量

def DFS_visit(G, u){
    color[u] = gray;
    for(w in G中u相邻的点) {
        L = DFS_visit(G, w);
    }
    color[u] = black;
	向L的结尾追加一个u; //因为u是最后完成的
    return L;
}


def DFS(G){
 	新建:
    	color[]
    for(u in V) {
        color[u] = white;
    }
    for(u in V) {
        if(color[u] == white) {
			L1 = DFS_visit(G,u)
        	向L的结尾追加L1;
        }
    }
    return L;
}

def SCC() {
    R = {};
    G_R = G中所有边反向;
    L = DFS(G_R);
    // 按完成时间反向进行dfs
    for(i=L.length to 1) {
        u = L[i];
        if(color[u] == white) {
            L_scc = DFS-visit();
            R = R + set(L_scc);
        }
    }
    return R;
}

6 最小生成树：prim 和 kruskal

生成树：生成子图且是连通无环的

安全边

割：图