Note_Tech

All technological notes.

Project maintained by simonangel-fong Hosted on GitHub Pages — Theme by mattgraham

DSA - Graph

Back

Graph

Terminology

Representation of Graphs

Action Adjacency Matrix Adjacency List
Adding Edge O(1) O(1)
Removing an edge O(1) O(N)
Initializing O(N*N) O(N)

Adjacency Matrix

matrix

Adjacency List

list

Implement: Graph using Adjacency List

class Vertex(object):
    '''Implement vertex'''

    def __init__(self, key):
        self.id = key   # key of current vertex
        self.neighbor = {}  # initialize neighbors of current vertex

    def __str__(self):
        return 'Vertex {0} connects to {1}'.format(self.id, str([x.id for x in self.neighbor]))

    def get_id(self):
        return self.id

    def add_neighbor(self, vertex, weight):
        '''add a target vertex with specific weight'''
        # Note that the key here is vertex, an object
        self.neighbor[vertex] = weight
        # set weight for both current and target vertex
        vertex.neighbor[self] = weight

    def get_neighbors(self):
        '''get all neighbors'''
        return [k for k in self.neighbor.keys()]

    def get_weight(self, target_vertex):
        '''get weight from current to target vertex'''

        # if target is in the neighbors
        if target_vertex in self.neighbor:
            return self.neighbor[target_vertex]
        else:
            return None

class Graph(object):
    def __init__(self) -> None:
        self.vertice = {}

    def add_vertex(self, key):
        '''create a new vertex with key'''
        new_vertext = Vertex(key)       # create a new vertex
        self.vertice[key] = new_vertext
        return new_vertext

    def get_vertex(self, key):
        if key in self.vertice.keys():
            return self.vertice[key]
        else:
            None

    def add_edge(self, from_key, to_key, cost=0):
        '''add edge'''
        # if from key does not exist, then create a new vertex
        if from_key not in self.vertice:
            self.add_vertex(from_key)

        # if to key does not exist, then create a new vertex
        if to_key not in self.vertice:
            self.add_vertex(to_key)

        self.vertice[from_key].add_neighbor(self.vertice[to_key], cost)

    def get_all_vertice(self):
        '''get all vertice'''
        return [k for k in self.vertice.keys()]

    def __iter__(self):
        return iter(self.vertList.values())

    def __contains__(self, key):
        return key in self.vertice

g = Graph()

for i in range(6):
    g.add_vertex(i)

print(g.get_vertex(0))  # Vertex 0 connects to []
g.add_edge(0, 1, 1)
g.add_edge(0, 2, 2)
g.add_edge(0, 3, 3)
g.add_edge(0, 7, 3)
print(g.get_vertex(0))      # Vertex 0 connects to [1, 2, 3, 7]
print(g.get_vertex(1))      # Vertex 1 connects to [0]
print(g.get_vertex(2))      # Vertex 2 connects to [0]
print(g.get_vertex(3))      # Vertex 3 connects to [0]
print(g.get_vertex(0))      # Vertex 0 connects to [1, 2, 3, 7]

g.get_all_vertice()     # [0, 1, 2, 3, 4, 5, 7]

3 in g      # True
10 in g     # False

Problem: Word Ladder

class Vertex:
    def __init__(self,key):
        self.id = key
        self.connectedTo = {}

    def addNeighbor(self,nbr,weight=0):
        self.connectedTo[nbr] = weight

    def __str__(self):
        return str(self.id) + ' connectedTo: ' + str([x.id for x in self.connectedTo])

    def getConnections(self):
        return self.connectedTo.keys()

    def getId(self):
        return self.id

    def getWeight(self,nbr):
        return self.connectedTo[nbr]

class Graph:
    def __init__(self):
        self.vertList = {}
        self.numVertices = 0

    def addVertex(self,key):
        self.numVertices = self.numVertices + 1
        newVertex = Vertex(key)
        self.vertList[key] = newVertex
        return newVertex

    def getVertex(self,n):
        if n in self.vertList:
            return self.vertList[n]
        else:
            return None

    def __contains__(self,n):
        return n in self.vertList

    def addEdge(self,f,t,cost=0):
        if f not in self.vertList:
            nv = self.addVertex(f)
        if t not in self.vertList:
            nv = self.addVertex(t)
        self.vertList[f].addNeighbor(self.vertList[t], cost)

    def getVertices(self):
        return self.vertList.keys()

    def __iter__(self):
        return iter(self.vertList.values())


def buildGraph(wordFile):
    '''function to build graph'''
    d = {}
    g = Graph()

    # 读取单词文件
    wfile = open(wordFile,'r')
    # create buckets of words that differ by one letter
    for line in wfile:
        print(line)
        word = line[:-1]  # 该处-1是去除换行号\n
        print(word)
        for i in range(len(word)):
            bucket = word[:i] + '_' + word[i+1:]  #该处按字母顺序替换为"_"符号作为bucket
            if bucket in d:
                d[bucket].append(word)    # bucket作为字典的键, 目的是如果单词特征相同的,加入到value
            else:
                d[bucket] = [word]    # 如果bucket不存在, 则加入, 注意value是list
    # add vertices and edges for words in the same bucket
    # 思路:
    # 1.遍历所有单词特征
    # 2.嵌套遍历相同特征下的list的成员,
    # 3.如果不是相同单词时, 向graph对象添加edge
    # 效果: 有相同特征的单词之间建立关联
    for bucket in d.keys():
        for word1 in d[bucket]:
            for word2 in d[bucket]:
                if word1 != word2:
                    g.addEdge(word1,word2)
    return g

Breadth First Search (Unfinished)

Depth First Search (Unfinished)

TOP