数据结构-6-图

发表于 | 分类于 | 评论数： | 阅读次数：

实现邻接矩阵表示图

邻接矩阵
实现有向图、无向图、有权图、无权图的邻接矩阵表示方法

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
# coding:utf-8
# 邻接矩阵

# 构建邻接矩阵
n, m = map(int, input().split())  # 顶点与边个数
e = [[9999999 for i in range(n + 1)] for i in range(n + 1)]  # 图存入邻接矩阵
for i in range(1, n + 1):
    e[i][i] = 0
for i in range(m):
    a, b = map(int, input().split())
    e[a][b] = 1
    e[b][a] = 1

# 遍历
for i in range(1, n + 1):
    for j in range(1, n + 1):
        print(e[i][j], end=" ")
    print()

'''
input：
5 5
1 2
1 3
1 5
2 4
3 5
output:
0 1 1 9999999 1 
1 0 9999999 1 9999999 
1 9999999 0 9999999 1 
9999999 1 9999999 0 9999999 
1 9999999 1 9999999 0 
'''

实现邻接表表示图

实现有向图、无向图、有权图、无权图的邻接表表示方法

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
# coding:utf-8
# 邻接表：使用列表实现邻接表。

# 构建邻接表
n, m = map(int, input().split()) # 顶点数和边数
u = [0 for i in range(m + 1)]
v = [0 for i in range(m + 1)]
w = [0 for i in range(m + 1)]
first = [-1 for i in range(n + 1)]
nex = [0 for i in range(m + 1)]
for i in range(1, m + 1):  # 读入边
    u[i], v[i], w[i] = map(int, input().split())
    nex[i] = first[u[i]]
    first[u[i]] = i
print(first[1:], nex[1:])

# 遍历每个顶点的边
for i in range(1, n + 1):
    k = first[i]
    while k != -1:
        print(u[k], v[k], w[k])
        k = nex[k]

'''
input：
4 5
1 4 9
4 3 8
1 2 5
2 4 6
1 3 7
output:
[5, 4, -1, 2] [-1, -1, 1, -1, 3]
1 3 7
1 2 5
1 4 9
2 4 6
4 3 8
'''

# first中，1号顶点的第一条边是编号为5的边（即1 3 7）
# next中，1号顶点，编号为5的边的下一条边编号为3（1 2 5），然后是1 4 9
# 即找到1号顶点的一条边后，剩下的边都可以在next数组中找到

# k=first[1]
# while k!=-1:
# 	print u[k],v[k],w[k]
# 	k=next[k]
# 每个顶点都设置了一个链表，保存了从顶底i出发的所有边的序号。
# 用邻接表存储图的时间复杂度是O(M)，遍历每条边的时间复杂度也是O(M)
# 如果一个图是稀疏图的话，M要远小于N^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
from collections import defaultdict


class Graph:

    def __init__(self):
        self.graph = defaultdict(list)  # 使用{v:[],v:[]}表示

    def add_edge(self, u, v):
        self.graph[u].append(v)

    def dfs_node(self, v, visited):
        visited[v] = True  # 当前访问的标记为True
        print(v, end=" ")

        for i in self.graph[v]:
            if visited[i] == False:
                self.dfs_node(i, visited)

    def dfs(self, v):
        visited = [False] * (len(self.graph))  # visited中所有节点初始化为False
        self.dfs_node(v, visited)

        # for i in range(len(self.graph)):
        #     if visited[i] == False:
        #         self.dfs_node(i, visited)

    def bfs(self, v):

        visited = [False] * (len(self.graph))
        queue = []
        queue.append(v)
        visited[v] = True

        while queue:

            s = queue.pop(0)
            print(s, end=" ")
            for i in self.graph[s]:
                if visited[i] == False:
                    queue.append(i)
                    visited[i] = True


g = Graph()
g.add_edge(0, 1)
g.add_edge(0, 2)
g.add_edge(1, 2)
g.add_edge(2, 0)
g.add_edge(2, 3)
g.add_edge(3, 3)
g.dfs(2)
# 2 0 1 3
print("\n")
g.bfs(2)
# 2 0 3 1

实现 Dijkstra 算法、A* 算法

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
# coding:utf-8
# Dijkstra算法：单源最短路径。求顶点1到其他顶点的最短路径。

n,m=map(int,raw_input().split())
inf=999999
e=[[inf for i in range(n+1)] for i in range(n+1)]
for i in range(n):
	e[i+1][i+1]=0
for i in range(m):
	a,b,c=map(int,raw_input().split())
	e[a][b]=c
dis=[0 for i in range(n+1)]
for i in range(1,n+1): #初始化dis列表
	dis[i]=e[1][i]
book=[0 for i in range(n+1)]
book[1]=1

for i in range(1,n+1):
	mi=inf #找到离1号顶点距离最近的点
	for j in range(1,n+1):
		if book[j]==0 and dis[j]<mi:
			mi=dis[j]
			u=j
	book[u]=1
	for v in range(1,n+1):
		if e[u][v]<inf and dis[v]>dis[u]+e[u][v]:
			dis[v]=dis[u]+e[u][v]

for i in range(1,n+1):
	print dis[i],

'''
input：
6 9
1 2 1
1 3 12
2 3 9
2 4 3
3 5 5
4 3 4
4 5 13
4 6 15
5 6 4
output:
0 1 8 4 13 17
'''

# 用邻接矩阵存，时间复杂度O(N^2)，不能有负权边。
# 基于贪心策略，每次扩展路径最短的点，更新与其相邻的点的路程。
# M远小于N^2的图称为稀疏图，而M相对较大的图称为稠密图
# 对于变数M少于N^2的稀疏图来说，用邻接表代替邻接矩阵，时间复杂度O(M+N)logN
# M在最坏情况下是N^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
# coding:utf-8
import sys

inf = 9999999


class Graph():

    def __init__(self, n):
        self.n = n  # 顶点数
        self.graph = [[0 for column in range(n)]
                      for row in range(n)]

    def printSolution(self, dist):
        for node in range(self.n):
            print(node, "\t", dist[node])

    def minDistance(self, dist, sptSet):
        min = inf
        for v in range(self.n):
            if dist[v] < min and sptSet[v] == False:
                min = dist[v]
                min_index = v

        return min_index

    def dijkstra(self, src):
        dist = [inf] * self.n
        dist[src] = 0
        sptSet = [False] * self.n

        for cout in range(self.n):
            u = self.minDistance(dist, sptSet)
            sptSet[u] = True
            for v in range(self.n):
                if self.graph[u][v] > 0 and sptSet[v] == False and dist[v] > dist[u] + self.graph[u][v]:
                    dist[v] = dist[u] + self.graph[u][v]
        self.printSolution(dist)


g = Graph(9)
g.graph = [[0, 4, 0, 0, 0, 0, 0, 8, 0],
           [4, 0, 8, 0, 0, 0, 0, 11, 0],
           [0, 8, 0, 7, 0, 4, 0, 0, 2],
           [0, 0, 7, 0, 9, 14, 0, 0, 0],
           [0, 0, 0, 9, 0, 10, 0, 0, 0],
           [0, 0, 4, 14, 10, 0, 2, 0, 0],
           [0, 0, 0, 0, 0, 2, 0, 1, 6],
           [8, 11, 0, 0, 0, 0, 1, 0, 7],
           [0, 0, 2, 0, 0, 0, 6, 7, 0]
           ]

g.dijkstra(0)

"""
0 	 0
1 	 4
2 	 12
3 	 19
4 	 21
5 	 11
6 	 9
7 	 8
8 	 14
"""

实现拓扑排序的 Kahn 算法、DFS 算法

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
from collections import defaultdict


class Graph:
    def __init__(self, n):
        self.graph = defaultdict(list)
        self.n = n

    def addEdge(self, u, v):
        self.graph[u].append(v)

    def topologicalSort(self):

        in_degree = [0] * (self.n)

        for i in self.graph:
            for j in self.graph[i]:
                in_degree[j] += 1

        queue = []
        for i in range(self.n):
            if in_degree[i] == 0:
                queue.append(i)

        cnt = 0
        top_order = []

        while queue:

            u = queue.pop(0)
            top_order.append(u)

            for i in self.graph[u]:
                in_degree[i] -= 1
                if in_degree[i] == 0:
                    queue.append(i)
            cnt += 1

        if cnt != self.n:
            print("存在环")
        else:
            print(top_order)


g = Graph(6)
g.addEdge(5, 2)
g.addEdge(5, 0)
g.addEdge(4, 0)
g.addEdge(4, 1)
g.addEdge(2, 3)
g.addEdge(3, 1)

g.topologicalSort()
# [4, 5, 2, 0, 3, 1]

对应的 LeetCode 练习题

Number of Islands（岛屿的个数）

英文版：https://leetcode.com/problems/number-of-islands/description/

中文版：https://leetcode-cn.com/problems/number-of-islands/description/

Valid Sudoku（有效的数独）

英文版：https://leetcode.com/problems/valid-sudoku/

中文版：https://leetcode-cn.com/problems/valid-sudoku/