Graph

[ahasusie]

Graphs

• DFS / BFS
• topological sorting
• backtracking
• shortest path
• connectivity
• graph cycle
• path related problems: shortest, diameter, all path, distance

  ---

  an acyclic graph is a graph with no cycles. a graph is connected if there is a path from every vertex to every other vertex in the graph.

  ---

  edges list: timeΘ(d), spaceΘ(E) adjacency matrix: time(O(1)) spaceΘ(V*2) adjacency list: time(O(1)) spaceΘ(d)

1. how much memory, or space, we need in each representation.
2. how long it takes to determine whether a given edge is in the graph.
3. how long it takes to find the neighbors of a given vertex.

[ahasusie]

Topological sorting topological sorting of a directed graph is a linear ordering of its vertices such that for every directed edge uv from vertex u to vertex v, u comes before v in the ordering. it's only possible in directed acyclic graph(DAG). eg: task scheduling quickly compute the shortest path through weighted DAG

---

There can be more than one topological sorting for a graph. The first vertex in topological sorting is always a vertex with in-degree as 0. In DFS, we print a vertex and then recursively call DFS for its adjacent vertices. In topological sorting, we need to print a vertex before its adjacent vertices.

---

good example: 207. courses schedule

# topsort, iteration, bfs
def canFinish(numCourses, graph):
    indegree = {i: 0 for i in range(numCourses)}
    for node in graph:
        for nei in graph[node]:
            indegree[nei] += 1

    q = deque()
    for k in indegree.keys():
        if indegree[k] == 0:
            q.append(k)

    visited = 0
    while q:
        node = q.popleft()
        visited += 1
        for nei in graph[node]:
            indegree[nei] -= 1
            if indegree[nei] == 0:
                q.append(nei)
    return visited == numCourses

    # # dfs
    visited = set()
    stack = []

    def dfs(node, visited, stack):
        visited.add(node)
        for nei in graph[node]:
            if nei not in visited:
                dfs(nei, visited, stack)
        stack.insert(0, node)

    for node in graph:
        if node not in visited:
            dfs(node, visited, stack)
    return len(stack) == numCourses

[ahasusie]

directed graph

# single source path from src->end, dfs
def dfsPath(graph, src, end):
    visited = set()
    prev = {node: None for node in graph}

    def dfs(graph, node):
        visited.add(node)
        for nei in graph[node]:
            if nei not in visited:
                prev[nei] = node
                dfs(graph, nei)
    dfs(graph, src)

    path = []
    while prev[end]:
        path.insert(0, end)
        end = prev[end]
    path.insert(0, src)
    return path

# single source shortest path, bfs
def bfsPath(graph, src, end):
    visited = set()
    prev = {node: None for node in graph}

    def bfs(graph, node):
        queue = deque()
        visited.add(node)
        queue.append(node)

        while queue:
            n = queue.popleft()
            for nei in graph[n]:
                if nei not in visited:
                    prev[nei] = n
                    visited.add(nei)
                    queue.append(nei)
    bfs(graph, src)

    path = []
    while prev[end]:
        path.insert(0, end)
        end = prev[end]
    path.insert(0, src)
    return path

# reachability problem in digraph
# find vertices in G that are reachable from src
def dfsDigraphReach(graph, src):
    visited = set()
    res = []
    def dfs(graph, node):
        visited.add(node)
        res.append(node)
        for nei in graph[node]:
            if nei not in visited:
                dfs(graph, nei)
    dfs(graph, src)
    return res

# find vertices in G that are reachable from multiple sources
def dfsDigraphReach1(graph, sources):
    visited = set()
    res = []
    def dfs(graph, node):
        visited.add(node)
        res.append(node)
        for nei in graph[node]:
            if nei not in visited:
                dfs(graph, nei)
    for s in sources:
        dfs(graph, s)
    return res

[ahasusie]

connectivity

# dfs to find connected components in a graph
def connectedComponent(graph):
    visited = set()
    id = {node: None for node in graph}
    count = 0

    def dfs(graph, node):
        visited.add(node)
        id[node] = count
        for nei in graph[node]:
            if nei not in visited:
                dfs(graph, nei)

    for node in graph:
        if node not in visited:
            dfs(graph, node)
            count += 1

    component = {i: [] for i in range(count)}
    for i in range(count):
        for n in id.keys():
            if id[n] == i:
                component[i].append(n)
    return component

[ahasusie]

undirected graph cycle: We do a DFS traversal of the given graph. For every visited vertex ‘v’, if there is an adjacent ‘u’ such that u is already visited and u is not parent of v, then there is a cycle in graph. If we don’t find such an adjacent for any vertex, we say that there is no cycle. The assumption of this approach is that there are no parallel edges between any two vertices.

class Graph():
    def hasCycle(self, graph):
        self.visited = set()
        self.hasCycle = False

        for node in graph:
            if node not in self.visited:
                self.dfs(graph, node, node)

        return self.hasCycle

    def dfs(self, graph, node, prev):   
        print "dfs(",node,",",prev,")"     
        self.visited.add(node)
        for nei in graph[node]:
            if nei not in self.visited:
                self.dfs(graph, nei, node)
            else:                
                if nei != prev:
                    self.hasCycle = True

    # use indegree to check if has cycle in directed graph

---

has cycle in directed graph similar like top sort, use indegree

def hasDiCycle(graph):
    inDegree = {i:0 for i in graph.keys()}
    for node in graph:
        for nei in graph[node]:
            inDegree[nei] += 1
    print inDegree
    q = deque()    
    for n, val in inDegree.items():
        if val == 0: 
            q.append(n)

    visited = 0
    while q:
        node = q.popleft()
        visited += 1
        for nei in graph[node]:
            inDegree[nei] -= 1
            if inDegree[nei] == 0:
                q.append(nei)

    print visited
    if visited != len(graph):
        return True
    else:
        return False

[ahasusie]

DFS usage in graph:

1) For an unweighted graph, DFS traversal of the graph produces the minimum spanning tree and all pair shortest path tree. 2) Detecting cycle in a graph 3) Path Finding 4) Topological Sorting 5) To test if a graph is bipartite 6) Finding Strongly Connected Components of a graph 7) Solving puzzles with only one solution, such as mazes.