(一)图（Graph）

1. 什么是图

表示“多对多”的关系
包含
- 一组顶点：通常用 V(Vertex) 表示顶点集合
- 一组边：通常用E (Edge) 表示边的集合
  - 边是顶点对： ( v , w ) ∈ E (v, w)\in E (v,w)∈E, 其中 v , w ∈ V v, w \in V v,w∈V
  - 有向边 < v , w > <v, w> <v,w>表示 v v v指向 w w w的边（单边线）
  - 不考虑重边和自回路

2. 抽象数据类型定义

类型名称：图（Graph）

数据对象集： G ( V , E ) G(V, E) G(V,E)由一个非空的有限顶点集合 V V V 和一个有限边集合 E E E 组成

操作集：对于任意图 G ∈ G r a p h G\in Graph G∈Graph，以及 v ∈ V , e ∈ E v\in V, e\in E v∈V,e∈E

Graph Create(): 建立并返回空图
Graph InsertVertex (Graph G, Vertex v): 将v插入G
Graph InsetEdge (Graph G, Edge e): 将e插入G
void DFS (Graph G, Vertex v): 从顶点v出发深度优先遍历图
void BFS (Graph G, Vertex v): 从顶点v出发广度优先遍历图
void ShortestPath (Graph G, Vertex v, int Dist[])：

计算图G中顶点v到任意其他顶点的最短距离
void MST (Graph G)：计算图G的最小生成树

3. 常见术语

无向图、有向图、网络…

4. 表示一个图

邻接矩阵

[外链图片转存失败(img-q7FVyJvf-1567356340202)(C:\Users\alway\AppData\Roaming\Typora\typora-user-images\1567340257441.png)]

对于无向图，邻接矩阵是对称矩阵，即可采用只存储下三角来省一半空间。

用一个长度 N ( N + 1 ) / 2 N(N+1)/2 N(N+1)/2 的1维数组A存储 { G 00 , G 10 , G 11 , . . . , G n − 1 , 0 , . . . G n − 1 , n − 1 } \{G_{00}, G_{10}, G_{11},...,G_{n-1,0},...G_{n-1 ,n-1}\} {G00,G10,G11,...,Gn−1,0,...Gn−1,n−1}

G i j G_{ij} Gij在A中对应的下标是： ( i ∗ ( i + 1 ) / 2 + j ) (i*(i+1)/2+j) (i∗(i+1)/2+j)

对于网络，只要把 G [ i ] [ j ] G[i][j] G[i][j]的值定义为边 < v i , v j > <v_i, v_j> <vi,vj>的权重即可，没有边值取-1
优点

直观、简单、好理解
方便检查任一对顶点间是否存在边
方便找任一顶点的所有“邻接点”
方便计算任一顶点的“度”（“入度”与“出度”）

缺点

浪费空间—适合于稠密图
浪费时间—统计稀疏图一共有多少条边

邻接表
[外链图片转存失败(img-3f6oyABG-1567356340203)(C:\Users\alway\AppData\Roaming\Typora\typora-user-images\1567344852820.png)]
优点/缺点
1. 方便找任一顶点的所有“邻接点”
2. 节省稀疏图的存储空间
  - 需要N个头指针+2E个结点（每个结点至少两个域）
3. 计算任一顶点的“度”？
  - 对无向图：方便
  - 对有向图：***只能计算"出度"***，需要构造“逆邻接表”（存指向自己的边）来计算“入度”
4. 检查一对顶点间是否存在边？NO

4. 代码实现

1. 邻接矩阵

/* 图的邻接矩阵表示法 */
 
#define MaxVertexNum 100    /* 最大顶点数设为100 */
#define INFINITY 65535        /* ∞设为双字节无符号整数的最大值65535*/
typedef int Vertex;         /* 用顶点下标表示顶点,为整型 */
typedef int WeightType;        /* 边的权值设为整型 */
typedef char DataType;        /* 顶点存储的数据类型设为字符型 */
 
/* 边的定义 */
typedef struct ENode *PtrToENode;
struct ENode{
    Vertex V1, V2;      /* 有向边<V1, V2> */
    WeightType Weight;  /* 权重 */
};
typedef PtrToENode Edge;
        
/* 图结点的定义 */
typedef struct GNode *PtrToGNode;
struct GNode{
    int Nv;  /* 顶点数 */
    int Ne;  /* 边数   */
    WeightType G[MaxVertexNum][MaxVertexNum]; /* 邻接矩阵 */
    DataType Data[MaxVertexNum];      /* 存顶点的数据 */
    /* 注意：很多情况下，顶点无数据，此时Data[]可以不用出现 */
};
typedef PtrToGNode MGraph; /* 以邻接矩阵存储的图类型 */
 
 
 
MGraph CreateGraph( int VertexNum )
{ /* 初始化一个有VertexNum个顶点但没有边的图 */
    Vertex V, W;
    MGraph Graph;
     
    Graph = (MGraph)malloc(sizeof(struct GNode)); /* 建立图 */
    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] = INFINITY;
             
    return Graph; 
}
        
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 BuildGraph()
{
    MGraph Graph;
    Edge E;
    Vertex V;
    int Nv, i;
     
    scanf("%d", &Nv);   /* 读入顶点个数 */
    Graph = CreateGraph(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->Data[V]));
 
    return Graph;
}

2. 邻接表

/* 图的邻接表表示法 */
 
#define MaxVertexNum 100    /* 最大顶点数设为100 */
typedef int Vertex;         /* 用顶点下标表示顶点,为整型 */
typedef int WeightType;        /* 边的权值设为整型 */
typedef char DataType;        /* 顶点存储的数据类型设为字符型 */
 
/* 边的定义 */
typedef struct ENode *PtrToENode;
struct ENode{
    Vertex V1, V2;      /* 有向边<V1, V2> */
    WeightType Weight;  /* 权重 */
};
typedef PtrToENode Edge;
 
/* 邻接点的定义 */
typedef struct AdjVNode *PtrToAdjVNode; 
struct AdjVNode{
    Vertex AdjV;        /* 邻接点下标 */
    WeightType Weight;  /* 边权重 */
    PtrToAdjVNode Next;    /* 指向下一个邻接点的指针 */
};
 
/* 顶点表头结点的定义 */
typedef struct Vnode{
    PtrToAdjVNode FirstEdge;/* 边表头指针 */
    DataType Data;            /* 存顶点的数据 */
    /* 注意：很多情况下，顶点无数据，此时Data可以不用出现 */
} AdjList[MaxVertexNum];    /* AdjList是邻接表类型 */
 
/* 图结点的定义 */
typedef struct GNode *PtrToGNode;
struct GNode{  
    int Nv;     /* 顶点数 */
    int Ne;     /* 边数   */
    AdjList G;  /* 邻接表 */
};
typedef PtrToGNode LGraph; /* 以邻接表方式存储的图类型 */
 
 
 
LGraph CreateGraph( int VertexNum )
{ /* 初始化一个有VertexNum个顶点但没有边的图 */
    Vertex V;
    LGraph Graph;
     
    Graph = (LGraph)malloc( sizeof(struct GNode) ); /* 建立图 */
    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> */
    /* 为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;
         
    /* 若是无向图，还要插入边 <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 BuildGraph()
{
    LGraph Graph;
    Edge E;
    Vertex V;
    int Nv, i;
     
    scanf("%d", &Nv);   /* 读入顶点个数 */
    Graph = CreateGraph(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;
}

(一)图（Graph）(一)图（Graph）

(一)图（Graph）

1. 什么是图

2. 抽象数据类型定义

3. 常见术语

4. 表示一个图

邻接矩阵

优点

缺点

邻接表

优点/缺点

4. 代码实现

1. 邻接矩阵

2. 邻接表

继续阅读

树的基本概念(定义、基本术语、性质)

GSL--GNU Scientific Library

D5|哈希表，善用数据结构

如何成为一名.net 工程师?

BMP文件结构及图像每行字节计算方法

D. Ehab the Xorcist(构造+思维)

查找算法之二分查找查找算法之二分查找

JAVA高效编程指南

CQ V1.0分词bates(基于双数组tire树)—应该是目前最快的中文分词算法

【数据结构】医院选址

[转]ISUP信令的IAM消息详细内容

笔试面试题目：滑动窗口(二)

交通/城市相关的公开的数据集上学时整理的Xie et al., 2020收集的

数据结构与算法（27）——排序（二）

GitHub连夜封杀！这份阿里 10W 字内部 Java 字面试手册到底有多强？

Linux设备模型（中）之上层容器