1. 编程号首页

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

编程小号 • • 未分类

学不完的数据结构（四）图5. 图 图 : 图是由有穷并且非空的集合V和边的集合E组成。 ​ 图中可以一条边都没有，但是至少需要一个顶点。 ​ 无向完全图：图中任意两个顶点之间都存在边。即时 ​ 图中的极大连通子图（即任意增加G中的结点或边后所得到的G的子图都不再连通）称为连通分量。 ​ 有向完全图：图…

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表示为

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

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

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

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

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

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

​ 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)

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

邻接矩阵表示唯一。

A^m[i][j]：从顶点 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 边结点个数
边相连 A[i][j] A[i][j] 边表 边表
空间复杂度 $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)找出最早发生时间和最迟发生时间相同的活动 就是关键活动 由关键活动组成的路径就是关键活动

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

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

赞 (0)
编程小号编程小号
0

相关推荐

发表回复

您的电子邮箱地址不会被公开。 必填项已用 * 标注