图的定义

图：G=(V,E)，V：顶点(数据元素)的有穷非空集合，E：边的有穷集合

有向图/无向图：每条边都是有/无方向的

完全图：任意两个点都有一条边相连，有n个顶点的无向完全图共有n(n-1)/2条边，有向完全图有n(n-1)条边

稀疏图：有很少边或弧的图e<nlogn

稠密图：有较多边或弧的图

网：边/弧带权的图

邻接：有边/弧相连的两个顶点之间的关系，无向图中存在(a,b)，则称a和b互为邻接点，有向图中存在<a,b>，则称a邻接到b，b邻接于a

关联(依附)：边/弧与顶点之间的关系，若存在(a,b)或<a,b>，则称该边/弧关联于a和b

度：与该顶点相关联的边的数目，有向图中顶点的度等于该顶点入度与出度之和

路径长度：路径上边或弧的数目/权值之和

简单路径：除路径起点和终点相同外，其余顶点均不相同

连通图：在无向图G=(V,{E})中，若对任何两个顶点a、b，都存在从a到b的路径，则称G为连通图，有向图中则称为强连通图

网：带权的图称为网

极大连通分量：该图是G的连通子图，将G的任何不在该图中的顶点加入，该图不再连通

极小连通分量：该图是G的连通子图，在该图中删除任何一条边，该图不再连通

连通分量：无向图G的极大连通子图称为G的连通分量，有向图中称为强连通分量

生成树：包含无向图G所有顶点的极小连通子图

生成森林：对非连通树，由各个连通分量的生成树的集合

图的存储结构

邻接矩阵表示法

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

顶点表Vexs用一维数组来表示，邻接矩阵用二维数组arcs表示，定义A.arcs[i][j]，若<i,j>∈E或(i,j)∈E时A.arcs[i][j]=1，否则为0

无向图的邻接矩阵是对称的
无向图顶点i的度等于邻接矩阵中第i行/列中1的个数
有向图顶点i的度等于邻接矩阵中第i行与第i列数字之和，行的元素为出度，列的元素为入度
完全图的邻接矩阵中，对角元素为0，其余为1
网(有权图)的邻接矩阵中每个元素等于该边的权值，无边则用∞表示

存储结构

#define MAX 100chua
typedef struct AMGraph {
    char V[MAX];
    int E[MAX][MAX];
    int Vnum;  // 顶点数
    int Enum;  // 边数
}AMGraph;

创建无向网

void CreateUDN(AMGraph &G) {
    cin >> G.Vnum >> G.Enum;
    for (int i = 0; i < G.Vnum; i++) {
        cin >> G.V[i];
    }
    // 初始化边
    for (int i = 0; i < G.Vnum; i++) {
        for (int j = 0; j < G.Vnum; j++) {
            G.E[i][j] = INT_MAX;
        }
    }
    for (int k = 0; k < G.Enum; k++) {
        char u, v;
        int w;
        cin >> u >> v >> w; // 输入边的两个顶点及其权重
        int i = Search(G, u);  // 查找顶点u在数组中的位置
        int j = Search(G, v);
        G.E[i][j] = w;
        G.E[j][i] = w;
    }
}

若要创建无向图，只需要删掉w的输入，将邻接矩阵的元素赋值为1，初始化赋值为0
若要创建有向网，只需要去掉对相反元素的赋值
有向图则需要同时修改以上两条内容

缺点

不便于增加和删除顶点
浪费空间
浪费时间

邻接表表示法

按编号顺序将顶点数据存储在一维数组中
用线性链表存储该点相关联的边
头结点包含顶点数据，后接表结点
表结点用来接在头结点之后，存储与该顶点相邻接的顶点所对应的数组序号
若无向图中有n个顶点，e条边，则其邻接矩阵需n个头结点和2e个表结点，适合存储稀疏图
有向图中顶点的出度是该单链表的结点个数

存储结构

// 边的结构体
typedef struct ArcNode {
    int adj;  // 该边指向的顶点的位置
    int weight;  // 该边的权重
    ArcNode* next;
}ArcNode;

// 顶点的结构体
#define MVNum 100
typedef struct VNode {
    char data;
    ArcNode* fir;
}VNode,AdjList[MVNum];

// 图的结构体
typedef struct ALGraph{
    AdjList vertices;  // 图的顶点表
    int vexnum;  // 图的顶点数
    int arcnum;  // 图的边数
}ALGraph;

缺点

不方便计算有向图的度
不方便检查任意一对顶点间是否存在边

改进方案

十字链表

邻接表存储有向图时不便于计算度，因此可以设计为十字链表

在顶点结构体中添加第一个入度边的指针域，边的结构体中添加下一个入度边，遍历即可得到入度数量

// 边的结构体
typedef struct ArcNode {
    int in;  // 该边的入度顶点
    int out;  // 该边的出度顶点
    ArcNode* nextin;  // 下一个入度边
    ArcNode* nextout;  // 下一个出度边
}ArcNode;

// 顶点的结构体
#define MVNum 100
typedef struct VNode {
    char data;
    ArcNode* firstout;  // 指向第一个出度边
    ArcNode* firstin;  // 指向第一个入度边
}VNode,AdjList[MVNum];

邻接多重表

邻接表在存储无向图时每条边都要存储两遍，浪费资源，可设计成邻接多重表

在边的结构体中加上边的两个端点及其下一个边的指针域

// 边的结构体
typedef struct ArcNode {
    int mark;  // 标志域，标记次边是否被搜索过，可有可无
    int ivex;  // 该边的顶点i
    ArcNode* nextiedge； // 顶点i的下一个边
    int jvex;  // 该边的顶点j
    ArcNode* nextjedge;  // 顶点j的下一个边
}ArcNode;

// 顶点的结构体
#define MVNum 100
typedef struct VNode {
    char data;
    ArcNode* firstedge;  // 指向第一个边
}VNode,AdjList[MVNum];

图的遍历

从连接图的某一顶点出发，访问图中所有的顶点，且每个顶点只访问一次

深度优先遍历(DFS)

从起点出发，访问它的任一邻接顶点，再访问该顶点的未被访问过的任一邻接顶点，以此循环直至没有邻接顶点未被访问，此时回溯到上一结点，继续访问未被访问过的邻接顶点，重复此步骤，直至回溯到起点且所有结点访问完毕

连通图的深度优先遍历类似于树的先根遍历

邻接矩阵作为结构体

函数传入的值分别为图的结构体，判断是否访问过的不为1的数组，将要访问的第n行代表的顶点
先对该顶点进行访问，并将isVisitied值设置为1
对邻接矩阵的第n行进行遍历，检查是否有相邻的未被访问过的顶点
将该顶点所对应的行数传入函数中，进行递归

用邻接矩阵来表示图，遍历图中每个顶点都要从头扫描所有顶点，因此时间复杂度是O(N^2)

void DFS(AMGraph &G, int isVisited[], int n) {
    isVisited[n] = 1;
    cout << G.V[n] << " ";
    for (int i = 0; i < G.Vnum; i++) {
        if (G.E[n][i] != INT_MAX && isVisited[i] != 1) {
            DFS(G, isVisited, i);
        }
    }
}

邻接表作为结构体

与邻接表的算法基本一致，用p来遍历与该顶点相关的顶点

用邻接表来表示图，只需要扫描E个结点即可完成遍历，在加上访问N个头结点的时间，因此时间复杂度是O(N + E)

void DFS(ALGraph &G, int isVisited[], int n) {
    isVisited[n] = 1;
    cout << G.vertices[n].data << " ";
    ArcNode* p = G.vertices[n].fir;
    while (p) {
        if (isVisited[p->adj] != 1) {
            DFS(G, isVisited, p->adj);
        }
    }
}

广度优先搜索(BFS)

从起点出发，先依次访问与起点相邻的所有结点，在按顺序依次访问与这些结点相邻的未被访问的结点，直至所有结点都被访问

先访问起点并将起点的位置入队，在遍历起点的边，将起点出队并记录下其位置，若与起点相邻的点未被访问，则访问该点并将其入队，以此循环直至队列为空

若用邻接矩阵来表示，则需要对每一行进行遍历，因此时间复杂度为O(N^2)

若用邻接表来表示，只需访问E个结点与N个头结点，时间复杂度为O(N + E)

void BFS(ALGraph &G, int n) {
    int queue[G.vexnum];  // 队列
    int l = 0, r = 0;  // 队列的头和尾
    int isVisited[G.vexnum] = {0};
    queue[r++%G.vexnum] = n;  // 将起点的位置入队
    cout << G.vertices[n].data << " ";  // 输出起点
    isVisited[n] = 1;  // 标记起点为已访问
    while (l != r) {
        int i = queue[l++%G.vexnum];  // 出队的位置
        ArcNode* p = G.vertices[i].fir; 
        while (p) {
            if (isVisited[p->adj] != 1) {  // 如果该顶点未被访问
                cout << G.vertices[p->adj].data << " ";  // 输出该顶点
                isVisited[p->adj] = 1;  // 标记该顶点为已访问
                queue[r++%G.vexnum] = p->adj;  // 将该顶点入队
            }
            p = p->next;  // 指向该顶点的下一个边
        }
    }
}