一、思维导图

二、重要概念

1.图的定义和基本术语

a.图的结构定义

定义：是由一个顶点集 V 和一个顶点间的关系集合组成的数据结构Graph = (V , VR)；

b.基本术语

·有（无）向网

·子图

·完全图

·有向完全图

·稀疏图、稠密图

·邻接点、相关联、度

·路径、路径长度

·连通图、连通分量、强连通图、强连通分量

·生成树、生成森林

2.图的存储结构

a.邻接矩阵

#define MaxInt 32767 
#define MVNum 100 
typedef char VerTexType; 
typedef int ArcType; 
typedef struct { 
VerTexType vexs[MVNum]; // 顶点表
ArcType arcs[MVNum][MVNum]; // 弧的信息(邻接矩阵)
int vexnum, arcnum; // 图的顶点数和边数
} AMGraph; //邻接矩阵

b.邻接表

表（弧/边）：
typedef struct ArcNode { 
int adjvex; // 该弧所指向的顶点的位置
struct ArcNode *nextarc;//指向下一条弧的指针
InfoType *info; // 该弧相关信息的指针
} ArcNode;
头结点：
typedef struct VNode { 
VerTexType data; // 顶点信息
ArcNode *firstarc; // 指向第一条依附该顶点的弧
} VNode, AdjList[MVNUM];

3.图的遍历

a.深度优先遍历

1）连通图的深度优先遍历描述：

void DFS(Graph G, int v) {
//从顶点v出发，深度优先搜索遍历连通图G
访问v; visited[v] = TRUE; 
//FirstAdjVex为获得v的第一个邻接点, NextAdjVe为获得下一
个邻接点
for(w=FirstAdjVex(G, v); w>=0; w=NextAdjVex(G,v,w)) 
if (!visited[w]) DFS(G, w); 
// 对v的尚未访问的邻接顶点w递归调用DFS
}

·邻接表：按顺序访问指针，且按顺序访问其指向，并访问其指向的指向

以上图为例：先访问A，A的第一个指向为B，便访问B，B的第一个指向为C，就访问C，以此类推。

·邻接矩阵：与上面的原理类似，行遍历，找第一个不为无穷的点，并遍历该点为行下标的行，循环以上步骤。

2）非连通图

先按连通图遍历步骤遍历，遍历后找原有点中未遍历过的，重复连通图遍历步骤。

深度优先遍历图的实质：对每个顶点查找其邻接点的过程

b.广度优先遍历

算法描述：

void BFSTraverse(Graph G){
·   for (v=0; v<G.vexnum; ++v)
    visited[v] = FALSE; //初始化访问标志
    InitQueue(Q); // 置空的辅助队列Q
    for ( v=0; v<G.vexnum; ++v )
        if ( !visited[v]) {// v 尚未访问
        访问v; visited[v] = TRUE; // 访问v
        EnQueue(Q, v); // v入队列
        while (!QueueEmpty(Q)) {
            DeQueue(Q, u); // 队头元素出队并置为u
            for(w=FirstAdjVex(G, u);
            w!=0;
            w=NextAdjVex(G,u,w))
            if ( ! visited[w]) {
                访问v; visited[w]=TRUE; 
                EnQueue(Q, w); // 访问的顶点w入队列
            } // if
        }//while
    } //for
}

广度优先遍历：类似于树的层次遍历，所以是先输出每个点所有的邻接点，再输出邻接点的邻接点。

4.最小生成树

a.普里姆算法：

算法描述：

struct {
VertexType adjvex; //U集中的顶点序号
VRType lowcost; //边的权值
} closedge[MAXVNUM];
void MiniSpanTree_P(MGraph G, VertexType u) {
//用普里姆算法从顶点u出发构造网G的最小生成树
    k = LocateVex ( G, u ); 
    for (j=0; j<G.vexnum; ++j )//辅助数组初始化
        if (j!=k) 
        closedge[j] = {u,G.arcs[k][j].adj }; 
        closedge[k].lowcost = 0; //初始，U＝{u}
    for (i=0; i<G.vexnum; ++i) {
继续向生成树上添加顶点; }
    k = Min(closedge);//求出加入生成树的下一个顶点k
    printf(closedge[k].adjvex, G.vexs[k]); 
    //输出生成树上一条边
    closedge[k].lowcost = 0;//第k顶点并入U集
    for(j = 0; j < G.vexnum; ++j) 
    //修改其它顶点的最小边
    if (G.arcs[k][j].adj < closedge[j].lowcost)
    closedge[j]={G.vexs[k], G.arcs[k][j].adj };

b.克鲁斯卡尔算法：

算法描述：

构造非连通图 ST=( V,{ } );
    k = i = 0; // k 计选中的边数
    while (k<n-1) {
        ++i;
    检查边集 E 中第 i 条权值最小的边(u,v);
    若(u,v)加入ST后不使ST中产生回路，则输出边(u,v); 
    且k++;
    }

两种算法比较：

·普里姆算法：O(n*n)，适用于稠密图

·克鲁斯卡尔算法：O(eloge)，适用于稀疏图

5.最短路径

a.Dijkstra算法思想(与普里姆算法类似)

算法描述：

void ShortestPath_DIJ(AMGraph G, int v0){
//初始化
    n = G.vexnum;
    for(v = 0; v<n; ++v){
        S[v] = false; //s初始为空集
        D[v] = G.arcs[v0][v]; //v0到各个顶点的弧的权值
        if (D[v] < MaxInt) 
        Path[v] = v0; //v0和v之间有弧
        else Path[v] = -1; //v0和v之间无弧
    }
    S[v0] = true; //v0加入s
    D[v0] = 0;
    for(i = 1;i < n; ++i){
    min = MaxInt;
    for(w = 0; w < n; ++w)
    if(!S[w] && D[w] < min)
        {v = w; min = D[w];}//选择一条当前最短路径
    S[v] = true; //将v加入s
    for(w = 0; w < n; ++w)//加入v后，v0到其他节点需更新
    if(!S[w] && (D[v] + G.arcs[v][w] < D[w]){
        D[w] = D[v] + G.arcs[v][w];
        Path[w] = v;
        }
    }
}

b.弗洛伊德(Floyd)算法：每一对顶点之间的最短路径

对每个顶点进行Dijkstra算法

6.有向无环图及其应用

a.有向无环图

一个无环的有向图称作有向无环图(Directed Acycline Graph)，简称DAG图。

有向无环图也是描述一项工程或系统的进行过程的有效工具。

绝大多数的工程都可分为若干个活动的子工程，而这些子工程之间，通常都受着一定条件的约束。

对应于有向图，即为进行拓扑排序和求关键路径的操作。

b.拓扑排序

算法描述：

while (v<>0) {
    printf(v); ++m;
    w:=FirstAdj(v);
    while (w<>0) {
    inDegree[w]--;
    w:=nextAdj(v,w);
    }
    取下一个入度为零的顶点v;
}
if m<n printf(“图中有回路”);
CountInDegree(G,indegree); //对各顶点求入度
InitStack(S);
for ( i=0; i<G.vexnum; ++i)
if (!indegree[i]) Push(S, i); //入度为零的顶点入栈
count=0; //对输出顶点计数
while (!EmptyStack(S)) {
    Pop(S, v); ++count; printf(v);
    for (w=FirstAdj(v); w; w=NextAdj(G,v,w)){
        --indegree(w); // 弧头顶点的入度减一
        if (!indegree[w]) Push(S, w);
    }
}
if (count<G.vexnum) printf(“图中有回路”);

1）从有向图中选取一个没有前驱的顶点，并输出之；

2）从有向图中删去此顶点以及所有以它为尾的弧；

3）重复上述两步，直至图空，或者图不空但找不到无

前驱的顶点为止。

4）没有前驱的顶点  入度为零的顶点；

删除顶点及以它为尾的弧  弧头顶点的入度减1。

7.关键路径

·整个工程完成的时间为：从有向图的源点到汇点的最长路径

·“关键活动”指的是：该弧上的权值增加将使有向图上的最长路径的长度增加。

·事件vi的最早发生时间：从开始点v1到vi的最长路径长度。用ve(i)表示。

·事件vi的最迟发生时间：在不推迟整个工期的前提下，事件vi允许的最晚发生时间。用vl(i)表示。

·活动ai的最早开始时间：即为ai的弧尾顶点(事件)的最早发生时间。用e(i)表示。

·活动ai的最迟开始时间：在保证不推迟整个工程的完成时间的前提下，活动ai的最迟开始时间。用l(i)表示。

·计算公式：e(i) = ve(j)（j为边的头）

l(i) =vl(k) - dut(<j, k>)（k为边的尾，dut为边的权重）

·求ve的顺序应该是按拓扑有序的次序，求vl的顺序应该是按拓扑逆序的次序。

·根据e(i)、l(i)能更准确求出关键路径。

三、疑难问题

1.Dijkstra算法思想中的Path[]数组

每点对应的值是该点所对应最短路径的上一个顶点

以上图为例

要到达的顶点为0，按顺序分别是2,3,4,5的数组值：

所以2到1的最短路径为2到1，

3到1的为3到4到1，

4到1的为4到1，

5到1的为5到3到4到1.