学不完的数据结构（四）图

5. 图

5.1 图的基本概念

图 : 图是由有穷并且非空的集合V和边的集合E组成。

图中可以一条边都没有，但是至少需要一个顶点。

图的标记：

图：G(V,E)\\
顶点集：V(G) \quad 顶点数量：|V|(\ge 1)\\
边集：E(G)\quad 边数量:|E|

无向图：

概念：每条边都无方向

度：与该顶点相关的边的条数 $\sum _{i=1}^n TD(V_i)=2e$ （常用于计算）

无向完全图：图中任意两个顶点之间都存在边。即 |V|=n 时 $|E|=\frac {n(n-1)}{2}$

连通图：在无向图中，图中任意两个顶点之间都存在路径（连通）

图中的极大连通子图（即任意增加G中的结点或边后所得到的G的子图都不再连通）称为连通分量。

有向图：

概念：每条边都有方向,由1指向2表示为 $<1,2>” src=”https://juejin.cn/equation?tex=%3C1%2C2%3E” loading=”lazy”> 出度：由该顶点发出的边的条数 <noscript><img decoding=$ $\sum _{i=1} ^n ID(V_i)=e$

入度：指向该顶点的边的条数 $\sum _{i=1} ^n OD(V_i)=e$

有向完全图：图中任意两个顶点之间都存在方向相反的两条弧。即 |V|=n 时

强连通图：在有向图中，对于图中的任意一对顶点之间都存在相互的路径（强连通）

其中的极大强连通子图称为强连通分量

子图：并非所有点和边的子集都可以组成子图，需要边对应点。

生成树：包含图中所有顶点的一个极小连通子图。

n个顶点的环有n个生成树。

路径和路径长度：路径为相邻顶点序偶所构成的序列 路径长度是指路径上边的数目

简单路径:顶点不重复出现的路径

回路：路径中第一个顶点和最后一个顶点相同的路径

环（回路）判断方式：深度优先遍历

拓扑排序

关键路径（前提拓扑排序）

稠密图：边数多的图稀疏图：边数少的图

n个顶点的图的性质：

	有环的最少边数	必有环的边数
无向图	3	n
有向图	2	n
	(强)连通的最少边数	必(强)连通的边数
无向图	n-1（树）	$\frac{(n-1)(n-2)}{2}+1$
有向图	n（环）	(n-1)(n-2)+1

5.2 图的储存结构

5.2.1邻接矩阵

邻接矩阵的结构型定义如下

typedef struct {
    int no;            //顶点编号
    char info;         //顶点信息
}VertexType;           //顶点类型

typedef struct{
    int edges[maxsize][maxsize];  //邻接矩阵定义
    int N,E;                      //N 定点数 E 边数
    VertexType vex[maxsize];      //存放结点信息
}MGraph;

无向图：

邻接矩阵为对称矩阵。

第i行非0元素数量和=第i列元素和= TD(V_i)

有向图：

第i行的非0元素数量和= OD(V_i)

第i列的非0元素数量和= ID(V_i)

无向图的邻接矩阵是对称矩阵

邻接矩阵表示唯一。

：从顶点 i** 到顶点 j 长度为 m 的路径长度

5.2.2邻接表

结构型定义如下：

typedef struct ArcNode{
    int adjvex; //所指向结点的位置
    struct ArcNode *nextArc; //下一条边的指针
    int info;   //边的相关信息
}ArcNode;      //边的定义

typedef struct{
    char data;  //顶点信息
    ArcNode *firstarc; //该顶点指向的第一条边的指针
}VNode;        //顶点

typedef struct{
    VNode adjlist[maxsize];
    int n,e;
}AGraph;     //图的定义

有向图：

出度：结点个数

入度：需要遍历全部邻接表

图的邻接表表示不唯一。

	邻接矩阵	邻接矩阵	邻接表	邻接表
	无向图	有向图	无向图	有向图
特性	对称矩阵
出度	i行(列)和	i行和	边表个数	边表个数
入度	i行(列)和	i列和	边表个数	边表结点为i的和
边数	1的个数/2	1的个数	边结点个数/2	边结点个数
边相连			边表	边表
空间复杂度	$O(	V	^2)$	$O(
适用	稠密图	稠密图	稀疏图	稀疏图

5.3 图的遍历算法操作

图的遍历是指从图中的某一顶点出发（非连通图可能一个顶点不足以访问全部），按照某种搜索方法对所有顶点访问一次且仅访问一次。

5.3.1 广度优先遍历（BFS）

广度优先遍历不是一个递归算法

方法：

1.首先将根节点放入队列中

2.从队列中取出第一个节点，并检验它是否为目标

*如果找到目标，则结束搜索并回传结果

*否则将它所有尚未检验过的直接子节点加入队列中

3.若队列为空，表示整张表都检查过了

以邻接表为储存结构的算法如下：

int visit[maxsize];

void BFS(AGraph *G,int v)
{
    ArcNode *p;
    int que[maxsize],front=0,rear=0;
    int j;
    visit[v] = 1;
    Visit(v);
    rear = (rear+1)%maxsize;
    que[rear] = v; //V入队
    while(front!=rear)
    {
        front = (front+1)%maxsize;
        j = que[front]; //顶点出队
        p = G->adjlist[j].firstarc;
        while(p!=NULL)
        {
            if(visit[p->adjvex]==0)
            {
                visit[p->adjvex] = 1; //邻接顶点访问并入队
                Visit(p->adjvex);
                rear = (rear+1)%maxsize;
                que[rear] = p->adjvex;
            }
            p=p->nextarc;
        }
    }
}

void bfs(AGraph *g)
{
    int i;
    for(i=0;i<g->n;i++)
        if(visit[i]==0)
            BFS(g,i);
}

BFS算法可以用来解决权值相等的图的单源最短路径问题（注意权值不等不可）。

广度优先生成树：

用邻接矩阵表示的图的广度优先生成树是唯一的。

用邻接表表示的图的广度优先生成树是不唯一的。

5.3.2深度优先遍历（DFS）

深度优先搜索是一个递归算法

//以邻接表为储存结构的递归算法如下：
int visit[maxsize];//全局变量 标记数组

void DFS(AGraph *G,int v) //从结点V开始的遍历
{
    AGraph *p;
    visit[v] = 1;     //置已访问标记
    Visit(v);         //访问节点
    p = G->adjlist[v].firstarc;   //指向顶点v的第一条边
    while(p!=NULL)
    {
        if(visit[p->adjvex]==0)   //未访问 则递归访问他
            DFS(G,p->adjvex);
        p = p->nextarc;           //下一条边继续
    }
}

//以邻接矩阵为储存结构的递归算法如下：
int visit[maxsize];//全局变量 标记数组

void DFS(MGraph *G,int v) //从结点V开始的遍历
{
    visit[v] = 1;     //置已访问标记
    Visit(v);         //访问节点
	int i;
    for(i=0;i<G->n;i++)
    {
        if(G->adges[v][i]>0 && visit[i]==0)
            DFS(G,i);
    }
}

以邻接表为储存结构的非递归算法如下：

int visit[maxsize];

void DFS(AGraph *G,int v)
{
    AGraph *p;
    int j;
    int stack[maxsize],top; //该栈用来暂存节点
    top = -1; 
    stack[++top] = v; //起始节点入栈
    while(top!=-1)
    {
        j = stack[top--]; //取出栈顶节点
        visit[j] = 1;
        Visit(j);
        p = G->adjlist[j].firstarc;
        while(p!=NULL)
        {
			if(visit[p->adjvex]==0)
                stack[++top] = p->adjvex;
            p = p->nextarc;
        }
    }
}

void dfs(AGraph *g)
{
    int i;
    for(i=0;i<g->n;i++)
        if(visit[i]==0)
            DFS(g,i);
}

DFS用来解决图中的回路存在问题：

无向图：DFS过程中遇到了回边必定存在环。

<<<<<<< HEAD

//以邻接表为储存结构的算法如下：
int visit[maxsize];
void BFS(AGraph *G,int v)
{
    ArcNode *p;
    int que[maxsize],front=0,rear=0;
    int j;
    visit[v] = 1;
    Visit(v);
    rear = (rear+1)%maxsize;
    que[rear] = v; //V入队
    while(front!=rear)
    {
        front = (front+1)%maxsize;
        j = que[front]; //顶点出队
        p = G->adjlist[j].firstarc;
        while(p!=NULL)
        {
            if(visit[p->adjvex]==0)
            {
                visit[p->adjvex] = 1; //邻接顶点访问并入队
                Visit(p->adjvex);
                rear = (rear+1)%maxsize;
                que[rear] = p->adjvex;
            }
            p=p->nextarc;
        }
    }
}

void bfs(AGraph *g)
{
    int i;
    for(i=0;i<g->n;i++)
        if(visit[i]==0)
            BFS(g,i);
}

//以邻接矩阵为储存结构的算法如下：
int visit[maxsize];
void BFS(MGraph *G,int v)
{
    int que[maxsize],front=0,rear=0;
    int j;
    visit[v] = 1;
    Visit(v);
    rear = (rear+1)%maxsize;
    que[rear] = v; //V入队
    while(front!=rear)
    {
        front = (front+1)%maxsize;
        j = que[front]; //顶点出队
        for(int i=0;i<G->n;i++)
        {
            if(G->adges[j][i]>0&&visit[i]==0)
            visit[i] = 1; //邻接顶点访问并入队
            Visit(i);
            rear = (rear+1)%maxsize;
            que[rear] = i;
        }
    }
}

======= 有向图：若在一次从一结点出发的遍历结束之前碰到该节点，则存在环。

DFS遍历一个无环有向图，在退出递归时输出其逆拓扑有序序列（退出递归时是逆是因为其栈性质，否则不逆）

深度度优先生成树：

用邻接矩阵表示的图的深度优先生成树是唯一的。

用邻接表表示的图的深度优先生成树是不唯一的。

5.3.3 DFS和BFS总结

	对应树遍历	借助结构	时间复杂度	空间复杂度
广搜（BFS）	层次遍历	队列	邻接矩阵：$O(	V
深搜（DFS）	先序遍历	栈	邻接矩阵：$O(	V

对于同一个图，基于邻接矩阵的遍历所得的DFS序列和BFS序列是唯一的，而邻接表的遍历得到的序列是不唯一的（具体给出物理存储结构是唯一的）。

无向图：连通：从任一节点出发，则仅需一次便可遍历所有结点。

非连通：任一节点一次遍历只能遍历其该连通分量的顶点。

有向图：强连通：任一节点开始可以一次遍历所有结点。

非强连通：任一节点一次无法遍历其连通分量。（若为强连通分量则可遍历该强连通分量）

使用标号法判断遍历序列是否合法。

深度优先生成树高>=广度优先生成树高

5.4最小代价生成树

（普里姆算法和科鲁斯卡算法都是针对于无向图的）

最小生成树：

最小生成树是图的极小连通子图（并非连通分量），包含图中所有顶点，只包含尽可能少的边，若砍去它的一条边，则变成非连通图，若增加一条边，则形成一条回路。

性质：

1.最小生成树不是唯一的，只有当各边的权值互不相等时唯一，当边为n-1时，就是其本身。

或者有相等的边，但是在构造最小生成树的过程中权值相等的边都被并入生成树的图

2.最小生成树的权值之和总是唯一的。

3.最小生成树的边数为顶点数减一。

4.若(u,v)是一条具有最小权值的边，其中 $u\in U,v\in V-U$ ,则必存在一颗包含这条边的最小生成树。

5.4.1普里姆算法（加点法）：

以邻接矩阵为储存结构

void Prim(MGraph g,int v0,int &sum)
{
    int lowcost[maxsize],vset[mexsize],v;
    int i,j,k,min;
    v = v0;
    for(i=0;i<g.n;i++) //初始化lowcost数组
    {
        lowcost[i] = g.edges[v0][i];
        vset[i] = 0;
    }
    vset[v] = 1; //把V0并入到树中
    sum = 0; //sum用来累计树的权值
    for(i=0;i<g.n-1;i++)
    {
        min = INF; 
        //选出候选边的最小值
        for(j=0;j<g.n;j++)
        {
            if(vset[j]==0&&lowcost[j]<min)
            {
                min = lowcost[j];
                k = j;
            }
        }
        v = k;
        sum += min; //记录了最小生成树的权值
        //更新候选边
        for(j=0;j<g.n;j++)
        {
            if(vset[j]==0&&g.edges[v][j]<lowcost[j])
                lowcost[j] = g.edges[v][j];
        }
    }
}

5.4.2科鲁斯卡算法（加边法）:

算法思想：选出权值最小的边（并检测该边的并入是否会造成回路）然后将该边并入到当前生成树中

代码实现: （要用到并查集）

同样也是借助邻接矩阵来实现的

typedef struct
{
    int a,b; //一条边所依附的两个顶点
    int w; //一条边所对应的权值
}Road; //边的定义
Road road[maxsize];
int v[maxsize]; //声明并查集数组
int getRoot(int a)       //查找并查集中根节点的函数
{
    while(a!=v[a])
        a = v[a];
    return a;
}

void Kruskal(MGraph g,int &sum,Road road[])    //传入的road数组中已经包含路径信息
{
    int i;
    int N,E,a,b;
    N = g.n; E = g.e;
    sum = 0; //初始化清零
    //并查集的初始化
    for(i=0;i<N;i++) v[i] = i;
    sort(road,E); //对road数组中的E条边按照权值从小到大排列
    for(i=0;i<E;i++)
    {
        a = getRoot(road[i].a);
        b = getRoot(road[i].b);
        if(a!=b)          //这条边的并入并不会导致环
        {
            v[a] = b;
            sum+=road[i].w;
        }
    }
}

5.5.3 总结

	时间复杂度	适用范围
Prim	$O(	V
Kruskal	$O(	E

5.5最短路径

权值相等的图或者无权图可以用广度优先搜索。

带权图都可以使用以下两种求法。

两点之间的最短路径也包含了路径上其它顶点间的最短路径。（动态规划：最优子结构）

5.5.1迪杰斯特拉算法（单源最短路径）

算法思想：设两个顶点集合 S(已找到的最短路径顶点) T(未找到的最短路径顶点) 初始时 S中只含有初始顶点v0 然后不断从集合T中选取到V0的路径长度最短的顶点Vu 并入到S中 S每并入一个新顶点都要修改V0到集合T中各顶点的最短路径长度值不断重复此过程直到T为空

算法实现

同样也是借助于邻接矩阵

void Dijkstra(MGraph g,int v,int dist[],int path[])
{
    int set[maxsize];
    int min,i,j,u;
    //对各数组进行初始化
    for(i=0;i<g.n;i++)
    {
        dist[i] = g.edges[v][i];
        set[i] = 0;
        if(g.edges[v][i]<INF)
            path[i] = v; 
        else
            path[i] = -1;
    }
    set[v] = 1;path[v] = -1; //把V加入set数组中
    for(i=0;i<g.n-1;i++)
    {
        min = INF;
        //每次从剩余顶点中选取一个通往该点路径是所有剩余顶点中最短的
        for(j=0;j<g.n;j++)
        {
            if(set[j]==0&&dist[i]<min)
            {
                u = j;
                min = dist[j];
            }
        }
        set[u] = 1; //加入最短路径
        //更新dist
        for(j=0;j<g.n;j++)
        {
            if(set[j]==0&&dist[u]+g.edges[u][j]<dist[j])
            {
                dist[j] = dist[u]+g.edges[u][j];
                path[j] = u;
            }
        }
    }
}

//打印最短路径
void PrintPath(int path[],int a)      //由V到a的最短路径
{
    int stack[maxsize],top = -1;
    while(path[a]!=-1)
    {
        stack[++top] = a;
        a = path[a];
    }
    stack[++top] = a;
    while(top!=-1)
        print(stack[top--]);
}

5.5.2弗洛伊德算法

//算法思想如下: 借助邻接矩阵实现

//1)设置两个矩阵 A 和 Path 初始时把图的邻接矩阵赋值给A 把Path中元素全部设置为-1

//2)以顶点K（K取0~n-1）作为中间顶点 对图中所有顶点做如下修改：
//	if A[i][j]>A[i][k]+A[k][j] 
//  {
//		A[i][j] = A[i][k]+A[k][j];path[i][j] = k
//  }
//  else 啥也不做;

void Floyd(MGraph h,int Path[][maxsize])
{
    int i,j,k;
    int A[maxsize][maxsize];
    for(i=0;i<g.n;i++) //初始化
        for(j=0;j<g.n;j++)
        {
            A[i][j] = g.edges[i][j];
            Path[i][j] = -1;
        }
    //以K为中间节点对所有顶点对进行修改检测
    for(k=0;k<g.n;k++)
    	for(i=0;i<g.n;i++)
            for(j=0;j<g.n;j++)
                if(A[i][k]+A[k][j]<A[i][j])
                {
                    A[i][j] = A[i][k]+A[k][j];
                    Path[i][j] = k;
                }
}

//路径的打印算法
void PrintPath(int u,int v,int Path[][maxsize]) //输出U到V的最短路径序列
{
    if(Path[u][v] == -1)           //U到V有直接顶点
    {
        cout<<"("<<u<<","<<v<<")"<<;
    }
    else
    {
        int mid = Path[u][v];
        PrintPath(u,mid,Path);
        PrintPath(mid,v,Path);
    }
}

5.5.3 总结

	求解问题	时间复杂度	适用范围
Dijkstra	单源最短路径	$O(	V
Floyd	各顶点最短路径	$O(	V

5.6 拓扑排序

AOV网：简而言之就是活动在顶点上的网

拓扑排序存在：必要条件是该有向图无环（回路），或者说成没有顶点数大于1的强连通分量。

充分条件是该有向图邻接矩阵为三角矩阵。

拓扑有序序列存在：充分必要条件是邻接矩阵为三角矩阵

根据唯一的拓扑排序可以确定多种样式的图。

拓扑排序的核心算法：（真题中有过类似）

//算法思想：
// 1）从有向图中选择一个入度为零的顶点输出
// 2）删除该顶点 并且删除从该顶点出发的全部边
// 3）重复上面两步 直到剩余的图中不存在没有前驱的顶点为止

//对邻接表表头结构做出相应调整
typedef struct
{
    char data;
    int count; //count 用来统计入度
    ArcNode *firstarc;
}VNode;

//借助邻接表存储结构实现
int TopSort(AGraph *G)
{
    int i,j,n=0;
    int stack[maxsize],top=-1;
    ArcNode *p;
    for(i=0;i<G->n;i++) //将入度为零的顶点入栈
        if(G->adjlist[i].count==0)
            stack[++top] = i;
    while(top!=-1)
    {
        i = stack[top--]; //顶点出栈
        ++n;
        cout<<i<<endl;
        p = G->adjlist[i].firstarc;
        while(p!=NULL)
        {
            j = p->adjvex;
            --(G->adjlist[j].count);
            if(G->adjlist[j].count==0)
                stack[++top] = j;
            p = p->nextarc;
        }
    }
    if(n==G->n)            //拓扑排序成功
        return 1;
    else                   //拓扑排序失败
        return 0;
}

//借助邻接矩阵存储结构实现
int TopSort(MGraph *G)
{
    int i,j,n=0;
    int stack[maxsize],top=-1;
    for(i=0;i<G->n;i++) //将入度为零的顶点入栈
        if(G->vex[i].count==0)
            stack[++top] = i;
    while(top!=-1)
    {
        i = stack[top--]; //顶点出栈
        ++n;
        cout<<i<<endl;
        for(j=0;j<G->n;j++)
        {
            if(G->edges[i][j]>0)
            {
                G->vex[j].indegree--;
                if(G->vex[j].indegree==0)
                {
                    stack[++top] = j;
                }
            }
        }
    }
    if(n==G->n)            //拓扑排序成功
        return 1;
    else                   //拓扑排序失败
        return 0;
}

//拓扑排序后的序列可能并不唯一

求逆拓扑序列的方法也类似。。。另外按照DFS算法的先后次序（即顶点退出系统栈的顺序）记录下的顶点序列即为逆向的拓扑有序序列

拓扑排序的算法复杂度为O(n+e);

(重点掌握手工进行拓扑排序的过程)

5.7 关键路径

AOE网：活动在边上的网

在AOE网中从源点到汇点的所有路径中具有最大路径长度的路径称为关键路径。

关键路径既代表了最长路径 又代表了整个工期所完成的最短时间

关键路径上的活动是关键活动，关键活动一定在关键路径上。

网中的关键路径并不唯一，只有加快所有关键路径上的活动才可减少时间。

具体步骤为：

1)根据图求出拓扑有序序列a 和逆拓扑有序序列b

2)根据序列a求出最早发生时间

根据序列b求出最迟发生时间

3)求出每个活动的最早最迟发生时间

4)找出最早发生时间和最迟发生时间相同的活动就是关键活动由关键活动组成的路径就是关键活动

今天的文章学不完的数据结构（四）图分享到此就结束了，感谢您的阅读。

版权声明：本文内容由互联网用户自发贡献，该文观点仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容，请发送邮件至举报，一经查实，本站将立刻删除。
如需转载请保留出处：https://bianchenghao.cn/22459.html

学不完的数据结构（四）图

5. 图

5.1 图的基本概念

5.2 图的储存结构

5.2.1邻接矩阵

5.2.2邻接表

5.3 图的遍历算法操作

5.3.1 广度优先遍历（BFS）

5.3.2深度优先遍历（DFS）

5.3.3 DFS和BFS总结

5.4最小代价生成树

5.4.1普里姆算法（加点法）：

5.4.2科鲁斯卡算法（加边法）:

5.5.3 总结

5.5最短路径

5.5.1迪杰斯特拉算法（单源最短路径）

5.5.2弗洛伊德算法

5.5.3 总结

5.6 拓扑排序

5.7 关键路径

相关推荐

发表回复