MyNote
0%

Posted on Edited on In ,

ReplicaSet&Deployment

replica

创建pod的副本

不会以kubectl delete pod podName的方式而被删除。必须通过replicaset相关命令进行操作。

创建replicaset模板文件

  • apiVersion: apps/v1
  • kind: ReplicaSet
  • metadata:
  • spec:
    • selector
      • matchLables: :wq必须和template中metadata里面的label一样
    • replicas:确定replica的个数。（删除pod后自动添加新的pod。当pod数为replicas指定个数时，不能创建新pod）
    • template：里面是pod的定义(metadata和spec的部分)
Read more »

Posted on Edited on In ,

k8s-PODs with YAML

YAML in Kubernetes

  • k8s definition file always contains 4 top level fields.(apiVersion,kind,metadata,spec)

pod-definition.yml

1
2
3
4
5
apiVersion:
kind:
metadata:

spec:
Read more »

Posted on Edited on In

Python中的dict（其他语言称map）

使用键-值（key-value）存储，这种key-value存储方式，在放进去的时候，必须根据key算出value的存放位置，这样，取的时候才能根据key直接拿到value。
把数据放入dict的方法，除了初始化时指定外，还可以通过key放入：

1
2
3
>>> d['Adam'] = 67
>>> d['Adam']
67

in：判断key是否存在：

1
2
>>> 'Thomas' in d
False

get()方法：如果key不存在，可以返回None，或者自己指定的value：

1
2
3
>>> d.get('Thomas')
>>> d.get('Thomas', 1)
1

若key存在则返回value

还可以用来统计string字符个数

1
2
3
4
5
6
7
8
9
s ='aabbccdd'
d ={}
for item in s:
    d[item]=d.get(item,0)+1 
print(d)

"""
{'a': 2, 'b': 2, 'c': 2, 'd': 2}
"""

pop(key)方法：删除一个key，对应的value也会从dict中删除

1
2
3
4
>>> d.pop('Bob')
75
>>> d
{'Michael': 95, 'Tracy': 85}

Python中的set

与dict不同之处：没有value

add(key)：添加元素，可以重复添加，但不会有效果

remove(key)方法可以删除元素：

Posted on Edited on In

set的使用和map的使用

两类查找问题

查找有无

——元素’a’是否存在？set；集合

查找对应关系（键值对应）

——元素’a’出现了几次？map；字典dict

set和map

通常语言的标准库中都内置set和map

——容器类

——屏蔽了实现细节

——了解语言中标准库例常见容器类的使用

Python中的set

add(key)：添加元素，可以重复添加，但不会有效果

remove(key)方法可以删除元素：

Leetcode 349 Intersection of Two Arrays

给定两个数组nums，求两个数组的公共元素。

——如nums1 = [1,2,2,1]，nums2 = [2,2]

——结果为[2]。结果中每个元素只能出现一次，出现的顺序可以是任意的

1
2
3
4
5
6
7
8
9
10
def intersection(nums1,nums2):
    record1 = set()
    for i in range(len(nums1)):
        record1.add(nums1[i])
    
    res = set()
    for i in range(len(nums2)):
        if nums2[i] in record1:
            res.add(nums2[i])
    return res

Python中的dict（其他语言称map）

使用键-值（key-value）存储，这种key-value存储方式，在放进去的时候，必须根据key算出value的存放位置，这样，取的时候才能根据key直接拿到value。

把数据放入dict的方法，除了初始化时指定外，还可以通过key放入：

1
2
3
>>> d['Adam'] = 67
>>> d['Adam']
67

in：判断key是否存在：

1
2
>>> 'Thomas' in d
False

get()方法：如果key不存在，可以返回None，或者自己指定的value：

1
2
3
>>> d.get('Thomas')
>>> d.get('Thomas', 1)
1

若key存在则返回value

还可以用来统计string字符个数

1
2
3
4
5
6
7
8
9
s ='aabbccdd'
d ={}
for item in s:
    d[item]=d.get(item,0)+1 
print(d)

"""
{'a': 2, 'b': 2, 'c': 2, 'd': 2}
"""

pop(key)方法：删除一个key，对应的value也会从dict中删除

1
2
3
4
>>> d.pop('Bob')
75
>>> d
{'Michael': 95, 'Tracy': 85}

LeetCode 350 Intersection of Two Arrays

给定两个数组nums,求两个数组的交集。

——如nums1=[1,2,2,1],nums2=[2,2]

——结果为[2,2]

——出现的顺序可以是任意的

解题：

使用dict，遍历nums1，将nums1的字符作为key，出现频率作为value。

遍历nums2，如果在dict有nums2的字符，将其加入res中，该字符对应的value减1

1
2
3
4
5
6
7
8
9
10
11
def subString(nums1,nums2):
    dict1 ={}
    res = []
    for i in range(len(nums1)):
        dict1[nums1[i]]=dict1.get(nums1[i],0)+1
    
    for i in range(len(nums2)):
        if dict1[nums2[i]]>0:  
            res.append(nums2[i])
            dict1[nums2[i]]-=1
    return res

Posted on Edited on In

set和map不同底层实现的区别

[python]list, tuple, dictionary, set的底层细节

https://blog.csdn.net/siyue0211/article/details/80560783

Python中dict的实现细节

CPython使用伪随机探测(pseudo-random probing)的散列表(hash table)作为字典的底层数据结构。由于这个实现细节，只有可哈希的对象才能作为字典的键。

Python中所有不可变的内置类型都是可哈希的。可变类型（如列表，字典和集合）就是不可哈希的，因此不能作为字典的键。

字典的三个基本操作（添加元素，获取元素和删除元素）的平均事件复杂度为O(1)，但是他们的平摊最坏情况复杂度要高得多，为O(N).

操作 平均复杂度 平摊最坏情况复杂度 获取元素 O(1) O(n) 修改元素 O(1) O(n) 删除元素 O(1) O(n) 复制 O(n) O(n) 遍历 O(n) O(n) 还有一点很重要，在复制和遍历字典的操作中，最坏的复杂度中的n是字典曾经达到的最大元素数目，而不是当前的元素数目。换句话说，如果一个字典曾经元素个数很多，后来又大大减小了，那么遍历这个字典可能会花费相当长的事件。因此在某些情况下，如果需要频繁的遍历某个词典，那么最好创建一个新的字典对象，而不是仅在旧字典中删除元素。

Python中set的实现

练习题

Leetcode242 Valid Anagram

https://leetcode.com/problems/valid-anagram/

判断字符串t是否是字符串s变换字符顺序后得到的结果

Example 1:

1
2
Input: s = "anagram", t = "nagaram"
Output: true

Example 2:

1
2
Input: s = "rat", t = "car"
Output: false

解题：

创建两个dict分别记录s和t的字符和该字符出现的频率，再比较两个记录的dict是否相等。

1
2
3
4
5
6
7
8
9
10
11
12
class Solution:
    def isAnagram(self, s: str, t: str) -> bool:
        record = {}
        record2 = {}
        for i in range(len(s)):
            record[s[i]] = record.get(s[i],0)+1
            
        for i in range(len(t)):
            record2[t[i]] = record2.get(t[i],0)+1
            
        return record2 == record

Leetcode202 Happy Number

https://leetcode.com/problems/happy-number/

一个数将其替换为其各位数字的平方和，重复这个过程，如果最终能得到1，这是happy number，如果这个过程陷入了一个不包含1的循环，则不是happy number

Example:

1
2
3
4
5
6
7
Input: 19
Output: true
Explanation: 
12 + 92 = 82
82 + 22 = 68
62 + 82 = 100
12 + 02 + 02 = 1

解题：

用set()记录每次操作的num，如果该num没有在set中出现，则才能进行循环操作；

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
def happyNumber(num):
    record = set()
    
    while num not in record:#如果num不在set中进行循环操作；若在set中证明进入死循环，不符合题目要求
        record.add(num) #记录每次操作的num
        squareSum = 0 #每次的和是要重新计算的
       
        #把一个数字的所有位数取出，并进行操作
        while num>0: 
            remain = num%10
            squareSum += remain*remain
            num = num//10
        
        
        if squareSum ==1:
            return True
        else:
            num = squareSum
    
    return False

Leetcode290 Word Pattern

https://leetcode.com/problems/word-pattern/

给出一个模式(pattern)以及一个字符串，判断这个字符串是否符合模式？

Example 1:

1
2
Input: pattern = "abba", str = "dog cat cat dog"
Output: true

Example 2:

1
2
Input:pattern = "abba", str = "dog cat cat fish"
Output: false

Example 3:

1
2
Input: pattern = "aaaa", str = "dog cat cat dog"
Output: false

Example 4:

1
2
Input: pattern = "abba", str = "dog dog dog dog"
Output: false

注意：字符集？ 空串符合任意模式？还是不符合任意模式？

解题

1
2
3
4
5
6
7
8
9
10
11
12
13
14
def wordPattern(pattern, word_str):

        words = word_str.split(" ")
        if len(pattern) != len(words):
            return False

        pattern_map, word_map = {}, {}
        for i in range(len(pattern)):
            if pattern_map.get(pattern[i], -1) != word_map.get(words[i],-1):
                return False
            pattern_map[pattern[i]] = pattern_map.get(pattern[i], 0)+i
            word_map[words[i]] = word_map.get(words[i],0)+i

        return True

Leetcode205.Isomorphic Strings

Leetcode451 Sort Characters By Frequency

Posted on Edited on In

在滑动窗口中做记录 Longest Substring Without Repeating Characters

LeetCode 3

在一个字符串中寻找没有重复字母的最长子串

——如”abcabcbb”，则结果为”abc”

——如“bbbbb”，则结果为”b“

——如”pwwkew”，则结果为”wke”

解题步骤

s[i...j]构成了一个滑动窗口

图1

如果j+1所指的字符，在当前这个子字符串中不存在(没有重复的元素)，则j向前滑动，并把其所指字符纳入子字符串中

图2

直到j+1遇到一个字符，是在子字符串中出现过的重复字符。此时j停止滑动，记录下当前的长度，更新结果

图3

此时i，向前滑动直到窗口内，没有重复的字符。此时，j又可以继续向前滑动

图4

代码实现。

借助了visited来判断是否有重复的字符串

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
def lengthOfLongestSubstring(s):
    if not s: 
        return 0
    
    i,j = 0,-1
    s = list(s)
    visited = []
    res = 1  #字符串不为空时，至少有1个
    while i<len(s):
        if j+1<len(s) and s[j+1] not in visited:
            j+=1
            visited.append(s[j])
        else: #在visited有这个元素
            visited.pop(0) #删除左边元素
            i +=1
        
        #结果的保存和更新
        if len(visited)>1:
           # res = max(res,len(visited))
            res = max(res,j-i+1)
    
    return res

Posted on Edited on In

双指针——滑动窗口

滑动窗口代码模板

在数组arr中，arr[i…j]为滑动窗口

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
i,j = 0,-1  #初始时，窗口中不能有元素，右边界为-1
"""
result 初始值
辅助变量等
"""

while i<len(arr): #只要窗口左边不越界，就能一直滑动下去
    
    if j+1<len(arr) and condition: #只要窗口右边界不越界，且满足题目条件时进行操作
        j+=1 
        process(arr[j])
    
    else:  #当前窗口不满足题目条件时，先进行操作，再使左边界向前滑动
        process(arr[i]) 
        i-=1
"""
    记录，并更新result
"""

return result

LeetCode 209 Minimum Size Subarray Sum

https://leetcode.com/problems/minimum-size-subarray-sum/

题目理解：给定我们一个数字，让我们求子数组之和大于等于给定值的最小长度

Input: s = 7, nums = [2,3,1,2,4,3]

Output: 2

解释：满足子数组和=7的最小长度数组是[4,3],所以output=2

解法1：暴力解法：

遍历所有的连续子数组[i..j]，计算其和sum，验证sum>=s，时间复杂度为O(n^3)

最大问题：大量重复计算

解法2：滑动窗口

整个过程保持一个窗口，而这个窗口的长度不是固定的，且不停向前滑动

从i到j的一个连续子数组构成滑动窗口

图1

如果当前这个子数组nums[i...j]中元素的和sum<s的话，则j向前移动一位，并将nums[j+1]纳入子数组中。j+1不能越界。

图2

j继续向前移动直到子数组的和sum>s，并记录当前的i和j之间的距离（子数组长度）

图3

随后从i端缩小这个连续子数组。

注意：代码实现时，要先是移除i所指元素，再进行i++

图4

直到sum<s，此时j又可以继续前进，去寻找下一个符合条件的连续子数组。左边界不越界就能一直滑下去。

图5

代码实现

注意：这个窗口是前闭后闭的区间，初始时不能有任何元素，因此j需要从-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
class Solution:
    def minSubArrayLen(self, s: int, nums: List[int]) -> int:
        i,j = 0,-1 #注意j从-1开始
        sum = 0  #初始时sum为0
        res = len(s)+1 #初始设置为不可能取到的一个最大值
       
      #窗口滑动的过程，只要左边界不越界就能滑动下去
        while i<len(nums):
            if sum<s and j+1<len(s):#j+1不能越界 
                j+=1  #j向前滑动，并将所指元素纳入子数组中
                sum+=nums[j]
            else: #sum>=s，先移除i所指元素，i向前移动
                sum-=nums[i]
                i+=1
            
            #经过一系列操作后，满足条件的子数组出现了
            #此时存储当前满足条件的子数组的结果
            if sum >= s: 
                res = min(res,j-l+1)
        #注意：遍历一遍没有解的情况
        if res == len(nums): 
            return 0
        return res

其他例题

子数组类题目

序号 题目 难度 代码
78 Subsets medium python、java、c++
90 Subsets II medium python、java、c++
53 Maximum Subarray easy python、java、c++
152 Maximum Product Subarray medium python、java、c++
239 Sliding Window Maximum hard python、java、c++
295 Find Median from Data Stream hard python、java、c++
228 Summary Ranges medium python、java、c++
163 Missing Ranges medium python、java、c++
325 Maximum Size Subarray Sum Equals k medium python、java、c++
209 Minimum Size Subarray Sum medium python、java、c++
238 Product of Array Except Self medium python、java、c++
128 Longest Consecutive Sequence Hard python、java、c++

Posted on Edited on In

快速排序

核心思想：分治—辅助函数partition（）

普通的快速排序

首先选择数组中的一个元素，比如用 l 索引指向最左边的元素v，逐渐遍历数组所有位于l左边的元素，在遍历的过程中，我们将逐渐整理出小于v的元素和大于v的元素，当然我们继续用一个索引j来记录小于v和大于v的分界点，然后我们当前访问的元素索引为i。

img

那么i怎么处理呢？很简单当i指向的元素e大于v的时候，直接包含进大于v的部分中，像这样：

img

然后我们继续讨论下一个元素，此时i++，如图：

img

如果元素e小于v的时候怎么做呢？只需要把元素e（arr[i]）和橙色部分之后的一个元素（arr[j+1]）交换就可以了，交换后索引j++。或者是先进行j++，后交换arr[i]和arr[j]。如图：

img

img

最后i继续往后走，到最后的时候就直接将数组分成了等于v，小于v，大于v的三部分。

最后将l位置和j位置交换，就实现了快速排序的子过程，如图：

img

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
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
import java.util.*;

public class QuickSort {

    // 我们的算法类不允许产生任何实例
    private QuickSort(){}

    // 对arr[l...r]部分进行partition操作
    // 返回p, 使得arr[l...p-1] < arr[p] ; arr[p+1...r] > arr[p]
    private static int partition(Comparable[] arr, int l, int r){

        // 随机在arr[l...r]的范围中, 选择一个数值作为标定点pivot
        swap( arr, l , (int)(Math.random()*(r-l+1))+l );

        Comparable v = arr[l];

        int j = l; // arr[l+1...j] < v ; arr[j+1...i) > v
        for( int i = l + 1 ; i <= r ; i ++ )
            if( arr[i].compareTo(v) < 0 ){
                swap(arr, j+1, i);
                j ++;
            }

        swap(arr, l, j); //最后在把pivot交换到分界点

        return j;   //此时j所指的就是pivot，返回pivot所在的index
    }
    

    // 递归使用快速排序,对arr[l...r]的范围进行排序
    private static void sort(Comparable[] arr, int l, int r){
        
        int p = partition(arr, l, r); //通过调用partition函数使数组分为
        sort(arr, l, p-1 );
        sort(arr, p+1, r);
    }

    public static void sort(Comparable[] arr){

        int n = arr.length;
        sort(arr, 0, n-1);
    }

    private static void swap(Object[] arr, int i, int j) {
        Object t = arr[i];
        arr[i] = arr[j];
        arr[j] = t;
    }

    // 测试 QuickSort
    public static void main(String[] args) {

        // Quick Sort也是一个O(nlogn)复杂度的算法
        // 可以在1秒之内轻松处理100万数量级的数据
        int N = 1000000;
        Integer[] arr = SortTestHelper.generateRandomArray(N, 0, 100000);
        SortTestHelper.testSort("bobo.algo.QuickSort", arr);

        return;
    }
}

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
import random
def QuickSort(arr):
    n = len(arr)
    QuickSortHelper(arr, 0, n-1)
    return arr


def QuickSortHelper(arr, l, r):
    if l<r:  
        p = partition(arr, l, r)
        QuickSortHelper(arr, l, p - 1)
        QuickSortHelper(arr, p + 1, r)


def partition(arr, l, r):
    ran = random.randint(l, r)  # 在数组中选择一个随机数作为pivot
    arr[ran], arr[l] = arr[l], arr[ran]
    v = arr[l] #pivotvalue
    j = l
    for i in range(l + 1, r+1, 1): #i从l+1移动到r
        if (arr[i] < v):
            arr[i], arr[j + 1] = arr[j + 1], arr[i]
            j += 1
    arr[l], arr[j] = arr[j], arr[l]
    return j

快速排序虽然高效，但并不稳定，当数组中存在大量重复元素时，比如举个例子，我用模板测试归并排序和快速排序的时间，设置一个1000000的数组，数组元素在0-10之间随机取值，那么用归并需要花费0.290727s而快排需要花费171.151s，对，你没有看错。当快速排序最优的时候是o（nlgn），而此时显然退化到了o（n^2）的级别。这是为什么？

还记得上面我写的快排的子过程么，考虑到了e>v,e<v，而e=v的情况没有考虑对吧。看了代码理解了的同学应该清楚，其实我是把等于v这种情况包含进了大于v的情况里面了，那么会出现什么问题？ 不管是当条件是大于等于还是小于等于v，当数组中重复元素非常多的时候，等于v的元素太多，那么就将数组分成了极度不平衡的两个部分，因为等于v的部分总是集中在数组的某一边。

双路快排–处理很多重复元素

思路：和快排不同的是，此时我们将小于v和大于v的元素放在数组的两端，那么我们将引用新的索引j的记录大于v的边界位置。

如图：把数组分为arr[l+1…i-1]<v和arr[j…r] >v两部分。

img

i索引不断向后扫描，当i的元素小于v的时候继续向后扫描，直到碰到了某个元素大于等于v。j同理，直到碰到某个元素小于等于v。如图：

img

然后绿色的部分便归并到了一起，而此时只要交换i和j的位置就可以了，然后i++，j–就行了。如图：

img

img

直到i和j遍历完毕，整个数组排序完成。

这种优化当它遇到重复元素的时候，也能近乎将他们平分开来。

代码实现思路：

在sort函数中进行partition函数操作，返回pivot。后进行sort(arr,l,p-1)和sort(arr,p+1,r)的递归调用。（关键是partition函数的构造。）

partition函数的构造

1，先随机选取一个index，并将其对应的元素于arr[l]进行交换，使其成为v

2，i的初始值从l+1开始，j从r开始。目的是：开始时arr[l+1…i)和arr（j…r]数组为空。

3，进行while（true）循环且其中有两个子while循环：只要arr[i]<v,循环继续，i++;只要arr[j]>v，循环继续，j–。

(为什么不挂等号？当 i 和 j 所指向的元素都==v时，两个元素仍然需要交换位置，这样一来不会有大量==v的元素集中在一边。而使得算法时间复杂度降低。)

当不满足两个子while循环的条件时，（意味着a[i]>=v;a[j]<=v）需要交换i,j对应两个元素

如果 i>j 则跳出循环。

4，当全部循环结束后，由于i >j ，j对应元素<v,所以a[l]与a[j]交换

5，返回j（pivot所在的index）

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
45
46
47
48
49
50
51
public class QuickSort2Way{
    //定义交换元素的方法
    private static void swap(arr[i],arr[j]){
        Object tmp = arr[i];
        arr[i] = arr[j];
        arr[j] = tmp;
    }
    //双路快速排序的partition
    //将数组分为>=v和<=v两部分并返回pivot所对应的index，
    private static int partion(Comparable[] arr,int l,int r){
        //随机在arr[l..r]的范围中，选择一个index对应的数值作为标定点pivot，避免arr[l]就是最小值
        swap(arr[l],arr[(int)(Math.random()*(r-l+1)+l)]);
        //把v设置为最左端的元素
        Comparable v = arr[l];
        
        //为了把数组分为arr[l+1...i)<=v和arr(j...r]>=v两部分
        int i = l+1,j = r;
        while(true){
            //这里的边界不能挂等号
            while(i <= r && arr[i].compareTo(v) < 0)
                i++;  
            while(j >= l+1 && arr[j].compareTo(v) > 0 )
                j--;
            if(i>j)  //如果i超过了j的循环结束
                break; 
            swap(arr[i],arr[j]); // i，j都不移动了，证明a[i]>=v;a[j]<=v，就交换i,j对应两个元素
            i++;                 //交换后，i，j继续移动
            j--;
        }
        swap(arr[l],arr[j]);     //全部循环结束后，由于j已经小于i，j对应的是<v的元素，因此
        return j;
    }
    //递归使用快速排序，对arr[l...r]的范围进行排序
    private static void sort(Comparable[] arr,int l,int r){
        
        // 对于小规模数组, 使用插入排序
        if( r - l <= 15 ){
            InsertionSort.sort(arr, l, r);
            return;
        }
        
        //传入数组，左边界和右边界
        int p = partition(arr,l,r); //p为pivot左边<=v;右边>=v
        sort(arr,l,p-1); //继续递归调用直到将数组分为一个元素，则返回它自身
        sort(arr,p+1,r);
    }
    public static void sort(Comparable[] arr){
        int n = arr.length;
        sort(arr,0,n-1);
    }
}

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
39
import random

def QuickSort2Way(arr):
    n = len(arr)
    QuickSortHealper(arr,0,n-1)
    return arr

def QuickSortHealper(arr,l,r):
    if l<r: #没写这个一直报bug
        p = partition(arr, l, r)
        QuickSortHealper(arr, l, p - 1)
        QuickSortHealper(arr, p + 1, r)


def partition(arr,l,r):
    rand = randint(l,r)  # 优化，随机取标定点，以解决近乎有序的列表
    arr[l], arr[rand] = arr[rand], arr[l]

    #设置两个指针l和r
    i = l+1
    j = r
    #设置pivotvalue
    v = arr[l]

    while True:
        while(arr[i]<arr[l] and i<=r): #当arr[i]>=v时停止前进
            i+=1
        while(arr[j]>arr[l] and j>=l+1):
            j-=1
        if(i>j):
            break
        else:
            # i，j都停止前进时，进行交换
            arr[i], arr[j] = arr[j], arr[i]
            i += 1
            j -= 1
    #跳出循环后
    arr[l],arr[j]=arr[j],arr[l]
    return j

三路快排

思路：把数组分为arr[l+1…lt]<v; arr[lt+1…i) == v; arr[gt…r]>v三部分。

此时不需要partition函数。直接在sort函数中分情况讨论，后进行递归调用。

1，先随机选取一个index，并将其对应的元素于arr[l]进行交换，使其成为v

2，由于是闭区间，因此设 lt 初始值为l；gt的初始值为r+1。即开始时arr[l+1…lt]和arr[gt…r]中不存在元素。

3，开始while循环,循环条件是 i<gt 。==v的数组范围没有和>v的数组范围对撞。

4，在while循环中，如果arr[i]<v，则与（arr[lt+1…i)==v数组左边界的）arr[lt+1]进行交换，由于换过来的元素等于v，因此i直接向前移动；（且arr[l+1…lt] <v 的数组范围扩容）lt+1对应的是 <v 的元素因此lt需要向前移动一个位置。如果arr[i]>v, 则直接与arr[gt-1]进行交换，此时gt-1对应的是 >v 的元素，因此gt需要向前移动一位，但是由于交换过来的元素是未知的所以 i 不能向前移动。如果arr[i] == v 则 i 直接向前移动。

因为i是紧挨左边界的所以左边界交换来的元素已知，而右边界交换来的元素未知。

5,最后进行arr[l]与(arr[l+1…lt]<v的右边界)arr[lt]的交换。

6，最后进行sort(arr, l, lt-1)和sort(arr, gt, r)的递归调用。

1

LeetCode真题—75.Sort Colors

  1. Sort Colors

Medium

Given an array with n objects colored red, white or blue, sort them in-place so that objects of the same color are adjacent, with the colors in the order red, white and blue.

Here, we will use the integers 0, 1, and 2 to represent the color red, white, and blue respectively.

Note: You are not suppose to use the library’s sort function for this problem.

Example:

1
2
Input: [2,0,2,1,1,0]
Output: [0,0,1,1,2,2]

本题：只有三个元素0，1，2三个元素。适合使用三路快排。arr[i] ==0排到左边，arr[i]==2排到右边，最后中间剩下的是1

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution {
    public void sortColors(int[] nums) {
       int l = -1, r = nums.length , i = 0;
        while (i < r) {
            if (nums[i] == 0) {
                int tmp = nums[i] ;
                nums[i] = nums[l+1];
                nums[l+1] = tmp;
                l++;
            }
            if (nums[i] == 2) {
            	int tmp = nums[i] ;
                nums[i] = nums[r-1];
                nums[r-1] = tmp;
                r--;
                i--; //由与交换过来的元素未知也许还是2，所以i还要检查一遍
            }
            i++;
        }
}

Python版本

1
2
3
4
5
6
7
8
9
10
11
12
def sortColors(nums):
    l,r,i = -1,len(nums),0
    while(i<r):
        if nums[i] ==0:
            nums[i],nums[l+1]=nums[l+1],nums[i]
            l+=1
        if nums[i] ==2:
            nums[i],nums[r-1]=nums[r-1],nums[i]
            r-=1
            i-=1
        i+=1
    return nums

Posted on Edited on In

堆

底层：数组

1. 什么是堆？

堆是一种数据结构，它是一颗完全二叉树。

堆分为最大堆和最小堆：

  1. 最大堆：任意节点的值不大于其父亲节点的值。
  2. 最小堆：任意节点的值不小于其父亲节点的值。

如下图所示，就是个最大堆：

img

2. 堆有什么用途？

堆最常用于优先队列以及相关动态问题。

优先队列指的是元素入队和出队的顺序与时间无关，既不是先进先出，也不是先进后出，而是根据元素的重要性来决定的。

例如，操作系统的任务执行是优先队列。一些情况下，会有新的任务进入，并且之前任务的重要性也会改变或者之前的任务被完成出队。而这个出队、入队的过程利用堆结构，时间复杂度是O(log2_n)。

img

3. 实现堆结构

3.1 元素存储

堆中的元素存储，一般是借用一个数组：这个数组是从 1 开始计算的。更方便子节点和父节点的表示。

img

3.2 入堆

入堆即向堆中添加新的元素，然后将元素移动到合适的位置，以保证堆的性质。

在入堆的时候，需要shift_up操作，如下图所示：

img

插入 52 元素后，不停将元素和上方父亲元素比较，如果大于，则交换元素；直到达到堆顶或者小于等于父亲元素。

3.3 出堆

出堆只能弹出堆顶元素（最大堆就是最大的元素），调整元素为止保证堆的性质。

在入堆的时候，需要shift_down操作，如下图所示：

img

已经取出了堆顶元素，然后将位于最后一个位置的元素放入堆顶（图中是16被放入堆顶）。

重新调整元素位置。此时元素应该和子节点比较，如果大于等于子节点或者没有子节点，停止比较；否则，选择子节点中最大的元素，进行交换，执行此步，直到结束。

3.4 实现优化

在优化的时候，有两个部分需要做：

  1. swap操作应该被替换为：单次赋值，减少赋值次数
  2. 入堆操作：空间不够的时候，应该开辟 2 倍空间，防止数组溢出

3.5堆排序

根据实现的MaxHeap类，实现堆排序很简单：将元素逐步insert进入堆，然后再extract_max逐个取出即可。当然，这个建堆的平均时间复杂度是O(n*log2_n)代码如下：

过程叫做heapify,实现思路如下：

  1. 将数组的值逐步复制到this->data
  2. 从第一个非叶子节点开始，执行shift_down
  3. 重复第 2 步，直到堆顶元素

这种建堆方法的时间复杂度是: O(n)。因此, 编写heap_sort2函数：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
public MaxHeap(Item arr[]) {
		
		int n = arr.length;
		//创建一个可比较类型的数组，作为堆的底层，data从1开始
		data = (Item[])new Comparable[n+1];
		capacity = n;
		
		//在堆中，为了方便计算，从1开始
		for(int i = 0; i<n;i++)
			data[i+1] = arr[i];
		count = n; //堆中元素个数
		
		//heapify过程。找到堆中第一个非叶子节点，作为开始
		for(int i = count/2;i>=1;i--)
			shiftDown(i); 
	}

整体代码实现

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
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
import java.util.*;
public class MaxHeap<Item extends Comparable> {
	
	protected Item[] data; //作为堆的底层的数组
	protected int count;   //堆中元素个数
	protected int capacity;
	
	//构造函数，构建一个空堆，可容纳capacity个元素
	public MaxHeap(int capacity) {
		data = (Item[]) new Comparable[capacity+1];
		count = 0;
		this.capacity = capacity;
	}
	
	//构造函数，通过一个给定数组创建一个最大堆
	public MaxHeap(Item arr[]) {
		
		int n = arr.length;
		//创建一个可比较类型的数组，作为堆的底层，data从1开始
		data = (Item[])new Comparable[n+1];
		capacity = n;
		
		//在堆中，为了方便计算，从1开始
		for(int i = 0; i<n;i++)
			data[i+1] = arr[i];
		count = n; //堆中元素个数
		
		//heapify过程。找到堆中第一个非叶子节点，作为开始
		for(int i = count/2;i>=1;i--)
			shiftDown(i); 
	}
	
	//返回堆中元素个数
	public int size() {
		return count;
	}
	
	//返回一个布尔值，表示堆中是否为空
	public boolean isEmpty() {
		return count == 0;
	}
	
	//向最大堆中插入一个新元素item
	public void insert(Item item) {
		//先判断是否超过容量
		assert count+1 <= capacity;
		data[count+1] = item; //把元素加到末尾
		count++;              //增加count数量
		shiftUp(count);       //把新添加的元素放到其合适的位置
	}
	
	//从最大堆中取出堆顶元素，即堆中所存储的最大数据
	public Item extractMax() {
		//先判断堆中有元素
		assert count>0;
		Item ret = data[1];
		//交换堆顶和末尾元素
		swap(1,count);
		count--;     //减少count的数量
		shiftDown(1);//把放到堆顶的末尾元素放到合适的位置去
		
		return ret;
	}
	
	//获取最大堆中的堆顶元素
	public Item getMax() {
		assert (count>0);
		return data[1];
	}
	
	//交换堆中索引为i和j的两个元素
	private void swap(int i,int j) {
		Item t = data[i];
		data[i] = data[j];
		data[j] = t;
	}
	
	//重要辅助函数
	private void shiftUp(int idx) {
		//当前节点不是root节点且当前节点idx大于母节点idx/2。
		while(idx>1 && data[idx/2].compareTo(data[idx])<0) {
		//则元素交换。idx变成idx/2
		        swap(idx/2,k);
			idx = idx/2;
		}
	}
	
	private void shiftDown(int idx) {
		while(2*idx <= count) {//保证节点idx是有孩子的。idx只要有左孩子，证明一点有孩子
			int j = 2*idx; //j是k的左孩子
			
			if(j+1<= count && data[idx+1].compareTo(data[j])>0)
				j++; //j是idx的右孩子
			//保证data[idx]是data[2*idx]和data[2*idx+1]中的最大值
			//这样才能保证换上来的元素是最大的
			if(data[idx].compareTo(data[j])>=0)
				break;
			swap(idx,j);
			idx = j;
	
		}
	}
	// 测试 MaxHeap
    public static void main(String[] args) {

        MaxHeap<Integer> maxHeap = new MaxHeap<Integer>(100);
        int N = 100; // 堆中元素个数
        int M = 100; // 堆中元素取值范围[0, M)
        for( int i = 0 ; i < N ; i ++ )
            maxHeap.insert( new Integer((int)(Math.random() * M)) );

        Integer[] arr = new Integer[N];
        // 将maxheap中的数据逐渐使用extractMax取出来
        // 取出来的顺序应该是按照从大到小的顺序取出来的
        for( int i = 0 ; i < N ; i ++ ){
            arr[i] = maxHeap.extractMax();
            System.out.print(arr[i] + " ");
        }
        System.out.println();

        // 确保arr数组是从大到小排列的
        for( int i = 1 ; i < N ; i ++ )
            assert arr[i-1] >= arr[i];
    }

}

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
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
import random
#创建Array类固定长度的数组
#一个下划线开头的实例变量名，比如_name，这样的实例变量外部是可以访问的，
#但是，按照约定俗成的规定，当你看到这样的变量时，意思就是，
# “虽然我可以被访问，但是，请把我视为私有变量，不要随意访问”。

class Array(object):
    def __init__(self,size=32): #默认长度32
        self._size = size      #_size可以被外部访问但是要视为私有变量
        self._items = [None]*size #用*号创建长度为size，元素全为None的列表

    def __getitem__(self,index): #模式方法。实现通过[]进行访问
        return self._items[index]

    def __setitem__(self, index, value): #设置相应位置的元素
        self._items[index] = value

    def __len__(self):  #返回长度值
        return self._size

    def clear(self,value=None):
        for i in range(self._items):
            self._items[i]=value



    def __iter__(self): #遍历数组
        for item in self._items:
            yield item
            
class MaxHeap(object):
    def __init__(self,capacity=None):

        self.capacity = capacity+1 #堆的容量
        self._data = Array(self.capacity) #创建内部数组，用来实现最大堆
        self._count = 0  #堆中元素个数

    def __len__(self):  #最大堆的长度
        return self._count

    def add(self,item): #向堆中添加元素
        if self._count>=self.capacity:
            raise Exception('full')

        self._count += 1
        self._data[self._count] = item
        self.__shiftUp(self._count)

    def size(self):
        return self.count

    def isEmpty(self):
        return self.count ==0

    def extractMax(self):
        if self._count <=0:
            raise Exception("empty")
        ret = self._data[1] #存储顶点元素
        self._data[1],self._data[self._count] = self._data[self._count],self._data[1]
        self._count-=1
        self.__shiftDown(1)
        return ret

    def __shiftUp(self,k):  #
        # 指针k对应节点不是root节点且子节点大于父节点
        while(k>1 and self._data[k]>self._data[k//2]):
            self._data[k//2],self._data[k]=self._data[k],self._data[k//2]
            k //=2

    def __shiftDown(self,k):
        while(2*k<=self._count): #该节点有左孩子（证明肯定有孩子）
            j = k*2
            #如果该节点有右孩子且右孩子更大时，指针指向右孩子
            if(j+1<=self._count and self._data[j+1]>self._data[j]):
                j+=1
            if(self._data[k]>=self._data[j]):
                break
            self._data[k],self._data[j]=self._data[j],self._data[k]
            k=j
            
def test_MaxHeap():
    arr = list(range(33))
    random.shuffle(arr)
    print(arr)
    heap = MaxHeap(len(arr))
    res = []
    for i in range(len(arr)): #将随机生成的arr元素入堆
        heap.add(arr[i])
    for i in range(len(arr)): #堆中元素出堆
        res.append(heap.extractMax())
    print(res) #从大到小
    for i in range(len(arr) // 2): #反转数组
        res[i], res[len(res) - 1 - i] = res[len(res) - 1 - i], res[i]
    print(res)

数据结构–索引堆

何为索引堆？

索引堆是对堆进行了优化。关于堆的介绍可以查看数据结构–堆。

优化了什么？

在堆中，构建堆、插入、删除过程都需要大量的交换操作。在之前的实现中，进行交换操作是直接交换datas数组中两个元素。而索引堆交换的是这两个元素的索引，而不是直接交换元素。

有什么好处？

主要有两个好处：

  1. 减小交换操作的消耗，尤其是对于元素交换需要很多资源的对象来说，比如大字符串。
  2. 可以根据原位置找到元素，即便这个元素已经换了位置。

如何做到的？

索引堆使用了一个新的int类型的数组，用于存放索引信息。部分代码如下：

1
2
3
// 属性
T[] datas; // 存放数据的数组 datas[1..n]
int[] indexes; // 索引数组

这里这个indexes数组，存放的是什么信息呢？它是如何工作的呢？假如我们有这样一个最小堆：

用数组表示是：

datas: [-, 1, 15, 20, 34, 7]

现在要维护最小堆的有序性，就需要交换15和7这两个元素。交换之后的元素数组是：

datas: [-, 1, 7, 20, 34, 15]

而此时，我们再想找到原来在datas[2]位置的元素，已经找不到了。因为此时data[2]已经换成了7，而系统并没有记录15被换到了什么地方。

这个时候，想要得到i位置的元素，直接datas[i]就可以了。

使用索引堆

元素比较的时候是datas的数据，而交换时候是indexes的数据(索引)，datas不做任何改动。

使用索引堆后，初始化两个数组应该是这样的：

  • datas: [-, 1, 15, 20, 34, 7]
  • indexes: [-, 1, 2, 3, 4, 5]

这个时候，我们就交换indexes数组里面的索引2和5，而不操作datas数组。交换后两个数组是这个样子：

  • datas: [-, 1, 15, 20, 34, 7]
  • indexes: [-, 1, 5, 3, 4, 2]

这个时候，想要得到i位置的元素，就需要datas[indexes[i]]来获取。

用图来理解：

构建前：

img

构建后：

img

索引堆的优化

前面的index heap 虽然解决了改变堆中元素，由于data位置是不改变的，所以可以通过 data[i] = newItem; 但是，改变index数组以维护队的性质这个操作就无法通过一步实现了，此时，需要先遍历indexes数组，时间复杂度是O(N)，再调整的时间复杂度是O(logN),所以T(N) = O(N0+O(logN)。

比如，我们想要改变所以位置4的data，更改后要维护这个堆，这个堆中存储的元素是上一行的索引，所以要在indexes数组中找到4所在位置，需要遍历indexes数组，找到是第9个位置，然后对滴9个位置调整，如果，我们在对这个类中添加一个reverse属性，关系如下：

img

rev与index的关系：

img

Posted on Edited on In

Chp7图论

基本概念：

img

图论〔Graph Theory〕是数学的一个分支。它以图为研究对象。图论中的图是由若干给定的点及连接两点的线所构成的图形，这种图形通常用来描述某些事物之间的某种特定关系，用点代表事物，用连接两点的线表示相应两个事物间具有这种关系。

图论是一种表示 “多对多“ 的关系

图是由顶点和边组成的：(可以无边，但至少包含一个顶点)

  • 一组顶点：通常用 V(vertex) 表示顶点集合
  • 一组边：通常用 E(edge) 表示边的集合

图可以分为有向图和无向图，在图中：

  • (v, w) 表示无向边，即 v 和 w 是互通的
  • <v, w> 表示有向边，该边始于 v，终于 w

图可以分为有权图和无权图：

  • 有权图：每条边具有一定的权重(weight)，通常是一个数字
  • 无权图：每条边均没有权重，也可以理解为权为 1

图又可以分为连通图和非连通图：

  • 连通图：所有的点都有路径相连
  • 非连通图：存在某两个点没有路径相连

图中的顶点有度的概念：

  • 度(Degree)：所有与它连接点的个数之和
  • 入度(Indegree)：存在于有向图中，所有接入该点的边数之和
  • 出度(Outdegree)：存在于有向图中，所有接出该点的边数之和

图的表示：

图在程序中的表示一般有两种方式：

1. 邻接矩阵：

  • 在 n 个顶点的图需要有一个 n × n 大小的矩阵
  • 在一个无权图中，矩阵坐标中每个位置值为 1 代表两个点是相连的，0 表示两点是不相连的
  • 在一个有权图中，矩阵坐标中每个位置值代表该两点之间的权重，0 表示该两点不相连
  • 在无向图中，邻接矩阵关于对角线相等

2. 邻接链表：

  • 对于每个点，存储着一个链表，用来指向所有与该点直接相连的点
  • 对于有权图来说，链表中元素值对应着权重

例如在无向无权图中：

img

在无向有权图中：

img

可以看出在无向图中，邻接矩阵关于对角线对称，而邻接链表总有两条对称的边

而在有向无权图中：

img

邻接矩阵和链表对比：

  1. 邻接矩阵由于没有相连的边也占有空间，因此存在浪费空间的问题，而邻接链表则比较合理地利用空间
  2. 邻接链表比较耗时，牺牲很大的时间来查找，因此比较耗时，而邻接矩阵法相比邻接链表法来说，时间复杂度低。

结论： 邻接表适合表示稀疏图 (Sparse Graph)；邻接矩阵适合表示稠密图 (Dense Graph)

稠密图 - 邻接矩阵代码实现

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
45
46
47
48
49
// 稠密图 - 邻接矩阵
public class DenseGraph {

    private int n;  // 节点数
    private int m;  // 边数
    private boolean directed;   // 是否为有向图
    private boolean[][] g;      // 图的具体数据

    // 构造函数
    public DenseGraph( int n , boolean directed ){
        assert n >= 0;
        this.n = n;
        this.m = 0;    // 初始化没有任何边
        this.directed = directed;
        // g初始化为n*n的布尔矩阵, 每一个g[i][j]均为false, 表示没有任和边
        // false为boolean型变量的默认值
        g = new boolean[n][n];
    }

    public int V(){// 返回节点个数
    	return n;
    } 
    public int E(){ // 返回边的个数
    	return m;
    } 

    // 向图中顶点v和顶点v之间添加一条边
    public void addEdge( int v , int w ){
    //先判断是否越界
        assert v >= 0 && v < n ;
        assert w >= 0 && w < n ;
    //如果v，w之间已经有边了，则直接返回
        if( hasEdge( v , w ) )
            return;

        g[v][w] = true; //表示从v到w有(添加)条边
        if( !directed ) //如果是无向图
            g[w][v] = true;

        m ++; //边的个数增加
    }

    // 验证图中是否有从v到w的边
    boolean hasEdge( int v , int w ){
        assert v >= 0 && v < n ; //先判断是否越界
        assert w >= 0 && w < n ;
        return g[v][w];  //返回布尔矩阵中所对应元素值
    }
}

稀疏图 - 邻接表代码实现

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
45
46
47
48
49
50
51
52
import java.util.Vector;
import java.util.LinkedList;

// 稀疏图 - 邻接表
public class SparseGraph {

    private int n;  // 节点数
    private int m;  // 边数
    private boolean directed;    // 是否为有向图
    private Vector<Integer>[] g; // 图的具体数据

    // 构造函数
    public SparseGraph( int n , boolean directed ){
        assert n >= 0;
        this.n = n;
        this.m = 0;    // 初始化没有任何边
        this.directed = directed;
        // g初始化为n个空的vector, 表示每一个g[i]都为空, 即没有任和边
        g = (Vector<Integer>[])new Vector[n];
        //g的每一个元素g[i]也都是一个Vector
        for(int i = 0 ; i < n ; i ++)
            g[i] = new Vector<Integer>();
    }

    public int V(){ return n;} // 返回节点个数
    public int E(){ return m;} // 返回边的个数

    // 向图中添加一个边
    public void addEdge( int v, int w ){

        assert v >= 0 && v < n ;
        assert w >= 0 && w < n ;

        g[v].add(w);
        if( v != w && !directed )
            g[w].add(v);

        m ++;
    }

    // 验证图中是否有从v到w的边
    boolean hasEdge( int v , int w ){

        assert v >= 0 && v < n ;
        assert w >= 0 && w < n ;
        //g[v]是一个Vector，循环g[v]查看其中是否含有w
        for( int i = 0 ; i < g[v].size() ; i ++ )
            if( g[v].elementAt(i) == w )
                return true;
        return false;
    }
}

通过节点遍历它的临边所对应节点

  1. 在邻接矩阵中：需要将这个节点的这一行全部遍历一遍，如果为0说明不相邻；如果为1说明相邻。
  2. 在邻接表中：因为这个点这一行所存储的就是相邻的节点元素，则直接输出。

实现思路：

  1. 将变量g(矩阵或链表)从priavte改为public，直接进行循环。
  2. 保持g本身为private，借助迭代器实现

设置迭代器的意义：

稠密图和稀疏图这两个实现，里面的具体实现被屏蔽了。它们呈现给外面的接口是完全一样的，这为我们后续实现图相关的算法带来了方便。我们的每一个算法既对稀疏图也对稠密图成立，因为我们调用的是同一个接口，我们的图算法都应该封装在同一个模板类中。我们就可以任意传入稀疏图或者稠密图到这个模板中。

1、邻接矩阵的迭代器方法实现:

这里的g是boolean型矩阵。

1
2
3
4
5
6
7
8
9
10
11
12
// 返回图中一个顶点的所有邻边
// 由于java使用引用机制，返回一个Vector不会带来额外开销,
    
public Iterable<Integer> adj(int v) {
     //定义一个可迭代方法，求v节点的临边所对应节点
     assert v >= 0 && v < n;
     Vector<Integer> adjV = new Vector<Integer>(); 
     for(int i = 0 ; i < n ; i ++ )  //遍历v节点所在的那一行
         if( g[v][i] )               //如果为true证明有临边
             adjV.add(i);            //将临边对应的节点存入vector
     return adjV;                    //返回vector   
}

2、邻接链表的迭代方法实现：

这里的g是Vector类型变量，里面存储的元素就是临边所对应的节点。

1
2
3
4
5
6
// 返回图中一个顶点的所有邻边
// 由于java使用引用机制，返回一个Vector不会带来额外开销,
public Iterable<Integer> adj(int v){
    assert v >= 0 && v < n;
    return g[v]; 
}

图的算法框架

1、首先建立Graph的接口

1
2
3
4
5
6
7
8
9
10
// 图的接口
public interface Graph {

    public int V(); //返回节点个数
    public int E(); //返回边的个数
    public void addEdge( int v , int w ); // 向图中添加一个边
    boolean hasEdge( int v , int w );    // 验证图中是否有从v到w的边
    void show();   // 显示图的信息
    public Iterable<Integer> adj(int v); // 返回图中一个顶点的所有邻边(所对应节点)
}

2、实现接口，创建稠密图类DenseGraph（建立邻接矩阵）和稀疏图类SparseGraph（建立邻接表）

稠密图 - 邻接矩阵 具体实现

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
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
import java.util.Vector;

// 稠密图 - 邻接矩阵
public class DenseGraph implements Graph{

    private int n;  // 节点数
    private int m;  // 边数
    private boolean directed;   // 是否为有向图
    private boolean[][] g;      // 图的具体数据

    // 构造函数
    public DenseGraph( int n , boolean directed ){
        assert n >= 0;
        this.n = n;
        this.m = 0;    // 初始化没有任何边
        this.directed = directed;
        // g初始化为n*n的布尔矩阵, 每一个g[i][j]均为false, 表示没有任和边
        // false为boolean型变量的默认值
        g = new boolean[n][n];
    }

    public int V(){ return n;} // 返回节点个数
    public int E(){ return m;} // 返回边的个数

    // 向图中添加一个边
    public void addEdge( int v , int w ){

        assert v >= 0 && v < n ;
        assert w >= 0 && w < n ;

        if( hasEdge( v , w ) )
            return;

        g[v][w] = true;
        if( !directed )
            g[w][v] = true;

        m ++;
    }

    // 验证图中是否有从v到w的边
    public boolean hasEdge( int v , int w ){
        assert v >= 0 && v < n ;
        assert w >= 0 && w < n ;
        return g[v][w];
    }

    // 显示图的信息
    public void show(){

        for( int i = 0 ; i < n ; i ++ ){
            for( int j = 0 ; j < n ; j ++ )
                System.out.print(g[i][j]+"\t");
            System.out.println();
        }
    }

    // 返回图中一个顶点的所有邻边
    // 由于java使用引用机制，返回一个Vector不会带来额外开销,
    public Iterable<Integer> adj(int v) {
        assert v >= 0 && v < n;
        Vector<Integer> adjV = new Vector<Integer>();
        for(int i = 0 ; i < n ; i ++ )
            if( g[v][i] )
                adjV.add(i);
        return adjV;
    }
}

稀疏图 - 邻接表 具体实现

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
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
// 稀疏图 - 邻接表
import java.util.Vector;
public class SparseGraph implements Graph {

    private int n;  // 节点数
    private int m;  // 边数
    private boolean directed;   // 是否为有向图
    private Vector<Integer>[] g; // 图的具体数据

    // 构造函数
    public SparseGraph( int n , boolean directed ){
        assert n >= 0;
        this.n = n;
        this.m = 0;    // 初始化没有任何边
        this.directed = directed;
        // g初始化为n个空的vector, 表示每一个g[i]都为空, 即没有任和边
        g = (Vector<Integer>[])new Vector[n];
        for(int i = 0 ; i < n ; i ++)
            g[i] = new Vector<Integer>();
    }

    public int V(){ return n;} // 返回节点个数
    public int E(){ return m;} // 返回边的个数

    // 向图中添加一个边
    public void addEdge( int v, int w ){

        assert v >= 0 && v < n ;
        assert w >= 0 && w < n ;

        g[v].add(w);
        if( v != w && !directed )
            g[w].add(v);

        m ++;
    }

    // 验证图中是否有从v到w的边
    public boolean hasEdge( int v , int w ){

        assert v >= 0 && v < n ;
        assert w >= 0 && w < n ;

        for( int i = 0 ; i < g[v].size() ; i ++ )
            if( g[v].elementAt(i) == w )
                return true;
        return false;
    }

    // 显示图的信息
    public void show(){

        for( int i = 0 ; i < n ; i ++ ){
            System.out.print("vertex " + i + ":\t");
            for( int j = 0 ; j < g[i].size() ; j ++ )
                System.out.print(g[i].elementAt(j) + "\t");
            System.out.println();
        }
    }

    // 返回图中一个顶点的所有邻边
    // 由于java使用引用机制，返回一个Vector不会带来额外开销,
    public Iterable<Integer> adj(int v) {
        assert v >= 0 && v < n;
        return g[v];
    }
}

3、创建类ReadGraph: 读取图的信息，并将此算法封装在类中。而且无论是对于稀疏图还是稠密图都可以在这个算法上运行。

ReadGraph实现关键：

  1. 创建读取文件的方法readFile()，并根据文件内容在节点之间添加边。
  2. 因为构造函数的传入类型定义为Graph（向上转型）使得既能传入稀疏图也能传入稠密图，所以在调用addEdge（）方法添加边时，则调用的是各自子类的方法。
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
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
import java.io.BufferedInputStream;
import java.io.File;
import java.io.FileInputStream;
import java.io.IOException;
import java.util.Scanner;
import java.util.Locale;
import java.util.InputMismatchException;
import java.util.NoSuchElementException;

public class ReadGraph {

    private Scanner scanner;

    public ReadGraph(Graph graph, String filename){//
   //定义类型为Graph(向上转型)，使得在这个模板中既可以传入稀疏图又可以传入稠密图。
        readFile(filename);  //读取文件

        try {
            int V = scanner.nextInt(); //读取文本文件第一行第一个元素（代表节点个数）
            if (V < 0)
                throw new IllegalArgumentException("number of vertices in a Graph must be nonnegative");
            assert V == graph.V();  //判断读取文件的节点数和图中的节点数是一致的

            int E = scanner.nextInt(); //读取文本文件第一行第二个元素（代表临边个数）
            if (E < 0) 
                throw new IllegalArgumentException("number of edges in a Graph must be nonnegative");

            for (int i = 0; i < E; i++) { 
                int v = scanner.nextInt(); //读取第二行第一个元素(代表节点)
                int w = scanner.nextInt(); //读取第二行第二个元素(代表节点)
                assert v >= 0 && v < V;
                assert w >= 0 && w < V;
            //在这两个节点之间加一条临边,调用的是传进来的graph所对应子类的addEdge方法。     
                graph.addEdge(v, w); 
            }
        }
        catch (InputMismatchException e) {
            String token = scanner.next();
            throw new InputMismatchException("attempts to read an 'int' value from input stream, but the next token is \"" + token + "\"");
        }
        catch (NoSuchElementException e) {
            throw new NoSuchElementException("attemps to read an 'int' value from input stream, but there are no more tokens available");
        }
    }

    private void readFile(String filename){ //定义读取文件的方法
        assert filename != null;
        try {
            File file = new File(filename);
            if (file.exists()) { //如果该文件存在
                FileInputStream fis = new FileInputStream(file);
                scanner = new Scanner(new BufferedInputStream(fis), "UTF-8");
                scanner.useLocale(Locale.ENGLISH);
            }
            else
                throw new IllegalArgumentException(filename + "doesn't exist.");
        }
        catch (IOException ioe) { //无法打开该文件
            throw new IllegalArgumentException("Could not open " + filename, ioe);
        }
    }
}

4、测试通过文件读取图的信息

传入testG1.txt

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
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
testG1.txt
13 13   //13个节点和13条临边
0 5     //节点0和节点5有一条临边
4 3
0 1
9 12
6 4
5 4
0 2
11 12
9 10
0 6
7 8
9 11
5 3

testG2.txt
6 8    //6个节点和8条临边
0 1    //0和1之间有一条临边
0 2
0 5
1 2
1 3
1 4
3 4
3 5
// 测试通过文件读取图的信息
public class Main {

    public static void main(String[] args) {

        // 使用两种图的存储方式读取testG1.txt文件
        String filename = "testG1.txt";
        SparseGraph g1 = new SparseGraph(13, false);  //g1有13个节点，无向图
        ReadGraph readGraph1 = new ReadGraph(g1, filename);
        System.out.println("test G1 in Sparse Graph:");
        g1.show();

        System.out.println();

        DenseGraph g2 = new DenseGraph(13, false);
        ReadGraph readGraph2 = new ReadGraph(g2 , filename );
        System.out.println("test G1 in Dense Graph:");
        g2.show();

        System.out.println();

        // 使用两种图的存储方式读取testG2.txt文件
        filename = "testG2.txt";
        SparseGraph g3 = new SparseGraph(6, false);
        ReadGraph readGraph3 = new ReadGraph(g3, filename);
        System.out.println("test G2 in Sparse Graph:");
        g3.show();

        System.out.println();

        DenseGraph g4 = new DenseGraph(6, false);
        ReadGraph readGraph4 = new ReadGraph(g4, filename);
        System.out.println("test G2 in Dense Graph:");
        g4.show();
    }
}

输出结果

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
45
test G1 in Sparse Graph:
vertex 0:	5	1	2	6	
vertex 1:	0	
vertex 2:	0	
vertex 3:	4	5	
vertex 4:	3	6	5	
vertex 5:	0	4	3	
vertex 6:	4	0	
vertex 7:	8	
vertex 8:	7	
vertex 9:	12	10	11	
vertex 10:	9	
vertex 11:	12	9	
vertex 12:	9	11	

test G1 in Dense Graph:
false	true	true	false	false	true	true	false	false	false	false	false	false	
true	false	false	false	false	false	false	false	false	false	false	false	false	
true	false	false	false	false	false	false	false	false	false	false	false	false	
false	false	false	false	true	true	false	false	false	false	false	false	false	
false	false	false	true	false	true	true	false	false	false	false	false	false	
true	false	false	true	true	false	false	false	false	false	false	false	false	
true	false	false	false	true	false	false	false	false	false	false	false	false	
false	false	false	false	false	false	false	false	true	false	false	false	false	
false	false	false	false	false	false	false	true	false	false	false	false	false	
false	false	false	false	false	false	false	false	false	false	true	true	true	
false	false	false	false	false	false	false	false	false	true	false	false	false	
false	false	false	false	false	false	false	false	false	true	false	false	true	
false	false	false	false	false	false	false	false	false	true	false	true	false	

test G2 in Sparse Graph:
vertex 0:	1	2	5	
vertex 1:	0	2	3	4	
vertex 2:	0	1	
vertex 3:	1	4	5	
vertex 4:	1	3	
vertex 5:	0	3	

test G2 in Dense Graph:
false	true	true	false	false	true	
true	false	true	true	true	false	
true	true	false	false	false	false	
false	true	false	false	true	true	
false	true	false	true	false	false	
true	false	false	true	false	false

图的遍历：

相当于在漆黑的夜里，你只能看清你站的位置和你前面的路，但你不知道每条路能够通向哪里。搜索的任务就是，给出初始位置和目标位置，要求找到一条到达目标的路径。

图的遍历就是要找出图中所有的点，一般有以下两种方法：

  • 深度优先就是，从初始点出发，不断向前走，如果碰到死路了，就往回走一步，尝试另一条路，直到发现了目标位置。这种不撞南墙不回头的方法，即使成功也不一定找到一条好路，但好处是需要记住的位置比较少。
  • 广度优先就是，从初始点出发，把所有可能的路径都走一遍，如果里面没有目标位置，则尝试把所有两步能够到的位置都走一遍，看有没有目标位置；如果还不行，则尝试所有三步可以到的位置。这种方法，一定可以找到一条最短路径，但需要记忆的内容实在很多，要量力而行。

1. 深度优先遍历：(Depth First Search, DFS)

基本思路：深度优先遍历图的方法是，从图中某顶点 v 出发

  1. 访问顶点 v
  2. 从 v 的未被访问的邻接点中选取一个顶点 w，从 w 出发进行深度优先遍历
  3. 重复上述两步，直至图中所有和v有路径相通的顶点都被访问到

伪码实现：

1
2
3
4
5
6
7
8
9
//伪码实现，类似于树的先序遍历
public void DFS(Vertex v){
    visited[v] = true;   //遍历此节点
    for(v 的每个邻接点 W){
        if(!visited[W]){ //如果没有遍历这个节点。
	    DFS(W);          //则递归去遍历它
	    }
    }
}

连通分量

无向图G的极大连通子图称为G的最强连通分量(Connected Component)。 注意： 　　① 任何连通图的连通分量只有一个，即是其自身 　② 非连通的无向图有多个连通分量。 【例】下图中的G4是非连通图，它有两个连通分量H1和H2。

img

求无权图的联通分量

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
45
46
47
48
49
50
51
52
53
// 求无权图的联通分量
public class Components {

    Graph G;                    // 图的引用
    private boolean[] visited;  // 记录dfs的过程中节点是否被访问
    private int ccount;         // 记录联通分量个数
    private int[] id;           // 每个节点所对应的联通分量标记

    // 图的深度优先遍历
    void dfs( int v ){

        visited[v] = true; //遍历此节点
        id[v] = ccount;    

        for( int i: G.adj(v) ){//循环和adj()函数遍历图中v这个节点所有相连节点
            if( !visited[i] )
                dfs(i);
        }
    }

    // 构造函数, 求出无权图的联通分量。
    public Components(Graph graph){

        // 算法初始化
        G = graph;
        visited = new boolean[G.V()]; //根据图中节点数量给visited开空间
        id = new int[G.V()]; 
        ccount = 0;
        for( int i = 0 ; i < G.V() ; i ++ ){ //通过循环初始化visited，将每个元素都设为false
            visited[i] = false;
            id[i] = -1;
        }

        // 求图的联通分量
        for( int i = 0 ; i < G.V() ; i ++ ) //
            if( !visited[i] ){ //如果该节点没有被访问过(visited[i]为false)
                dfs(i);        //dfs()它可以将i和与i相连接的所有节点遍历一遍，没遍历的节点一定在另外的一个联通分量中
                ccount ++;
            }
    }

    // 返回图的联通分量个数
    int count(){
        return ccount;
    }

    // 查询点v和点w是否联通
    boolean isConnected( int v , int w ){
        assert v >= 0 && v < G.V();
        assert w >= 0 && w < G.V();
        return id[v] == id[w];
    }
}

深度优先搜索寻路

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
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
import java.util.Vector;
import java.util.Stack;

public class Path {

    private Graph G;   // 图的引用
    private int s;     // 起始点
    private boolean[] visited;  // 记录dfs的过程中节点是否被访问
    private int[] from;         // 记录路径, from[i]表示查找的路径上i的上一个节点

    // 图的深度优先遍历
    private void dfs( int v ){
        visited[v] = true;
        for( int i : G.adj(v) )
            if( !visited[i] ){
                from[i] = v;
                dfs(i);
            }
    }

    // 构造函数, 寻路算法, 寻找图graph从s点到其他点的路径
    public Path(Graph graph, int s){

        // 算法初始化
        G = graph;
        assert s >= 0 && s < G.V();    //先判断s是否越界
        visited = new boolean[G.V()];  //visited的长度定义为图G中节点个数
        from = new int[G.V()];         //from长度也定义为图G中节点个数
        for( int i = 0 ; i < G.V() ; i ++ ){ //初始默认所有节点都没有被遍历，前一个节点为-1
            visited[i] = false;
            from[i] = -1;
        }
	this.s = s;                    
	
        // 寻路算法
        dfs(s);
    }

    // 查询从s点到w点是否有路径
    boolean hasPath(int w){
        assert w >= 0 && w < G.V();
        return visited[w];     //如果w被遍历了，证明s和w之间有路径（同一个连通分量）
    }

    // 查询从s点到w点的路径, 存放在vec中
    Vector<Integer> path(int w){

        assert hasPath(w) ;

        Stack<Integer> s = new Stack<Integer>();
        // 通过from数组逆向查找到从s到w的路径, 存放到栈中
        int p = w;           //设置指针p指向当前节点w
        while( p != -1 ){    //不是起始节点。因为起始节点的前一个节点是-1，而当p==-1时，证明起始节点已经压入栈中，则退出循环
            s.push(p);       //将当前节点压入栈中
            p = from[p];     //指针p指向当前节点的前一个节点
        }

        // 从栈中依次取出元素, 获得顺序的从s到w的路径
        Vector<Integer> res = new Vector<Integer>();
        while( !s.empty() )   //只要栈不为空，则出栈
            res.add( s.pop() );

        return res;
    }

    // 打印出从s点到w点的路径
    void showPath(int w){

        assert hasPath(w) ;        

        Vector<Integer> vec = path(w);  
        for( int i = 0 ; i < vec.size() ; i ++ ){ //
            System.out.print(vec.elementAt(i));
            if( i == vec.size() - 1 )  //遍历到了最后一个节点
                System.out.println();
            else                       
                System.out.print(" -> ");
        }
    }
}

测试寻路算法

传入文件testG.txt

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
7 8   //该图有7个节点8条临边
0 1   //节点0和节点1之间有一条临边
0 2   
0 5
0 6
3 4
3 5
4 5
4 6
public class Main {

    // 测试寻路算法
    public static void main(String[] args) {

        String filename = "testG.txt";
        SparseGraph g = new SparseGraph(7, false);
        ReadGraph readGraph = new ReadGraph(g, filename);
        g.show();
        System.out.println();

        Path path = new Path(g,0);
        System.out.println("Path from 0 to 6 : ");
        path.showPath(6);
    }
}

结果表示

1
2
3
4
5
6
7
8
9
10
vertex 0:	1	2	5	6	
vertex 1:	0	
vertex 2:	0	
vertex 3:	4	5	
vertex 4:	3	5	6	
vertex 5:	0	3	4	
vertex 6:	0	4	

Path from 0 to 6 : 
0 -> 5 -> 3 -> 4 -> 6

2. 广度优先搜索：(Breadth First Search, BFS)–无权图最短路径

广度优先搜索，可以被形象地描述为 “浅尝辄止”，它也需要借助一个队列以保持遍历过的顶点顺序，以便按出队的顺序再去访问这些顶点的邻接顶点。

实现思路：

  1. 顶点 s 入队列,标记s已被访问，把s的顺序标记为0
  2. 开始循环，当队列非空时则继续执行，否则结束
  3. 出队列取得队头节点并记作 v
  4. 查找顶点 v 的第一个邻接顶点 i。(通过循环迭代adj()方法)
  5. 若 v 的邻接顶点 i 未被访问过的，则把节点 i 加入队列，标记节点 i 已被访问， 记录路径，即把v存进from[i]表示查找的路径上i的上一个节点，并在遍历次序加一。
  6. 查找顶点v 的另一个新的邻接顶点 i`，转到步骤 5 入队列，直到顶点 v 的所有未被访问过的邻接点处理完。转到步骤 2，结束循环

要理解深度优先和广度优先搜索，首先要理解搜索步，一个完整的搜索步包括两个处理

  1. 获得当前位置上，有几条路可供选择
  2. 根据选择策略，选择其中一条路，并走到下个位置
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
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
import java.util.Vector;
import java.util.Stack;
import java.util.LinkedList;
import java.util.Queue;

public class ShortestPath {

    private Graph G;   // 图的引用
    private int s;     // 起始点
    private boolean[] visited;  // 记录dfs的过程中节点是否被访问
    private int[] from;         // 记录路径, from[i]表示查找的路径上i的上一个节点
    private int[] ord;          // 记录路径中节点的次序。ord[i]表示i节点在路径中的次序。


    // 构造函数, 寻路算法, 寻找图graph从s点到其他点的路径
    public ShortestPath(Graph graph, int s){

        // 算法初始化
        G = graph;
        assert s >= 0 && s < G.V();

        visited = new boolean[G.V()];  //是否已经遍历
        from = new int[G.V()];
        ord = new int[G.V()];
        for( int i = 0 ; i < G.V() ; i ++ ){
            visited[i] = false;
            from[i] = -1;
            ord[i] = -1;
        }
        this.s = s;

        // 无向图最短路径算法, 从s开始广度优先遍历整张图
        Queue<Integer> q = new LinkedList<Integer>();

        q.add(s);               //把点s加入队列
        visited[s] = true;      //点s已经遍历
        ord[s] = 0;             //记录点s遍历的顺序
        while( !q.isEmpty() ){  //如果队列不为空
            int v = q.remove(); //把点s移除队列记录为v
            for( int i : G.adj(v) ) //通过循环和adj函数遍历与v相邻的节点i
                if( !visited[i] ){  //如果i没有被遍历
                    q.add(i);       //就把i加进队列
                    visited[i] = true; //遍历节点i
                    from[i] = v;    //把v存进from[i]表示查找的路径上i的上一个节点
                    ord[i] = ord[v] + 1;  //次序加一
                }
        }
    }

    // 查询从s点到w点是否有路径
    public boolean hasPath(int w){
        assert w >= 0 && w < G.V(); 
        return visited[w];
    }

    // 查询从s点到w点的路径, 存放在vec中
    public Vector<Integer> path(int w){

        assert hasPath(w) ;

        Stack<Integer> s = new Stack<Integer>();
        // 通过from数组逆向查找到从s到w的路径, 存放到栈中
        int p = w;
        while( p != -1 ){
            s.push(p);
            p = from[p];
        }

        // 从栈中依次取出元素, 获得顺序的从s到w的路径
        Vector<Integer> res = new Vector<Integer>();
        while( !s.empty() )
            res.add( s.pop() );

        return res;
    }

    // 打印出从s点到w点的路径
    public void showPath(int w){

        assert hasPath(w) ;

        Vector<Integer> vec = path(w);
        for( int i = 0 ; i < vec.size() ; i ++ ){
            System.out.print(vec.elementAt(i));
            if( i == vec.size() - 1 )
                System.out.println();
            else
                System.out.print(" -> ");
        }
    }

    // 查看从s点到w点的最短路径长度
    // 若从s到w不可达，返回-1
    public int length(int w){
        assert w >= 0 && w < G.V();
        return ord[w];
    }
}

测试无权图最短路径算法 导入文件

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
//testG.txt
7 8   //7个节点8个临边
0 1   //0和1之间有一条临边
0 2
0 5
0 6
3 4
3 5
4 5
4 6

//testG1.txt
13 13 //13个节点和13条临边
0 5   //0和5之间有一条临边
4 3
0 1
9 12
6 4
5 4
0 2
11 12
9 10
0 6
7 8
9 11
5 3

开始测试

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
public class Main {

    // 测试无权图最短路径算法
    public static void main(String[] args) {

        String filename = "testG.txt";
        SparseGraph g = new SparseGraph(7, false);
        ReadGraph readGraph = new ReadGraph(g, filename);
        g.show();

        // 比较使用深度优先遍历和广度优先遍历获得路径的不同
        // 广度优先遍历获得的是无权图的最短路径
        Path dfs = new Path(g,0);
        System.out.print("DFS : ");
        dfs.showPath(6);

        ShortestPath bfs = new ShortestPath(g,0);
        System.out.print("BFS : ");
        bfs.showPath(6);

        System.out.println();

        filename = "testG1.txt";
        SparseGraph g2 = new SparseGraph(13, false);
        ReadGraph readGraph2 = new ReadGraph(g2, filename);
        g2.show();

        // 比较使用深度优先遍历和广度优先遍历获得路径的不同
        // 广度优先遍历获得的是无权图的最短路径
        Path dfs2 = new Path(g2,0);
        System.out.print("DFS : ");
        dfs2.showPath(3);

        ShortestPath bfs2 = new ShortestPath(g,0);
        System.out.print("BFS : ");
        bfs.showPath(3);
    }
}

输出结果

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
vertex 0:	1	2	5	6	
vertex 1:	0	
vertex 2:	0	
vertex 3:	4	5	
vertex 4:	3	5	6	
vertex 5:	0	3	4	
vertex 6:	0	4	
DFS : 0 -> 5 -> 3 -> 4 -> 6
BFS : 0 -> 6

vertex 0:	5	1	2	6	
vertex 1:	0	
vertex 2:	0	
vertex 3:	4	5	
vertex 4:	3	6	5	
vertex 5:	0	4	3	
vertex 6:	4	0	
vertex 7:	8	
vertex 8:	7	
vertex 9:	12	10	11	
vertex 10:	9	
vertex 11:	12	9	
vertex 12:	9	11	
DFS : 0 -> 5 -> 4 -> 3
BFS : 0 -> 5 -> 3

最短路径算法 (Shortest Path Algorithm)

  1. 无权图：

问题：在图中找到某一个顶点到其它所有点的距离

对于初始点 v 来说，某个点的 d 代表该点到初始点的距离。

基本步骤：

  1. 将所有点的距离 d 设为无穷大
  2. 挑选初始点 s，将 ds 设为 0，将 shortest 设为 0
  3. 找到所有距离为 d 为 shortest 的点，查找他们的邻接链表的下一个顶点 w，如果 dw 的值为无穷大，则将 dw 设为 shortest + 1
  4. 增加 shortest 的值，重复步骤 3，直到没有顶点的距离值为无穷大

img

\2. 有权图：

在有权图中，常见的最短路径算法有 Dijkstra 算法 Floyd 算法

迪杰斯特拉 Dijkstra 算法：Dijkstra 算法适用于权值为正的的图

Dijkstra 算法属于单源算法，即只能求出某点到其它点最短距离，并不能得出任意两点之间的最短距离。

算法步骤：

  1. 将所有边初始化为无穷大
  2. 选择一个开始的顶点，添加到优先队列中
  3. 对于该点的所有邻接顶点进行判断，如果到该点的距离小于原先的值，则将该值进行更新
  4. 将该点所有邻接顶点添加到优先队列中
  5. 从优先队列中挑选出一个路径值最小的顶点，将其弹出，作为新的顶点，重复步骤 3，4，5
  6. 直到所有点都被处理过一次

例如：

img

首先选取 v0 作为起始点，添加到优先队列中，将v0弹出，然后对 v0 邻接点进行判断，由于一开始所有边都为无穷大，那么 <v0, v1> 和 <v0, v3> 都更新，值为 2 和 1，按路径大小升序将v3、v1添加到优先队列。

img

之后将 v3 弹出，对所有 v3 邻接点进行值的更新，并将所有邻接点按路径大小升序添加到优先队列中，若遇到值相同，则无所谓其先后顺序

img

img

重复这样的过程，直到所有的点都被处理过，则算法终止，这样最后可以得出从 v0 到其它 v1~v6 节点的距离。

Dijkstra 算法适合于权值为正的情况下，若权值为负则不能使用，因为出现死循环。这时候我们需要计算每个顶点被处理的次数，当某个顶点已经处理过的话，就跳出该循环。

佛洛伊德 Floyd 算法：可以求出任意两点的最短距离

Floyd 算法是一个经典的动态规划算法。用通俗的语言来描述的话，首先我们的目标是寻找从点 i 到点 j 的最短路径。

从任意节点 i 到任意节点 j 的最短路径不外乎 2 种可能：

  1. 是直接从 i 到 j
  2. 是从 i 经过若干个节点 k 到 j

所以，我们假设 Dis(i,j) 为节点 u 到节点 v 的最短路径的距离，对于每一个节点 k，我们检查Dis(i,k) + Dis(k,j) < Dis(i,j) 是否成立，如果成立，证明从 i 到 k 再到 j 的路径比 i 直接到 j 的路径短，我们便设置 Dis(i,j) = Dis(i,k) + Dis(k,j)，这样一来，当我们遍历完所有节点 k，Dis(i,j) 中记录的便是 i 到 j 的最短路径的距离。

时间复杂度： O(n^3)

1
2
3
4
5
6
7
8
9
for(int k=0; k<n; k++) { 
    for(i=0; i<n; i++) {
         for(j=0; j<n; j++)
             if(A[i][j]>(A[i][k]+A[k][j])) {
                  A[i][j]=A[i][k]+A[k][j];
                  path[i][j]=k;
             } 
    }
}

最小生成树 (Minimum Spanning Trees MST)

例如：要在 n 个城市之间铺设光缆，主要目标是要使这 n 个城市的任意两个之间都可以通信，但铺设光缆的费用很高，且各个城市之间铺设光缆的费用不同，因此另一个目标是要使铺设光缆的总费用最低。这就需要找到带权的最小生成树。

特点：

  1. 该树是连通的
  2. 权值之和最小
  3. 边数比顶点个数少 1

存在个数：最小生成树在一些情况下可能会有多个

  1. 当图的每一条边的权值都相同时，该图的所有生成树都是最小生成树
  2. 如果图的每一条边的权值都互不相同，那么最小生成树将只有一个

比如：

img

生成最小生成树的算法一般有两种，分别是 Prim 算法和 Kruskal 算法

1. 普里姆算法 (Prim 算法):

算法步骤：

  1. 输入：一个加权连通图，其中顶点集合为 V，边集合为 E
  2. 初始化：Vnew = {x}，其中 x 为集合 V 中的任一节点(起始点)，Enew = {} 为空
  3. 在集合 E 中选取权值最小的边 <u, v>，其中 u 为集合 Vnew 中的元素，而 v 不在 Vnew 集合当中，并且 v∈V (如果存在有多条满足前述条件即具有相同权值的边，则可任意选取其中之一）
  4. 将 v 加入集合 Vnew 中，将 <u, v> 边加入集合 Enew 中
  5. 重复步骤 3、4 直到 Vnew = V

时间复杂度：O(V^2)

2. Kruskal 算法：需要一个集合用来升序存储所有边

算法步骤：

  1. 先构造一个只含有 n 个顶点，而边集为空的子图
  2. 从边集 E 中选取一条权值最小的边，若该条边的两个顶点分属不同的树，则将其加入子图。(也就是说，将这两个顶点分别所在的两棵树合成一棵树) 反之，若该条边的两个顶点已落在同一棵树上，则不可取，而应该取下一条权值最小的边再试之
  3. 重复步骤 2，直到所有点连通

时间复杂度：O( ElogV )

例如：

img

在对所有边进行排序之后，我们得到一个边集合，从边集合中取出最小权的边 AD

img

剩下的边中寻找。我们找到了 CE。这里边的权重也是 5，依次类推我们找到了 6,7,7

img

尽管现在长度为 8 的边是最小的未选择的边。但是他们已经连通了

img

最后就剩下 EG 和 FG 了。当然我们选择了 EG