小奥的学习笔记

  • Home
  • Learning & Working
    • Speech Enhancement Notes
    • Programming language
    • Computer & DL
    • MOOC
  • Life
    • Life Time
    • Thinking & Comprehension
    • Volunteer
    • Plan
    • Travel
  • Footprints
  • GuestBook
  • About
    • About Me
    • 个人履历
    • 隐私策略
  1. 首页
  2. Study-notes
  3. Computer & DL
  4. Data Structure
  5. 正文

数据结构【浙江大学】(第6节)整理

2018年4月26日 1842点热度 0人点赞 0条评论

第六节:图(上)

6.1 图

1.关于图

图表示的是“多对多”的关系。它包含:

(1)一组顶点:通常用V(Vertex)表示顶点集合。

(2)一组边:通常用E(Edge)表示边的集合,表示顶点与顶点的关系:

①边是顶点对:(v,w)∈E,其中v,w∈V。这是一个双向的。

②有向边:<v,w>,表示从v指向w的边(单行线)。

③不考虑重边和自回路。

其抽象数据类型为:

类型名称:图(Graph)

数据对象集:一非空的顶点集合Vertex和一个边集合Edge,每条边用对应的一对顶点表示。

操作集:对于任意的图G Î Graph,顶点v、v1和v2   Î ertex,以及任一访问顶点的函数visit(),操作举例:

Graph Create( ):构造并返回一个空图;

void Destroy( Graph G ):释放图G占用的存储空间;

Graph InsertVertex( Graph G, Vertex v   ):返回一个在G中增加了新顶点v的图

Graph InsertEdge( Graph G, Vertex v1,   Vertex v2 ):返回一个在G中增加了新边 (v1, v2) 的图;

Graph DeleteVertex( Graph G, Vertex v   ):删除G中顶点v及其相关边,将结果图返回;

Graph DFS( Graph   G, Vertex v, visit()):在图G中,从顶点v出发进行深度优先遍历;

图的一些分类:

(1)无向图。边(v, w)等同于边(w, v)。用圆括号“()”表示无向边。

(2)有向图(Directed Graphs): 边<v, w>不同于边<w, v>。用尖括号“< >”表示有向边;有向边也称“弧(Arc)”。

(3)简单图(Simple Graphs):没有重边和自回路的图。

(4)邻接点: 如果(v, w)或 < v, w >是图中任意一条边,那么称v和w互为“邻接点(Adjacent Vertices)”。

(5)路径、简单路径、回路、无环图:

图G中从vp 到 vq 的路径 = { vp, vi1, vi2, ×××, vin, vq } 使得( vp, vi1 ), ( vi1, vi2 ), ×××, ( vin, vq ) 或 < vp, vi1 >, ×××, < vin, vq > 都属于E( G )。

路径长度:路径中边的数量。

简单路径:vi1, vi2, ×××, vin 都是不同顶点。

回路:起点和终点相同(vp = vq )的路径。

无环图:不存在任何回路的图。

有向无环图:不存在回路的有向图,也称DAG(Directed Acyclic Graph)。

(6)完全图:分为有向完全图(n(n-1)条边)和无向完全图(n(n-1)/2条边)。

(7)度:与顶点v相关的边数。从该点发出的边数为“出度”,指向该点的边数为“入度”。

(8)稠密图、稀疏图:是否满足 |E| > |V|log2|V|,作为稠密图和稀疏图的分界条件。

(9)权(Cost) 、网络(Network)。

(10)图G的子图 G’ : V( G’ ) Í V( G )  &&  E( G’ ) Í E( G )。

(11)无向图的顶点连通、连通图、连通分量:如果无向图从一个顶点vi到另一个顶点vj (i≠j)有路径,则称顶点vi和vj是“连通的(Connected)”;无向图中任意两顶点都是连通的,则称该图是“连通图(Connected Graph)”;无向图的极大连通子图称为“连通分量(Connected Component)”。连通分量的概念包含以下4个要点:子图、连通、极大顶点数、极大边数

(12)有向图的强连通图、连通分量:有向图中任意一对顶点vi 和vj (i≠j)均既有从vi到vj的路径,也有从vj到vi的路径,则称该有向图是“强连通图(Strongly Connected Graph)”。有向图的极大强连通子图称为“强连通分量(Strongly Connected Component)”。连通分量的概念也包含前面4个要点。

(13)树、生成树:树是图的特例:无环的无向图。

所谓连通图G的“生成树(Spanning Tree)”,是G的包含其全部n 个顶点的一个极小连通子图。它必定包含且仅包含G的n-1条边。

生成树有可能不唯一。

当且仅当G满足下面4个条件之一(完全等价):

① G有n-1条边,且没有环;

② G有n-1条边,且是连通的;

③ G中的每一对顶点有且只有一条路径相连;

④ G是连通的,但删除任何一条边就会使它不连通。

2.表示图——邻接矩阵

邻接矩阵G[N][N]-N个顶点从0到N-1编号。其中G[i][j]=1(若<vi,vj>是G中的边)或0(不是G中的边)。可以看出邻接矩阵有以下特点:

(1)主对角线全为0;

(2)这是一个对称矩阵。

那么,对于无向图来说,怎样可以节省一半空间?

可以用一个长度为N(N+1)/2的1维数组A存储{G00,G10,…,G(n-1)0,…,G(n-1)(n-1)}。则Gij在A中对应的下标是:(i*(i+1)/2+j)。对于网络,只要把G[i][j]的值定义为边<vi,vj>的权重即可。

问题:vi和vj在网络中它们之间没有边该如何表示?

邻接矩阵有以下优点:

(1)直观、简单、好理解;

(2)方便检查任意一对顶点间是否存在边;

(3)方便找任一顶点的所有“邻接点”(有边直接相连的顶点);

(4)方便计算任一顶点的“度”:

对于无向图来说,对应行(列)非0的元素的个数。对于有向图来说,对应行非0元素的个数是“出度”,对应列非0元素的个数是“入度”。

邻接矩阵的缺点:

(1)浪费空间:存稀疏图有大量无效元素。但是对于稠密图(特别是完全图)还是很合算。

(2)浪费时间:统计系数图中一共有多少条边。

3.表示图——邻接表

邻接表:G[N]为指针数组,对应矩阵每行一个链表,只存非0元素。对于图G中的每个顶点vi,将所有邻接于vi的顶点vj链成一个单链表,这个单链表就称为顶点vi的邻接表,再将所有点的邻接表表头放到一个数组中,就构成了图的邻接表。

一定要够稀疏用邻接表才合算!!!!

邻接表的特点:

(1)方便找任一顶点的所有“邻接点”。

(2)节约稀疏图的空间:需要N个头指针+2E个结点。

(3)方便计算任一顶点的“度”:对于无向图来说是如此,对于有向图来说,这只能计算“出度”;需要构造“逆邻接表”(存指向自己的边)来方便计算“入度”。

6.2 图的遍历

1.深度优先搜索(DFS)

代码实现:

void DFS( Graph G,  int V )
{ /* 从第V个顶点出发递归地深度优先遍历图G */
    VertexType W;
      Visited[V] = TRUE;
    VisitFunc(V);      /* 访问第V个顶点 */
    for( W = FirstAdjV(G, V);  W;  W = NextAdjV (G, V, W) )
        if( !Visited[W] )
           DFS(G, W); /* 对V的尚未访问的邻接顶点W递归调用DFS */
}

    这段代码的意思是,首先我们开始访问,然后每访问一个节点,都将其标记为True,然后开始访问V的邻接点,如果没访问,那就去访问并且置为True,当看到邻接点都是True时,我们原路返回,若发现没访问过的邻接点,立即去访问;如果没有发现,继续原路返回,直到返回到第一个结点。

若由N个顶点,E跳边,时间复杂度是:

(1)用邻接表存储图:O(N+E);

(2)用邻接矩阵,有O(N2)。

2.广度优先搜索(BFS)

相当于层序遍历。

void BFS(Graph G)
{   /* 按广度优先遍历图G。使用辅助队列Q和访问标志数组Visited */
        Queue *Q;    VertexType U, V, W;
        for ( U = 0; U < G.n; ++U )  Visited[U] = FALSE;
        Q = CreatQueue( MaxSize ); /* 创建空队列Q */
        for ( U = 0; U<G.n; ++U )
         if (!Visited[U] ) {           /* 若U尚未访问 */
                 Visited[U] = TRUE;
                          VisitFunc(U);        /* 访问U */
                 AddQ (Q, U);        /* U入队列 */
                 while ( ! IsEmptyQ(Q) ) {
                     V = DeleteQ( Q );  /*  队头元素出队并置为V */
                     for( W = FirstAdjV(G, V);  W;  W = NextAdjV(G, V, W) )
                         if ( !Visited[W] ) {
                  Visited[W] = TRUE;
                                      VisitFunc (W);      /* 访问W */
                             AddQ (Q, W);
              }
                  } /* while结束*/
                  } /* 结束从U开始的BFS */
}

若由N个顶点,E跳边,时间复杂度是:

(1)用邻接表存储图:O(N+E);

(2)用邻接矩阵,有O(N2)。

6.3 图的应用

1.应用实例:拯救007

如图1所示,如何让007通过这一个个结点(鳄鱼),一步一步跳到岸边呢?这里用深度优先算法更为合适。

原来的总体算法(伪代码):

void ListComponents(Graph G)
{
       for(each V in G)
              if(!visited[V]){
                     DFS(V);
              }
}

这里的总体算法(伪代码):

void Save007(Graph G)
{
       for(each V in G)
              if(!visited[V]&& FirstJump(V))/*判断是否踩过这个鳄鱼还有是否能够得着*/
              {
                     answer = DFS(V);
                     if(answer ==YES) break;
              }
              if(answer ==YES) output("YES");
              else output("BYEBYE");
}

DFS部分的伪代码:

int DFS(Vertex V)
{
       visited[V] = True;
       if(IsSafe(V)) answer = YES;
       else{
              for(V的每个邻接点W)
                     if(!visited[W]&& Jump(V,W))
                            /*Jump计算两个鳄鱼之间距离是否小于007最大跳动距离*/
                     {
                            answer=DFS(W);
                            DFS(W);
                     }
       }
       return answer;            
}

6.4 图的建立

1.用邻接矩阵表示图

typedef struct GNode *PtrToGNode;
struct GNode{
       int Nv;/*顶点数*/
       int Ne;/*边数*/
       WeightType G[MaxVertexNum][MaxVertexNum];
       DataType Data[MaxVertexNum];/*存顶点的数据*/
};
typedef PtrToGNode MGraph;/*以邻接矩阵存储的图类型*/

2.初始化图

typedef int Vertex;/*用顶点下标表示顶点,为整型*/
MGraph CreateGraph(int 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] = 0;/*有向图是INFINITY*/
       return Graph;
}

3.插入边

typedef struct ENode *PtrToGNode;
struct ENode
{
       Vertex V1,V2;/*有向边<V1,V2>*/
       WeightType Weight;/*权重*/
};
typedef PtrToGNode Edge;
 
void InsertEdge( MGraph Graph, Edge E)
{
       /*插入边<V1,V2>*/
       Graph->G[E->V1][E->V2]=E->Weight;
       /*无向图*/
       Graph->G[E->V2][E->V1]=E->Weight;
      
}

4.建立图

(1)输入格式:Nv Ne

     V1 V2 Weight

代码如下:

MGraph BuildGraph()
{     
       Edge E;
       MGraph Graph;
       Vertex V;
       int Nv,i;
       scanf("%d",&Nv);
       Graph = CreateGraph(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[MAXN][MAXN],Nv,Ne;
void BuildGraph()
{
       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;/*初始化,有向图为无穷*/
       scanf("%d", &Ne);/*输入有多少个结点*/
       for(i=0;i<Ne;i++)
       {
              scanf("%d %d %d", &v1,&v2,&w);
              /*将边插入*/
              G[v1][v2]=w;
              G[v2][v1]=w;
       }
}

    一气呵成。

5.邻接表表示的图结点的结构

邻接表:G[N]为指针数组,对应矩阵每行一个链表,只存非0元素。

typedef struct GNode *PtrToGNode;
struct GNode{
       int Nv;/*顶点数*/
       int Ne;/*边数*/
       AdjList G;/*邻接表*/
};
typedef PtrToGNode LGraph;
 
typedef struct Vnode{
       PtrToAdjVNode FirstEdge;
       DataType Data;/*存顶点的数据*/
}AdjList[MaxVertexNum];
/*AdjList是邻接表类型*/
 
typedef struct AdjVNode *PtrToAdjVNode;
struct AdjVNode{
       Vertex AdjV;/*邻接点下标*/
       WeightType Weight;
       PtrToAdjVNode Next;/*指向下一个邻接点的指针*/
};

6.邻接表表示的图-建立图

(1)初始化一个由VertexNum个顶点但没有边的图

typedef int Vertex;/*用顶点下标表示顶点,为整型*/
LGraph CreateGraph(int VertexNum)
{
       Vertex V,W;
       LGraph Graph;
      
       Graph = (LGraph)malloc(sizeof(struct GNode));
       Graph->Nv = VertexNum;
       Graph->Ne =0;
       /*每一个顶点跟着的链表都是空的为没有边*/
       for(V=0;V<Graph->Nv;V++)
              Graph->G[V].FirstEdge = NULL;
       return Graph;
}

(2)向LGraph中插入边

void InsertEdge(LGraph Graph, Edge E)
{
       PtrToAdjVNode NewNode;
      
       /*插入边<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;
      
       /*若是无向图,还要插入边<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;
}

(3)完整建立LGraph

LGraph BuildGraph()
{
       LGraph Graph;
/*剩余与邻接矩阵完整版类似*/
}

本作品采用 知识共享署名 4.0 国际许可协议 进行许可
标签: 数据结构
最后更新:2018年4月26日

davidcheung

这个人很懒,什么都没留下

打赏 点赞
< 上一篇
下一篇 >

文章评论

razz evil exclaim smile redface biggrin eek confused idea lol mad twisted rolleyes wink cool arrow neutral cry mrgreen drooling persevering
取消回复

搜索
欢迎关注我的个人公众号
最新 热点 随机
最新 热点 随机
DEEPFILTERNET:一种基于深度滤波的全频带音频低复杂度语音增强框架 奥地利匈牙利九日游旅程 论文阅读之Study of the General Kalman Filter for Echo Cancellation 小奥看房之鸿荣源珈誉府 杭州往返旅途及西溪喜来登和万怡的体验报告 2022年的第一篇碎碎念
奥地利匈牙利九日游旅程论文阅读之Study of the General Kalman Filter for Echo CancellationDEEPFILTERNET:一种基于深度滤波的全频带音频低复杂度语音增强框架
A very interesting View 解析动态规划问题(1) 《ultraman china》第三话新的英雄(下) 小花豆生活第4天:美国大兵&“谢谢” 高一第二次学分认定考试反思 “中国国际航空体育节专题站”正式开启!
标签聚合
Java 生活 python学习 leetcode 高中 鸟哥的linux私房菜 学习 Python 算法 linux
最近评论
davidcheung 发布于 5 个月前(02月09日) The problem has been fixed. May I ask if you can s...
tk88 发布于 5 个月前(02月07日) Hmm is anyone else having problems with the pictur...
cuicui 发布于 9 个月前(10月20日) :wink:
niming 发布于 10 个月前(09月19日) 同级校友,能刷到太巧了
davidcheung 发布于 2 年前(08月16日) 我得找一下我之前整理的word文档看一下,如果找到了我就更新一下这篇文章。
Nolan 发布于 2 年前(07月25日) 您的笔记非常有帮助。贴图不显示了,可以更新一下吗?
davidcheung 发布于 3 年前(06月19日) 到没有看webrtc的代码。现在主要在看我们公司的代码了。。。只是偶尔看一看webrtc的东西。。。
aobai 发布于 3 年前(03月13日) gain_change_hangover_ 应该是每三个block 只能够调整一次,这样保证每帧...
匿名 发布于 5 年前(12月30日) 烫
小奥 发布于 5 年前(12月12日) webRTC里面的NS本身我记得就是在C++里面呀

COPYRIGHT © 2025 小奥的学习笔记. ALL RIGHTS RESERVED.

Theme Kratos Made By Seaton Jiang

陕ICP备19003234号-1

鲁公网安备37120202000100号