思维导图

重要概念

图的存储结构

邻接矩阵

1.其表示是唯一的，一维数组代表顶点，二维数组存储图中的边或弧的信息。
2.对于含n个顶点的有向图还是无向图，无论边的数目是多少，其存储空间均为O（n^2）。
3.对于有向图，邻接矩阵数组第i行（或第i列）非0元素、非∞元素的个数正好是顶点i的出度（入度）.
4.有向图的邻接矩阵要有顶点数组
5.常用于提取边权值的算法

邻接表

1.其表示是不唯一的。
2.适用于提取某个顶点的所有邻接点的算法。
3.邻接表画法有三种分别是：无向图、有向图、有向带权图。

图的遍历

以邻接表为存储结构的DFS算法

int visited[MAX]={0}；//全局数组
void DFS（AdjGraph *G,int V）
{ArcNode *p;
visited[v]=1;//置以访问标记
printf("%d",v);
p=G->adjust[v].firstarc;//输出被访问顶点编号
while(!p==NULL)
{
if(visited[p->adjvex]==0)
DFS(G,p->adjvex);
p=p->nextarc//p指向下一个邻接点
}
}

用图遍历求迷宫问题

用栈搜索迷宫路径使用DFS算法，用队列搜索迷宫路径使用BFS算法。

最小生成树

Prim算法（加点图）

• 该算法时间复杂度为 O(n^2)，与图结构的边数无关，适合稠密图。

算法步骤

• 将初始化的顶点v加入U
• 重复以下步骤（n-1）次，使其他（n-1）个顶点加入U中

1. 将顶点最小边选出加入TE，该边在U-V中顶点为k,将k加入U中
   2.考察U-V中所有顶点，更新每组权值最小的边，诺小于之前边权值则该边作为侯选边

代码实现

void MiniSpanTree_Prim(MGraph G)
{
    int min;
    int i,j,k;
    int closest[MAXV];    //存贮最小边在 U 中的顶点
    int lowcost[MAXV];    //存储最小边上的权值
    
    for(i = 1; i < G.n; i++)    //初始化，给lowcost[]、closest[]置初值
    {
        lowcost[i] = G.edges[0][i];    //将 v0 顶点存在边的权值存入 lowcost
        closest[i] = 0；    //初始化都为 v0 的下标
    }
    for(i = 1; i < G.n; i++)//找出（n-1）个顶点
    {
        min = INFINITY;    //初始化最小权值为 ∞
        j = 1;
        k = 0;
        while(j < G.n)    //循环全部顶点
        {
            if(lowcost[j] != 0 && lowcost[j] < min)///如果权值不为0，并且权值小于min
            {                
                min = lowcost[j];    //令当前权值为最小值
                k = j;    //当前最小值的下标赋给 k
            }
            j++;
        }
        cout <<closest[k] << k;    //输出当前顶点边中权值最小边
        lowcost[k] = 0;    //表示该节点已添加入生成树
        for(j = 1; j < G.n; j++)
        {
            if(lowcost[j] != 0 && G.edges[k][j] < lowcost[j])
            {         //若下标为 k 的顶点各边权值小于当前顶点未被加入生成树权值
                lowcost[j] = G.edges[k][j];    //将最小权值存入 lowcost
                closest[j] = k;    //将下标为 k 的顶点存入 closest
            }
        }
    }
}

Kruskal算法（加边图）

• 该算法时间复杂度为O(e㏒2e)，且算法执行时间仅有图的边数有关，更适合于稀疏图。

算法步骤

• 将边集数组权值按小到大排序
• 在边集数组中选取边(i,j)，判断是否产生回路，即查找顶点数组Vi，Vj所在连通分量n,m是否相等,诺不相等则不存在回路；诺相等，则选择下一条权值最小的边。

代码实现

void MiniSpanTree_Kruskal(MGraph G)
{
    int i,n,m;
    Edge edges[MAXE];    //定义边集数组
    int parent[MAXV]；    //判断回路的并查集
 
    for(i = 0; i < G.n; i++)//循环每一条边
    {
        n = Find(parent, edges[i].begin);    
        m = Find(parent, edges[i].end);
        if(m != n)    //若 n 和 m 不相等，则说明回路不存在（这条边的两端点不在同一个连通）
        {
            parent[n] = m;    //将此边结尾顶点放入下标为起点的 parent 中
            cout << edges[i].begin <<  edges[i].end << edges[i].weight << endl;
        }
    }
}
 
int Find(int *parent, int f)    //查连线顶点的尾部下标
{
    while(parent[f] > 0)
        f = parent[f];
    return f;
}

最短路径

Dijkstra算法

• 算法时间复杂度为O（n^2)

算法设计

1.S[]:以求出最短路径的顶点集合
2.path[]:从v0到终点vi的最短路径上，vi的前驱节点；若v0到vi没有路径则用-1作为前驱节点序号
3.D[]:是记录v0到vi的最短路径的长度，若v0到vi有直接路径则其初态为弧的权值，若无则为 ∞

代码实现

void ShortestPath_DIJ(MGraph g, int v0)
{   //初始化
    int v,min;
    int Path[MAXV],S[MAXV],D[MAXV];
    
    for(int i = 0; i < g.n; i++)
    {
        S[i] = false;    //S 初始化为空集
        D[i] = g.edges[v0][i];    //将 v0 到各个终点的弧的权值
        if(D[i] <MAXINT)    //v0 到 i 的弧存在，设置前驱为 v0
        {
            Path[i] = v0;
        }
        else    //v0 到 i 的弧不存在，设置前驱为 -1
        {
            Path[i] = -1;
        }
    }
    S[v0] = true;    // v0 加入 S
    D[v0] = 0;    //源点到源点本身的距离为 0
 
    /*初始化结束，开始最短路径求解*/
    for(int i = 1; i < g.n; i++)    //依次考虑剩余的 n - 1 个顶点
    {
        min = MAXINT;
        for(int j = 0; j < g.n; j++)
        {
            if(S[j] == false && D[j] < min)    //若 vj 未被添加入 S 且路径最短
            {
                v = j;    //选择当前最短路径，终点是 v
                min = D[j];
            }
        }
        s[v] = true;    //将 v 加入 S
        for(int j = 0; j < g.n; j++)
        {
            if(S[j] == false && (D[v] + g.edges[v][j] < D[j]))    //判断是否要更新路径
            {
                D[j] = D[v] + g.edges[v][j];
                Path[j] = v;    //修改 vj 的前驱为 v 
            }
        }
    }
}

Floyd算法

• 其时间复杂度为O(n^3)

算法实现

1.图用邻接矩阵存储
2.二维数组D[][]:存放顶点对之间最短路径长度
3.path[][]:从Vi到Vj最短路径上，Vj的前驱节点序号

代码实现

void ShortestPath_Floyd(MGraph g)
{
    int Path[MAXV][MAXV];    //最短路径上顶点 vj 的前驱节点的序号
    int [MAXV][MAXV];    //记录顶点 vi 和 vj 之间的最短路径长度
    int i，j,k;
     for(int i = 1; i < g.n; i++)
    {
        for(int j = 1; j < g.n; j++)
        {
            D[i][j] = g.edges[i][j];
            if(D[i][j] < MAXINT && i != j)
            {
                Path[i][j] = i;    //若 i 和 j 之间有弧，则将 j 的前驱置为 i;
            }
            else
            {
                Path[i][j] = -1;    //若 i 和 j 之间没有弧，则将 j 的前驱置为 -1;
            }
        }
    }
    for(int k = 0; k < g.n; k++)//依次考察所有顶点
    {
        for(int i = 1; i < g.n; i++)
        {
            for(int j = 1; j < g.n; j++)
            {
                if(D[i][k] + D[k][j] < D[i][j])    //从 i 经过 k 到 j 的路径更短
                {
                    D[i][j] = D[i][k] + D[k][j];    //修改路径长度
                    Path[i][j] = Path[k][j];    //修改最短路径
                }
            }
        }
    }
   Dispath(g,D,path)//函数输出最短路径
}

拓扑排序

1.从有向图中选取一个没有前驱的顶点并输出他
2.从图中删去该顶点，及该顶点出发的边
3.重复上面步骤直至图中不存在没有前驱的顶点

AOE网和关键路径

1.事件的最早发生时间ve=顶点v的最早发生时间。
2.事件的最晚发生时间vl=即顶点v的最晚发生时间（每个事件最晚需要开始的时间）。
3.活动的最早开始时间e=弧ai的最早发生时间。
4.活动的最晚开始晚时间l=弧ai的最晚发生时间。

• 关键活动：l(i) = e(i)的活动
• 求关键活动
  *e(i) = ve(j)
  *l(i) = vl(k) - dut<j,k>//从后面顶点的vl 减去<j,k>边的权值

疑难问题及解决方案

PTA题集

解决办法

• 之前少考虑了当最短路径的长度不变时，花费减小，要更新cost[]的值
  

Dijkstra算法理解不透彻

• 对于如何检查路径是否有回路的代码不理解

解决办法

查找网上内容，学会了如何通过s1和s2的计较，看他们是否相同，来判断路径中是否有回路，这个方法也可以用在拓扑排序中。

数据结构图的知识点

原文：https://www.cnblogs.com/wsj2496/p/14824930.html