图：由顶点的有穷非空集合和顶点之间边的集合组成，通常表示为：G(V,E)，其中，G表示一个图，V是图G中顶点的集合，E是图G中边的集合。

基本概念

注意：

线性表中数据元素称为元素，树中称为结点，图中称为顶点。
在图结构中，不允许没有顶点。
在图中，任意两个顶点间都可能有关系，顶点之间的逻辑关系用边来表示，边集可以是空的。

各种图的定义

若顶点vi到vj之间的边没有方向，则称这条边为无向边，用无序偶对(vi,vj)来表示。如果图中任意两个顶点间的边都是无向边，则称该图为无向图。

若顶点vi到vj之间的边有方向，则称这条边为有向边，也称为弧，用有序偶对<vi,vj> 来表示，其中vi称为弧尾，vj称为弧头。如果图中任意两个顶点间的边都是有向边，则称该图为有向图。

简单图：不存在顶点到其自身的边，且同一条边不重复出现。

无向完全图：任意两个顶点之间都存在边。含有n个顶点的无向完全图有n(n-1)/2条边。

有向完全图：任意两个顶点之间都存在方向互为相反的弧。含有n个顶点的有向完全图有n*(n-1)条边。

对于有n个顶点e条边的图，无向图0 <= e <= n(n-1)/2，有向图0 <= e <= n*(n-1)

有很少条边或弧的图称为稀疏图，反之称为稠密图。(相对概念)

有些图的边或弧具有与它相关的数字，这种与图的边或弧相关的数叫做权。这种带权的图通常称为网。

假设有两个图G1 = (V1,{E1})，G2 = (V2,{E2})，如果V2属于V1，E2属于E1，则称G2为G1的子图。

图的顶点与边间的关系

对于无向图G = (V,{E}),如果边(v,v′) ∈E，则称顶点v和v′互为领接点，即v与v′相邻接。边(v,v′)依附于顶点v和v′，或者说(v,v′)与顶点v和v′相关联。顶点v的度是相关联的边的数目，记为TD(v)。

边数即为各顶点度数和的一半。

对于有向图G = (V,{E}),如果弧<v,v′>∈E,则称顶点v邻接到顶点v′，顶点v′邻接自顶点v。弧<v,v′>和顶点v，v′相关联。以顶点v为头的弧的数目称为v的入度，记为ID(v)，顶点v为尾的弧的数目称为v的出度，记为OD(v)。

TD(v) = ID(v) + OD(v)

路径的长度是路径上的边或弧的数目。

第一个顶点和最后一个顶点相同的路径称为回路或环。序列中顶点不重复出现的路径称为简单路径。除了第一个顶点和最后一个顶点之外，其余顶点不重复出现的回路，称为简单回路或简单环。

连通图相关术语

在无向图中，如果从顶点v到顶点v′有路径，则称v和v′是连通的。如果对于图中任意两个顶点vi，vj∈E，vi和vj都是连通的，则称G是连通图。(不一定闭合)

无向图中极大连通子图称为连通分量。注意：

要是子图
子图要是连通的
连通子图含有极大顶点数
具有极大顶点数的连通子图包含依附于这些顶点的所有边

在有向图中，如果对于每一对vi、vj∈V，vi≠vj，从vi到vj和从vj到vi都存在路径，则称G为强连通图。有向图中的极大连通子图称做有向图的强连通分量。

连通图的生成树：一个极小的连通子图，它含有图中全部n个顶点，但只有足以构成一棵树的n-1条边。

如果一个图有n个顶点和小于n-1条边，则是非连通图，如果它多余n-1条边，必定构成一个环，因为这条边使得它依附的那两个顶点之间有了第二条路径。有n-1条边并不一定是生成树。

如果一个有向图恰有一个顶点的入度为0，其余顶点入度均为1，则是一棵有向树。

一个有向图的生成森林由若干棵有向树组成，含有图中全部顶点，但只有足以构成若干棵不相交的有向树的弧。

图的抽象数据类型

mark

图的存储结构

邻接矩阵

用两个数组来表示图，一个一位数组存储图中顶点信息，一个二维数组(称为邻接矩阵)存储图中的边或弧的信息。

无向图的边数组是一个对称矩阵。

mark

第i行(列)的元素之和即为vi的度。

有向图：

mark

第i行各数之和为vi的出度。

第i列各数之和为vi的入度。

网图：

mark

结构代码

typedef char VertexType;//顶点类型
typedef int EdgeType;//边上权值类型
#define MAXVEX 100//最大顶点数
#define INFINITY 65535//用65535来代表∞
typedef struct
{
    VertexType vexs[MAXVEX];//顶点表
    EdgeType arc[MAXVEX][MAXVEX];//邻接矩阵，可看作边表
    int numVertexes,numEdges;//当前顶点数和边数
}MGraph;

创建邻接矩阵

void CreateMGraph (MGraph *G)
{
    int i,j,k,w;
    printf("输入顶点数和边数:\n");
    scanf("%d,%d",&G->numVertexes,&G->numEdges);
    for (i = 0;i < G->numVertexes;i++)//建立顶点表
        scanf("%d",&G->vexs[i]);
    for (i = 0;i < G->numEdges;i++)
        for (j = 0;j < G->numVertexes;j++)
            G->arc[i][j] = INFINITY;//邻接矩阵初始化
    for (k = 0;k < G->numEdges;k++)
    {
        printf("输入边(vi,vj)上的下标i，下标j和权数w：\n");
        scanf("%d,%d,%d",&i,&j,&w);
        G->arc[i][j] = w;
        G->arc[j][i] = G->arc[i][j];//无向图矩阵对称
    }
}

时间复杂度为O(n+n²+e)

对于边数相对顶点较少的图，邻接矩阵对存储空间比较浪费。

邻接表

数组与链表相结合的存储方法。

顶点用一维数组存储，每个数据元素还存储指向第一个邻接点的指针。
每个顶点的所有邻接点构成一个线性表，用单链表存储。(有向图为出边表)

mark

对于有向图还可以建立一个逆邻接表，即入边表：

mark

对于带权值的网图，可以在边表结点中增加一个weight数据域：

mark

结构代码

typedef char VertexType;
typedef int EdgeType;
typedef struct EdgeNode//边表结点
{
    int adjvex;//邻接点域，存储该顶点对应的下标
    EdgeType weight;//用于存储权值
    struct EdgeNode *next;//链域，指向下一个邻接点
}EdgeNode;

typedef struct VertexNode//邻接表结点
{
    VertexType data;
    EdgeNode *firstedge;
}VertexNode,AdjList[MAXVEX];

typedef struct
{
    AdjList adjList;//上机已证实可以这么用
    int numVertexes,numEdges;
}GraphAdjList;

创建邻接表

void CreateALGraph (GraphAdList *G)
{
    int i,j,k;
    EdgeNode *e;
    printf("输入顶点数和边数:\n");
    scanf("%d,%d",&G->numVertexes,&G->numEdges);
    for (i = 0;i < G->numVertexes;i++)
    {
        scanf("%d",&G->adjList[i].data);//输入顶点信息
        G->adjList[i].firstedge = NULL;//将边表置为空表
    }
    for (k = 0;k < G->numEdges;k++)
    {
        printf("输入边(vi,vj)上的下标i，下标j和权数w：\n");
        scanf("%d,%d,%d",&i,&j,&w);
        e = (EdgeNode*)malloc(sizeof(EdgeNode));
        e->adjvex = j;
        e->weight = w;
        e->next = G->adjList[i].firstedge;
        G->adjList[i].firstEdge = e;
        
        e = (EdgeNode*)malloc(sizeof(EdgeNode));
        e->adjvex = i;
        e->weight = w;
        e->next = G->adjList[j].firstedge;
        G->adjList[j].firstEdge = e;
    }
}