数据结构—从图论到数据存储

By lx | Apr 18, 2023 | Category: 默认分类 | 共 3908 个字符

图G在是一种表示表示事物之间关系的一种结构，用顶点表示对象，用连线表示对象间存在关系

基本概念

顶点集V->顶点个数->阶
边集E->边->边界
无向图()
有向图<>
简单图-不存在重复边<->存在重复边-多重图
完全图-子图-生成子图

连通-顶点间有路径存在-连通图-任意俩点连通连通分量-极大连通子图
来回都连通-强连通图强连通分量

生成树生成森林
顶点度入度出度
边的权和网
稠密图-稀疏图临界是|E|<|V|log|V|
路径路径长度回路简单路径简单回路
距离
有向图

存储方式以及基本操作

邻接矩阵法
o(|v|^2) 稠密图
数组记录顶点，二维数组记录边信息，无权记录是否存在，有权记录带权信息
A^ni->i到j，长度为n的路径
出入度，遍历边行即可得到

#define #define MaxVertrxNum 100
typedef struct{
  char Vex[MaxVertexNum];//顶点表
  int Edge[MaxVertexNum][MaxVertexNum];//边表
  int vexnum,arcnum;//图的当前定点数和边数/弧度
}MGraph;

邻接法
o(|v|+|E|) 稀疏图
类似于孩子表示法-每条链指相邻的所有节点
出度好找，入度要遍历。只表示结点，表示方式不唯一，顺序不同
删除很不方便

#define MaxVertrxNum 100
typedef struct ArcNode{//边表
  int adjvex;
  struct ArcNode *nextarc;
}ArcNode;

typedef struct VNode{//顶点表
  VertexType data;
  ArcNode *firstarc;
}VNode,AdjList[MaxVertexNum];

typedef struct{//邻接表
  AdjList vertices;
  int  vexnum,arcnum;
}ALGraph;

十字链表法(有向图)与邻接多重表(无向图)
o(|v|+|E|)
结点和边表分开表示
点：数据指向它的第一个弧结点它指向的第一个弧结点
边：尾点头点头同弧尾同弧权值
最后以头尾同弧都是以NULL结束
增删都很方便

#define MaxVertrxNum 100
typedef struct ArcNode{//边表
  int tailvex,headvex;
  struct ArcNode *hlink;
  struct ArcNode *tlink;
  InfoType info;
}ArcNode;

typedef struct VNode{//顶点表
  VertexType data;
  VexNode *firstin;
  VexNode *firstout;
}VNode,AdjList[MaxVertexNum];

typedef struct{//十字链表
  AdjList vertices;
  int  vexnum,arcnum;
}Graph;

基本操作
增删检查
边角关系

广度优先遍历BFS

类似于层序遍历

初始化：全部初始化为fails，初始化队列，从0号开始遍历，每个连通分量进行一次BFS
BFS：从第一个fails开始，找到所有相邻顶点(FirstNeighbor NestNeigh
bor)，并标记那些被访问过，设置一个辅助队列记录以及访问过的顶点，从访问过的中开始下一轮寻找
空间复杂度主要来源于队列的空间大小
时间复杂度的主要来源于访问顶点和各条边，综合分析即可
广度有限生成树/森林
根据广度优先遍历顺序，改造成二叉树/森林
邻接表不唯一，零阶矩阵唯一
最短路径问题
尽量选择能够一次遍历完所有的顶点的初始顶端来遍历

深度优先遍历DFS

类似于先序遍历
深度优先生成树/森林
按照DFS生成算法树

最小生成树

Prim算法
类似于Dijkstra算法，依次寻找相连的最短权值，到头依次返回，直到遍历
O(|V|^2)
Kruskal算法
按权值构造，优先找最短的权值构造路，然后连接全部。

最短路径问题

BFS算法
从最开始到各个顶点的距离依次合并为最短路径(比赛胜出)
依次访问并标记，记录依次路径和前驱

Floyd算法
求出每一对顶点之间的最短路径
两个矩阵表示，一个记录目前的最短路径，一个两个顶点之间的中转点。
从初始不允许中转到依次中转相顶点，按照0-n，依次添加作为中转点。
左右两个矩阵同时更新中转节点后的结果

Dijkstra算法
带权路径长度的最短路径
改进BFS，从初始结点出发，三个数组，一个依次遍历各个顶点是否已经找到最短路径final，一个记录此时最短长度dist，一个记录对应的前驱path
先找没有确定且dist最小的
时间复杂度o(n^2)

有向无环图DAG

在描述表达式时可以合并的都尽量合并
方法：列出所有出现的操作数，然后按生效顺序标注出运算符，最后按顺序加入操作数，并注意乘法除法的层级，最后再检查是否可以同层合并。
也可以通过先序表达，来方便观察哪一些说同一级可以合并的表达式

拓扑排列

AOV网-用DAG图表示一个工程，顶点表示活动有向边表示先后顺序
拓扑排序：找到做事的先后顺序
实现方法(无回路才行)：
从AOE网中找到一个没有前驱的顶点
删除顶点和他所指向的所有以它为起点的有向边
重复前面操作直到当前AOE网为空或是当前网中不存在无前驱的顶点为止

//Graph是以邻接表储存的图类型
bool TopologicalSort(Gragph G){
  InitStack(S);
  for(int i=0;i<G.vexnum;i++)
    if(indegree[i]==0)
      Push(S,i);
  int count=0;
  while(!IsEmpty(S)){
    Pop(S,i);
    print[count++]=i;
    for(p=G.vertices[i].firstarc;p;p=p->nextarc){
      v=p->adjvex;
      if(!(--indegree[v]))
        Push(S,v);
    }
  }
  if(count<G.vexnum)
    return false;
  else
    return true;
}

时间复杂度：O(|V|+|E|),用邻接矩阵则需要O(|V|^2)

逆拓扑排序的实现(DFS算法)

从没有出度的开始,方便找入度的边用邻接矩阵来改良

bool TopologicalSort(Gragph G){
  InitStack(S);
  for(int i=0;i<G.vexnum;i++)
    if(outdegree[i]==0)
      Push(S,i);
  int count=0;
  while(!IsEmpty(S)){
    Pop(S,i);
    print[count++]=i;
    for(p=G.vertices[i].firstarc;p;p=p->nextarc){
      v=p->adjvex;
      if(!(--indegree[v]))
        Push(S,v);
    }
  }
  if(count<G.vexnum)
    return false;
  else
    return true;
}

关键路径

AOE网
关键路径：最长的路径关键活动
弧头到弧尾的连线
最早开始时间与最迟开始时间的差值为时间余量，为零则为关键活动，之间的路径为关键路径