图的邻接矩阵、邻接表遍历(python实现)(递归与非递归)(dfs bfs)_图遍历 环 python 邻接矩阵

图的python实现

---

图的储存

1.邻接矩阵

2.邻接表

---

图的遍历

DFS

递归与非递归

---

BFS

递归非递归

---

代码实现

---

图的邻接矩阵的遍历

"""
author:Anderson
data:2020-11-13
图的邻接矩阵的遍历（递归与非递归）
"""

class GraphAX:
    def __init__(self, vertx, mat):  # vertx 顶点表；mat邻接矩阵
        self.vnum = len(vertx)
        self.vertx = vertx
        self.mat = mat  # [mat[i][:] for i in range(vnum)]


def creat_matrix():
    nodes = ['v0', 'v1', 'v2', 'v3', 'v4']
    matrix = [[0, 1, 0, 1, 0],
              [1, 0, 1, 0, 1],
              [0, 1, 0, 1, 1],
              [1, 0, 1, 0, 0],
              [0, 1, 1, 0, 0]]
    mygraph = GraphAX(nodes, matrix)
    return mygraph


def DFS1(graph, cur_vertx_indx):  # 递归方式
    global visited_list
    v = graph.vertx[cur_vertx_indx]
    print(v, end=' ')
    visited_list[cur_vertx_indx] = 1
    w = []
    for i in range(graph.vnum):
        if graph.mat[cur_vertx_indx][i] == 1 and visited_list[i] == 0:
            w.append(i)
    if len(w) != 0:
        for i in range(len(w)):
            a = w[i]
            if visited_list[a] == 0:
                DFS1(graph, a)


class Sstack():
    def __init__(self):
        self.slist = []

    def is_empty(self):
        if self.slist == []:
            return 1
        else:
            return 0

    def pushstack(self, data):
        self.slist.append(data)

    def popstack(self):
        return self.slist.pop()

def DFS2(graph, cur_vertx_indx):  # 非递归方式
    visited_li = [0] * graph.vnum
    s = Sstack()
    s.pushstack(cur_vertx_indx)
    print(graph.vertx[cur_vertx_indx], end=' ')
    visited_li[cur_vertx_indx] = 1
    while s.is_empty() !=1:
        for j in range(graph.vnum):
            if graph.mat[cur_vertx_indx][j]==1 and visited_li[j]==0:
                print(graph.vertx[j],end=' ')
                visited_li[j]=1
                s.pushstack(j)
                cur_vertx_indx=j
        if s.is_empty()!=1:
            cur_vertx_indx=s.popstack()


if __name__ == '__main__':
    graph = creat_matrix()
    print('图的顶点表为：')
    print(graph.vertx)
    print('\n图的邻接矩阵为®：')
    print(graph.mat)
    print('\n深度遍历（递归）:')
    visited_list = [0] * graph.vnum
    DFS1(graph, 0)
    print('\n\n深度遍历（非递归）:')
    DFS2(graph, 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
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

---

图的邻接表的遍历

"""
author:Anderson
data:2020-11-13
图的邻接表阵的遍历（bfs）以及求出每个顶点的度

"""
class Anode:  # 边表节点类
    def __init__(self, adjvex, weight=0):
        self.Adjvex = adjvex  # 邻接点在顶点列表中的下标
        self.Next = None
        self.Weight = weight


class Vnode:  # 顶点表节点类
    def __init__(self, data):
        self.Data = data  # 顶点的值
        self.Firstarc = None  # 指向边表（单链表）的表头节点


class Graph:
    def __init__(self):
        self.vertList = []  # 表头列表
        self.numVertics = 0  # 实际顶点数

    def add_vertex(self, key):
        vertex = Vnode(key)
        self.vertList.append(vertex)
        self.numVertics = self.numVertics + 1
        return vertex

    def add_edge(self, val1, val2, weight=0):  # 在val1 顶点和val2节点之间添加一个权值为weight的边
        i = 0
        while i < len(self.vertList):  # 判断val1是否存在于顶点表中
            if val1 == self.vertList[i].Data:
                vnode1 = self.vertList[i]
                break
            i = i + 1
        if i == len(self.vertList):  # if不在，生成val1节点加入到顶点表中
            vnode1 = self.add_vertex(val1)

        i = 0
        while i < len(self.vertList):  # 判断val2是否存在于顶点表中
            if val2 == self.vertList[i].Data:
                vnode2 = self.vertList[i]
                break
            i = i + 1
        if i == len(self.vertList):  # if不在，生成val2节点加入到顶点表中
            vnode2 = self.add_vertex(val2)

        v2id = self.vertList.index(vnode2)
        p = Anode(v2id, weight)
        p.Next = vnode1.Firstarc  ##头插法
        vnode1.Firstarc = p

        # 将val2 加入到val1的边表中,采用头插法


class Queue:
    def __init__(self, maxsize=20):
        self.sequeue = maxsize * [None]
        self.front = 0
        self.rear = 0
        self.maxsize = maxsize

    def is_empty(self):
        if self.front == self.rear:
            return 1
        else:
            return 0

    def inqueue(self, data):
        for i in range(self.maxsize):
            if self.sequeue[i] == None:
                self.sequeue[i] = data
                self.rear += 1
                break

    def dequeue(self):
        self.front += 1
        return self.sequeue.pop(0)


def BFS(graph, cur_vertex_ind):
    visited_list = [0] * graph.numVertics
    q = Queue()
    visited_list[cur_vertex_ind] = 1
    q.inqueue(cur_vertex_ind)
    while q.is_empty() != 1:
        temp = q.dequeue()
        node = graph.vertList[temp]
        if node.Firstarc != None:
            start = node.Firstarc
            if visited_list[start.Adjvex] == 0:
                q.inqueue(start.Adjvex)
                visited_list[start.Adjvex] = 1
            while start.Next != None:
                second = start.Next
                if visited_list[second.Adjvex] == 0:
                    q.inqueue(second.Adjvex)
                    visited_list[second.Adjvex] = 1
                start = second
        print(graph.vertList[temp].Data, end=' ')



def degree_each_node(nodeid):
    count=0
    node=graph.vertList[nodeid]
    if node.Firstarc!=None:
        count+=1
        start = node.Firstarc
        while start.Next!=None:
            second = start.Next
            count+=1
            start = second
    return count

def degree_node(graph):
    for i in range(graph.numVertics):
        print("degree of {} is {}".format(graph.vertList[i].Data,degree_each_node(int(i))),end='\n')




if __name__ == '__main__':
    graph = Graph()
    graph.add_vertex('v0')
    graph.add_vertex('v1')
    graph.add_vertex('v2')
    graph.add_vertex('v3')
    graph.add_vertex('v4')

    graph.add_edge('v0', 'v3')
    graph.add_edge('v0', 'v1')
    graph.add_edge('v1', 'v4')
    graph.add_edge('v1', 'v2')
    graph.add_edge('v1', 'v0')
    graph.add_edge('v2', 'v4')
    graph.add_edge('v2', 'v3')
    graph.add_edge('v2', 'v1')
    graph.add_edge('v3', 'v2')
    graph.add_edge('v3', 'v0')
    graph.add_edge('v4', 'v2')
    graph.add_edge('v4', 'v1')
    print('\n顶点表的元素为： ')
    for i in range(graph.numVertics):
        print(graph.vertList[i].Data, end=' ')

    print('\n\n邻接表的广度遍历：')
    BFS(graph, 0)

    print('\n')
    degree_node(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
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
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155

什么是邻接表？

---

邻接表包括顶点表，以及边表。