The realization of adjacency matrix mainly uses two-dimensional array
Establishment and traversal of adjacency matrix:
import numpy as np
class AdjacencyMatrix(): #Adjacency matrix class
def __init__(self,n=2):
self.Matrix=np.zeros((n,n)) #Fill 2D array with 0
def getMatrix(self): #Print adjacency matrix
for d in self.Matrix:
print(d)
def addEdge(self,x,y,value):
self.Matrix[x,y]=value #Setting 1 means that there is a relationship between nodes, and 0 means that there is no relationship
#================================
airport=AdjacencyMatrix(4) #Four airport nodes
airport.addEdge(0,1,1) #Establish relationship between A and B
airport.addEdge(0,2,1) #Relationship between A and C
airport.addEdge(0,3,1) #Relationship between A and D
airport.addEdge(2,3,1) #Relationship between C and D
airport.addEdge(3,0,1) #Establish relationship between D and A
airport.getMatrix() #Print adjacency table
The implementation of adjacency list is that all nodes are recorded in a dictionary, and each dictionary value points to the linked list of all edges related to the node, and all edges must be numbered in order.
Establishment and traversal of adjacency table:
class Node(): # Create a linked list node class
def __init__(self, NodeValue, Edgevalue):
self.Edgevalue = Edgevalue
self.NodeValue = NodeValue
self.Next = None
class AdjacencyTable():
def __init__(self, Lines):
self.Lines = Lines # Dictionary object
def getTopNode(self): # Get graph node
for k in self.Lines:
print("Graph node:", k)
def addNewEdgeNode(self, TopKey, NodeValue, EdgeValue): # Add linked list node
if TopKey in self.Lines: # Determine whether the key is in the dictionary
Address = self.Lines[TopKey] # Get the address pointing to the linked list
if Address is None:
self.Lines[TopKey] = Node(NodeValue, EdgeValue) # Add the first node of the linked list
else:
while Address: # Non empty address
if Address.Next:
Address = Address.Next
else: # If it is an empty address
Address.Next = Node(NodeValue, EdgeValue) # Add a new linked list node
break
else: # The dictionary does not have this key
print('No nodes in this diagram:', TopKey)
# ===============================================Graph traversal
def printAll(self):
if self.Lines is None:
print('The graph has no nodes!')
else:
for k, v in self.Lines.items():
print('Diagram node:', k)
while v:
print(' Its connection node is%d,Connecting edges are%d' % (v.NodeValue, v.Edgevalue))
v = v.Next
# ===============================================Instantiation
TopNode = {1: None, 2: None, 3: None, 4: None, 5: None, 6: None, 7: None}
CityLines = AdjacencyTable(TopNode)
CityLines.addNewEdgeNode(1, 2, 1)
CityLines.addNewEdgeNode(1, 3, 2)
CityLines.addNewEdgeNode(1, 4, 3)
CityLines.addNewEdgeNode(2, 6, 4)
CityLines.addNewEdgeNode(3, 6, 5)
CityLines.addNewEdgeNode(3, 5, 6)
CityLines.addNewEdgeNode(4, 5, 7)
CityLines.addNewEdgeNode(5, 7, 8)
CityLines.addNewEdgeNode(6, 7, 9)
CityLines.getTopNode()
print('Graph traversal:')
CityLines.printAll()
The dictionary is a little rusty again. I'm reviewing it
Dictionary: in order to save data with mapping relationship, Python provides a dictionary. The dictionary is equivalent to saving two groups of data, one of which is key data, called key; Another set of data can be accessed through key, which is called value. My personal understanding is equivalent to a one-to-one functional relationship. The computer obtains y by accessing x. Keys and values are separated by colons, items are separated by commas, and the whole dictionary is enclosed by braces {}.
Usage:
1,dict.clear()
clear() is used to clear all elements (key value pairs) in the dictionary. After executing the clear() method on a dictionary, the dictionary will become an empty dictionary.
list1 = ['Author', 'age', 'sex']
list2 = ['Python When the year of fighting', 99, 'male']
dic1 = dict(zip(list1, list2))
# dic1 = {'Author': 'Python's year of fighting', 'age': 99, 'sex': 'male'}
dic1.clear()
# dic1 = {}
**2. dict.copy()**copy() is used to return a shallow copy of a dictionary.
list1 = ['Author', 'age', 'sex']
list2 = ['Python When the year of fighting', 99, 'male']
dic1 = dict(zip(list1, list2))
dic2 = dic1 # Shallow copy: reference objects
dic3 = dic1.copy() # Shallow copy: deep copy the parent object (Level 1 directory), and the child object (Level 2 directory) is not copied or referenced
dic1['age'] = 18
# dic1 = {'Author': 'Python's year of fighting', 'age': 18, 'sex': 'male'}
# dic2 = {'Author': 'Python's year of fighting', 'age': 18, 'sex': 'male'}
# dic3 = {'Author': 'Python's year of fighting', 'age': 99, 'sex': 'male'}
dic2 is the reference of dic1, so the output results are consistent. The parent object of dic3 is a deep copy and will not be modified with the modification of dic1. The child object is a shallow copy, so it will be modified with the modification of dic1. Pay attention to the parent-child relationship.
Extended deep copy: copy.deepcopy()
import copy
list1 = ['Author', 'age', 'sex']
list2 = ['Python When the year of fighting', [18,99], 'male']
dic1 = dict(zip(list1, list2))
dic2 = dic1
dic3 = dic1.copy()
dic4 = copy.deepcopy(dic1)
dic1['age'].remove(18)
dic1['age'] = 20
# dic1 = {'Author': 'Python's year of fighting', 'age': 20, 'sex': 'male'}
# dic2 = {'Author': 'Python's year of fighting', 'age': 20, 'sex': 'male'}
# dic3 = {'Author': 'Python's fighting year', 'age': [99], 'sex': 'male'}
# dic4 = {'Author': 'Python's year of fighting', 'age': [18, 99], 'sex': 'male'}
dic2 is a reference to dic1, so the output results are consistent; The dic3 parent object is a deep copy and will not be modified with the modification of dic1. The child object is a shallow copy, so it will be modified with the modification of dic1; Dic4 makes a deep copy and recursively copies all data, which is equivalent to completely creating an original dictionary in another memory. Therefore, modifying dic1 will not affect the data of dic4
**3. dict.fromkeys()**fromkeys() creates a new dictionary with given keys. The default values are None. You can also pass in a parameter as the default value.
list1 = ['Author', 'age', 'sex']
dic1 = dict.fromkeys(list1)
dic2 = dict.fromkeys(list1, 'Python When the year of fighting')
# dic1 = {'Author': None, 'age': None, 'sex': None}
# Dic2 = {'author':'python when playing ',' age ':'python when playing', 'sex':'python when playing '}
4,dict.get()
get() is used to return the value of the specified key, that is, get the value according to the key. If the key does not exist, return None or specify the return value.
list1 = ['Author', 'age', 'sex']
list2 = ['Python When the year of fighting', [18,99], 'male']
dic1 = dict(zip(list1, list2))
Author = dic1.get('Author')
# Author = the year of Python
phone = dic1.get('phone')
# phone = None
phone = dic1.get('phone','12345678')
# phone = 12345678
**5. dict.items()**items() obtains all key value pairs in the dictionary. Generally, the results can be converted into a list for subsequent processing.
list1 = ['Author', 'age', 'sex']
list2 = ['Python When the year of fighting', [18,99], 'male']
dic1 = dict(zip(list1, list2))
items = dic1.items()
print('items = ', items)
print(type(items))
print('items = ', list(items))
# items = dict_ Items ([('author ',' Python when playing '), ('age', [18, 99]), ('sex ',' male '))
# <class 'dict_items'>
# Items = [('author ',' Python's playing year '), ('age', [18, 99]), ('sex ',' male ')]
**6. dict.keys()**keys() returns all keys of a dictionary.
list1 = ['Author', 'age', 'sex']
list2 = ['Python When the year of fighting', [18,99], 'male']
dic1 = dict(zip(list1, list2))
keys = dic1.keys()
print('keys = ', keys)
print(type(keys))
print('keys = ', list(keys))
# keys = dict_keys(['Author', 'age', 'sex'])
# <class 'dict_keys'>
# keys = ['Author', 'age', 'sex']
**7. dict.pop()**pop() returns the value corresponding to the specified key and deletes the key value pair from the original dictionary.
list1 = ['Author', 'age', 'sex']
list2 = ['Python When the year of fighting', [18,99], 'male']
dic1 = dict(zip(list1, list2))
sex = dic1.pop('sex')
print('sex = ', sex)
print('dic1 = ',dic1)
# sex = male
# dic1 = {'Author': 'Python's year of fighting', 'age': [18, 99]}
**8. dict.popitem()**popitem() deletes the last pair of keys and values in the dictionary.
list1 = ['Author', 'age', 'sex']
list2 = ['Python When the year of fighting', [18,99], 'male']
dic1 = dict(zip(list1, list2))
dic1.popitem()
print('dic1 = ',dic1)
# dic1 = {'Author': 'Python's year of fighting', 'age': [18, 99]}
**9. dict.setdefault()**setdefault() is similar to get(), but if the key does not exist in the dictionary, the key will be added and the value will be set to default.
list1 = ['Author', 'age', 'sex']
list2 = ['Python When the year of fighting', [18,99], 'male']
dic1 = dict(zip(list1, list2))
dic1.setdefault('Author', 'When the year of fighting')
print('dic1 = ',dic1)
# dic1 = {'Author': 'Python's fighting year', 'age': [18, 99], 'sex': 'male'}
dic1.setdefault('name', 'When the year of fighting')
print('dic1 = ',dic1)
# dic1 = {'Author': 'Python when playing', 'age': [18, 99], 'sex': 'male', 'name': 'when playing'}
**10. dict.update(dict1)**update() dictionary updates the key value pair of dict1 dictionary to dict. If the updated dictionary already contains the corresponding key value pair, the original key value pair will be overwritten. If the updated dictionary does not contain the corresponding key value pair, the key value pair will be added.
list1 = ['Author', 'age', 'sex']
list2 = ['Python When the year of fighting', [18,99], 'male']
dic1 = dict(zip(list1, list2))
print('dic1 = ',dic1)
# dic1 = {'Author': 'Python's fighting year', 'age': [18, 99], 'sex': 'male'}
list3 = ['Author', 'phone' ]
list4 = ['When the year of fighting', 12345678]
dic2 = dict(zip(list3, list4))
print('dic2 = ',dic2)
# dic2 = {'Author': 'year of play', 'phone': 12345678}
dic1.update(dic2)
print('dic1 = ',dic1)
# dic1 = {'Author': 'the year of playing', 'age': [18, 99], 'sex': 'male', 'phone': 12345678}
**11. dict.values()**values() returns all values of a dictionary.
list1 = ['Author', 'age', 'sex']
list2 = ['Python When the year of fighting', [18,99], 'male']
dic1 = dict(zip(list1, list2))
values = dic1.values()
print('values = ', values)
print(type(values))
print('values = ', list(values))
# values = dict_values(['Python's year of fighting', [18, 99], 'male'])
# <class 'dict_values'>
# values = ['Python's year of fighting', [18, 99], 'male']