数据结构学习笔记之图

作者: 刚刚悟道 | 来源:发表于2016-10-08 19:43 被阅读4475次

概念

图的定义

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

需要注意：

图中数据元素叫做顶点（Vertext）。
在图中，不允许没有顶点。若 V 是图的顶点的集合，那么，V 是非空
有穷集合。
图的任意两个顶点之间都可能有关系，它们的关系用边来表示。边集可
以是空的。

其他概念

无向边

若顶点 $V_i$ 到 $V_j$ 之间的边没有方向，这条边就叫做无向边（Edge）,
用无序偶对 ($V_iV_j$) 来表示。

无向图

如果图中任意两个顶点之间的边都是无向边，则称该图为无项图（Undirected graphs）。

有向边

若从顶点 $V_i$ 到 $V_j$ 的边有方向，则称这条边为有向边，也称为弧 (Arc)。

这条有向边用有序偶 $<V_i,V_j>来表示，$V_j是弧尾(Tail)，$V_j$是弧头(Head)。

有向图

如果图中任意两个顶点之间的边都是有向边，这个图就是有向图。

无向边用小括号 “（）”表示，有向边用尖括号“<>”表示。

简单图

在图中，若不存在顶点到其自身的边，且同一条边不重复出现，这样的图就是简单图。

数据结构_图_简单图

无向完全图

在无向图中，如何任意两点之间都存在边，这个图就是无向完全图。

n 个顶点的无向完全图有 ${n(n-1)} \over 2$ 条边。

有向完全图

在有向图中，如果任意两点之间都存在方向互为相反的两条弧，这个图就是有向完全图。

n个顶点的有向完全图有 $n(n-1) \over 2$ 条边。

稠密图和稀疏图

边或弧很少的图是稀疏图；边或弧很多的图是稠密图。

它们都是相对概念。

权、网

与图的边或弧相关的数字叫做权（Weight）。

权可以表示一个顶点到另一个顶点的距离或耗费。

带权的图叫做网（Network）。

子图

假设有两个图 $G = (V,\lbrace E \rbrace)$，$G' = (V',\lbrace E' \rbrace)$，$V' \subseteq V$，$E' \subseteq E$，那么，
G' 是 G 的子图。

图的顶点与边间的关系（暂时不做笔记，有空再补充）

概念太多，记录太麻烦，暂时不做笔记，有空再补充。

连通图

图7-2-13图2根据定义，我认为它不是强连通图。

数据结构_图_连通图

数据结构_图_连通图_2

数据结构_图_连通图_3

数据结构_图_连通图_4

生成树

不理解。

数据结构_图_生成树_1

数据结构_图_生成树_2

有向树

不理解。

数据结构_图_有向树_1

数据结构_图_有向树_2

图的抽象数据类型

ADT 图(Graph)

Data
    顶点的有穷非空集合和边的集合
    
Operation
    CreateGraph(*G, V, VR)：按照顶点集 V 和 边弧集 VR 的定义构造图 G。
    DestroyGraph(*G)：图G存在则销毁它。
    LocateVex(G, u)：若图 G 中存在顶点 u，则返回它在图中的位置。
    GetVex(G, v)：返回图 G 中顶点 v 的值。
    PutVex(G, v, value)：将图 G 中顶点 v 赋值 value。
    FirstAdjVex(G, *v)：返回顶点 v 的一个邻接顶点，若顶点在 G 中无邻接顶点则返回空。
    NextAdjVex(G, v, *w)：返回顶点 v 相对于顶点 w 的下一个邻接顶点，若 w 是 v 的最后
                          一个邻接点则返回“空”。
    InsertVex(*G, v)：在图 G 中增添新顶点 v。
    DeleteVex(*G, v): 删除图  G 中顶点 v 及其相关的弧。
    InsertArc(*G, v, w)：在图中增添弧 <v,w>，若 G 是无向图，还要增加对称弧 <w,v>。
    DeleteArc(*G, v, w)：在图中删除弧 <v,w>，若 G 是无向图，还需要删除对称弧 <w,v>。
    DFSTraverse(G)：对图 G 深度优先遍历，在遍历过程中对每个顶点调用。
    HFSTraverse(G):对图 G 广度优先遍历，在遍历过程中对每个顶点调用。
endADT

图的存储结构（难理解）

邻接矩阵

定义

图的邻接矩阵（Adjacency Matrix）存储方式是用两个数组表示图。一个一维数组存储图中顶点信息，一个
二维数组（称为邻接矩阵）存储图中的边或弧信息。

数据结构_图_邻接矩阵_定义

无向图实例

数据结构_图_邻接矩阵_解释

有向图实例

数据结构_图_邻接矩阵_有向图

网图

数据结构_图_邻接矩阵_网图定义

数据结构_图_邻接矩阵_网图

邻接矩阵存储结构

邻接矩阵存储结构代码：

备注：用65536代替 $\infty$

typedef char VertexType;
typedef int EdgeType;
#define MAXVEX 100;     // 最大顶点数
#define INFINITY 65535;  
typedef struct
{
    VertexType vexs[MAXVEX];    // 顶点表
    EdgeType arc[MAXVEX][MAXVEX];   // 邻接矩阵，可看作边表
    int numVertexes, numEdges;  // 图中当前顶点数和边数
}MGraph;

创建无向网图代码：

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

邻接表

概念

定义

数组与链表相结合的方法称为邻接表（Adjacency List）。

思路

图中顶点用一个一维数组存储。该数组存储两部分内容：顶点信息和指针。
该指针指向该顶点的第一个邻接点。
图中的每个顶点 $v_i$ 的所有邻接点构成一个线性表，用单链表存储。
这个线性表可能叫边表，也可能叫 出边表。

当图为无向图的时候，这个线性表叫做顶点 $v_i$ 的边表。

当图为有向图的时候，这个线性表叫做顶点 $v_i$ 作为弧尾的出边表。

摘抄书本

无向图的邻接表结构

数据结构_图_邻接表_无向图的邻接表结构

$v_0$ 的邻接点是 $v_1，v_2，v_3$，$v_0$的 firstEdge 存储的指针指向它的第一个邻接点 $v_1$。
$v_1$ 的 adjvex 存储的是该顶点在顶点表中的下标，next 存储的指针指向 $v_0$ 的第二个邻接点 $v_2$。

有向图的邻接表结构

数据结构_图_邻接表_有向图的邻接表结构_1

数据结构_图_邻接表_有向图的邻接表结构_2

网图的邻接表结构

数据结构_图_邻接表_网图

邻接表存储结构（看不懂）

结点定义代码

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;

边表结点 EdgeNode 为什么如此定义？

无向图的邻接表创建代码

void CreateALGraph(GraphAdjList *G)
{
    int i, j, k;
    EdgeNode *e;
    printf("输入顶点数和边数：\n");
    scanf("%d, %d", &G->numVertexes, &G->numEdges);     // 输入顶点数和边数 
    
    for(i = 0; i < G->numVertexes; i++){
        scanf(&G->adjList[i].data);     // 输入顶点信息。这种写法，有问题吗？
        G->adjList[i].firstEdge = NULL;     // 将边表置为空表。为什么？
    }
    
    for(k = 0; k < G->numVertexes; i++){    // 建立边表
        printf("输入边(Vi,Vj)上的顶点序号：\n");
        scanf("%d, %d", &i, &j);    // 输入边(Vi,Vj)上的顶点序号
        e = (EdgeNode *)malloc(sizeof(EdgeNode));       // 申请内存空间，创建边表结点
        e->adjvex = j;      // 邻接序号为j
        e->next = G->adjList[i].firstEdge;  // 将e指针指向当前顶点指向的结点 ？
        G->adjList[i].firstEdge = e;    // 将当前顶点的指针指向e
        e = (EdgeNode *)malloc(sizeof(EdgeNode));   // 申请内存空间，创建边表结点
        e->adjvex = i;  // 邻接序号为i
        e->next = G->adjList[j].firstEdge;  // 将e指针指向当前顶点指向的结点
        G->adjList[j].firstEdge = e;    // 将当前顶点的指针指向e
    }
}

十字链表（看不懂）

摘抄

数据结构_图_十字链表_1

数据结构_图_十字链表_2

数据结构_图_十字链表_3

数据结构_图_十字链表_4

邻接多重表（看不懂）

摘抄

数据结构_图_邻接多重表_1

数据结构_图_邻接多重表_2

数据结构_图_邻接多重表_3

数据结构_图_邻接多重表_4

数据结构_图_邻接多重表_5

边集数组

摘抄

数据结构_图_边集数组_1

数据结构_图_边集数组_2

图的遍历

定义

从图中某一个顶点出发遍访图的其余所有顶点，且使所有顶点被访问且只访问一次。
这个过程，就叫做图的遍历（Traversing Graph）。

深度优先遍历(Depth_First_Search)

摘抄

数据结构_图_深度优先遍历_摘抄_1

虚线表示已经遍历过的点，实线表示未遍历过的点。

数据结构_图_深度优先遍历_摘抄_2

数据结构_图_深度优先遍历_摘抄_3

代码

邻接矩阵代码

typedef int Boolean;    // Boolean是布尔类型，其值是TRUE或FALSE
Boolean visited[MAX];   // 访问标志的数组

void DFS(MGraph G, int i)
{
    int j;
    visited[i] = TRUE;
    printf("%c", G.vexs[i]);
    
    /*2*/for(j = 0; j < G.numVertexes; j++){
        /*1*/if(G.arc[i][j] == 1 && !visited[j] ){
            DFS(G, j);  // 对未访问的顶点递归调用
        }
    }
}

void DFSTraverse(MGraph G)
{
    int i;
    
    for(i = 0; i < G.numVertexes; i++){
        visited[i] = FALSE;     // 初始所有顶点状态都是未访问过状态
    }
    
    for(i = 0; i < G.numVertexes; i++){
        if(!visited[i]){
            DFS(G, i);
        }
    }
}

第1行，G.arc[i][j] == 1 表明 $v_iv_j$ 边存在，这是根据邻接图矩阵定义得出的
结果。

第1行，visited[j] 不能理解这句。

第2行的循环里面的递归，什么时候终止？

邻接表代码（不懂）

void DFS(GraphAdjList GL, int i)
{
    EdgeNode *p;
    visited[i] = TRUE;
    printf("%c", GL->adjList[i].data);
    p = GL->adjList[i].firstEdge;
    while(p){
        if(!visited[p->adjvex]){
            DFS(GL, p->adjvex);
        }
        p = p->next;
    }
}

void DFSTraverse(GraphAdjList GL)
{
    int i;
    for(i = 0; i < GL->numVertexes; i++){
        visited[i] = FALSE;
    }
    for(i = 0; i < GL->numVertexes; i++){
        if(!visited[i]){
            DFS(GL, i);
        }
    }
}

广度优先遍历(Breadth_First_Search)

摘抄

数据结构_图_广度优先遍历_摘抄_1

数据结构_图_广度优先遍历_摘抄_2

不明白如何得到这张图。

代码

邻接矩阵代码（不懂）

void BFSTraverse(MGraph G)
{
    int i, j;
    Queue Q;
    for(i = 0; i < G.numVertexes; i++){
        visited[i] = FALSE;
    }
    InitQueue(&Q);  // 初始化一个辅助用的队列
    for(i = 0; i < G.numVertexes; i++){     // 对每一个顶点做循环
        if(!visited[i]){
            visited[i] = TRUE;
            printf("%c", G.vexs[i]);
            EnQueue(&Q, i);     // 将此顶点入队列
            while(!QueueEmpty(Q)){
                DeQueue(&Q, &i);    // 将队列中元素出队列，赋值给i
                for(j = 0; j < G.numVertexes; j++){
                    if(G.arc[i][j] == 1 && !visited[j]){
                        visited[j] = TRUE;
                        printf("%c", G.vexs[j]);
                        EnQueue(&Q, j);
                    }
                }
            }
        }
    }
}

邻接表代码（不懂）

void BFSTraverse(GraphAdjList GL)
{
    int i;
    EdgeNode *p;
    Queue Q;
    for(i = 0; i < GL->numVertexes; i++){
        visited[i] = FALSE;
    }
    InitQueue(&Q);
    for(i = 0; i < GL->numVertexes; i++){
        if(!visited[i]){
            visited[i] = TRUE;
            printf("%c", GL->adjList[i].data);
            EnQueue(&Q, i);
            while(!QueueEmpty(Q)){
                DeQueue(&Q, &i);
                p = GL->adjList[i].firstEdge;   // 找到当前顶点边表链表头指针
                while(p){
                    if(!visited[p->adjvex]){
                        visited[p->adjvex] = TRUE;
                        printf("%c", GL->adjList[p->adjvex].data);
                        EnQueue(&Q, p->adjvex);
                    }
                }
                p = p->next;    // 指针指向下一个邻接点
            }
        }
    }
}

最小生成树

定义（不懂）

把构造连通网的最小代价生成树称为最小生成树（Minimum Cost Spanning Tree）。

普里姆(Prim)算法（不懂）

代码

void MiniSpanTree_Prim(MGraph G)
{
    int min, i, j, k;
    int adjvex[MAXVEX];     // 保存相关顶点下标
    int lowcost[MAXVEX];    // 保存相关顶点间边的权值
    // 初始化第一个权值为0，即v0加入生成树
    // lowcost的值为0，在这里就是此下标的顶点已经加入生成树
    lowcost[0] = 0;     
    adjvex[0] = 0;  // 初始化第一个顶点下标为0
    for(i = 1; i < G.numVertexes; i++){
        lowcost[i] = G.arc[0][i];   // 将v0顶点与之有边的权值存入数组
        adjvex[i] = 0;  // 初始化都为v0的下标
    }
    for(i = 1; i < G.numVertexes; i++){
        min = INFINITY; //  初始化最小权值为 INFINITY
        j = 1; k = 0;
        while(j < G.numVertexes){
            if(lowcost[j] != 0 && lowcost[j] < min){
                min = lowcost[j];   // 让当前权值成为最小值
                k = j;      // 将当前最小值的下标存入k
            }
            j++;
        }
        printf("(%d, %d)", adjvex[k], k);   //打印当前顶点边中权值最小的边
        lowcost[k] = 0;     // 将当前顶点的权值设置为0，表示此顶点已经完成任务
        for(j = 1; j < G.numVertexes; j++){
            if(lowcost[j] != 0 && G.arc[k][j] < lowcost[j]){
                lowcost[j] = G.arc[k][j];   // 将较小权值存入lowcost
                adjvex[j] = k;      // 将下标为k的顶点存入adjvex
            }
        }
    }
}

代码解释

数据结构_图_普里姆算法_代码解释_8

数据结构_图_普里姆算法_代码解释_1

数据结构_图_普里姆算法_代码解释_2

数据结构_图_普里姆算法_代码解释_3

数据结构_图_普里姆算法_代码解释_4

数据结构_图_普里姆算法_代码解释_5

数据结构_图_普里姆算法_代码解释_6

数据结构_图_普里姆算法_代码解释_7

克鲁斯卡尔（Kruskal）算法

代码

typedef struct 
{
    int begin;
    int end;
    int weight;
}Edge;

void MiniSpanTree_Kruskal(MGraph G)
{
    int i, n, m;
    Edge edges[MAXEDGE];    // 定义边集数组
    int parent[MAXVEX];     // 定义一数组用来判断边与边是否形成环路
    for(i = 0; i < G.numVertexes; i++){
        parent[i] = 0;      // 初始化数组值为0
    }
    for(i = 0; i < G.numVertexes; i++){
        n = Find(parent, edges[i].begin);
        m = Find(parent, edges[i].end);
        if(n != m){     // 假如n与m不等，说明此边没有与现有生成树形成环路
            // 将此边的结尾顶点放入下标为起点的parent中
            // 表示此顶点已经在生成树集合中
            parent[n] = m;      
            printf("(%d, %d) %d", edges[i].begin, edges[i].end, edges[i].weight);
        }
    }
}

int Find(int *parent, int f)    // 查找连线顶点的尾部下标
{
    while(parent[f] > 0){
        f = parent[f];
    }
    
    return f;
}

代码解释

数据结构_图_克鲁斯卡尔算法_代码解释_1

数据结构_图_克鲁斯卡尔算法_代码解释_2

数据结构_图_克鲁斯卡尔算法_代码解释_3

数据结构_图_克鲁斯卡尔算法_代码解释_4

数据结构_图_克鲁斯卡尔算法_代码解释_5

数据结构_图_克鲁斯卡尔算法_代码解释_6

数据结构_图_克鲁斯卡尔算法_代码解释_7

数据结构_图_克鲁斯卡尔算法_代码解释_8

数据结构_图_克鲁斯卡尔算法_代码解释_9

数据结构_图_克鲁斯卡尔算法_代码解释_10

数据结构_图_克鲁斯卡尔算法_代码解释_11

数据结构_图_克鲁斯卡尔算法_代码解释_12

最短路径（看不懂）

暂时放弃

定义

非网图的最短路径，是指两顶点之间经过的边数最少的路径。

网图的最短路径，是指两顶点之间经过的边上的权值之和最小的路径。
路径上的第一个源点，最后一个顶点是终点。

数据结构学习笔记之图

概念

图的定义

其他概念

无向边

无向图

有向边

有向图

简单图

无向完全图

有向完全图

稠密图和稀疏图

权、网

子图

图的顶点与边间的关系（暂时不做笔记，有空再补充）

连通图

连通图

生成树

有向树

图的抽象数据类型

图的存储结构（难理解）

邻接矩阵

定义

无向图实例

有向图实例

网图

邻接矩阵存储结构

邻接表

概念

定义

思路

摘抄书本

无向图的邻接表结构

有向图的邻接表结构

网图的邻接表结构

邻接表存储结构（看不懂）

十字链表（看不懂）

摘抄

邻接多重表（看不懂）

摘抄

边集数组

摘抄

图的遍历

定义

深度优先遍历(Depth_First_Search)

摘抄

代码

邻接矩阵代码

邻接表代码（不懂）

广度优先遍历(Breadth_First_Search)

摘抄

代码

邻接矩阵代码（不懂）

邻接表代码（不懂）

最小生成树

定义（不懂）

普里姆(Prim)算法（不懂）

代码

代码解释

克鲁斯卡尔（Kruskal）算法

代码

代码解释

最短路径（看不懂）

定义

拓扑排序

关键路径

相关文章

网友评论

延伸阅读

深度阅读

栏目导航

热点阅读

每周500字

unity3D技术分享

数据结构和算法分析

Unity教程合集

数据结构