面试笔试中算法题复习之图问题

发表于 | 分类于 | 阅读次数

最近笔试遇到好多图的问题，将笔试常见的套路算法和面试中遇到的算法进行总结。。。

Dijkstra算法

问题定义：
定义无向图中（V代表图G中的顶点集合，E代表图G中边的集合），假设每条边的长度为，找到由顶点到其余各点的最短路径
算法思想：
将图中的节点分为两部分S和U，S为已求出最短路径的顶点集合，U为未确定最短路径的顶点集合。S中值为key-value对，其中key为节点，value为对应的最短路径。U中的值也为key-value对，其中key为节点，value为路径(表示S中节点到key的距离)，每次将U中最小距离对应的节点添加到S中，并对应的更新U中的节点距离，重复其过程，直到U中没有节点为止
下面是自己按照这个思路实现的完整代码，如果不清楚可以看参考1：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
#找到U集合中路劲的最小值，-1为无穷大
def find_min_node(u_dict):
    tuple_list=[(key,val) for key,val in u_dict.items()]
    tuple_list=sorted(tuple_list,key=lambda x:x[1])
    for tup in tuple_list:
        if tup[1]>0:return tup
    return None
def find_min_route(matrix,start_node):
    s_dict={}#S集合
    u_dict={}#U集合
    s_dict[start_node]=0#S集合初始化
    for j in range(len(matrix[start_node])):
        if j!=0:u_dict[j]=matrix[start_node][j]#U集合初始化
    while len(u_dict)>0:
        node_tuple=find_min_node(u_dict)#找到U集合中路劲的最小值，-1为无穷大
        u_dict.pop(node_tuple[0])#将对应的节点从U集合中去除
        s_dict[node_tuple[0]]=node_tuple[1]#将对应的节点添加到S集合中
        #更新U集合中的路径值
        for j in range(len(matrix[node_tuple[0]])):
            if j in u_dict.keys() and matrix[node_tuple[0]][j]>0 and (matrix[node_tuple[0]][j]+node_tuple[1]<u_dict[j] or u_dict[j]<0):
                u_dict[j]=matrix[node_tuple[0]][j]+node_tuple[1]
    print(s_dict)
def gener_matrix(relation_list,n):
    """
    :param relation_list: 一个tuple的集合，tuple为三元组，其中：（节点1，节点2，边权重）
    :param n: 节点个数
    :return: 打印出第0号节点到其他节点的最短路径
    """
    matrix=[[-1 for i in range(n)] for i in range(n)]
    for tup in relation_list:
        matrix[tup[0]-1][tup[1]-1]=tup[2]
        matrix[tup[1]-1][tup[0]-1]=tup[2]
    find_min_route(matrix,0)
gener_matrix([(1,3,9),(1,2,7),(1,6,14),(3,2,10),(3,6,9),(3,4,11),(2,4,15),(6,5,9),(5,4,6)],6)

二分图判断

这里最近遇到的一道面试题：
给出一个二分图的定义：图中的节点被涂上黑白两色，如果满足节点和其相连的节点的颜色不同，则为二分图。
问给定一个图，判断是否是二分图
算法步骤：

  1. 选取一个未染色的点u进行染色
  2. 遍历u的相邻节点v：若v未染色，则染成不同的颜色，并对v执行第2步；如果v已经染色，如果u和v颜色相同，判定不可行退出遍历
  3. 如果所有节点均已染色，判定为可行

参考2中给出的java版本有点累赘，这里使用BFS的python版本解决，如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
"""
matrix
-1表示没有边连接
0表示有边连接
染色：-1，1
"""
def solve(relation_list,node_num):
    """
    
    :param relation_list: 
    :param node_num: 
    :return: 
    """
    matrix=[[-1 for i in range(node_num)] for i in range(node_num)]
    for tup in relation_list:
        matrix[tup[0]-1][tup[1]-1]=0
        matrix[tup[1]-1][tup[0]-1]=0
    #下面的思路是BFS解法
    s_node={} #已经染色的点
    u_node=[i for i in range(node_num)] #没有染色的点
    temp={0:-1} #初始状态
    while len(u_node)>0:
        temp2={}
        for key,value in temp.items():
            s_node[key]=value
            u_node.remove(key)
            for j in range(len(matrix[key])):
                if matrix[key][j]==0:
                    if j in s_node.keys() and s_node[j]==value:return False
                    if j not in s_node.keys():temp2[j]=-value
        temp=temp2
    return True
print(solve([(1,2),(1,3),(3,4),(5,2),(1,5)],5))
print(solve([(1,2),(1,3),(3,4),(5,2),(3,5)],5))

遍历全部节点的最短路径

给定一个有n个节点，n-1条边的无向图（节点之间可通），从指定节点开始出发，问遍历完全部节点所需要的最短步数？
不管是什么类型的遍历问题，一般的的解法都是bfs和dfs，更细的，bfs一般解决的问题是最短路径问题，dfs一般解决的是最短时间的问题。
上面的题目最常规的方法就是把所有的遍历路径全部找出来，然后返回这些路径中最短的路径。这样的思路就是典型的dfs思想，于是写出如下代码：
说明：matrix为邻接矩阵

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
static int minRoute=100;
public static void dfs(int[][]matrix,List<Integer> arr,int curRoute,int curValue,int preValue){
    if(arr.size()==0||curRoute>minRoute){
        if(curRoute<minRoute)minRoute=curRoute;
    }else{
        for(int i=0;i<matrix.length;i++){
            if(matrix[curValue][i]==1){
                boolean flag=false;
                if(arr.contains(i)){
                    arr.remove(new Integer(i));
                    flag=true;
                }
                dfs(matrix,arr,curRoute+1,i,curValue);
                if(flag==true){
                    arr.add(i);
                }
            }
        }
    }
}

这个代码的问题是，遍历的过程中没有对出现的环进行判断，因为正常路径是允许出现环的问题的，于是我设置minRoute的初始值，对于一个路径如果一直循环，其路径必然会大于minRoute，当大于的时候，就判定其不是最短路径，也就是说我设置最后的最短路径不可能超过minRoute的初始值。
对于出现环的问题，有一个很经典的解决方法就是BFS，其原理可以这样理解：你在一个路口上前进，每前进一步都可能有多个分叉路口，于是每次遇到分叉路径，你就将自己分成多个分身，然后同时前进，知道某一个分身到达终点，其对应的路径就为最短路径，于是写下如下代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
public static int bfs(int[][]matrix,int nodeValue){
    List<List<Integer>> arr=new ArrayList<>();
    arr.add(new ArrayList<>());
    arr.get(0).add(nodeValue);
    int step=0;
    while (true){
        int length=arr.size();
        for(int i=0;i<length;i++){
            List<Integer> temp=arr.get(0);
            if(new HashSet<Integer>(temp).size()==matrix.length)return step;
            for(int j=0;j<matrix.length;j++){
                if(matrix[temp.get(temp.size()-1)][j]==1) {
                    temp.add(j);
                    arr.add(new ArrayList<>(temp));
                    temp.remove(temp.size() - 1);
                }
            }
            arr.remove(0);
        }
        step++;
    }
}

这样这道题的常规解法就完成了，但是遗憾的是，这样的解法并不是出题者的意图，我们想这样一个问题：从某一个起点出发，遍历完全部节点后，又回到该起点的的步数是多少呢？是节点边的个数的2倍，那么再想原问题，怎么样遍历的路径最小呢，定义起点为s1，终点为s2，起点到终点的距离为s12，我们要求的距离为s，而，显然起点和终点相聚最远的路径是最短路径，那么将原问题转换为离起点最远的节点的路径问题，于是得到如下公式：

于是写出如下代码：

1
2
3
4
5
6
7
8
9
10
11
static int maxDeep=0;
public static void findMaxDeep(int[][]matrix,int nodeValue,int preNodeValue,int curDeep){
    for(int i=0;i<matrix.length;i++){
        if(matrix[nodeValue][i]==1&&i!=preNodeValue){
            findMaxDeep(matrix,i,nodeValue,curDeep+1);
        }
    }
    if(curDeep>maxDeep)maxDeep=curDeep;
}
System.out.println((matrix.length-1)*2-maxDeep);

参考

  1. 最短路劲-Dijkstra算法和Floyd算法
  2. 二分图判定
  3. 美团笔试-图的最短路径-树的深度
如果觉得有帮助，给我打赏吧！