【算法与数据结构】——离散化、拓扑排序以及最短路算法的堆优化

怼烎@ 2022-11-11 05:57 104阅读 0赞

## 离散化 ##

### 定义 ###

通俗的说，离散化是在不改变数据相对大小的条件下，对数据进行相应的缩小,

### 基本思路 ###

struct Node
    {
    	int val;
    	int order;
    }a[100001];
    int b[100001];
    其中:
    val是原始数值,
    order是原始下标

对数组a(原始结构体数据)按val从小到大排序;此时,val和结构体的新下标就是一个意义映射关系,而且满足原来的相对大小关系;  
更新b数组:

for(i=1;i<=N;i++)
    {
    	b[a[i].order] = i;
    }

示例图如下  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ1NDg4NDUz_size_16_color_FFFFFF_t_70]

### 重复元素处理 ###

对于有重复元素的情况,由于数组是排序过的,只需要将当前的值与上一个值判等就行.代码如下

b[a[1].order]=1;
    for(i=2,count=1;i<=N;i++){
    	if(a[i].val==a[i-1].val)
    		b[a[i].order]=count;
    	else
    	b[a[i].order]= ++count;
    }

## 拓扑排序 ##

### 定义 ###

“拓扑排序"是指将一个有向无环图G的所有节点排成一个线性序列,使得有向无环图G的边集中的任意一条边<u,v>,始终满足u出现在v的前面。通常,这样的序列称为是"拓扑序列”

### 基本思想 ###

1.在有向无环图中找到一个没有前驱的结点输出  
2.然后从图中将此节点删除并且删除以该节点为尾的弧;  
3.如果所有结点都以输出,则程序结束;否则,返回步骤1.

### 实现方法 ###

#### 邻接矩阵 ####

创建二维数组,用坐标表示对应的2个结点,用坐标上的值表示两个节点是否连接(相比之下比较浪费空间,时间复杂度也比较高,不提倡使用)

#### vector的应用-邻接表 ####

实现方法

struct edge{
    	int to;
    	int value;
    }

相比邻接矩阵优势在于顶点数比较多, 边数比较少时,存储效率,和运算效率.

#### 链式前向星(邻接表的数组实现) ####

//比较流行的用法
    int n,m,s,u,v,w,cnt,head[100005];
    struct Edge{
     	int to,dis,next;
    }edge[200005];
    
    void Add_edge(int_from,int to ,int w)
    {
    	edge[++cnt].to=to;
    	edge[cnt].dis=w;
    	edge[cnt].next = head[from];
    	head[from]=cnt;
    }
    for(int i=1;i<=m;i++){
    	scanf("%d%d%d",&u,&v,&w);
    	Add_edge(u,v,w);
    }

基于链式前向星的图的遍历

for(int=1;i<=n;i++)
    {
    	for(k = head[i];~k;k=edge[k].next)
    		{
    		//~k  按位取反,k=-1时~k等于0
    		}
    }

### 最短路算法的堆优化 ###

#### 迪杰斯特拉算法 ####

常规情况下时间复杂度O( N 2 N^2 N2),如果图的结点比较多,很容易超时,因此考虑利用优先队列维护dist的值从小到大排列(log量级)

#### 基本思想 ####

采用临界表存储图,并利用优先队列维护每个节点的Dist值,避免了每次从n个结点找一个最优解,可以O(1)时间得到本堂的最短路,代价是松弛中的更新操作,每次需要O( L o g 2 E Log\_2E Log2E),因为总的松弛操作数和E成正比,所以优化后时间复杂度E l o g 2 E log\_2E log2E.

#### 参考代码 ####

int n,m,s;
    int cnt,head[100005],vis[100005];
    struct Edge{
    	int to,dis,next;
    }edge[200005];
    void Add_edge(int_from,int to ,int w)
    {
    	edge[++cnt].to=to;
    	edge[cnt].dis=w;
    	edge[cnt].next = head[from];
    	head[from]=cnt;
    }
    struct node{
    	int id,dis;
    	bool operator<(const node &a)const
    	{
    		return a.dis<dis;
    	}
    };
    void Dijkstra()
    {
    	priority_queue<node> q;
    	q.push(node{s,0};
    	for(int i =1;i<=n;i++)
    	dist[i]=INF;
    	dist[s]=0;
    	while(!q.empty())
    	{
    		node a = q.top();
    		q.pop();
    		int now=a.id;
    		if(vis[now]) continue;
    		vis[now]=1;
    		for(int i = head[now];i;i=edgee[i].next)
    		{
    			int j = edge[i].to;
    			if(dist[now]+edge[i].dis<dist[j])
    			{
    				dis[j]=dist[now]+edge[i].dis;
    				q.push(node{j,dist[j]});
    			}
    		}
    	}
    }
    int main(){.......}

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ1NDg4NDUz_size_16_color_FFFFFF_t_70]: /images/20221022/08e6c63488d049cc85ef93567cc9eb6a.png