五. 图

图的存储

  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;
  1. 链表(邻接链表)
/*链表*/
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
©著作权归作者所有,转载或内容合作请联系作者
平台声明：文章内容（如有图片或视频亦包括在内）由作者上传并发布，文章内容仅代表作者本人观点，简书系信息发布平台，仅提供信息存储服务。

推荐阅读更多精彩内容