"""
图
"""
from random import randint
import time
import copy
import Queue
class DenseGraph(object):
"""稠密图 - 邻接矩阵"""
def __init__(self, n, directed):
self.n = n
self.m = 0
self.directed = directed
self.g = [[False for _ in range(n)] for _ in range(n)]
def V(self):
return self.n
def E(self):
return self.m
def addEdge(self, v, w):
if v >= 0 and v < n and w >= 0 and w < n:
if self.hasEdge(v, w):
return None
self.g[v][w] = True
if not self.directed:
self.g[w][v] = True
self.m += 1
def hasEdge(self, v, w):
if v >= 0 and v < n and w >= 0 and w < n:
return self.g[v][w]
class adjIterator(object):
"""相邻节点迭代器"""
def __init__(self, graph, v):
self.G = graph
self.v = v
self.index = 0
def __iter__(self):
return self
def next(self):
while self.index < self.G.V():
if self.G.g[self.v][self.index]:
r = self.index
self.index += 1
return r
self.index += 1
raise StopIteration()
class SparseGraph(object):
"""稀疏图- 邻接表"""
def __init__(self, n, directed):
self.n = n
self.m = 0
self.directed = directed
self.g = [[] for _ in range(n)]
def V(self):
return self.n
def E(self):
return self.m
def addEdge(self, v, w):
if v >= 0 and v < n and w >= 0 and w < n:
self.g[v].append(w)
if v != w and not self.directed:
self.g[w].append(v)
self.m += 1
def hasEdge(self, v, w):
if v >= 0 and v < n and w >= 0 and w < n:
if w in self.g[v]:
return True
else:
return False
class adjIterator(object):
"""相邻节点迭代器"""
def __init__(self, graph, v):
self.G = graph
self.v = v
self.index = 0
def __iter__(self):
return self
def next(self):
if len(self.G.g[self.v]):
if self.index < len(self.G.g[self.v]):
r = self.G.g[self.v][self.index]
self.index += 1
return r
else:
raise StopIteration()
else:
raise StopIteration()
class ReadGraph(object):
"""读取文件中的图"""
def __init__(self, graph, filename):
with open(filename, 'r') as f:
line = f.readline()
v, e = self.stringstream(line)
if v == graph.V():
lines = f.readlines()
for i in lines:
a,b = self.stringstream(i)
if a >= 0 and a < v and b >=0 and b < v:
graph.addEdge(a, b)
def stringstream(self, text):
result = text.strip('\n')
result = result.split()
a, b = result
return int(a), int(b)
class Component(object):
"""深度优先遍历和联通分量"""
def __init__(self, graph):
self.G = graph
self.ccount = 0
self.visited = [False for _ in range(self.G.V())]
self.id = [-1 for _ in range(self.G.V())]
i = 0
while i < self.G.V():
if not self.visited[i]:
self.dfs(i)
self.ccount += 1
i += 1
def dfs(self, v):
self.visited[v] = True
self.id[v] = self.ccount
adj = self.G.adjIterator(self.G, v)
for i in adj:
if not self.visited[i]:
self.dfs(i)
def count(self):
return self.ccount
def isConnected(self, v, w):
if v >=0 and v < self.G.V() and w >= 0 and w < self.G.V():
return self.id[v] == self.id[w]
class Path(object):
"""寻找路径"""
def __init__(self, graph, s):
self.G = graph
self.s = s
self.visited = [False for _ in range(self.G.V())]
self.fromed = [-1 for _ in range(self.G.V())]
self.dfs(s)
def dfs(self, v):
self.visited[v] = True
adj = self.G.adjIterator(self.G, v)
for i in adj:
if not self.visited[i]:
self.fromed[i] = v
self.dfs(i)
def hasPath(self, w):
if w >= 0 and w < self.G.V():
return self.visited[w]
def path(self, w):
s = []
p = w
while p != -1:
s.append(p)
p = self.fromed[p]
s.reverse()
return s
def showPath(self, w):
s = self.path(w)
for i in s:
print i
class ShortestPath(object):
"""广度优先遍历和最短路径"""
def __init__(self, graph, s):
self.G = graph
self.s = s
self.visited = [False for _ in range(self.G.V())]
self.fromed = [-1 for _ in range(self.G.V())]
self.ord = [-1 for _ in range(self.G.V())]
q = Queue.Queue()
q.put(s)
self.visited[s] = True
self.ord[s] = 0
while not q.empty():
v = q.get()
adj = self.G.adjIterator(self.G, v)
for i in adj:
if not self.visited[i]:
q.put(i)
self.visited[i] = True
self.fromed[i] = v
self.ord[i] = self.ord[v] + 1
def hasPath(self, w):
if w >= 0 and w < self.G.V():
return self.visited[w]
def path(self, w):
s = []
p = w
while p != -1:
s.append(p)
p = self.fromed[p]
s.reverse()
return s
def showPath(self, w):
s = self.path(w)
for i in s:
print i
def length(self, w):
if w >= 0 and w < self.G.V():
return self.ord[w]
if __name__=="__main__":
n = 13
g1 = DenseGraph(n, False)
filename = 'graph.txt'
readgraph1 = ReadGraph(g1, filename)
path1 = Path(g1, 0)
print path1.path(8)
path1.showPath(8)
本文内容由网友自发贡献，版权归原作者所有，本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容，请联系:hwhale#tublm.com(使用前将#替换为@)
