graph

概念

vertex 节点

A vertex (also called a “node”) is a fundamental part of a graph. It can have a name, which we will call the “key.” A vertex may also have additional information. We will call this additional information the “payload.”

edge 边

An edge (also called an “arc”) is another fundamental part of a graph. An edge connects two vertices to show that there is a relationship between them. Edges may be one-way or two-way. If the edges in a graph are all one-way, we say that the graph is a directed graph, or a digraph. The class prerequisites graph shown above is clearly a digraph since you must take some classes before others.

weight 权重

Edges may be weighted to show that there is a cost to go from one vertex to another. For example in a graph of roads that connect one city to another, the weight on the edge might represent the distance between the two cities.

图的符号表示

图结构可以表示为 G=(V,E)
V 是节点的集合

路径 path

A path in a graph is a sequence of vertices that are connected by edges. Formally we would define a path as w1,w2,...,wn such that (wi,wi+1)∈E for all 1≤i≤n−1 . The unweighted path length is the number of edges in the path, specifically n−1. The weighted path length is the sum of the weights of all the edges in the path.

环路 cycle

A cycle in a directed graph is a path that starts and ends at the same vertex.
A graph with no cycles is called an acyclic graph.
A directed graph with no cycles is called a directed acyclic graph or a DAG.

图的抽象数据类型

1 Graph()
2 addVertex(vert)
3 addEdge(start, end)
4 addEdge(start, end, weight)
5 getVertex(vertKey)
6 getVertices() returns the list of all vertices in the graph
7 in

图的表示形式

adjacency matrix

the number of the elements in matrix is |V|2 .

The advantage of the adjacency matrix is that it is simple, and for small graphs it is easy to see which nodes are connected to other nodes. However, notice that most of the cells in the matrix are empty. Because most of the cells are empty we say that this matrix is “sparse.” A matrix is not a very efficient way to store sparse data.
The adjacency matrix is a good implementation for a graph when the number of edges is large

adjancency list

′V′3linksto{V0:1}

The advantage of the adjacency list implementation is that it allows us to compactly represent a sparse graph. The adjacency list also allows us to easily find all the links that are directly connected to a particular vertex.

class Vertex(object):
    def __init__(self, key):
        self.key = key
        self.connectedTo = dict()

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

    def __str__(self):
        return str(self.key) + ' connected to ' + str(self.connectedTo)

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

    def getKey(self):
        return self.key

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


class Graph(object):

    def __init__(self):
        self.vertList = dict()
        self.numVertices = 0

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

    def getVertex(self, key):
        return self.vertList.get(key, None)

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

    def addEdge(self, start, end, cost=0):
        if start not in self.vertList:
            self.addVertex(start)
        if end not in self.vertList:
            self.addVertex(end)
        self.vertList[start].addNeighbor(end, cost)

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

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

g = Graph()        
for i in range(6):
    g.addVertex(i)
print(g.vertList)

g.addEdge(0,1,5)
g.addEdge(0,5,2)
g.addEdge(1,2,4)
g.addEdge(2,3,9)
g.addEdge(3,4,7)
g.addEdge(3,5,3)
g.addEdge(4,0,1)
g.addEdge(5,4,8)
g.addEdge(5,2,1)

for v in g:
    for w in v.getConnections():

        print("( %s, %s )"%(v.getKey(), w))

{0: <__main__.Vertex object at 0x0000000003CCF828>, 1: <__main__.Vertex object at 0x0000000003CCB9B0>, 2: <__main__.Vertex object at 0x0000000003CCB978>, 3: <__main__.Vertex object at 0x0000000003B4E668>, 4: <__main__.Vertex object at 0x0000000003D5AEB8>, 5: <__main__.Vertex object at 0x0000000003D7CCC0>}
( 0, 1 )
( 0, 5 )
( 1, 2 )
( 2, 3 )
( 3, 4 )
( 3, 5 )
( 4, 0 )
( 5, 2 )
( 5, 4 )

minimum weight spanning tree

Formally we define the minimum spanning tree T for a graph G(V,E) as follows.
T is acyclic subset of E that connects all the vertices in V .

The algorithm we will use to solve this problem is called Prim’s algorithm. Prim’s algorithm belongs to a family of algorithms called the “greedy algorithms” because at each step we will choose the cheapest next step. In this case the cheapest next step is to follow the edge with the lowest weight. Our last step is to develop Prim’s algorithm.

The basic idea in constructing a spanning tree is as follows:
While T is not yet a spanning tree
Find an edge that is safe to add to the tree
Add the new edge to T

The trick is in the step that directs us to “find an edge that is safe.” We define a safe edge as any edge that connects a vertex that is in the spanning tree to a vertex that is not in the spanning tree. This ensures that the tree will always remain a tree and therefore have no cycles.

Prim’s algorithm is similar to Dijkstra’s algorithm in that they both use a priority queue to select the next vertex to add to the growing graph.

下图为初始的图结构示意图：

经过最小生成树prim算法后应该去掉三条边（下图虚线的边）：

代码如下：
import heapq

class PriorityQueue(object):
    def __init__(self):
        self._ele = []
        self._idx = 0

    def push(self, item, priority):
        heapq.heappush(self._ele, (priority, self._idx, item))
        self._idx += 1

    def pop(self):
        return heapq.heappop(self._ele)[-1]

    def isEmpty(self):
        return len(self._ele) == 0

graph = {'A':{'B':2,'C':3},'B':{'A':2,'C':1,'D':1},
         'C':{'A':3,'F':5,'B':1},'D':{'B':1,'E':1},
         'E':{'D':1,'B':4,'F':1},'F':{'E':1,'C':5,'G':1},
         'G':{'F':1}}

def prim(graph, start):
    prim = dict()
    pque = PriorityQueue()
    pque.push((None, start), 0)
    while not pque.isEmpty():
        src,dst = pque.pop()
        if dst in prim:
            continue
        prim[dst] = src
        for k,v in graph[dst].items():
            pque.push((dst,k), v)
    return prim

print(prim(graph, 'A'))    

{'F': 'E', 'D': 'B', 'A': None, 'B': 'A', 'G': 'F', 'E': 'D', 'C': 'B'}

Dijkstra

Dijkstra算法的与prim算法很类似，但是Dijkstra算法是最短路径算法。

详见另一片文章最短路径