图

定义

G=(V, E)

V：顶点的有穷非空集合 V(G)为图G的顶点集合

E：V中顶点偶对（边）的有穷集合 E(G)为图G的边集合

E(G)为空时，图G只有顶点而没有边

无向图

顶点对(x,y)和(y,x)是同一条边，每条边都是无方向的

有向图

顶点对<x,y>是有序的，称为从顶点x到顶点y的一条有向边，每条边都是有方向的

基本术语

• 完全图：任意两个点都有一条边相连，分为无向n*(n-1)/2条边，和有向n*(n-1)条边
• 子图：G=(V, E)，G'=(V', E')，V'包含于V，E'包含于E'，则称G'为G的子图
• 稀疏图：有很少的边或弧的图
• 稠密图：和稀疏图相反
• 权：图上每条边可以带上数值，表示从一个顶点到另一个的距离或耗费等
• 网：边/弧带权的图
• 邻接点：对无向图，(v, v')属于E，则称顶点v和v'互为邻接点，即它俩相邻接，边(v, v')依附于俩顶点，或说边(v, v')与俩顶点相关联
• 顶点的度：与该顶点相关联的边的数目，记为TD(v)

有向图中，顶点的度等于入度与出度的和

• 路径：连续的边构成的顶点序列
• 路径长度：路径上边或弧的数目/权值之和
• 回路（环）：第一个顶点和最后一个顶点相同的路径
• 简单路径：序列中顶点均不相同的路径
• 简单回路（简单环）：除路径起点和终点相同外，其余顶点均不相同的路径
• 连通图：无向图中任意两个顶点连通（有路径），则称G为连通图，否则为非连通图
• 连通分量：无向图中的极大连通子图
• 强连通图：有向图（无向图）任意两个顶点间都存在路径
• 强连通分量：有向图中的极大连通子图
• 极小连通子图：G的连通子图，在该子图中删除任何一条边，子图不再连通
• 连通图的生成树：包含无向图G的所有顶点的极小连通子图
• 有向树：有一个顶点的入度为0，其余顶点的入度均为1的有向图
• 生成森林：若干有向树组成，包含图中全部顶点

图的存储结构

顺序存储结构

邻接矩阵（数组表示法）

建立顶点表（记录各个顶点信息）和一个邻接矩阵（表示各个顶点间关系）

A.Edge[i][j]=1, 若<i, j>属于E或(i, j)属于E

无向图

• 无向图的邻接矩阵是对称的
• 顶点i的度=第i行（列）中1的个数
• 完全图中除主对角线为0，其余均为1

有向图

• 第i行：以结点v~i~为出度的有向边
• 第i列：以结点v~i~为入度的有向边
• 顶点的出度等于第i行元素之和
• 顶点的入度等于第i列元素之和

网（有权图）

算法描述

创建无向网

• 输入总顶点数和总边数
• 依次输入点的信息存入顶点表中
• 初始化邻接矩阵，是每个权值初始化为极大值
• 构造邻接矩阵

Status CreateUDN(AMGraph &G){ 
    //采用邻接矩阵表示法，创建无向网G 
    cin>>G.vexnum>>G.arcnum;     //输入总顶点数，总边数 
    for(i = 0; i<G.vexnum; ++i)  
      cin>>G.vexs[i];                            //依次输入点的信息 
    for(i = 0; i<G.vexnum;++i)     //初始化邻接矩阵，边的权值均置为极大值
       for(j = 0; j<G.vexnum;++j)   
         G.arcs[i][j] = MaxInt;   
    for(k = 0; k<G.arcnum;++k){                     //构造邻接矩阵 
      cin>>v1>>v2>>w;         //输入一条边依附的顶点及权值 
      i = LocateVex(G, v1); 
      j = LocateVex(G, v2);          //确定v1和v2在G中的位置
      G.arcs[i][j] = w;                   //边<v1, v2>的权值置为w 
      G.arcs[j][i] = G.arcs[i][j];    //置<v1, v2>的对称边<v2, v1>的权值为w 
   }//for 
   return OK; 
}//CreateUDN 

优点

• 便于判断两个顶点间是否有边
• 便于计算各个顶点的度

缺点

• 不便于增加和删除顶点
• 不便于统计边的数目，需要扫描邻接矩阵所有元素才能统计完毕，时间复杂度为O(n^2^)
• 空间复杂度高，对稀疏图来说浪费空间

链式存储结构

邻接表（链式）表示法

对每个顶点v~i~都建立一个单链表，把所有与v~i~关联的边的信息链接起来，每个结点设置三个域

设图为n个顶点，e条边结点

无向图

注意：里面的数字表示的是数组下标

邻接表不唯一，各个边结点链入顺序不一样

空间效率O(n+2e)，比邻接矩阵节省空间

有向图

空间效率O(n+e)

邻接表存储表示

#define MVNum 100                            //最大顶点数 
typedef struct ArcNode{                        //边结点 
    int adjvex;                                  //该边所指向的顶点的位置 
    struct ArcNode * nextarc;              //指向下一条边的指针 
    OtherInfo info;                                        //和边相关的信息 
}ArcNode; 
typedef struct VNode{ 
    VerTexType data;                        //顶点信息 
    ArcNode * firstarc;                    //指向第一条依附该顶点的边的指针 
}VNode, AdjList[MVNum];                   //AdjList表示邻接表类型 
typedef struct{ 
    AdjList vertices;                         //邻接表 
    int vexnum, arcnum;                      //图的当前顶点数和边数 
}ALGraph; 

创建无向网

• 输入总顶点数和总边数
• 依次输入点的信息存入顶点表中 ，是每个表头结点的指针域初始化为NULL
• 创建邻接表

Status CreateUDG(ALGraph &G){ 
    //采用邻接表表示法，创建无向图G 
    cin>>G.vexnum>>G.arcnum;       //输入总顶点数，总边数 
    for(i = 0; i<G.vexnum; ++i){          //输入各点，构造表头结点表 
        cin>> G.vertices[i].data;               //输入顶点值 
        G.vertices[i].firstarc=NULL; //初始化表头结点的指针域为NULL 
    } 
    for(k = 0; k<G.arcnum;++k){            //输入各边，构造邻接表 
        cin>>v1>>v2;                         //输入一条边依附的两个顶点 
        i = LocateVex(G, v1);  j = LocateVex(G, v2);  
        p1=new ArcNode;                           //生成一个新的边结点*p1 
        p1->adjvex=j;                               //邻接点序号为j 
        p1->nextarc= G.vertices[i].firstarc;  G.vertices[i].firstarc=p1;  
        //将新结点*p1插入顶点vi的边表头部 
        p2=new ArcNode; //生成另一个对称的新的边结点*p2 
        p2->adjvex=i;                               //邻接点序号为i 
        p2->nextarc= G.vertices[j].firstarc;  G.vertices[j].firstarc=p2;  
        //将新结点*p2插入顶点vj的边表头部 
    } 
    return OK; 
}//CreateUDG 

优点

• 便于增加和删除结点
• 便于统计边的数目，按顶点表顺序扫描所有边表可得到边的数目
• 空间效率高

缺点

• 不便于判断顶点间是否有边
• 不便于计算有向图各个顶点的度

邻接矩阵多用于稠密图，邻接表多用于稀疏图

十字链表

有向图的另一种链式存储结构，可以看成是将有向图的邻接表和逆邻接表结合起来的一种链表

有向图

无向图

图的遍历

深度优先（DFS）

步骤

• 访问起始点v
• 若v的第一个邻接点没访问过，深度遍历此邻接点w~1~
• 再重w~1~出发，访问与w~1~邻接但还未访问的顶点w~2~
• 再从w~2~出发，进行类似的访问……
• 直到所有邻接顶点都被访问过为止

中间如果没有其他没有被访问过的邻接顶点，就退回一步进行搜索，并重复

邻接矩阵

递归

void DFS(AMGraph G, int v){            //图G为邻接矩阵类型 
    cout<<v;  visited[v] = true;          //访问第v个顶点
    for(w = 0; w< G.vexnum; w++)      //依次检查邻接矩阵v所在的行  
        if((G.arcs[v][w]!=0)&& (!visited[w]))  
            DFS(G, w); 
      //w是v的邻接点，如果w未访问，则递归调用DFS 
} 

邻接表

递归

void DFS(ALGraph G, int v){        //图G为邻接表类型 
    cout<<v;  visited[v] = true;          //访问第v个顶点
    p= G.vertices[v].firstarc;             //p指向v的边链表的第一个边结点 
    while(p!=NULL){                        //边结点非空 
        w=p->adjvex;                         //表示w是v的邻接点 
        if(!visited[w])  DFS(G, w);          //如果w未访问，则递归调用DFS 
        p=p->nextarc;                         //p指向下一个边结点 
    } 
} 

广度优先

分层搜索，不是递归

步骤

• 访问起始点v后，依次访问v的邻接点，访问过的置visited[v]为true，并将v入队
• 然后依次访问这些顶点中未被访问过的邻接点
• 直到所有顶点都被访问过（即队空）为止

void BFS (Graph G, int v){ 
    //按广度优先非递归遍历连通图G 
    cout<<v; visited[v] = true;             //访问第v个顶点
    InitQueue(Q);                          //辅助队列Q初始化，置空   
    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]){                   //w为u的尚未访问的邻接顶点 
             cout<<w; visited[w] = true;    EnQueue(Q, w); //w进队 
          }//if 
    }//while 
}//BFS 

DFS和BFS比较

• 空间复杂度相同，O(n)
• 时间复杂度于存储结构相关（是邻接矩阵还是邻接表）与搜索路径无关

图的应用

最小生成树

• 使用不同的遍历图方法，可以得到不同的生成树
• 从不同顶点出发，也能得到不同生成树
• 按照生成树的定义，n个顶点的连通网络的生成树有n个顶点、n-1条边

最小生成树目标：寻找各边权值之和最小的生成树

Prim算法

归并顶点，与边数无关，适于稠密网

• 从某顶点起，选择与它关联的最小权值的边，将其顶点加入到生成树的顶点集合
• 每一个顶点都如此，选择没有选过且具有最小权值的边
• 直到所有顶点都加入生成树的顶点集合

Kruskel算法

归并边，适于稀疏网

• 构造n个顶点的非连通图
• 选取其中权值最小边，两个顶点相连
• 重复直到所有顶点在同一连通分量上为止

最短路径

与最小生成树区别是不用包含全部n个顶点

单源最短路径

一顶点到其他顶点最短距离

• 初始化：先找出从源点v~0~到各终点v~k~的直达路径(v~0~, v~k~)

• 选择：从这些路径中找出一条长度最短的路径(v~0~, u)

  if    (v

~0~, u) + (u, v~k~) < (v~0~, v~k~)

(v

~0~, u, v~k~)代替(v~0~, v~k~)

• 更新：对其余各条路径进行调整

所有顶点间最短路径

任意两顶点间

拓扑排序

关键路径