Διασχίσεις γράφων και δένδρων

README.md

Γράφοι και δένδρα

Παραδείγματα διάσχισης

• Διάσχιση γράφου DFS και BFS (traversals.py)
• Προδιατεταγμένη, μεταδιατεταγμένη και ενδοδιατεταγμένη διάσχιση δυαδικού δένδρου (order-processing.py)
• Υπολογισμός δένδρου αριθμητικής έκφρασης με μεταδιατεταγμένη διάσχιση (postorder-computing.py)

order-processing.py

# -*- coding: utf-8 -*-

class Node:
	def __init__(self,value,left=None,right=None):
		self.value = value
		self.left = left
		self.right = right

	
def process(node):
	print node.value,	

	
def dfs_preorder(root):
	if root is None: return
	process(root)
	dfs_preorder(root.left)
	dfs_preorder(root.right)

def dfs_postorder(root):
	if root is None: return
	dfs_postorder(root.left)
	dfs_postorder(root.right)
	process(root)

def dfs_inorder(root):
	if root is None: return
	dfs_inorder(root.left)
	process(root)
	dfs_inorder(root.right)

t1 = Node('+',Node(8),Node(2))
t2 = Node('-',Node(3))
root = Node('*',t1,t2)

dfs_preorder(root)
print
dfs_postorder(root)
print
dfs_inorder(root)
print

postorder-computing.py

# -*- coding: utf-8 -*-

class Node:
	def __init__(self,value,left=None,right=None):
		self.value = value
		self.left = left
		self.right = right
	
	
def dfs_postorder(root):
	if root is None: return
	x = dfs_postorder(root.left)
	y = dfs_postorder(root.right)
	if root.value=='+':
		if x is None: return y
		else: return x+y		 
	elif root.value=='-':
		if x is None: return -y
		else: return x-y
	elif root.value=='*':
		return x*y		
	elif root.value=='/':
		return x/y
	else:
		return root.value



t1 = Node('+',Node(8),Node(2))
t2 = Node('-',None,Node(3))
root = Node('*',t1,t2)

print dfs_postorder(root)

traversals.py

# -*- coding: utf-8 -*-

# Λίστα γειτνίασης γράφου
graph = { 'A':['B','C'],
          'B':['A','C','D'],
          'C':['A','B','D','E'],
          'D':['B','C'],
          'E':['C']
        }


# Διάσχιση DFS με στοίβα
        
visited = set()
stack = []

stack.append('A')
while len(stack)>0:
	node = stack.pop()
	if node not in visited:
		print 'visiting:',node
		visited.add(node)
		stack += graph[node]
		

# Διάσχιση BFS με ουρά
from collections import deque
visited = set()
queue = deque()

queue.append('A')
while len(queue)>0:
	node = queue.popleft()
	if node not in visited:
		print 'visiting:',node
		visited.add(node)
		queue.extend(graph[node])