Last active
August 29, 2015 14:20
-
-
Save Kyly/8c8c52349e3d1b2c7a9f to your computer and use it in GitHub Desktop.
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| class vert: | |
| def __init__(self, id): | |
| self.id = id | |
| self.adj = [] | |
| self.pre = 0 | |
| self.post = 0 | |
| self.visited = False | |
| def __repr__(self): | |
| return "< {} pre:{} post:{} visited:{} >".format(self.id, self.pre, self.post, self.visited) | |
| A = vert('A') | |
| B = vert('B') | |
| C = vert('C') | |
| D = vert('D') | |
| E = vert('E') | |
| F = vert('F') | |
| G = vert('G') | |
| H = vert('H') | |
| A.adj = [C] | |
| B.adj = [C] | |
| C.adj = [D, E] | |
| D.adj = [F] | |
| E.adj = [F] | |
| F.adj = [G, H] | |
| graph = [A,B,C,D,E,F,G,H] | |
| clock = 1 | |
| def pre(v): | |
| global clock | |
| v.pre = clock | |
| clock += 1 | |
| def post(v): | |
| global clock | |
| v.post = clock | |
| clock += 1 | |
| def explore(v): | |
| pre(v) | |
| v.visited = True | |
| for u in v.adj: | |
| if not u.visited: explore(u) | |
| post(v) | |
| def DFS(G): | |
| global clock | |
| clock = 1 | |
| for v in G: | |
| v.visited = False | |
| for v in G: | |
| if not v.visited: explore(v) | |
| ''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''' | |
| Solution | |
| ''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''' | |
| def findSource(G): | |
| max_post = None | |
| for v in G: | |
| if max_post == None: | |
| max_post = v | |
| elif max_post.post < v.post: | |
| max_post = v | |
| return max_post | |
| def reachableFromS(G): | |
| DFS(G) # Assign post numbers | |
| source = findSource(G) # Get highest post value | |
| for v in G: # Clear visited fields | |
| v.visited = False | |
| explore(source) # Explore from source vertex | |
| for v in G: # Check if all vertices have been visited | |
| if not v.visited: | |
| return False | |
| return True |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment