强连通分支 - webdancer's Blog

强连通分支

webdancer posted @ 2011年5月18日 21:17 in 算法 with tags python 算法 , 1055 阅读

 

#!/usr/bin/python
class Graph:
	def __init__(self,nv):
		self.v=nv
		self.e=0
		self.adj=[]
		for ele in range(nv):
			self.adj.append([])
			ele+=1
	
	def insert(self,e):
		u=e[0]
		v=e[1]
		self.adj[u].append(v)
		#self.adj[v].append(u) 
		self.e+=1

	def dfs(self):
		global p
		global c
		global d
		global f
		global time
		global t
		p=[]
		c=[]
		d=[]
		f=[]
		t=[]
		for ele in range(self.v):
			ele+=1
			p.append(-1)
			c.append(0)
			d.append(0)
			f.append(0)
			t.append(0)
		time=0
		m=0
		for elev in range(self.v):
			if c[elev] == 0:
				self.dfs_visit(elev,m)
	
	def dfs_visit(self,u,m):
		global time
		c[u]=1
		t[u]=m
		time+=1
		d[u]=time
		for v in self.adj[u]:
			if c[v] == 0:
				p[v]=u
				t[v]=m
				self.dfs_visit(v,m)
		c[u]=2
		time+=1
		f[u]=time

	
	'''def printpath(self,s,v):
		if s==v:
			print s,
		elif p[v]==-1:
			print 'no path',
		else:
			self.printpath(s,p[v])
			print v,'''
def scc(g):
	g.dfs()
	gt=Graph(g.v)
	for u in range(len(g.adj)):
		for v in g.adj[u]:
			gt.adj[v].append(u)
		u+=1
	f1=[]
	for e in f:
		f1.append(e)
	for i in range(gt.v):
		p[i]=-1
		c[i]=0
		d[i]=0
		f[i]=0
		t[i]=0
	print c
	time=0
	global m
	m=0
	for i in range(gt.v):
		v=max(f1)
		fi=f1.index(v)
		if c[fi] == 0:
			m+=1
			gt.dfs_visit(fi,m)
		f1[fi]=-1

if __name__=='__main__':
	g=Graph(8)
	e=[(0,1),(1,2),(1,4),(1,5),(2,3),(2,6),(3,2),(3,7),(4,0),(4,5),(5,6),(6,5),(6,7),(7,7)]
	for each in e:
		g.insert(each)
	scc(g)
	print t
	for i in range(m+1):
		for v in range(g.v):
			if t[v]==i+1:
				print v,
		print '\n'

 


登录 *


loading captcha image...
(输入验证码)
or Ctrl+Enter
Host by is-Programmer.com | Power by Chito 1.3.3 beta | © 2007 LinuxGem | Design by Matthew "Agent Spork" McGee