五. 图

图的存储

1. 顺序表(矩阵存储)

/*顺序表*/
typedef struct {
    int matrix[V][V];   //存放所有的边. 有边就是1, 没边写0或者-1;
    VNode NodeList[V];   //存放所有的结点
    int n, e;   //n节点数, e边数;
}matrixGraph;

typedef struct{
    int vNo;   
    vInfoType VInfo;  //典型的如v.key, v.parent, v.used
}VNode;

2. 链表(邻接链表)

/*链表*/
typdef struct{
    int vNo;
    ENode *firstENode;
}VNode;

typedef struct{
    int adjvNo;  //refers to vNo
    struct ENode *nextENode;
}ENode;

typedef struct{
    VNode nodeList[V];
    int n, e;
}LinkedGraph;

图的遍历

BFS, DFS

图的最小生成树

Prim, Kruskal

图的最短路径问题

Dijkstra, Floyd

Dijkstra(G, w, s)
Init-Single-Source(G, s);   //set v.pr=null, v.d = ∞, s.d = 0
S = ∅
Q = G.V
while (Q!=∅):
    u = extract-min(Q)
    for each v of G.adj[u]:
        relax(u, v)   //v.d>u.d+w(u, v)就更新v.d, v.pr