class Vertex(object):
	# 初始化頂點(diǎn)
	def __init__(self, key):
		self.id = key 							#初始化頂點(diǎn)的鍵
		self.connectedTo = {}					#初始化頂點(diǎn)的值

	# 添加鄰居頂點(diǎn)，參數(shù)nbr是鄰居頂點(diǎn)的鍵，默認(rèn)權(quán)重為0	
	def addNeighbor(self, nbr, weight=0):
		self.connectedTo[nbr] = weight

	def __str__(self):
		return str(self.id) + ' connectedTo: ' + str([x.id for x in self.connectedTo])

	# 獲取該頂點(diǎn)所有鄰居頂點(diǎn)的鍵
	def getConnections(self):
		return self.connectedTo.keys()

	# 獲取頂點(diǎn)的鍵
	def getId(self):
		return self.id

	# 獲取到某鄰居頂點(diǎn)的權(quán)重
	def getWeight(self, nbr):
		return self.connectedTo[nbr]

# 自定義圖類(lèi)
class Graph(object):
	# 初始化圖
	def __init__(self):
		self.vertList = {}						#初始化鄰接表
		self.numVertices = 0 					#初始化頂點(diǎn)數(shù)

	# 添加頂點(diǎn)
	def addVertex(self, key):
		newVertex = Vertex(key)					#創(chuàng)建頂點(diǎn)
		self.vertList[key] = newVertex 			#將新頂點(diǎn)添加到鄰接表中
		self.numVertices = self.numVertices + 1 #鄰接表中頂點(diǎn)數(shù)+1
		return newVertex

	# 獲取頂點(diǎn)
	def getVertex(self, n):
		if n in self.vertList:					#若待查詢頂點(diǎn)在鄰接表中，則
			return self.vertList[n] 			#返回該頂點(diǎn)
		else:
			return None

	# 使之可用in方法
	def __contains__(self, n):
		return n in self.vertList

	# 添加邊，參數(shù)f為起始頂點(diǎn)的鍵，t為目標(biāo)頂點(diǎn)的鍵，cost為權(quán)重
	def addEdge(self, f, t, cost=0):
		if f not in self.vertList:				#起始頂點(diǎn)不在鄰接表中，則
			self.addVertex(f) 					#添加起始頂點(diǎn)
		if t not in self.vertList:				#目標(biāo)頂點(diǎn)不在鄰接表中，則
			self.addVertex(t)					#添加目標(biāo)頂點(diǎn)
		self.vertList[f].addNeighbor(self.vertList[t], cost)#在鄰接表中添加起始點(diǎn)的目標(biāo)點(diǎn)及權(quán)重

	# 獲取鄰接表中所有頂點(diǎn)的鍵
	def getVertices(self):
		return self.vertList.keys()

	# 迭代顯示鄰接表的每個(gè)頂點(diǎn)的鄰居節(jié)點(diǎn)
	def __iter__(self):
		return iter(self.vertList.values())


g = Graph() 									#實(shí)例化圖類(lèi)
for i in range(6): 
	g.addVertex(i) 								#給鄰接表添加節(jié)點(diǎn)
print(g.vertList)								#打印鄰接表
g.addEdge(0, 1, 5) 								#給鄰接表添加邊及權(quán)重
g.addEdge(0, 5, 2) 
g.addEdge(1, 2, 4) 
g.addEdge(2, 3, 9) 
g.addEdge(3, 4, 7) 
g.addEdge(3, 5, 3) 
g.addEdge(4, 0, 1) 
g.addEdge(5, 4, 8) 
g.addEdge(5, 2, 1) 
for v in g: 									#循環(huán)每個(gè)頂點(diǎn)
	for w in v.getConnections(): 				#循環(huán)每個(gè)頂點(diǎn)的所有鄰居節(jié)點(diǎn)
		print("(%s, %s)" % (v.getId(), w.getId())) #打印頂點(diǎn)和其鄰居節(jié)點(diǎn)的鍵

"""圖的鄰接表表示"""
 
class GraphNode(object):
    """節(jié)點(diǎn)類(lèi)"""
    def __init__(self,_elem=None):
        self._elem = _elem # 數(shù)據(jù)域
        self._next = None # 指針域
 
 
class Graph(object):
    """圖類(lèi)"""
    def __init__(self):
        """初始化一個(gè)序列"""
        self._graph = []
 
    def createPeak(self,newNode):
        """創(chuàng)建一個(gè)圖頂點(diǎn)"""
        self._graph.append(newNode)
        return self._graph
 
    def createSide(self):
        """創(chuàng)建圖的邊"""
        for node in self._graph:
            graphNode = node
            print(f"請(qǐng)輸入{graphNode._elem}的鄰接點(diǎn),以-1結(jié)束")
            while True:
                _graphNode = GraphNode() # 初始化每個(gè)節(jié)點(diǎn)的鄰接點(diǎn)
                end = input("請(qǐng)輸入: ")
                if end == '-1':
                    self.printGraph()
                    break
                else:
                    """臨時(shí)列表圖中的節(jié)點(diǎn)值,用來(lái)后續(xù)判斷"""
                    temp = []
                    for item in self._graph:
                        temp.append(item._elem)
                    if end not in temp:
                        """輸入的鄰接節(jié)點(diǎn)不在頂點(diǎn)中"""
                        print("輸入的節(jié)點(diǎn)不屬于圖中的頂點(diǎn),重新輸入")
                        continue
                    elif end == graphNode._elem:
                        """輸入的頂點(diǎn)就是當(dāng)前頂點(diǎn)"""
                        print("輸入的是當(dāng)前節(jié)點(diǎn),重新輸入")
                        continue
                    else:
                        # 新建節(jié)點(diǎn)
                        _graphNode._elem = end
                        # 指針向后移
                        _graphNode._next = graphNode._next
                        graphNode._next = _graphNode
                        graphNode = graphNode._next
 
    def printGraph(self):
        """遍歷當(dāng)前節(jié)點(diǎn)列表"""
        for node in self._graph:
            print(f"頂點(diǎn){node._elem}的鄰接鏈表: ",end='')
            while node != None:
                if node._next != None:
                    print(f'{node._elem}-->',end='')
                else:
                    print(f'{node._elem}', end='')
                node = node._next
            print() # 換節(jié)點(diǎn),換行
 
 
if __name__ == '__main__':
    count = int(input('請(qǐng)輸入頂點(diǎn)個(gè)數(shù): '))
    s = Graph()
    # 創(chuàng)建節(jié)點(diǎn)
    peakNodeStr = input('請(qǐng)輸入頂點(diǎn): ')
    peakNodes = peakNodeStr.split(' ')
    # 將輸入的節(jié)點(diǎn)實(shí)例化之后添加到圖的鏈表中
    for peakNode in peakNodes:
        peak = GraphNode(peakNode)
        s.createPeak(peak)
 
    print('圖中的節(jié)點(diǎn)：',end='')
    for peak in s._graph:
        print(peak._elem,end=' ')
    print()
 
    # 創(chuàng)建邊
    s.createSide()