精华内容
下载资源
问答
  • 2019-02-28 09:52:13

    在图论中,连通图基于连通的概念。在一个无向图G 中,若从顶点vi到顶点vj有路径相连(当然从vj到vi也一定有路径),则称vi和vj是连通的。如果 G 是有向图,那么连接vi和vj的路径中所有的边都必须同向。如果图中任意两点都是连通的,那么图被称作连通图。如果此图是有向图,则称为强连通图(注意:需要双向都有路径)。图的连通性是图的基本性质。

                                                                       图1-连通图

    连通分量:无向图G的一个极大连通子图称为G的一个连通分量(或连通分支)。连通图只有一个连通分量,即其自身;非连通的无向图有多个连通分量。

    强连通图:有向图G=(V,E) 中,若对于V中任意两个不同的顶点 x和 y,都存在从x到 y以及从 y到 x的路径,则称 G是强连通图。相应地有强连通分量的概念。强连通图只有一个强连通分量,即是其自身;非强连通的有向图有多个强连分量。

    单向连通图:设G=<V,E>是有向图,如果u->v意味着图G至多包含一条从u到v的简单路径,则图G为单连通图。

    弱连通图:将有向图的所有的有向边替换为无向边,所得到的图称为原图的基图。如果一个有向图的基图是连通图,则有向图是弱连通图。

    /**
    *    实验题目:
    *        求连通图的所有深度优先遍历序列
    *    实验目的:
    *        领会图的深度优先遍历算法
    *    实验内容:
    *        编写程序,假设一个连通图采用邻接表存储,输出它的所有深度优先
    *    遍历序列。
    */

    #include <stdio.h>
    #include <malloc.h>

    #define INF     32767               //定义∞
    #define MAXV    100                 //最大顶点个数

    typedef char InfoType;
    /*-------------------------以下定义邻接矩阵类型---------------------------*/
    typedef struct
    {
        int no;                         //顶点编号
        InfoType info;                  //顶点信息
    }VertexType;                        //顶点类型

    typedef struct
    {
        int edges[MAXV][MAXV];          //邻接矩阵数组(用一个二维数组存放顶点间关系(边或弧)的数据)
        int n;                          //顶点数
        int e;                          //边数
        VertexType vexs[MAXV];          //存放顶点信息(用一个一维数组存放图中所有顶点数据)
    }MatGraph;                          //完整的图邻接矩阵类型

    //邻接表表示法-将每个顶点的邻接点串成一个单链表
    /*-----------以下定义邻接表类型--------------*/
    typedef struct ArcNode
    {
        int adjvex;                     //该边的邻接点编号
        struct ArcNode *nextarc;        //指向下一条边的指针
        int weight;                     //该边的相关信息,如权值(用整型表示)
    }ArcNode;                           //边结点类型

    typedef struct VNode
    {
        InfoType info;                  //顶点其他信息
        int cnt;                        //存放顶点入度,仅用于拓扑排序
        ArcNode *firstarc;              //指向第一条边
    }VNode;                             //邻接表结点类型

    typedef struct
    {
        VNode adjlist[MAXV];            //邻接表头结点数组
        int n;                          //图中顶点数
        int e;                          //图中边数
    }AdjGraph;                          //完整的图邻接表类型

    /*-------------------------邻接矩阵的基本运算算法---------------------------*/
    /*------------由边数组A、顶点数n和边数e创建图的邻接矩阵g--------------------*/
    void CreateMat(MatGraph &g, int A[MAXV][MAXV], int n, int e)
    {
        int i, j;

        g.n = n;
        g.e = e;
        for(i = 0; i < g.n; i++)
            for(j = 0; j < g.n; j++)
                g.edges[i][j] = A[i][j];
    }

    /*------------输出邻接矩阵g--------------------*/
    void DispMat(MatGraph g)
    {
        int i, j;

        for(i = 0; i < g.n; i++)
        {
            for(j = 0; j < g.n; j++)
            {
                if(g.edges[i][j] != INF)
                    printf("%4d", g.edges[i][j]);
                else
                    printf("%4s", "∞");
            }
            printf("\n");
        }
    }

    /*-------------------------邻接表的基本运算算法---------------------------*/
    /*-------------------由边数组A、顶点数n和边数e创建图的邻接表G--------------------*/
    void CreateAdj(AdjGraph *&G, int A[MAXV][MAXV], int n, int e)
    {
        int i, j;
        ArcNode *p;

        G = (AdjGraph *)malloc(sizeof(AdjGraph));
        for(i = 0; i < n; i++)                              //给邻接表中所有头结点的指针域置初值NULL
        {
            G->adjlist[i].firstarc = NULL;
        }

        for(i = 0; i < n; i++)                              //检查邻接矩阵中的每个元素
        {
            for(j = n - 1; j >= 0; j--)
            {
                if(A[i][j] != 0 && A[i][j] != INF)          //存在一条边
                {
                    p = (ArcNode *)malloc(sizeof(ArcNode)); //创建一个结点p
                    p->adjvex = j;                          //邻接点编号
                    p->weight = A[i][j];                    //边的权重
                    p->nextarc = G->adjlist[i].firstarc;    //采用头插法插入结点p
                    G->adjlist[i].firstarc = p;
                }
            }
        }
        G->n = n;
        G->e = e;
    }

    /*-------------------输出邻接表G--------------------*/
    void DispAdj(AdjGraph *G)
    {
        ArcNode *p;

        for(int i = 0; i < G->n; i++)
        {
            p = G->adjlist[i].firstarc;
            printf("%d: ", i);
            while(p != NULL)
            {
                printf("%3d[%d]->", p->adjvex, p->weight);  //邻接点编号[权重]
                p = p->nextarc;
            }
            printf("∧\n");
        }
    }

    /*-------------------销毁图的邻接表G--------------------*/
    void DestroyAdj(AdjGraph *&G)
    {
        ArcNode *pre, *p;

        for(int i = 0; i < G->n; i++)
        {
            pre = G->adjlist[i].firstarc;                   //pre指向第i个单链表的首结点
            if(pre != NULL)
            {
                p = pre->nextarc;
                while(p != NULL)                            //释放第i个单链表的所有边结点
                {
                    free(pre);
                    pre = p;
                    p = p->nextarc;
                }
                free(pre);
            }
        }
        free(G);                                            //释放头结点数组
    }

    int visited[MAXV];                                  //全局数组

    /**
    *   功能:
    *       求图G中从顶点v出发的所有深度优先遍历序列
    *   @param path:记录访问过的顶点序列
    *   @param d:记录访问的顶点数,其初值为0,当d=n时输出path中的访问序列
    *
    */
    void DFSALL(AdjGraph *G, int v, int path[], int d)
    {
        ArcNode *p;

        visited[v] = 1;                                         //置已访问标记
        path[d] = v;
        d++;
        if(d == G->n)                                           //如果已访问所有顶点,则输出访问序列
        {
            for(int k = 0; k < d; k++)
                printf("%3d", path[k]);
            printf("\n");
        }
        p = G->adjlist[v].firstarc;                             //p指向顶点v的第一个相邻点
        while(p != NULL)
        {
            if(visited[p->adjvex] == 0)                         //若p->adjvex顶点未访问,递归访问它
            {
                DFSALL(G, p->adjvex, path, d);
            }
            p = p->nextarc;                                     //找顶点v的下一个相邻点
        }
        visited[v] = 0;
    }


    int main(void)
    {
        AdjGraph *G;
        int n = 5;                                  //图顶点数
        int e = 8;                                  //图边数
        int A[MAXV][MAXV] = {
            {0, 1, 0, 1, 1}, {1, 0, 1, 1, 0},
            {0, 1, 0, 1, 1}, {1, 1, 1, 0, 1},
            {1, 0, 1, 1, 0}
        };

        CreateAdj(G, A, n, e);
        printf("图的邻接表:\n");
        DispAdj(G);
        int path[MAXV];
        int v = 1;
        printf("从顶点%d出发的所有深度优先序列:\n", v);
        DFSALL(G, v, path, 0);
        printf("销毁图的邻接表\n");
        DestroyAdj(G);

        return 0;
    }
    输出结果:

    图G的邻接表:
    0:   1[1]->  3[1]->  4[1]->∧
    1:   0[1]->  2[1]->  3[1]->∧
    2:   1[1]->  3[1]->  4[1]->∧
    3:   0[1]->  1[1]->  2[1]->  4[1]->∧
    4:   0[1]->  2[1]->  3[1]->∧
    从顶点1出发的所有深度优先序列:
      1  0  3  2  4
      1  0  3  4  2
      1  0  4  2  3
      1  0  4  3  2
      1  2  3  0  4
      1  2  3  4  0
      1  2  4  0  3
      1  2  4  3  0
      1  3  0  4  2
      1  3  2  4  0
    销毁图的邻接表

    更多相关内容
  • 数据结构笔记5:

    千次阅读 2020-11-20 12:17:46
    的基本概念 题目 的存储结构: 题目 的遍历 题目 的应用 最小生成树 Prim算法 Kruskal算法 最短路径 Dijkstra ...以下关于的叙述,正确的是(CA.强连通有的任何顶点到其他

    目录

    图的基本概念

    题目

    图的存储结构:

    题目

    图的遍历

    题目

    图的应用

    最小生成树

    Prim算法

    Kruskal算法

    最短路径

    Dijkstra

    Floyd

    拓补排序

    关键路径

    题目


    图的基本概念

    题目

    CSDN新版编辑器真见鬼,这回没加编号,结果项目符号都被转成错的编号了,连图片也粘不上,我等明天有空重新来粘

    1. 2009年计算机联考真题)下列关于无向连通图特性的叙述中,正确的是I
      I所有顶点的度之和为偶数
      边数大于顶点个数减1
      至少有一个顶点的度为1
      I:若图G中任意两个顶点都是连通的(不一定直接相连,可经过中间结点),则称图G为连通图。对于任何一条边来说,连接两个顶点,总度为2。若有n条边,则度之和为2

    Ⅱ:树是连通的,=顶点-1

    Ⅲ:回路所有点度>=2

    1. 以下关于图的叙述中,正确的是(C
      A.强连通有向图的任何顶点到其他所有顶点都有弧
      B.图的任意顶点的入度等于出度
      C.有向完全图一定是强连通有向图
      D.有向图的边集的子集和顶点集的子集可构成原有向图的子图

    A:强连通有向图: 在有向图中,若从顶点x到顶点y和从顶点y到顶点x之间都有路径(路径可以不直接相连,经过中间结点),则称这两个顶点是强连通的。

    C有向完全图任何顶点到其他所有顶点都有弧

    1. 对于一个有n个顶点的图:如果是连通无向图,其边的个数至少为()如果是强连通有向图,其边的个数至少为()A
      A. n-1,n
      D.n,n(n-1)

    连通无向图:树形结构

    强连通有向图:环

    1. 无向图G23条边,度为4的顶点有5,度为3的顶点有4,其余都是度为2的顶点,则图G最多有()个顶点D
      A.11
      D.16

    一条边产生2个度,具有e条边的无向图中,有总度数∑TD(Vi)=2e

    这一部分的计算题主要抓住边与度数(顶点)关系

    图的存储结构:

    题目

    1. 关于图的存储结构,()是错误的
      A.使用邻接矩阵存储一个图时,在不考虑压缩存储的情况下,所占用的存储空间大小只与图中的顶点数有关,与边数无关
      B.邻接表只用于有向图的存储,邻接矩阵适用于有向图和无向图
      C.个有向图的邻接矩阵,对角线以下元紊为0,则该图的拓扑序列必定存在
      D.存储无向图的邻接矩阵是对称的,故只需存储邻接矩阵的下(或上)三角部分即可

    An个顶点的图,邻接矩阵不压缩,存储空间大小为o(n2)
    C:由于邻接矩阵中对角线以下的元素全为0,若存在<i,j>,则必i<j,由传递性可知图中路径的顶点编号是依次递增的,假设存在环k->…->j->k,k<j<k矛盾,不存在环(拓补序列存在的条件)

    1. (2015年计算机联考真题)已知含有5个顶点的图G如下图所示
      1)写出图G的邻接矩阵A(行、列下标从0开始)
      2)A2,矩阵A2中位于03列元素值的含义是什么?
      3)若已知具有n(n2)个顶点的图的邻接矩阵为B,Bm(2≤m≤n)中非零元素的含义是什么?

    Bm(2≤msn)中位于ij(0i,jn-1)的非零元素的含义是:图中从顶点i到顶点j长度为m的路径条数

    A2 为长度为2的路径条数:0-2-30-1-30-4-3

    图的遍历

    题目

    1. 设无向图G=(V,E)G'=(V',E'),如果G'G的生成树,则下列说法中错误的是()B
      A.G'G的子图
      B.G'G的连通分量
      C.G'G的极小连通子图且V=V'
      D.G'G的一个无环子图

    连通分量中包含连通子图的所有边

    1. 分别采用基于深度优先遍历和广度优先遍历算法判别以邻接表方式存储的有向图中是否存在由顶点vi到顶点νj的路径(ij)注意,算法中涉及的图的基本操作必须在此存储结构上实现。

    1.深度搜索

    2.广度搜索(层次)

    1. 写出图的深度优先搜索DFS的非递归算法(图采用邻接表形式)

    在深度优先搜索的非递归算法中使用了一个栈S,记忆下一步可能访问的顶点,同时使用了一个访问标记数组 visited[i], visited[i]中记忆第个顶点是否在栈内或曾经在栈内。若是,以后它不能再进栈。

    1. 试设计一个算法,判断一个无向图G是否为一棵树。若是一棵树,则算法返回true,否则返回false

    采用深度优先搜索算法在遍历图的过程中统计可能访问到的顶点个数和边的条数,如果一次遍历就能访问到n个顶点和n-1条边,则可断定此图是一棵树。

    图的应用

    最小生成树

    Prim算法

    选择最小权值的边,其中一个顶点在结果集中,另一个在结果集外(不回路)

    初始化:向空的结果树T=(VT,ET)中添加图G=NE)的任顶点u0,使VT={u0},ET为空集;

    循环(直到VT=V):从图G中选择满足{(u,v)|uVT,vV-VT}且具有最小权值的边(u,v),并置VT=VT{v}, ET=ET{(u,v)}

    时间复杂度O(|V|2)适合稠密图,边再多也不妨碍时间效率

    Kruskal算法

    初始时结果集就包含所有顶点
    初始化: VT=V,ET=空集。即是每个顶点构成一棵独立的树,T是一个仅含|V|个顶点的森林;循环(直到T为树),按图G的边的权值递增的顺序依次从E- ET中选择1条边,若这条边加入后不构成回路,则将其加入ET,否则舍弃

    用堆排序或并查集挑选边

    通过并查集找根是否相同,判断是否属于同一个连通分量

    传入参数为Edges数组,使用堆排序对边排序,parent为并查集

    ab分别为这条边的两个端点,a_root!=b_root代表两条边属于不同的连通分量,可以加入(奇怪,加入的不是a,b而是root)

    时间复杂度O(|E|log|E|),其中外层for循环为O(|e|),堆排序O(|E|log|E|)

    时间复杂度只与边相关,适合稀疏图

    最短路径

    Dijkstra

    带权图单源(一个起始点)最短路径

    辅助数组

    s[]:标记已经计算完成的顶点。

    初始化:数组中的值全部初始化为0。源点下标的值初始化为1。

    distn :记录从源点v0到其他各顶点当前的最短路径长度。

    数组中的值初始化为源点到各个顶点边的权值,即dist[i]=arcs[0][i];。

    path[]:记录从最短路径中顶点的前驱顶点,即path[i]为v到vi最短路径上vi

    的前驱顶点。

    数组中的值初始化:

    若源点v0到该顶点vi有一有向边(无向边),则另path[i]=0;

    否则path[i]=-1;

    算法

    1)初始化数组,并集合S初始为{0};

    2)从顶点集合V-S中选出vj满足dist[j]=Min{dist[i]| vj∈V-S},

    vj就是当前求得的最短醃径的终点,并另S∪{j};

    3)修改此时从v0出发到集合V-S上任一顶点vk最短路径的长度:

    若 dist[j]+arcs[j][k]<dist[k]

    则令 dis[k]=distfj]+arcs[j][k];      path[k]=j;

    4)重复2)、3)操作n-1次,直到S中包含全部顶点;

    初始化

    挑选最小值并保存其顶点下标

    判断未被标记,且为最小

    时间复杂度O(|V|2)

    不适合负权边

    Floyd

    求出每一对顶点之间的最短路径

    (啊我的脚标格式也被清空了,早知道还不如粘图片)

    递推产生一个n阶方阵序列A-1~An-1

    A(k)[i][j]:顶点vi到vj最短路径长度,且该路径经过的顶点编号不大于k

    原理:动态规划

    #初始:不允许在其他顶点中转,最短路径是? A-1[i][j]=arcs[i][j]

    #递推:k:若允许在 V0、V1、V2 …… Vk 中转,最短路径是?A(k)[i][j] = Min{ A(k-1) [i][j], A(k-1)[i][k]+ A(k-1)[k][j]},k=0,1,…,n-1

    每加入一个顶点,对矩阵中每一个值修改(共三重循环)

    时间复杂度O(|V|3)

    拓补排序

    有向无环图简称DAG图。

    AOV网若用一个DAG图表示一个工程,其顶点表示活动,用有向边< vi, vj >表示活动vi先于活动vj进行的传递关系,则将这种DAG称为顶点表示活动网络,记为AOV网。

    拓补排序对DAG所有顶点的一种排序,使若存在一条从顶点A到顶点B的路径,在排序中B排在A的后面。

    算法思想

    1)    从DAG图中选择一个没有前驱的顶点并输出(入度=0)

    2)    从图中删除该顶点和所有以它为起点的有向边

    3)    重复1)、2)直到当前的DAG图为空或当前图中不存在无前驱的顶点为止。后一种情况说明图中有环。

    拓补排序结果不唯一

    入度为0的顶点不唯一,需要用栈保存

    入度为0的顶点入栈,每出栈一个,遍历边表找到顶点修改入度

    要访问每个顶点,对其边表修改,时间复杂度:时间复杂度O(|V|+|E|)

    若邻接矩阵为三角矩阵,则存在拓扑排序;反之不一定成立。

    关键路径

    AOE (Activity On Edge NetWork)在带权有向图中,以顶点表示事件,以有向边表示活动,以边上的权值表示完成该活动的开销(如 完成活动所需的时间)

    从源点到汇点的有向路径可能有多条,所有路径中,具有最⼤路径⻓度的路径称为关键路径,⽽把关键路径上的活动称为关键活动

    事件vk的最早发时间ve(k)——决定了所有从vk开始的活动能够开⼯的最早时间

    ve(源点) = 0

    ve(k) = Max{ve(j) + Weight(vj, vk)}, vj为vk 的任意前驱

    最迟发时间 vl( )

    按逆拓扑排序序列,依次求各个顶点的 vl(k):

     vl(汇点) = ve(汇点)

    vl(k) = Min{vl(j) - Weight(vk, vj)} , vj为vk的任意后继

    活动ai的最早开始时间e(i)——指该活动弧的起点所表⽰的事件的最早发⽣时间

    若边表⽰活动ai,则有e(i) = ve(k)

    活动的最迟发时间 l( )

    若边表⽰活动ai,则有l(i) = vl(j) - Weight(vk, vj)

    有活动的时间余量 d( )

    d(i) = l(i) - e(i)

    题目

    1. (2012真题)下列关于最小生成树的叙述中,正确的是()
      I.最小生成树的代价唯一
      .所有权值最小的边一定会出现在所有的最小生成树中
      .使用普里姆(Prim)算法从不同顶点开始得到的最小生成树一定相同
      .使用普里姆算法和克鲁斯卡尔( Kruskal)算法得到的最小生成树总不相同
      最小生成树的树形可能不唯一(这是因为可能存在权值相同的边),但是代价一定是唯一的,I正确
      权值最小的边有多条并且构成环状,错误
      N个结点构成环,N-1条边权值相等,从不同的顶点开始prim算法会得到N-1种不同的最小生成树,错误。
      当最小生成树唯一时(各边的权值不同),错误。
    2. (2016真题)若将n个顶点e条弧的有向图采用邻接表存储,则拓扑排序算法的时间复杂度是?O(n+e)
      釆用邻接表作为AOV网的存储结构进行拓扑排序,需要对n个顶点做进栈、出栈、输出各一次,在处理e条边,需要检测这n个顶点的边链表的e个边结点,总共需要的时间代价为o(n+e)

    若采用邻接矩存储AOV网拓扑排序,e条边需要对每一个顶点检测相应矩阵中的某一行,寻找与它相关联的边以便对这些边的入度减1,需要的时间代价为o(n2)

    1. (2017真题)使用Pim(普里姆)算法求带权连通图的最小(代价)生成树(MST)。请回答下列问题
      1)对下列图G,从顶点A开始求GMST,依次给出按算法选出的边。
      2)GMST是唯一的吗?
      3)对任意的带权连通图,满足什么条件时,MST是唯一的?

    1)Prim算法从一个任意的顶点开始,每一步在连接树集合S中顶点和其他顶点的边
    ,选择一条使得树的总权重增加最小的边加入集合S。当算法终止时,S就是最小
    生成树。

    ①s中顶点为A,候选边为(A,D)(A,B)(A,E),选择(A,D)加入S
    ②s中顶点为AD,候选边为(A,B)(A,E)(D,E)(C,D),选择(D,E),加入S
    ③s中顶点为ADE,候选边为(A,B)(C,D)(C,E),选择(C,E)加入S
    ④s中顶点为ADEC,候选边为(A,B)(B,C),选择(B,C)加入S

    2)GMST是唯一的。第一小题的最小生成树包括了图中权值最小的四条边,其他边都比这四条边大,所以此图的MST唯一

    3)当带权连通图所有边的权值均不相同时,MST是唯一的。此题不要求回答充分
    必要条件,所以回答一个限制边权值的充分条件即可

    展开全文
  • 数据结构补——

    2022-03-06 19:17:01
    若V = {v1,v2,…,vn},则用|V|表示G中顶点的个数,也称为G的阶,E = {{u,v} | u∈V,v∈V},用|E|表示G边的条数 注意:线性表可以是空表,树可以是空树,但不可以是空,即V一定是费控集 无向 若...

    图基础

    图的定义

    图G顶点集V边集E组成,记为G = (V,E),其中V(G)表示图G中顶点的有限非空集;E(G)表示图G中顶点之间的关系(边)集合。若V = {v1,v2,…,vn},则用|V|表示图G中顶点的个数,也称为图G的阶,E = {{u,v} | u∈V,v∈V},用|E|表示图G中边的条数
    注意:线性表可以是空表,树可以是空树,但图不可以是空,即V一定是非空集
    在这里插入图片描述

    无向图、有向图

    若E是无向边(简称)的有限集合时,则图G为无向图。边是顶点的无序对,记为(v,w)或(w,v),因为(v,w)=(w,v),其中v、w是顶点。可以说顶点w和顶点v互为邻接点,边(v,w)依附于顶点w和v,或者说边(v,w)和顶点v、w相关联

    若E是有向边(也称)的有限集合时,则图G为有向图。弧是顶点的有序对,记为<v,w>,其中v、w是顶点,v称为弧尾,w称为弧头。<v,w>称为从顶点v到顶点w的弧,也称v邻接到w,或w邻接自v。<v,w> != <w,v>

    简单图、多重图

    在这里插入图片描述

    顶点的度、入度、出度

    在这里插入图片描述

    顶点-顶点的关系描述

    在这里插入图片描述

    连通图、强连通图

    在这里插入图片描述
    连通图最少有n-1条边是因为n个节点两两相连
    非连通图最多有的情况是当其他n-1个节点两两相连,而最后一个节点一个都不连

    子图

    在这里插入图片描述
    生成子图是拥有原图所有点的子图

    连通分量

    用于描述无向图
    在这里插入图片描述

    强连通分量

    用于描述有向图
    在这里插入图片描述

    生成树

    n个顶点有n-1条边,再多就会形成回路
    在这里插入图片描述

    生成森林

    在这里插入图片描述

    边的权、带权图/网

    在这里插入图片描述

    几种特殊形态的图

    在这里插入图片描述

    在这里插入图片描述
    在这里插入图片描述

    图的存储结构

    • 邻接矩阵:数组实现的顺序存储,空间复杂度高O(n²),不适合存储稀疏图
    • 邻接表:找有向图的入度不方便,删除顶点、删除边的时间复杂度高
    • 十字链表:存储有向图
    • 邻接多重表:存储无向图

    邻接矩阵法

    在这里插入图片描述
    在这里插入图片描述

    如何求顶点的度、入度、出度

    在这里插入图片描述
    带权图:
    在这里插入图片描述

    性能分析

    在这里插入图片描述
    在这里插入图片描述

    邻接矩阵的性质

    行*列
    在这里插入图片描述

    邻接表

    在这里插入图片描述
    在这里插入图片描述
    在这里插入图片描述
    在这里插入图片描述

    十字链表法

    只能用于有向图
    在这里插入图片描述

    性能分析

    在这里插入图片描述

    邻接多重表

    只用于存储无向图
    在这里插入图片描述

    总结

    在这里插入图片描述

    图的操作

    在这里插入图片描述

    判断图中是否有某条边

    无向图:
    在这里插入图片描述
    有向图:
    在这里插入图片描述

    列出图中与结点邻接的所有边

    无向图:
    在这里插入图片描述
    有向图:
    在这里插入图片描述

    在图中插入顶点

    在这里插入图片描述

    在图中删除顶点

    无向图:
    在这里插入图片描述
    有向图:
    在这里插入图片描述

    向图中添加一条边

    在这里插入图片描述

    求图中顶点x的第一个邻接点

    无向图:
    在这里插入图片描述
    有向图:
    在这里插入图片描述

    假设图中顶点x的一个邻接点y,返回除y之外顶点x 的下一个邻接点的顶点号,若y是x的最后一个邻接点,则返回-1

    无向图:
    在这里插入图片描述

    获取并设置图中边的权值

    在这里插入图片描述

    图的遍历

    • 广度优先遍历
    • 深度优先遍历

    广度优先遍历

    在这里插入图片描述

    代码实现

    在这里插入图片描述

    遍历序列的可变性

    在这里插入图片描述

    算法改进

    因为如果是非连通图,则无法遍历完所有结点
    在这里插入图片描述

    复杂度分析

    在这里插入图片描述

    广度优先生成树

    在这里插入图片描述

    广度优先生成森林

    在这里插入图片描述

    练习

    在这里插入图片描述

    深度优先遍历

    在这里插入图片描述

    算法改进

    在这里插入图片描述

    复杂度分析

    空间复杂度:
    在这里插入图片描述
    时间复杂度:
    在这里插入图片描述

    深度优先生成树

    在这里插入图片描述

    深度优先生成森林

    在这里插入图片描述

    图的遍历和图的连通性

    无向图:
    在这里插入图片描述
    有向图:
    在这里插入图片描述

    总结

    在这里插入图片描述

    图的最小生成树(MST)

    概念

    在这里插入图片描述
    在这里插入图片描述

    Prim算法(普里姆)

    在这里插入图片描述

    Kruskal算法(克鲁斯卡尔)

    在这里插入图片描述

    两种算法对比

    在这里插入图片描述

    Prim算法的实现思想

    在这里插入图片描述

    Kruskal算法的实现思想

    在这里插入图片描述
    在这里插入图片描述

    图的最短路径问题

    在这里插入图片描述

    BFS求无权图的单源最短路径

    BFS实际上的结果就是单源最短路径
    缺点:只能用于不带权的图

    代码实现

    在这里插入图片描述

    在这里插入图片描述

    Dijkstra(迪杰斯特拉)算法

    在这里插入图片描述

    步骤

    • 初始:
      在这里插入图片描述
    • 第一轮:
      在这里插入图片描述
    • 第二轮:
      在这里插入图片描述
    • 第三轮:
      在这里插入图片描述
    • 第四轮:
      在这里插入图片描述

    如何使用数组信息

    在这里插入图片描述

    时间复杂度

    在这里插入图片描述

    对比Prim算法的实现思想

    在这里插入图片描述

    用于负权值带权图

    在这里插入图片描述

    Floyd算法

    在这里插入图片描述
    在这里插入图片描述

    步骤

    在这里插入图片描述
    在这里插入图片描述
    在这里插入图片描述
    在这里插入图片描述
    在这里插入图片描述

    在这里插入图片描述

    在这里插入图片描述

    练习

    在这里插入图片描述

    不能解决的问题

    在这里插入图片描述

    总结

    在这里插入图片描述

    有向无环图描述表达式

    在这里插入图片描述
    在这里插入图片描述
    在这里插入图片描述
    在这里插入图片描述
    在这里插入图片描述

    拓扑排序

    AOV网

    在这里插入图片描述

    概念

    在这里插入图片描述
    在这里插入图片描述
    在这里插入图片描述

    代码实现

    在这里插入图片描述
    在这里插入图片描述
    在这里插入图片描述

    逆拓扑排序

    在这里插入图片描述
    在这里插入图片描述
    在这里插入图片描述

    关键路径

    AOE网

    在这里插入图片描述
    在这里插入图片描述

    概念

    在这里插入图片描述
    在这里插入图片描述

    在这里插入图片描述
    在这里插入图片描述
    在这里插入图片描述

    求所有事件的最早发生时间

    在这里插入图片描述

    求所有事件的最迟发生时间

    在这里插入图片描述

    求所有活动的最早发生时间

    在这里插入图片描述

    求所有活动的最迟发生时间

    在这里插入图片描述

    求所有活动的时间余量

    在这里插入图片描述

    求得关键活动、关键路径

    在这里插入图片描述

    关键活动、关键路径的特性

    在这里插入图片描述
    在这里插入图片描述

    展开全文
  • (单选题)已知的邻接矩阵为:A A. V1V2V4V6V8V10V9V7V5V3 B. V1V2V3V4V5V6V7V8V9V10 C. V1V3V2V4V5V7V6V9V8V10 D. V1V2V5V3V4V9VV6V8V10V7 (单选题)已知的邻接矩阵为: A. V1V2V3V4V5V6V7V9V8V10 B. V1V2V3...

    一. 单选题

    1. (单选题)已知图的邻接矩阵为:A
      在这里插入图片描述

    A. V1V2V4V6V8V10V9V7V5V3
    B. V1V2V3V4V5V6V7V8V9V10
    C. V1V3V2V4V5V7V6V9V8V10
    D. V1V2V5V3V4V9VV6V8V10V7

    1. (单选题)已知图的邻接矩阵为:
      在这里插入图片描述

    A. V1V2V3V4V5V6V7V9V8V10
    B. V1V2V3V4V5V6V7V8V9V10
    C. V1V2V4V6V8V10V9V7V5V3
    D. V1V3V5V7V9V2V4V6V8V10

    1. (单选题)任何一个带权的无向连通图的最小生成树( B)
      A. 只有一棵
      B. 有一棵或多棵
      C. 一定有多棵
      D. 可能不存在

    2. (单选题)以下说法正确的是(B )
      A. 连通分量是无向图中的极小连通子图。
      B. 强连通分量是有向图中的极大强连通子图。
      C. 在一个有向图的拓扑序列中,若顶点a在顶点b之前,则图中必有一条弧<a,b>。
      D. 对有向图G,如果从任意顶点出发进行一次深度优先或广度优先搜索能访问到每个顶点,则该图一定是完全图。

    3. (单选题)图中有关路径的定义是(A )。
      A. 由顶点和相邻顶点序偶构成的边所形成的序列
      B. 由不同顶点所形成的序列
      C. 由不同边所形成的序列
      D. 上述定义都不是

    4. (单选题)设无向图的顶点个数为n,则该图最多有(B )条边。
      A. n-1
      B. n(n-1)/2
      C. n(n+1)/2
      D. 0
      E. n2

    5. (单选题)要连通具有n个顶点的有向图,至少需要( B)条边。
      A. n-l
      B. n
      C. n+l
      D. 2n

    6. (单选题)在一个有向图中,所有顶点的入度之和等于所有顶点出度之和的( C )倍。
      A. 1/2
      B. 2
      C. 1
      D. 4

    7. (单选题)下列哪一种图的邻接矩阵是对称矩阵?(B )
      A. 有向图
      B. 无向图
      C. AOV网
      D. AOE网

    8. (单选题)下列说法不正确的是(C )。
      A. 图的遍历是从给定的源点出发每一个顶点仅被访问一次
      B. 遍历的基本算法有两种:深度遍历和广度遍历
      C. 图的深度遍历不适用于有向图
      D. 图的深度遍历是一个递归过程

    9. (单选题)下面哪一方法可以判断出一个有向图是否有环(回路): (B )
      A. 深度优先遍历
      B. 拓扑排序
      C. 求最短路径
      D. 求关键路径

    10. (单选题)在有向图G的拓扑序列中,若顶点Vi在顶点Vj之前,则下列情形不可能出现的是(D )。
      A. G中有弧<Vi,Vj>
      B. G中有一条从Vi到Vj的路径
      C. G中没有弧<Vi,Vj>
      D. G中有一条从Vj到Vi的路径

    11. (单选题)关键路径是事件结点网络中(A )。
      A. 从源点到汇点的最长路径
      B. 从源点到汇点的最短路径
      C. 最长回路
      D. 最短回路

    12. (单选题)下列关于AOE网的叙述中,不正确的是(B )。
      A. 关键活动不按期完成就会影响整个工程的完成时间
      B. 任何一个关键活动提前完成,那么整个工程将会提前完成
      C. 所有的关键活动提前完成,那么整个工程将会提前完成
      D. 某些关键活动提前完成,那么整个工程将会提前完成

    13. (单选题)对于具有n个顶点的图,若采用邻接矩阵表示,则该矩阵的大小为( B )。
      A. n
      B. n2
      C. n-1
      D. (n-1)2

    二. 填空题
    16. (填空题)具有10个顶点的无向图,边的总数最多为(45)。

    1. (填空题)在有n个顶点的有向图中,若要使任意两点间可以互相到达,则至少需要(n)条弧构成环

    2. (填空题)下图中的强连通分量的个数为(3)个。
      在这里插入图片描述

    3. (填空题)N个顶点的连通图用邻接矩阵表示时,该矩阵至少有(2(n-1))个非零元素。

    4. (填空题)在有向图的邻接矩阵表示中,计算第i个顶点入度的方法是第i(列)元素之和。

    5. (填空题)对于一个具有n个顶点e条边的无向图的邻接表的表示,则表头向量大小为(n),邻接表的边结点个数为(2e )。

    6. (填空题) 已知一无向图G=(V,E),其中V={a,b,c,d,e } E={(a,b),(a,d),(a,c),(d,c),(b,e)}现用某一种图遍历方法从顶点a开始遍历图,得到的序列为abecd,则采用的是(深度优先)遍历方法。

    7. (填空题)构造连通网最小生成树的两个典型算法是(普里姆算法;Prim算法)和 (克鲁斯卡尔算法;Kruskal算法)

    8. (填空题)有向图G可拓扑排序的判别条件是(不存在环 )。

    9. (填空题)在AOE网中,从源点到汇点路径上各活动时间总和最长的路径称为(关键路径 )。

    10. (填空题)在 AOV网 中,存在环意味着(某项活动以自己为先决条件 ),这是(荒谬;错误)的;对程序的数据流图来说,它表明存在(死循环 )。

    11. (填空题)AOV网中,结点表示(活动),边表示(活动间的优先关系)。AOE网中,结点表示(事件),边表示(活动)边上的权代表(活动持续时间)。

    12. (填空题)已知图的邻接矩阵为:当用邻接表作为图的存储结构,且邻接表都按序号从大到小排序时,试写出:该图的拓扑有序序列。
      在这里插入图片描述
      正确答案:V1V2V3V4V5V6V7V8V9V10

    三. 判断题
    29. (判断题)图的深度优先遍历可以判断出一个有向图是否有环(回路)。×

    1. (判断题)关键路径是事件结点网络中从源点到汇点的最短路径。×

    2. (判断题)图的生成树是惟一的。×

    3. (判断题)如果从无向图的任一顶点出发进行一次深度优先搜索即可访问所有顶点,则该图一定是连通图。√

    展开全文
  • 定义:将图中顶点以线性方式进行排序。即对于任何连接自顶点u到顶点v的向边u->v,最后的排序结果顶点u总是在顶点v的前面。 考虑一个非常非常经典的例子——选课。假设我非常想学习一门机器学习的...
  • 1.一个无向图中,所有顶点的度之和等于边数的______ 倍。 A、1/2 B、1 C、2 D、4 答案:C 2.一个n个顶点的无向最多______ 条边。 A、n B、n(n-1) C、n(n-1)/2 D、2n 答案:C 3.一个n...
  • **完全:**任意两个顶点一条边两连 **无向完全:**n个顶点 n(n-1)/2条边 **向完全:**n个顶点 n(n-1)条边 **稀疏:**很少边或弧地的 **稠密:**较多的边或弧的 **网:**边/弧带权的 **...
  • 数据结构 -详细介绍

    千次阅读 多人点赞 2020-12-02 16:03:39
    的基本定义和术语 一、的定义 是由顶点的非空穷集合(用V表示该集合)与顶点...直观地判断,无向图中的所有边都不带箭头,而图中的所有边(习惯称之为弧)都带箭头。 边上带权的称为带权,带权的连
  • 连通图连通图及特性 向图及性质 极大连通子图:极小连通子图:不存在这个概念 最小树形图(难点,考研忽略):邻接矩阵 邻接表 逆邻接表 十字链表 邻接多重表 特殊矩阵 图的遍历BFS DFS最短路径Dijkstra ...
  • 拓扑排序Topological Sorting

    千次阅读 2017-05-03 23:16:54
    http://blog.csdn.net/pipisorry/article/details/71125207拓扑排序Topological Sorting图论拓扑排序(Topological Sorting)是一个向无环(DAG, Directed Acyclic Graph)的所有顶点的线性序列。且该序列...
  • 本文的目的是记录一些学习贝叶斯网络(Bayesian Networks)过程遇到的基本问题。主要包括向无环(DAG),I-Maps,分解(Factorization),向分割(d-Separation),最小I-Maps(Minimal I-Maps)等。主要参考Nir ...
  • 在有向图G,如果两个顶点间至少存在一条路径,称两个顶点强连通(strongly connected),如果向图G的每两个顶点连通,称G是一个强连通图.通俗的说法是:从图G内任意一个点出发,存在通向图G内任意一点的的一条路径....
  • 给定一个,判断该是否存在一个合法的拓扑序列。 Input 输入包含多组,每组格式如下。 第一行包含两个整数n,m,分别代表该顶点数和边数。(n) 后面m行每行两个整数a b,表示从a
  • } 若要按字典序生成拓扑序列,则把 queue 改为 priority_queue 即可 强连通分量(SCC) Kosaraju 算法 可以找到图中所有的SCC 第一遍 dfs 确定原的逆后序序列 第二遍 dfs 图中按照逆后序序列进行遍历 反...
  • 详见:https://blog.csdn.net/zuiyishihefang?t=1 1、文章信息 《Spatio-Temporal Graph Convolutional Networks: A Deep Learning Framework for Traffic Forecasting》。 2017年第二十七届IJCAI国际人工智能...
  • 数据结构习题

    2022-05-25 16:17:59
    数据的物理结构是指数据计算机内的实际存储形式。 对 错 数据结构的抽象操作的定义与具体实现有关。 对 错 链式存储方式的优点是存储密度大,且插入、删除运算效率高。 对 错 程序一定是算法。 对 错 数据...
  • 学习

    2019-07-04 14:47:03
    作者:王小东大将军 ...1、 连通图上各边权值均不相同,则该图的最小生成树是唯一的。 (是自由树,即根结点不确定) 2、 用n表示图中顶点数目,e表示边或弧的数目: (1) 对于无向图,e的取值范围是0~N(N-1)/2;...
  • (4)向网如6.30所示,试用迪杰斯特拉算法求出从顶点a到其他各顶点间的最短路径,完成表6.9。 (5)试对图6.31所示的AOE-网: 3.算法设计题 (1)分别以邻接矩阵和邻接表作为存储结构,实现以下的基本操作...
  • 本文代码实现基本按照《数据结构》课本目录顺序,外加大量的复杂算法实现,一篇文章足够。换你一个收藏了吧?
  • P7

    2020-12-27 21:39:26
    1.Floyd算法,考虑不同顶点时,都可能改变任意点的路径 例:一个顶点编号为0~4的带权G,现用Floyd算法求任意两个顶点之间的最短路径,算法执行的某时刻已考虑了0~2的顶点,现考虑顶点3,则以下叙述...
  • 图论--强连通分支

    2019-02-18 20:48:49
    图论--强连通分支
  • 超硬核!数据结构学霸笔记,考试面试吹牛就靠它

    万次阅读 多人点赞 2021-03-26 11:11:21
    (对于概念的掌握也很重要) 元素之间的关系计算机中有两种表示方法:顺序映像和非顺序映像,由此得到两种不同的储存结构: 顺序存储结构和链式存储结构。 顺序:根据元素存储器的相对位置表示关系 链式:...
  • 连通性问题之Prim算法和克鲁斯卡尔(Kruskal)算法

    千次阅读 多人点赞 2020-06-13 11:04:01
    连通性问题 一.概念 二.求最小生成树的两个算法 三.向无环(DAG) 四.边学边练
  • 拓扑排序

    2017-11-14 12:18:55
    本文将从以下几个方面介绍拓扑排序: 拓扑排序的定义和前置条件 和离散数学偏序/全序概念的联系 典型实现算法 Kahn算法 基于DFS的算法 解的唯一性问题 实际例子 取材自以下材料: ...
  • 在图G,如果代表边的顶点对是无序的,则称G为无向。用圆括号序偶表示无向边。(0,1) 如果表示边的顶点对是有序的,则称G为。用尖括号序偶表示向边。<0,1>(通俗点讲箭头的是,无箭头的...
  • 的总结复习

    2021-05-27 21:22:03
    无权无向搜索最小生成树图拓扑排序连通性2.带权带权的最小生成树最短路径AOE网与关键路径三、疑难问题及解决方案 一、定义及基本术语 1.的定义 G=(V,E),V为顶点集,E为边集。设图有n个顶点...
  • 数据结构:(Graph)【详解】

    万次阅读 多人点赞 2021-02-26 17:03:48
    线性表,数据元素之间是被串起来的,仅线性关系,每个数据元素只有一个直接前驱和一个直接后继。树形结构,数据元素之间有着明显的层次关系,并且每一层上的数据元素可能和下一层多个元素相关,但只能和...
  • 目录 一、判断题 二、选择题 开始之前,先为大家推荐四篇介绍该章四个主要算法的的文章,供大家参考。...1、用邻接表法存储,占用的存储空间数只与图中结点个数有关,而与边数无关。F 解析:用邻.
  • 数据结构——

    2021-06-04 17:21:14
    1. 的定义:G是由顶点集V和边集E组成,记为G=(V,E),其中V(G)表示G中顶点的有限非空集;E(G)表示G中顶点之间的关系,也就是边的集合。 若,则用表示G中顶点的个数,也称G的阶,,用表示G边的条数...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 807
精华内容 322
关键字:

强连通图能有顶点排在拓扑序列中么csdn