1.图的定义和术语

1.图
图G由顶点集V和关系集E组成,记为:G=(V,E),V是顶点(元素)的有穷非空集,E是两个顶点之间的关系的集合。
若图G任意两顶点a,b之间的关系为有序对,∈E, 则称为从a到b的一条弧/有向边;其中: a是的弧尾,b是的弧头;称该图G是有向图。
若图G的任意两顶点a,b之间的关系为无序对(a,b), 则称(a,b)为无向边(边),称该图G是无向图。 无向图可简称为图。
2.完全图
3.网:带权的图
4.子图:对图 G=(V,E)和G’=(V’,E’),
若V’\inV 且 E’\inE,则称G’是G的一个子图
5.度:与顶点x相关联的边(x,y)的数目,称为x的度,记作TD(x) 或D(x)
以顶点x为弧尾的弧的数目,称为x的出度,记作OD(x)。
以顶点x为弧头的弧的数目,称为x的入度,记作ID(x)。
6.图的连通性质
对无向图G:
● 若从顶点vi到vj有路径,则称vi和vj是连通的。
● 若图G中任意两顶点是连通的,则称G是连通图。
● 若图G’是G的一个极大连通子图,则称G’是G的一个连通分量。(连通图的连通分量是自身)
对有向图G
● 若在图G中,每对顶点vi和vj之间, 从vi到vj,且从 vj到vi都存在路径,则称G是强连通图。
● 若图G’是G的一个极大强连通子图,则称G’是G的一个强连通分量。(强连通图的强连通分量是自身)
●设G=(V,E),G’=(V’,E’),V=V’,若G是连通图,G’是G的一个极小连通子图, 则G’是G的一棵生成树。
● 若有向图G有且仅有一个顶点的入度为0,其余顶点的入度
为1,则G是一棵有向树。

2.图的存储形式

1.数组表示法/邻接矩阵
顶点数组—用一维数组存储顶点(元素)
邻接矩阵—用二维数组存储顶点(元素)之间的关系(边或弧)
无向图的邻接矩阵是对称的由0-1构成

列和和行和都是i的度
有向图中a_{i,j}=n表示从i到j有n条边,列和就是入度,行和是出度

对于网来说道理亦同

2.邻接表:
无向图:把与头结点相连的所有元素都存进对应的链表里
有向图的邻接表:它指向的元素存进链表
有向图的逆邻接表:指向它的元素存进链表

如果把图改成了网,那就把每个指向的结点加上一个权重空间

3.有向图的十字链表
其实也很简单,每一个边结点加上弧尾和弧头,第一个指针下一个弧头一样的结点,第二个指针指向下一个弧尾一样结点
点结点就是两个指针:第一个指针指向第一个弧头为该结点的边结点;第二个指针就指向第一个弧尾为该结点的边结点

4.邻接多重表
点结点:就是data和第一个含有这个顶点的边
边结点,mark—-标志域,可用以标记该条边是否被搜索过;
vi和vj—-该条边依附的两个顶点在图中的位置;
vilink—-指向下一条依附于顶点vi的边;
vjlink—-指向下一条依附于顶点vj的边。

找不到下一个没有被指的边了,那就赋值为NULL,没有被指就是链接下来,该结点是最后一个没有被指的结点

3.图的遍历

1.深度优先搜索:一直往下走,如果没有没被搜索到的结点,就搜索上一个被搜索的结点(Stack)

2.广度优先搜索:无论如何先把该结点的每个儿子先遍历了(队列)

4.最小生成树

1.DFS和BFS的生成树

生成森林:对图的每个联通分枝进行生成树搜索

5.网的最小生成树:
在网G的各生成树中,其中各边的权之和最小的生成树称为G的最小生成树
MST性质:设G=(V,E)是一个连通图,通过某种算法构造其最小生成树,T=(U,TE)是正在构造的最小生成树。如果边(u,v)是G中所有一端在U中(即u∈U)而另一端在V-U中(即v∈V-U)具有最小值的一条边,则必存在一棵包含边(u,v)的最小生成树。

6.Prim算法:
对n个顶点的连通网,初始时, T=(U,TE),U为一个开始顶点,TE=φ,以后根据MST性质,每次增加一个顶点和一条边,重复n-1次。U不断增大,V-U不断减小直到为空。

初始化:把进入点标记为U集合,每个节点到进入点的距离标记为V-U中各顶点到U的最短直接路径,相邻结点数组标记为A
进入Prim算法:遍历一遍V-U中各顶点到U的最短直接路径,发现V集合中1是最小的,C进入U集
接着遍历与C连接的的点,更新V-U中各顶点到U的最短直接路径,我们发现C到F的距离为8,比无穷大小,更新值为8,把F中的相邻结点记为C
注意:在找最小的结点时,要忽略已经进入U集的结点的值,这是B进入结点,遍历一遍B到每个结点的距离,发现5<6,更新数据集,D的邻接结点为B
/* 邻接矩阵存储 - Prim最小生成树算法 */

Vertex FindMinDist( MGraph Graph, WeightType dist[] )
{ /* 返回未被收录顶点中dist最小者 */
    Vertex MinV, V;
    WeightType MinDist = INFINITY;

    for (V=0; V<Graph->Nv; V++) {
        if ( dist[V]!=0 && dist[V]<MinDist) {
            /* 若V未被收录,且dist[V]更小 */
            MinDist = dist[V]; /* 更新最小距离 */
            MinV = V; /* 更新对应顶点 */
        }
    }
    if (MinDist < INFINITY) /* 若找到最小dist */
        return MinV; /* 返回对应的顶点下标 */
    else return ERROR;  /* 若这样的顶点不存在,返回-1作为标记 */
}

int Prim( MGraph Graph, LGraph MST )
{ /* 将最小生成树保存为邻接表存储的图MST,返回最小权重和 */
    WeightType dist[MaxVertexNum], TotalWeight;
    Vertex parent[MaxVertexNum], V, W;
    int VCount;
    Edge E;
    
    /* 初始化。默认初始点下标是0 */
       for (V=0; V<Graph->Nv; V++) {
        /* 这里假设若V到W没有直接的边,则Graph->G[V][W]定义为INFINITY */
           dist[V] = Graph->G[0][V];
           parent[V] = 0; /* 暂且定义所有顶点的父结点都是初始点0 */ 
    }
    TotalWeight = 0; /* 初始化权重和     */
    VCount = 0;      /* 初始化收录的顶点数 */
    /* 创建包含所有顶点但没有边的图。注意用邻接表版本 */
    MST = CreateGraph(Graph->Nv);
    E = (Edge)malloc( sizeof(struct ENode) ); /* 建立空的边结点 */
           
    /* 将初始点0收录进MST */
    dist[0] = 0;
    VCount ++;
    parent[0] = -1; /* 当前树根是0 */

    while (1) {
        V = FindMinDist( Graph, dist );
        /* V = 未被收录顶点中dist最小者 */
        if ( V==ERROR ) /* 若这样的V不存在 */
            break;   /* 算法结束 */
            
        /* 将V及相应的边<parent[V], V>收录进MST */
        E->V1 = parent[V];
        E->V2 = V;
        E->Weight = dist[V];
        InsertEdge( MST, E );
        TotalWeight += dist[V];
        dist[V] = 0;
        VCount++;
        
        for( W=0; W<Graph->Nv; W++ ) /* 对图中的每个顶点W */
            if ( dist[W]!=0 && Graph->G[V][W]<INFINITY ) {
            /* 若W是V的邻接点并且未被收录 */
                if ( Graph->G[V][W] < dist[W] ) {
                /* 若收录V使得dist[W]变小 */
                    dist[W] = Graph->G[V][W]; /* 更新dist[W] */
                    parent[W] = V; /* 更新树 */
                }
            }
    } /* while结束*/
    if ( VCount < Graph->Nv ) /* MST中收的顶点不到|V|个 */
       TotalWeight = ERROR;
    return TotalWeight;   /* 算法执行完毕,返回最小权重和或错误标记 */
}

2.克鲁斯卡尔:
需要将边按递增次序排列以供选择。选择权重最小的边,然后保证没有环
怎么保证没有环?度!

4.有向无环图应用

一个无环的有向图称为有向无环图(directed acycline graph), 简称DAG图。

1.拓扑排序:
AOV网(Activity On Vertex network:以顶点表示活动,弧表示活动之间的优先关系的DAG图。

拓扑排序算法思想:重复下列操作,直到所有顶点输出完。
(1)在有向图中选一个没有前驱的顶点输出(选择入度为0的顶点);
(2)从图中删除该顶点和所有以它为尾的弧(修改其它顶点入度) 。

2.AOE网
AOE网研究的问题:
(1) 完成整项工程至少需要多少时间;
(2) 哪些活动是影响工程进度的关键。

1.(顶点)事件vi的最早发生时间ve(vi):从开始点到vi的最长路径长度。(ve(v1)=0),既表示事件vi的最早发生时间,也表示所有以vi为尾的弧所表示的活动ak的最早发生时间e(k)。
如果结点只有一个前驱结点:那就是前驱结点ve+到这个结点的边
有多个前驱结点:前驱结点ve+到这的边求最大值
2.活动最早开始时间ee(e)=所连接的弧尾的标记值
3.(顶点)事件vi允许的最迟开始时间vl(vi) = 完成点(汇点)vn的的最早发生时间ve(vn)减去vk到vn的最长路径长度。
如果有多个后继结点,对每个结点的值求最小即可
4.确定了顶点vi的最迟开始时间后,确定所有以vi为弧头的活动ak的最迟开始时间l(k):表示在不推迟整个工程完成的前提下,活动ak最迟必须开始的时间。
l(ak)=vl(ak弧头对应顶点)-活动ak的持续时间

5 最短路径

算法1(Dijkstra算法):
以每一个顶点为源点,重复执行Dijkstra算法n次,即可求出每一对顶点之间的最短路径。

/* 邻接矩阵存储 - 有权图的单源最短路算法 */

Vertex FindMinDist( MGraph Graph, int dist[], int collected[] )
{ /* 返回未被收录顶点中dist最小者 */
    Vertex MinV, V;
    int MinDist = INFINITY;

    for (V=0; V<Graph->Nv; V++) {
        if ( collected[V]==false && dist[V]<MinDist) {
            /* 若V未被收录,且dist[V]更小 */
            MinDist = dist[V]; /* 更新最小距离 */
            MinV = V; /* 更新对应顶点 */
        }
    }
    if (MinDist < INFINITY) /* 若找到最小dist */
        return MinV; /* 返回对应的顶点下标 */
    else return ERROR;  /* 若这样的顶点不存在,返回错误标记 */
}

bool Dijkstra( MGraph Graph, int dist[], int path[], Vertex S )
{
    int collected[MaxVertexNum];
    Vertex V, W;

    /* 初始化:此处默认邻接矩阵中不存在的边用INFINITY表示 */
    for ( V=0; V<Graph->Nv; V++ ) {
        dist[V] = Graph->G[S][V];
        if ( dist[V]<INFINITY )
            path[V] = S;
        else
            path[V] = -1;
        collected[V] = false;
    }
    /* 先将起点收入集合 */
    dist[S] = 0;
    collected[S] = true;

    while (1) {
        /* V = 未被收录顶点中dist最小者 */
        V = FindMinDist( Graph, dist, collected );
        if ( V==ERROR ) /* 若这样的V不存在 */
            break;      /* 算法结束 */
        collected[V] = true;  /* 收录V */
        for( W=0; W<Graph->Nv; W++ ) /* 对图中的每个顶点W */
            /* 若W是V的邻接点并且未被收录 */
            if ( collected[W]==false && Graph->G[V][W]<INFINITY ) {
                if ( Graph->G[V][W]<0 ) /* 若有负边 */
                    return false; /* 不能正确解决,返回错误标记 */
                /* 若收录V使得dist[W]变小 */
                if ( dist[V]+Graph->G[V][W] < dist[W] ) {
                    dist[W] = dist[V]+Graph->G[V][W]; /* 更新dist[W] */
                    path[W] = V; /* 更新S到W的路径 */
                }
            }
    } /* while结束*/
    return true; /* 算法执行完毕,返回正确标记 */
}
Source:ZJU

算法2(Floyd算法):
算法思想:
假设求Vi到Vj的最短路径,如果从Vi到Vj有弧,则存在一条长度为arcs[i][j]的路径,该路径不一定是最短路径,尚需进行n次试探。

首先考虑(Vi,V0,Vj)是否存在(即判断(Vi,V0)和( V0,Vj)是否存在),如果存在,比较(Vi, Vj)和(Vi,V0)+( V0,Vj),取长度较短的为从Vi到Vj的中间顶点序号不大于0的最短路径。

再考虑路径上再增加一个顶点V1,如果考虑(Vi,…V1)和(V1,….Vj), (Vi,…V1)和(V1,….Vj)都是中间顶点序号不大于0的最短路径。 (Vi,…V1,….Vj)可能是从Vi到Vj的中间顶点序号不大于1的最短路径。
比较Vi到Vj的中间顶点序号不大于0的最短路径和(Vi,…V1)+(V1,….Vj),取长度较短的为从Vi到Vj的中间顶点序号不大于1的最短路径。

bool Floyd( MGraph Graph, WeightType D[][MaxVertexNum], Vertex path[][MaxVertexNum] )
{
    Vertex i, j, k;

    /* 初始化 */
    for ( i=0; i<Graph->Nv; i++ )
        for( j=0; j<Graph->Nv; j++ ) {
            D[i][j] = Graph->G[i][j];
            path[i][j] = -1;
        }

    for( k=0; k<Graph->Nv; k++ )
        for( i=0; i<Graph->Nv; i++ )
            for( j=0; j<Graph->Nv; j++ )
                if( D[i][k] + D[k][j] < D[i][j] ) {
                    D[i][j] = D[i][k] + D[k][j];
                    if ( i==j && D[i][j]<0 ) /* 若发现负值圈 */
                        return false; /* 不能正确解决,返回错误标记 */
                    path[i][j] = k;/*记录I和j之间的中间结点*/
                }
    return true; /* 算法执行完毕,返回正确标记 */
}
最后修改日期:2020年11月5日