什么是“图”(Graph)？

  • 表示“多对多”的关系
    • 线性表：“一对一”关系，树：“一对多”关系
    • 实际上，线性表和树都可以认为是图的一种特例
  • 图中包含(两种结构共同建立起图的结构)
    • 一组顶点：通常用V(Vertex)表示顶点集合
    • 一组边：通常用E(Edge)表示边的集合
    • 边是顶点对的组合：
      • (v,w)∈E(v,w)∈E，其中v,w∈Vv,w∈V，表示无向边v−wv-w
      • <v,w><v,w>表示从vv指向ww的边(单行线)，表示有向边v→wv\rightarrow w
  • 不考虑重边和自回路
    • 无重边：对无向边，两个结点之间的边只有一条
    • 无自回路：对有向边，从一个顶点出发的边不能指向该顶点自身
  • 权重：如果图的边上带有权重，则称为“网络”

图的抽象数据类型定义

类型名称：图(Graph)
数据对象集：G(V,E)由一个非空的有限顶点集合V和一个有限边集合E组成
操作集：对于任意图G ∈ Graph，以及v ∈ V，e ∈ E
Graph Create():建立并返回空图;
Graph InsertVertex(Graph G,Vertex v):将v插入G;
Graph InsertEdge(Graph G,Edge e):将e插入G;
void DFS(Graph G,Vertex v):从顶点v出发深度优先遍历图G;
void BFS(Graph G,Vertex v):从顶点v出发宽度(广度)优先遍历图G;
void ShortestPath(Graph G,Vertex v,int Dist[]):计算图G中顶点v到任意其他顶点的最短距离;
void MST(Graph G):计算图G的最小生成树;

如何在程序中表示一个图

常用的两种方法：邻接矩阵、邻接表
(除此外还有各种五花八门的方法，使用哪种取决于研究问题的特点)

邻接矩阵

  • 使用邻接矩阵G[N][N]
    • N个顶点从0到N-1编号
    • 若<vi,vj><v_i,v_j>是G中的边则G[i][j]=1，否则G[i][j]=0
  • 问题：对于无向图的存储，怎样可以省一半的空间
    • 用一个长度为N(N+1)2\frac{N(N+1)}{2}的一维数组A存储半个矩阵(上三角或下三角)的元素
    • 则GijG_{ij}在A中对应的下标为i(i+1)2+j\frac{i(i+1)}{2}+j
    • 在一维数组压缩后，GijGij之前的元素包括前i行(从0开始)i列构成的三角形内的元素，再加上第i+1行的前j个元素
  • 对于网络，只需要把G[i][j]的值由1改为定义为边<vi,vj><v_i,v_j>的权重即可
    • 问题：viv_i和vjv_j之间若没有边该怎么表示？
      • 不一定，取决于权重的取值范围
      • 如使用16位带符号位的int的所能表示的最大数65535是一个比较通用的表示方法
  • 邻接矩阵的优点
    • 直观、简单、好理解
    • 方便检查任意一对顶点间是否存在边
    • 方便找任一顶点的所有“邻接点”(有边直接相连的顶点)
    • 方便计算任一顶点的“度”(从该顶点出发的总边数为“出度”，指向该顶点的边数为“入度”)
      • 无向图：对应行(或列)非0元素的个数
      • 有向图：对应行非0元素的个数是“出度”；对应列非0元素的个数是“入度”
  • 邻接矩阵的缺点
    • 浪费空间——存稀疏图(点很多但边很少)有大量的无效空间
    • 对稠密图(特别是完全图-任意两顶点之间均有一条边，共(N−1)N2\frac{(N-1)N}{2}条)还是很合算的
    • 浪费时间——如统计稀疏图中有几条边时需要遍历大量无效空间

邻接表

  • 使用邻接表：G[N]为指针数组，对应矩阵每行一个链表，只存非0元素
    • 对于网络，在非头结点中要增加一个记录权重的域
    • 一定要够稀疏才合算啊~~~
  • 需要NN个头指针+2E+2E个结点空间(无向图)
    • 每条边对应存储一个结点信息，每个结点至少两个域，一个储存边中结点的信息另一个是结点指针)
    • 如果指针和结点信息所占的空间相同的话，则使用邻接表存储无向图消耗的空间可以简单看作N+4EN+4E(而邻接矩阵则是N2N^2)
  • 邻接表的特点
    • 方便找任一顶点的所有“邻接点”
    • 节约稀疏图的空间
    • 当边数特别多时，不适合邻接表存储
      • 对无向图：方便计算任一顶点的“度”(无向图的入度出度相等，因此只需对头结点连接的链进行遍历即可)
      • 对有向图：只能计算“出度”；需要构造“逆邻接表”(存指向自己的边)来方便计算“入度”
      • 并且不方便检查任意一对顶点之间是否存在边以及其邻接点

图的实现演示

//浙江大学mooc数据结构课程
#include <stdlib.h>
#include <stdio.h>
/* 图的邻接矩阵表示法 */

#define MaxVertexNum 100    /* 最大顶点数设为100 */
#define INFINITY 65535        /* ∞设为双字节无符号整数的最大值65535*/
typedef int WeightType;        /* 边的权值设为整型 */
typedef char DataType;        /* 顶点存储的数据类型设为字符型 */

/* 顶点的定义 */
typedef int Vertex;         /* 用顶点下标表示顶点,为整型 */
/* 边的定义 */
typedef struct ENode *PtrToENode;
struct ENode{
    Vertex V1, V2;      /* 有向边<V1, V2> V1->V2 */
    WeightType Weight;  /* 权重 */
};
typedef PtrToENode Edge;

/* 图结点的定义 */
typedef struct MGNode *PtrToMGNode;
struct MGNode{
    int Nv;  /* 顶点数 */
    int Ne;  /* 边数   */
    WeightType G[MaxVertexNum][MaxVertexNum]; /* 邻接矩阵，因为其中有可能要存储边的权值，所以类型为WeightType */
    DataType Data[MaxVertexNum];      /* 存顶点的数据 */
    /* 注意：很多情况下，顶点无数据，此时Data[]可以不用出现 */
};
typedef PtrToMGNode MGraph; /* 以邻接矩阵存储的图类型 */

/* 图的邻接表表示法 */

/* 边的定义：同邻接矩阵 */
/* 邻接点的定义 */
typedef struct AdjVNode *PtrToAdjVNode; 
struct AdjVNode{
    Vertex AdjV;        /* 邻接点下标 */
    WeightType Weight;  /* 边权重 */
    PtrToAdjVNode Next;    /* 指向下一个邻接点的指针 */
};

/* 顶点表头结点的定义 */
typedef struct Vnode{
    PtrToAdjVNode FirstEdge;/* 边表头指针 */
    DataType Data;            /* 存顶点的数据 */
    /* 注意：很多情况下，顶点无数据，此时Data可以不用出现 */
} AdjList[MaxVertexNum];    /* 定义一个表头结点数组，下标对应图中的所有结点，再加上图的一些其他信息就可以构成图的结构*/

/* 图结点的定义 */
typedef struct LGNode *PtrToLGNode;
struct LGNode{  
    int Nv;     /* 顶点数 */
    int Ne;     /* 边数   */
    AdjList G;  /* 邻接表 */
};
typedef PtrToLGNode LGraph; /* 以邻接表方式存储的图类型 */

/* MGraph初始化 */
MGraph CreateMGraph( int VertexNum )
{ /* 初始化一个有VertexNum个顶点但没有边的图，顶点数必须要指定，不然无法分配邻接表的空间 */
    Vertex V, W;
    MGraph Graph;

    Graph = (MGraph)malloc( sizeof(struct MGNode) );
    Graph->Nv = VertexNum;
    Graph->Ne = 0;
     
    /* 注意：这里默认顶点编号从0开始，到(Graph->Nv - 1) */
    for(V=0; V<Graph->Nv; V++)
        for(W=0; W<Graph->Nv; W++)
            Graph->G[V][W] = 0; /* 或INFINITY */
    
    return Graph;
}

/* 向MGraph中插入边 */
void InsertEdge( MGraph Graph, Edge E)
{
    /* 插入边 <V1, V2> */
    Graph->G[E->V1][E->V2] = E->Weight;
    
    /* 若是无向图，还要插入边<V2, V1> */
    Graph->G[E->V2][E->V1] = E->Weight;
}

/* 完整地建立一个MGraph */
MGraph BuildMGraph()
{
    MGraph Graph;
    Edge E;
    Vertex V;
    int Nv, i;

    scanf("%d", &Nv);
    Graph = CreateMGraph(Nv);
    scanf("%d", &(Graph->Ne));
    if( Graph->Ne != 0) {
        E = (Edge)malloc(sizeof(struct ENode));
        for(i=0; i<Graph->Ne; i++) {
            scanf("%d %d %d",
                    &E->V1, &E->V2, &E->Weight);
            InsertEdge( Graph, E);
        }
    }
    /* 如果顶点有数据的话，读入数据 */
    for (V=0; V<Graph->Nv; V++)
        scanf(" %c", &(Graph->Data[V]));
    return Graph;
}

/* 简化的图的邻接矩阵实现 */
int G[MaxVertexNum][MaxVertexNum],Nv,Ne;
void BuildGraph_sim()
{
    int i, j, v1, v2, w;

    scanf("%d", &Nv);
    /* CreateGraph */
    for(i=0; i<Nv; i++)
        for(j=0;j<Nv;j++)
            G[i][j] = 0;/* 或INFINITY */
    scanf("%d", &Ne);
    for(i=0; i<Ne; i++) {
        scanf("%d %d %d", &v1, &v2, &w);
        /* InsertEdge */
        G[v1][v2] = w;
        G[v2][v1] = w;
    }
}


LGraph CreateLGraph( int VertexNum )
{ 
    Vertex V;
    LGraph Graph;
    
    Graph = (LGraph)malloc( sizeof(struct LGNode) ); /* 建立图 */
    Graph->Nv = VertexNum;
    Graph->Ne = 0;
    /* 初始化邻接表头指针 */
    /* 注意：这里默认顶点编号从0开始，到(Graph->Nv - 1) */
       for (V=0; V<Graph->Nv; V++)
        Graph->G[V].FirstEdge = NULL;
            
    return Graph; 
}

void InsertEdge( LGraph Graph, Edge E )
{
    PtrToAdjVNode NewNode;
    
    /* 插入边 <V1, V2> ，<V1, V2>代表V1->V2，所以要将V2插入到V1作为表头的链表中*/
    /* 为V2建立新的邻接点 */
    NewNode = (PtrToAdjVNode)malloc(sizeof(struct AdjVNode));
    NewNode->AdjV = E->V2;
    NewNode->Weight = E->Weight;
    /* 将V2插入V1的表头 */
    NewNode->Next = Graph->G[E->V1].FirstEdge; 
    /* 注意：表头存的是之前最后一次插入的表结点，而再向表中插入边实际上是将上一次插入的表结点与这次插入的结点之间相连 */
    Graph->G[E->V1].FirstEdge = NewNode;
    /* 更新FirstEdge */
        
    /* 若是无向图，还要插入边 <V2, V1> */
    /* 为V1建立新的邻接点 */
    NewNode = (PtrToAdjVNode)malloc(sizeof(struct AdjVNode));
    NewNode->AdjV = E->V1;
    NewNode->Weight = E->Weight;
    /* 将V1插入V2的表头 */
    NewNode->Next = Graph->G[E->V2].FirstEdge;
    Graph->G[E->V2].FirstEdge = NewNode;
}

LGraph BuildLGraph()
{
    LGraph Graph;
    Edge E;
    Vertex V;
    int Nv, i;
    
    scanf("%d", &Nv);   /* 读入顶点个数 */
    Graph = CreateLGraph(Nv); /* 初始化有Nv个顶点但没有边的图 */ 
    
    scanf("%d", &(Graph->Ne));   /* 读入边数 */
    if ( Graph->Ne != 0 ) { /* 如果有边 */ 
        E = (Edge)malloc( sizeof(struct ENode) ); /* 建立边结点 */ 
        /* 读入边，格式为"起点 终点 权重"，插入邻接表 */
        for (i=0; i<Graph->Ne; i++) {
            scanf("%d %d %d", &E->V1, &E->V2, &E->Weight); 
            /* 注意：如果权重不是整型，Weight的读入格式要改 */
            InsertEdge( Graph, E );
        }
    } 

    /* 如果顶点有数据的话，读入数据 */
    for (V=0; V<Graph->Nv; V++) 
        scanf(" %c", &(Graph->G[V].Data)); /* 只在表头存储即可 */

    return Graph;
}

图的遍历

深度优先搜索(Depth First Search,DFS)

  • 类似于树的先序遍历
  • 访问一个结点后继续顺着一个当前结点连接的结点往下访问，直到没有结点可以访问，然后原路返回上一层，直到回到起点位置
  • 原路返回——堆栈
  • 伪代码：(递归算法为例，非递归用堆栈)
void DFS(Vertex V)          //实际上是每调用一次DFS(V)是将V所在连通分量遍历一遍，BFS同理，不连通的结点并没有遍历到
{
    visited[V]=true;        //使用visited数组记录已经访问过的结点，并在每次调用函数(访问)时将当前结点状态改为已访问过
    for(V的每个邻接点W)       //考察当前结点的每个邻接顶点
        if(!visited[W])     //如果邻接结点没有访问过
            DFS(W);         //访问该结点
}

对有N个顶点、E条边的图：

  • 用邻接表存储图：时间复杂度为O(N+E)O(N+E)
    • 一共有n个表，表中的边各访问一次)
  • 用邻接矩阵存储图：时间复杂度为O(N2)O(N^2)

广度优先搜索(Breadth First Search,BFS)

  • 类似于树的层序遍历
  • 伪代码：(非递归算法为例)
void BFS(Vertex V)
{
    visited[V]=true;        
    Enqueue(V,Q);          //将访问的结点入队列
    while(!IsEmpty(Q))     //如果队列不为空
    {
        V=Dequeue(Q);      //队首元素出队列
        for(V的每个邻接点W)
            if(!visited[W]) //对没有访问过的邻接点
            {
                visited[W]=true;
                Enqueue(W,Q);   //将邻接点入队列
            }
    }
}

对有N个顶点、E条边的图：

  • 用邻接表存储图，时间复杂度为O(N+E)O(N+E)
  • 用邻接矩阵存储图，时间复杂度是O(N2)O(N^2)
  • 由此可见，图遍历的时间复杂度与存储方式无关

图的连通性

  • 连通(无向图的概念)：如果从v到w存在一条无向路径，则称v和w是连通的
    • 连通图：图中任意两顶点间均连通
    • 路径：v到w的路径是一系列顶点v,v1,v2,…,vn,Wv,v_1,v_2,…,v_n,W的集合，其中任一对相邻的顶点间都有图中的边相连接
      • 路径的长度是路径中的边数(如果带权，则是所有边的权重和)
      • 如果V到W之间所有顶点都不同，则称简单路径(没有回路)
      • 回路：起点等于终点的路径
  • 连通分量：无向图的极大连通子图
    • 极大顶点数：再加哪怕一个顶点就不连通了
    • 极大边数：包含子图中所有顶点相连的所有边
4_2.1_连通分量.png
  • 强连通(有向图的概念)：有向图中顶点v和w之间存在双向路径，则称v和w是强连通的
    • 强连通图：有向图中任一两顶点均强连通
    • 强连通分量：有向图的极大强连通子图
    • 弱连通：存在路径，但不存在双向路径
      • 判断图是否连通可以借助并查集

因此对不连通的图进行DFS、BFS时，需要在外层对图中所有结点在进行一次遍历

  • 防止极端情况如图中所有结点都不连通，都是极大连通子图
void ListComponents(Graph G)
{
    for(each V in G)
        if(!visited[V])DFS(V);//或者BFS(V);
}

图的遍历操作演示

/* 遍历操作实现 */
#include <stdio.h>
#include <queue>
#define MaxVertexNum 100
#define INFINITY 65535
#define MaxSize 100
typedef int ElementType;
typedef int Vertex;
typedef int WeightType;
typedef char DataType;
typedef struct AdjVNode *PtrToAdjVNode; 
typedef struct MGNode *PtrToMGNode;
typedef struct LGNode *PtrToLGNode;
typedef struct QNode *Queue;
typedef PtrToLGNode LGraph;
typedef PtrToMGNode MGraph;
bool Visited[MaxVertexNum];
struct AdjVNode{
    Vertex AdjV;       
    WeightType Weight; 
    PtrToAdjVNode Next;   
};
typedef struct Vnode{
    PtrToAdjVNode FirstEdge;
    DataType Data;        
} AdjList[MaxVertexNum];
struct LGNode{  
    int Nv;     
    int Ne;     
    AdjList G; 
};
struct MGNode{
    int Nv; 
    int Ne;  
    WeightType G[MaxVertexNum][MaxVertexNum]; 
    DataType Data[MaxVertexNum];     
};
struct Node{             
    ElementType Data;
    struct Node *Next;
};
struct QNode
{
    struct Node *rear;
    struct Node *front;
};
Queue CreateQueue( int );
void AddQ(Queue, ElementType);
bool IsEmpty(Queue);
ElementType DeleteQ(Queue);
/* 邻接表存储的图 - DFS */

void Visit( Vertex V )
{
    printf("正在访问顶点%d\n", V);
}

/* Visited[]为全局变量，已经初始化为false */
void DFS( LGraph Graph, Vertex V, void (*Visit)(Vertex) )
{   /* 以V为出发点对邻接表存储的图Graph进行DFS搜索 */
    PtrToAdjVNode W;
    
    Visit( V ); /* 访问第V个顶点 */
    Visited[V] = true; /* 标记V已访问 */

    for( W=Graph->G[V].FirstEdge; W; W=W->Next ) /* 对V的每个邻接点W->AdjV */
        if ( !Visited[W->AdjV] )    /* 若W->AdjV未被访问 */
            DFS( Graph, W->AdjV, Visit );    /* 则递归访问之 */
}

/* 邻接矩阵存储的图 - BFS */

/* IsEdge(Graph, V, W)检查<V, W>是否图Graph中的一条边，即W是否V的邻接点。  */
/* 此函数根据图的不同类型要做不同的实现，关键取决于对不存在的边的表示方法。*/
/* 例如对有权图, 如果不存在的边被初始化为INFINITY, 则函数实现如下:         */
bool IsEdge( MGraph Graph, Vertex V, Vertex W )
{
    return Graph->G[V][W]<INFINITY ? true : false;
}

/* Visited[]为全局变量，已经初始化为false */
void BFS ( MGraph Graph, Vertex S, void (*Visit)(Vertex) )
{   /* 以S为出发点对邻接矩阵存储的图Graph进行BFS搜索 */
    Queue Q;     
    Vertex V, W;

    Q = CreateQueue( MaxSize ); /* 创建空队列, MaxSize为外部定义的常数 */
    /* 访问顶点S：此处可根据具体访问需要改写 */
    Visit( S );
    Visited[S] = true; /* 标记S已访问 */
    AddQ(Q, S); /* S入队列 */
    
    while ( !IsEmpty(Q) ) {
        V = DeleteQ(Q);  /* 弹出V */
        for( W=0; W<Graph->Nv; W++ ) /* 对图中的每个顶点W */
            /* 若W是V的邻接点并且未访问过 */
            if ( !Visited[W] && IsEdge(Graph, V, W) ) {
                /* 访问顶点W */
                Visit( W );
                Visited[W] = true; /* 标记W已访问 */
                AddQ(Q, W); /* W入队列 */
            }
    } /* while结束*/
}