Skip to content

Instantly share code, notes, and snippets.

@Aisuko

Aisuko/graph.py

Last active April 16, 2023 06:15
Show Gist options

  • Select an option

    Learn more about clone URLs
  • Save Aisuko/7587b1cd4ad76f0bbfbc18f9c582e27c to your computer and use it in GitHub Desktop.

Select an option

Learn more about clone URLs
Save Aisuko/7587b1cd4ad76f0bbfbc18f9c582e27c to your computer and use it in GitHub Desktop.
Download ZIP

Revisions

  1. Aisuko revised this gist Apr 16, 2023. 1 changed file with 2 additions and 2 deletions.
    4 changes: 2 additions & 2 deletions graph.py
    View file
    Original file line number Diff line number Diff line change
    @@ -57,7 +57,7 @@ def shortest_path(self, s, t):
    visited=[False for _ in range(self.n)]
    queue=[s]
    visited[s]=True
    prev=[None for _ iin range(self.n)]
    prev=[None for _ in range(self.n)]
    while queue:
    u=queue.pop(0)
    for v in self.adj[u]:
    @@ -78,7 +78,7 @@ def get_path(self,prev,s,t):
    if prev[t] is not None or s==t:
    while t is not None:
    res.insert(0,t)
    t=prev(t)
    t=prev[t]
    return res

    if __name__ == '__main__':
  2. Aisuko revised this gist Apr 16, 2023. 1 changed file with 34 additions and 35 deletions.
    69 changes: 34 additions & 35 deletions graph.py
    View file
    Original file line number Diff line number Diff line change
    @@ -47,40 +47,40 @@ def dfs(self, s):
    return visited

    # function for finding the shortest path for the graph
    def shortest_path(self, s, t):
    """
    shortest path
    :param s: start node
    :param t: end node
    :return: the shortest path
    """
    visited = [False for _ in range(self.n)]
    queue = [s]
    visited[s] = True
    prev = [None for _ in range(self.n)]
    while queue:
    u = queue.pop(0)
    for v in self.adj[u]:
    if not visited[v]:
    queue.append(v)
    visited[v] = True
    prev[v] = u
    return self.get_path(prev, s, t)
    def shortest_path(self, s, t):
    """
    shortest path
    s: start node
    t: end node
    return: the shortest path
    """
    visited=[False for _ in range(self.n)]
    queue=[s]
    visited[s]=True
    prev=[None for _ iin range(self.n)]
    while queue:
    u=queue.pop(0)
    for v in self.adj[u]:
    if not visited[v]:
    queue.append(v)
    visited[v]=True
    prev[v]=u
    return self.get_path(prev,s,t)
    def get_path(self,prev,s,t):
    """
    get the path
    prev:previous node
    s; start node
    t: end node
    return: the path
    """
    res=[]
    if prev[t] is not None or s==t:
    while t is not None:
    res.insert(0,t)
    t=prev(t)
    return res

    def get_path(self, prev, s, t):
    """
    get the path
    :param prev: previous node
    :param s: start node
    :param t: end node
    :return: the path
    """
    res = []
    if prev[t] is not None or s == t:
    while t is not None:
    res.insert(0, t)
    t = prev[t]
    return res
    if __name__ == '__main__':
    g = Graph(6)
    g.add_edge(0, 1)
    @@ -93,6 +93,5 @@ def get_path(self, prev, s, t):
    g.add_edge(4, 5)
    print(g.bfs(0))
    print(g.dfs(0))
    # testcase for shortest path
    print(g.shortest_path(0, 5))
    print(g.shortest_path(0,5))

  3. Aisuko revised this gist Apr 16, 2023. No changes.
  4. Aisuko revised this gist Apr 16, 2023. 1 changed file with 52 additions and 11 deletions.
    63 changes: 52 additions & 11 deletions graph.py
    View file
    Original file line number Diff line number Diff line change
    @@ -4,7 +4,9 @@

    class Graph:
    def __init__(self, n):
    # n is the number of nodes
    self.n=n
    # adj is the adjacency list
    self.adj=[[] for _ in range(n)]
    def add_edge(self, u, v):
    self.adj[u].append(v)
    @@ -43,15 +45,54 @@ def dfs(self, s):
    stack.append(v)
    visited[v]=True
    return visited
    g = Graph(6)
    g.add_edge(0, 1)
    g.add_edge(0, 2)
    g.add_edge(1, 2)
    g.add_edge(1, 3)
    g.add_edge(2, 4)
    g.add_edge(3, 4)
    g.add_edge(3, 5)
    g.add_edge(4, 5)
    print(g.bfs(0))
    print(g.dfs(0))

    # function for finding the shortest path for the graph
    def shortest_path(self, s, t):
    """
    shortest path
    :param s: start node
    :param t: end node
    :return: the shortest path
    """
    visited = [False for _ in range(self.n)]
    queue = [s]
    visited[s] = True
    prev = [None for _ in range(self.n)]
    while queue:
    u = queue.pop(0)
    for v in self.adj[u]:
    if not visited[v]:
    queue.append(v)
    visited[v] = True
    prev[v] = u
    return self.get_path(prev, s, t)

    def get_path(self, prev, s, t):
    """
    get the path
    :param prev: previous node
    :param s: start node
    :param t: end node
    :return: the path
    """
    res = []
    if prev[t] is not None or s == t:
    while t is not None:
    res.insert(0, t)
    t = prev[t]
    return res
    if __name__ == '__main__':
    g = Graph(6)
    g.add_edge(0, 1)
    g.add_edge(0, 2)
    g.add_edge(1, 2)
    g.add_edge(1, 3)
    g.add_edge(2, 4)
    g.add_edge(3, 4)
    g.add_edge(3, 5)
    g.add_edge(4, 5)
    print(g.bfs(0))
    print(g.dfs(0))
    # testcase for shortest path
    print(g.shortest_path(0, 5))

  5. Aisuko revised this gist Apr 16, 2023. 1 changed file with 1 addition and 1 deletion.
    2 changes: 1 addition & 1 deletion graph.py
    View file
    Original file line number Diff line number Diff line change
    @@ -17,7 +17,7 @@ def bfs(self,s):
    return: visited nodes
    """
    visited=[False for _ in range(self.n)]
    queu=[s]
    queue=[s]
    visited[s]=True
    while queue:
    u=queue.pop(0)
  6. Aisuko created this gist Apr 16, 2023.
    57 changes: 57 additions & 0 deletions graph.py
    View file
    Original file line number Diff line number Diff line change
    @@ -0,0 +1,57 @@
    #! usr/local/bin python3

    # implementation for graph algorithms

    class Graph:
    def __init__(self, n):
    self.n=n
    self.adj=[[] for _ in range(n)]
    def add_edge(self, u, v):
    self.adj[u].append(v)
    self.adj[v].append(u)

    def bfs(self,s):
    """
    breadth first search
    s: start node
    return: visited nodes
    """
    visited=[False for _ in range(self.n)]
    queu=[s]
    visited[s]=True
    while queue:
    u=queue.pop(0)
    for v in self.adj[u]:
    if not visited[v]:
    queue.append(v)
    visited[v]=True
    return visited

    def dfs(self, s):
    """
    depth first search
    s:start node
    return: visited nodes
    """
    visited =[False for _ in range(self.n)]
    stack=[s]
    visited[s]=True
    while stack:
    u=stack.pop()
    for v in self.adj[u]:
    if not visited[v]:
    stack.append(v)
    visited[v]=True
    return visited
    g = Graph(6)
    g.add_edge(0, 1)
    g.add_edge(0, 2)
    g.add_edge(1, 2)
    g.add_edge(1, 3)
    g.add_edge(2, 4)
    g.add_edge(3, 4)
    g.add_edge(3, 5)
    g.add_edge(4, 5)
    print(g.bfs(0))
    print(g.dfs(0))