数据结构和算法

DSA - 主页 DSA - 概述 DSA - 环境设置 DSA - 算法基础 DSA - 渐近分析

数据结构

DSA - 数据结构基础 DSA - 数据结构和类型 DSA - 数组数据结构

链接列表

DSA - 链接列表数据结构 DSA - 双向链接列表数据结构 DSA - 循环链表数据结构

堆栈 &队列

DSA - 堆栈数据结构 DSA - 表达式解析 DSA - 队列数据结构

搜索算法

DSA - 搜索算法 DSA - 线性搜索算法 DSA - 二分搜索算法 DSA - 插值搜索 DSA - 跳跃搜索算法 DSA - 指数搜索 DSA - 斐波那契搜索 DSA - 子列表搜索 DSA - 哈希表

排序算法

DSA - 排序算法 DSA - 冒泡排序算法 DSA - 插入排序算法 DSA - 选择排序算法 DSA - 归并排序算法 DSA - 希尔排序算法 DSA - 堆排序 DSA - 桶排序算法 DSA - 计数排序算法 DSA - 基数排序算法 DSA - 快速排序算法

图形数据结构

DSA - 图形数据结构 DSA - 深度优先遍历 DSA - 广度优先遍历 DSA - 生成树

树数据结构

DSA - 树数据结构 DSA - 树遍历 DSA - 二叉搜索树 DSA - AVL 树 DSA - 红黑树 DSA - B树 DSA - B+ 树 DSA - 伸展树 DSA - 尝试 DSA - 堆数据结构

递归

DSA - 递归算法 DSA - 使用递归的汉诺塔 DSA - 使用递归的斐波那契数列

分而治之

DSA - 分而治之 DSA - 最大最小问题 DSA - 施特拉森矩阵乘法 DSA - Karatsuba 算法

贪婪算法

DSA - 贪婪算法 DSA - 旅行商问题(贪婪方法) DSA - Prim 最小生成树 DSA - Kruskal 最小生成树 DSA - Dijkstra 最短路径算法 DSA - 地图着色算法 DSA - 分数背包问题 DSA - 作业排序截止日期 DSA - 最佳合并模式算法

动态规划

DSA - 动态规划 DSA - 矩阵链乘法 DSA - Floyd Warshall 算法 DSA - 0-1 背包问题 DSA - 最长公共子序列算法 DSA - 旅行商问题(动态方法)

近似算法

DSA - 近似算法 DSA - 顶点覆盖算法 DSA - 集合覆盖问题 DSA - 旅行商问题(近似方法)

随机算法

DSA - 随机算法 DSA - 随机快速排序算法 DSA - Karger 最小割算法 DSA - Fisher-Yates 洗牌算法

DSA 有用资源

DSA - 问答 DSA - 快速指南 DSA - 有用资源 DSA - 讨论


Vertex Cover Algorithm



Have you ever wondered about the placement of traffic cameras? That how they are efficiently placed without wasting too much budget from the government? The answer to that comes in the form of vertex-cover algorithm. The positions of the cameras are chosen in such a way that one camera covers as many roads as possible, i.e., we choose junctions and make sure the camera covers as much area as possible.

A vertex-cover of an undirected graph G = (V,E) is the subset of vertices of the graph such that, for all the edges (u,v) in the graph,u and v ∈ V. The junction is treated as the node of a graph and the roads as the edges. The algorithm finds the minimum set of junctions that cover maximum number of roads.

It is a minimization problem since we find the minimum size of the vertex cover – the size of the vertex cover is the number of vertices in it. The optimization problem is an NP-Complete problem and hence, cannot be solved in polynomial time; but what can be found in polynomial time is the near optimal solution.

Vertex Cover Algorithm

The vertex cover approximation algorithm takes an undirected graph as an input and is executed to obtain a set of vertices that is definitely twice as the size of optimal vertex cover.

The vertex cover is a 2-approximation algorithm.

Algorithm

Step 1 − Select any random edge from the input graph and mark all the edges that are incident on the vertices corresponding to the selected edge.

Step 2 − Add the vertices of the arbitrary edge to an output set.

Step 3 − Repeat Step 1 on the remaining unmarked edges of the graph and add the vertices chosen to the output until there’s no edge left unmarked.

Step 4 − The final output set achieved would be the near-optimal vertex cover.

Pseudocode

APPROX-VERTEX_COVER (G: Graph)
c ← { }
E’ ← E[G]
while E’ is not empty do
   Let (u, v) be an arbitrary edge of E’
   c ← c U {u, v}
   Remove from E’ every edge incident on either u or v
return c

Example

The set of edges of the given graph is −

{(1,6),(1,2),(1,4),(2,3),(2,4),(6,7),(4,7),(7,8),(3,5),(8,5)}
Vertex_Cover_Problem

Now, we start by selecting an arbitrary edge (1,6). We eliminate all the edges, which are either incident to vertex 1 or 6 and we add edge (1,6) to cover.

arbitrary_edge

In the next step, we have chosen another edge (2,3) at random.

chosen_another_edge

Now we select another edge (4,7).

select_another_edge

We select another edge (8,5).

another edge 8 to 5

Hence, the vertex cover of this graph is {1,6,2,3,4,7,5,8}.

Analysis

It is easy to see that the running time of this algorithm is O(V + E), using adjacency list to represent E'.

Implementation

Following are the implementations of the above approach in various programming langauges −

#include <stdio.h>
#include <stdbool.h>
#define MAX_VERTICES 100
int graph[MAX_VERTICES][MAX_VERTICES];
bool included[MAX_VERTICES];
// Function to find Vertex Cover using the APPROX-VERTEX_COVER algorithm
void approxVertexCover(int vertices, int edges) {
   bool edgesRemaining[MAX_VERTICES][MAX_VERTICES];
   for (int i = 0; i < vertices; i++) {
      for (int j = 0; j < vertices; j++) {
         edgesRemaining[i][j] = graph[i][j];
      }
   }
   while (edges > 0) {
      int u, v;
      for (int i = 0; i < vertices; i++) {
         for (int j = 0; j < vertices; j++) {
            if (edgesRemaining[i][j]) {
               u = i;
               v = j;
               break;
            }
         }
      }
      included[u] = included[v] = true;
      for (int i = 0; i < vertices; i++) {
         edgesRemaining[u][i] = edgesRemaining[i][u] = false;
         edgesRemaining[v][i] = edgesRemaining[i][v] = false;
      }
      edges--;
   }
}
int main() {
   int vertices = 8;
   int edges = 10;
   int edgesData[10][2] = {
   {1, 6}, {1, 2}, {1, 4}, {2, 3}, {2, 4},
   {6, 7}, {4, 7}, {7, 8}, {3, 5}, {8, 5}};
   for (int i = 0; i < edges; i++) {
      int u = edgesData[i][0];
      int v = edgesData[i][1];
      graph[u][v] = graph[v][u] = 1;
   }
   approxVertexCover(vertices, edges);
   printf("Vertex Cover: ");
   for (int i = 1; i <= vertices; i++) {
      if (included[i]) {
         printf("%d ", i);
      }
   }
   printf("
");
   return 0;
}

Output

Vertex Cover: 1 3 4 5 6 7 
#include <iostream>
#include <vector>
using namespace std;
const int MAX_VERTICES = 100;
vector<vector<int>> graph(MAX_VERTICES, vector<int>(MAX_VERTICES, 0));
vector<bool> included(MAX_VERTICES, false);
// Function to find Vertex Cover using the APPROX-VERTEX_COVER algorithm
void approxVertexCover(int vertices, int edges) {
   vector<vector<bool>> edgesRemaining(vertices, vector<bool>(vertices, false));
   for (int i = 0; i < vertices; i++) {
      for (int j = 0; j < vertices; j++) {
         edgesRemaining[i][j] = graph[i][j];
      }
   }
   while (edges > 0) {
      int u, v;
      for (int i = 0; i < vertices; i++) {
         for (int j = 0; j < vertices; j++) {
            if (edgesRemaining[i][j]) {
               u = i;
               v = j;
               break;
            }
         }
      }
      included[u] = included[v] = true;
      for (int i = 0; i < vertices; i++) {
         edgesRemaining[u][i] = edgesRemaining[i][u] = false;
         edgesRemaining[v][i] = edgesRemaining[i][v] = false;
      }
      edges--;
   }
}
int main() {
   int vertices = 8;
   int edges = 10;
   int edgesData[10][2] = {
   {1, 6}, {1, 2}, {1, 4}, {2, 3}, {2, 4},
   {6, 7}, {4, 7}, {7, 8}, {3, 5}, {8, 5}};
   for (int i = 0; i < edges; i++) {
      int u = edgesData[i][0];
      int v = edgesData[i][1];
      graph[u][v] = graph[v][u] = 1;
   }
   approxVertexCover(vertices, edges);
   cout << "Vertex Cover: ";
   for (int i = 1; i <= vertices; i++) {
      if (included[i]) {
         cout << i << " ";
      }
   }
   cout << endl;
   return 0;
}

Output

Vertex Cover: 1 3 4 5 6 7 
import java.util.ArrayList;
import java.util.List;
public class Main {
   static final int MAX_VERTICES = 100;
   static int[][] graph = new int[MAX_VERTICES][MAX_VERTICES];
   static boolean[] included = new boolean[MAX_VERTICES];
   public static void approx_vertex_cover(int vertices, int edges) {
      int[][] edges_remaining = new int[MAX_VERTICES][MAX_VERTICES];
      for (int i = 0; i < vertices; i++) {
         for (int j = 0; j < vertices; j++) {
            edges_remaining[i][j] = graph[i][j];
         }
      }
      while (edges > 0) {
         int u = 1, v = 1;
         for (int i = 0; i < vertices; i++) {
            for (int j = 0; j < vertices; j++) {
               if (edges_remaining[i][j] != 0) {
                  u = i;
                  v = j;
                  break;
               }
            }
         }
         included[u] = included[v] = true;
         for (int i = 0; i < vertices; i++) {
            edges_remaining[u][i] = edges_remaining[i][u] = 0;
            edges_remaining[v][i] = edges_remaining[i][v] = 0;
         }
         edges--;
    }
}
public static void main(String[] args) {
   int vertices = 8;
   int edges = 10;
   List<int[]> edges_data = new ArrayList<>();
   edges_data.add(new int[] {1, 6});
   edges_data.add(new int[] {1, 2});
   edges_data.add(new int[] {1, 4});
   edges_data.add(new int[] {2, 3});
   edges_data.add(new int[] {2, 4});
   edges_data.add(new int[] {6, 7});
   edges_data.add(new int[] {4, 7});
   edges_data.add(new int[] {7, 8});
   edges_data.add(new int[] {3, 5});
   edges_data.add(new int[] {8, 5});
   for (int[] edge : edges_data) {
      int u = edge[0];
      int v = edge[1];
      graph[u][v] = graph[v][u] = 1;
}
approx_vertex_cover(vertices, edges);
System.out.print("Vertex Cover: ");
for (int i = 1; i <= vertices; i++) {
   if (included[i]) {
      System.out.print(i + " ");
   }
}
System.out.println();
}
}

Output

Vertex Cover: 1 3 4 5 6 7 
MAX_VERTICES = 100
graph = [[0 for _ in range(MAX_VERTICES)] for _ in range(MAX_VERTICES)]
included = [False for _ in range(MAX_VERTICES)]
# Function to find Vertex Cover using the APPROX-VERTEX_COVER algorithm
def approx_vertex_cover(vertices, edges):
    edges_remaining = [row[:] for row in graph]
    while edges > 0:
        for i in range(vertices):
            for j in range(vertices):
                if edges_remaining[i][j]:
                    u = i
                    v = j
                    break
        included[u] = included[v] = True
        for i in range(vertices):
            edges_remaining[u][i] = edges_remaining[i][u] = False
            edges_remaining[v][i] = edges_remaining[i][v] = False
        edges -= 1
if __name__ == "__main__":
    vertices = 8
    edges = 10
    edges_data = [(1, 6), (1, 2), (1, 4), (2, 3), (2, 4),
                  (6, 7), (4, 7), (7, 8), (3, 5), (8, 5)]
    for u, v in edges_data:
        graph[u][v] = graph[v][u] = 1
    approx_vertex_cover(vertices, edges)
    print("Vertex Cover:", end=" ")
    for i in range(1, vertices + 1):
        if included[i]:
            print(i, end=" ")
    print()

Output

Vertex Cover: 1 3 4 5 6 7