2017-02-01

关于图的知识点

图的存储结构

邻接矩阵（稠密矩阵：点少边多的情况）
邻接表（稀疏矩阵：点多边少的情况）

图的遍历

深度优先

void DepthFSearch(AdjMGraph G, int v, int visited[], void Visit(char item))
{
    int w;
    Visit(G.Vertices.list[v]);
    visited[v];
    w = GetFirstVex(G, v);
    /* 寻找当前顶点的邻接顶点 */
    while (w != -1)
    {
        if (!visited[w])
            DepthFSearch(G, w, visited, Visit)
        /* 若邻接顶点已被访问，则寻找下一个邻接顶点 */
        w = GetNextVex(G, v, w);
    }
}

广度优先

void BoardFSearch(AdjMGraph G, int v, int visited[], void Visit(char item))
{
    int u, w;
    SeqCQueue queue;
    QueueInitiate(&queue);
    Visit(G.Vertices.list[v]);
    visited[v];
    QueueAppend(&queue, v);
    /* 当队列为空时终止循环 */
    while(QueueNotEmpty(queue))
    {
        QueueDelete(&queue, &u);
        w = GetFirstVex(G, u);
        /* 遍历所有邻接顶点 */
        while(w != -1)
        {
            if (!visited[w])
            {
                Visit(G.Vertices.list[w]); // 访问顶点w
                visited[w]; // 标记顶点w
                QueueAppend(&queue, w); // 顶点w入队列
            }
            w = GetNextVex(G, u, w);
        }
    }
}

最小生成树－无向带权连通图

对于无向带权连通图，其所有生成树中边的权值总和最小的是最小生成树。例如在n个城市之间敷设光缆，且各城市之间敷设光缆的费用不同。

n个顶点的无向连通带权图的最小生成树必须满足如下条件：

包括n个顶点
有且只有n - 1条边
不存在回路

经典算法

Prim algorithm （点少边多，稠密矩阵）

typedef struct
{
    Vert vertex;
    int weight;
} MinSpanTree;
/* Prim algorithm */
void Prim(AdjMGraph G, MinSpanTree closeVertex[])
{
    Vert x;
    int i, j, k;
    int minCost;
    int n = G.Vertices.size;
    int * lowCost = (int *)malloc(sizeof(int) * n);
    for (i = 1; i < n; i ++)
        lowCost[i] = G.edge[0][i];
    lowCost[0] = -1;
    listGet(G.Vertices, 0, &x);
    closeVertex[0].vertex = x;
    for (i = 1; i < n; i++)
    {
        minCost = MaxWeight; // MaxWeight为定义的最大权值
        /* 寻找当前最小权值的边所对应的顶点k，但不包括lowCost = -1的 */
        for (j = 1; j < n; j++)
            if (minCost > lowCost[j] && lowCost[j] > 0)
            {
                k = j;
                minCost = lowCost[j];
            }
        listGet(G.Vertices, k, &x);
        closeVertex[i].vertex = x;
        closeVertex[i].weight = minCost;
        lowCost[k] = -1;
        /* 更新权值 */
        for (j = 1; j < n; j++)
            if (lowCost[j] > G.edge[k][j])
                lowCost = G.edge[k][j];
    }
}

Kruskal算法（点多边少，稀疏矩阵）：首先是带权图中各边的权值排序，其次是判断新选取的边的两个顶点是否属于同一个连通分量。

最短路径－有向带权图（连通／非连通）

经典算法

Dijkstra algorithm：按路径长度递增的顺序逐步产生最短路径的构造算法

void Dijkstra(AdjMGraph G, int v0, int distance[], int path[])
/* s[]用来表示顶点是否已从集合T移动到集合S中 */
/* path[]存放了从原点v0到其它各个顶点的最短路径的前一个顶点的下标 */
{
    int n = G.Vertices.size;
    int * s = (int *)malloc(sizeof(int) * n);
    int minDis, i, j, k;
    /* Initilization */
    for (i = 0; i < n;  i++)
    {
        distance[i] = G.edge[v0][j];
        s[i] = 0;
        if (i != v0 && distance[i] < MaxWeight) path[i] = v0;
        else path[i] = -1;
    }
    s[v0] = 1;
    /* 对于连通图来说，每一个循环能找到一个路径最短的顶点 */
    for (i = 1; i < n; i++)
    {
        minDis = MaxWeight;
        for (j = 0; j < n; j++)
        {
            if (s[i] == 0 && minDis > distance[j])
            {
                k = j;
                minDis = distance[j];
            }
        }
        /* 当不再存在路径时，算法结束。此语句对非连通图是必需的 */
        if (minDis == MaxWeight) return;
        s[k] = 1;
        /* 修改从v0到其它顶点的最短路径 */
        for (j = 0; j < n; j++)
            if (s[i] == 0 && G.edge[k][j] < MaxWeight && distance[k] + G.edge[k][j] < distance[j])
                distance[j] = distance[k] + G.edge[k][j];
                path[j] = k;
    }
}

Floyd algorithm：解决每对顶点之间最短路径的算法。