【数据结构】图的最短路径和拓扑排序及应用

Alex_Shen
2020-12-08 / 0 评论 / 0 点赞 / 99 阅读 / 11,186 字 / 正在检测是否收录...
温馨提示:
本文最后更新于 2022-04-06,若内容或图片失效,请留言反馈。部分素材来自网络,若不小心影响到您的利益,请联系我们删除。

问题 A: DS图—图的最短路径(不含代码框架)

题目描述

给出一个图的邻接矩阵,输入顶点v,用迪杰斯特拉算法求顶点v到其它顶点的最短路径。

输入

第一行输入t,表示有t个测试实例
第二行输入顶点数n和n个顶点信息
第三行起,每行输入邻接矩阵的一行,以此类推输入n行
第i个结点与其它结点如果相连则为距离,无连接则为0,数据之间用空格
隔开。第四行输入v0,表示求v0到其他顶点的最短路径距离
以此类推输入下一个示例

输出

对每组测试数据,输出:
每行输出v0到某个顶点的最短距离和最短路径
每行格式:v0编号-其他顶点编号-最短路径值----[最短路径]。没有路径输出:v0编号-其他顶点编号--1。具体请参考示范数据

样例输入

2
5 0 1 2 3 4
0 5 0 7 15
0 0 5 0 0
0 0 0 0 1
0 0 2 0 0
0 0 0 0 0
0
6 V0 V1 V2 V3 V4 V5
0 0 10 0 30 100
0 0 5 0 0 0
0 0 0 50 0 0
0 0 0 0 0 10
0 0 0 20 0 60
0 0 0 0 0 0
V0

样例输出

0-1-5----[0 1 ]
0-2-9----[0 3 2 ]
0-3-7----[0 3 ]
0-4-10----[0 3 2 4 ]
V0-V1--1
V0-V2-10----[V0 V2 ]
V0-V3-50----[V0 V4 V3 ]
V0-V4-30----[V0 V4 ]
V0-V5-60----[V0 V4 V3 V5 ]

题解

#include<iostream>
#include<algorithm>
#include<vector>
#define Infinity 99999
#define Maxlen 20
using namespace std;

class Map {
public:
	int Weight[Maxlen][Maxlen];
	string node[Maxlen];
	int Vexnum;
	void SetMatrix() {
		cin >> Vexnum;
		for (int i = 0; i < Vexnum; i++)
			cin >> node[i];
		for (int i = 0; i < Vexnum; i++)
			for (int j = 0; j < Vexnum; j++)
				cin >> Weight[i][j];
	}
	int FindNodeIndex(string str) {
		for (int i = 0; i < Vexnum; i++)
			if (node[i] == str)
				return i;
	}
	void DijAlgorithm() {
		string start_str;
		cin >> start_str;
		int starti = FindNodeIndex(start_str);
		//初始化D,Path,final数组
		int* D = new int[Vexnum];
		vector<string>* path = new vector<string>[Vexnum];
		bool* final = new bool[Vexnum];
		for (int v = 0; v < Vexnum; v++) {
			D[v] = Weight[starti][v];
			final[v] = false;
			path[v].push_back(start_str);
		}
		D[starti] = 0;
		final[starti] = true;
		for (int i = 0; i < Vexnum; i++) {
			int min = Infinity;
			int v = 0;
			for (int w = 0; w < Vexnum; w++) {
				if (!final[w] && D[w] != 0)
					if (D[w] < min) {
						v = w;
						min = D[w];
					}
			}
			final[v] = true;
			for (int w = 0; w < Vexnum; w++) {
				if (!final[w] && Weight[v][w] != 0 && (D[w] == 0 || (min + Weight[v][w] < D[w]))) {
					path[w] = path[v];
					D[w] = min + Weight[v][w];
					path[w].push_back(node[v]);
				}
			}
		}
		for (int i = 0; i < Vexnum; i++) {
			if (i != starti) {
				cout << node[starti] << "-" << node[i];
				if (D[i] != 0) {
					cout << "-" << D[i] << "----[";
					for (auto x : path[i])
						cout << x << " ";
					cout << node[i] << " ]" << endl;
				}
				else {
					cout << "--" << 1 << endl;
				}
			}
		}

	}
};

int main() {
	int t;
	cin >> t;
	while (t--) {
		Map map;
		map.SetMatrix();
		map.DijAlgorithm();
	}
	return 0;
}

问题 B: 图综合练习--拓扑排序

题目描述

已知有向图,顶点从0开始编号,求它的拓扑有序序列。
拓扑排序算法:给出有向图邻接矩阵
1.逐列扫描矩阵,找出入度为0且编号最小的顶点v
2.输出v,并标识v已访问
3.把矩阵第v行全清0
重复上述步骤,直到所有顶点输出为止
--程序要求--
若使用C++只能include一个头文件iostream;若使用C语言只能include一个头文件stdio
程序中若include多过一个头文件,不看代码,作0分处理
不允许使用第三方对象或函数实现本题的要求

输入

第一行输入一个整数t,表示有t个有向图
第二行输入n,表示图有n个顶点
第三行起,输入n行整数,表示图对应的邻接矩阵
以此类推输入下一个图的顶点数和邻接矩阵

输出

每行输出一个图的拓扑有序序列

样例输入

2
5
0 1 0 1 1
0 0 1 0 0
0 0 0 0 1
0 0 1 0 0
0 0 0 0 0
7
0 0 0 0 0 0 0
1 0 1 1 0 0 0
1 0 0 0 0 0 0
1 0 1 0 0 0 0
0 0 0 0 0 1 1
0 1 0 0 0 0 0
0 0 0 1 0 1 0

样例输出

0 1 3 2 4
4 6 5 1 3 2 0

题解

#include<iostream>
#define Infinity 99999
#define Maxlen 20
using namespace std;

class Map {
public:
	int Matrix[Maxlen][Maxlen];
	string node[Maxlen];
	int count[Maxlen];
	int sorted[Maxlen];
	bool visited[Maxlen];
	int Vexnum;
	void SetMatrix() {
		cin >> Vexnum;
		for (int i = 0; i < Vexnum; i++) {
			count[i] = 0;
			sorted[i] = 0;
			visited[i] = false;
		}			
		for (int i = 0; i < Vexnum; i++)
			for (int j = 0; j < Vexnum; j++) {
				cin >> Matrix[i][j];
				if (Matrix[i][j] == 1)
					count[j]++;
			}
	}
	int findMinIndex() {
		int min, min_i;
		for (int i = 0; i < Vexnum; i++) {
			if (visited[i] == false) {
				min = count[i];
				min_i = i;
			}
		}
		for (int i = 0; i < Vexnum; i++)
			if (min > count[i] && visited[i] == false) {
				min = count[i];
				min_i = i;
			}
		return min_i;
	}
	void Sort() {
		int I;
		for (I = 0; I < Vexnum; I++) {
			int p = findMinIndex();
			sorted[I] = p;
			for (int i = 0; i < Vexnum; i++){
				if (Matrix[p][i] == 1)
					count[i]--;
			}
			visited[p] = true;
		}
		for (int i = 0; i < Vexnum; i++)
			cout << sorted[i] << " ";
		cout << endl;
	}
};

int main() {
	int t;
	cin >> t;
	while (t--) {
		Map map;
		map.SetMatrix();
		map.Sort();
	}
	return 0;
}

问题 C: 追星

题目描述

城市总共有N座。yintama是右京女神的狂热粉,当他得知右京女神将要在城市N举办演唱会的时候,马上开始准备动身前往城市N。原本他可以直接乘飞机直达城市N,然而贫穷使他屈服,他必须选择总花费最少的那条路径。设总共有N座城市(2<=N<=1000),城市编号分别为1,2,3......N。M条航线(1<=M<=2000),每条航线连接两座城市,相互可以到达(无向的)。yintama目前在身在城市1,求最后yintama参加右京女神演唱会所需要的最少花费。(PS:重边考虑一下?)

输入

有多组输入。
第一行输入一个N、M,代表城市的总数,以及航线的总数。
接下来M行,每行输入三个数字u v w,代表城市u、v之间存在航线,机票花费为w。

输出

每行输出一个数,代表yintama参加右京女神演唱会所需的最少花费。

样例输入

5 5
1 2 20
2 3 30
3 4 20
4 5 20
1 5 100

样例输出

90

题解

#include<iostream>
#include<vector>
#include<algorithm>
#define MaxLen 2000
#define Infinity 99999 

using namespace std;

class Map {
private:
	bool* Visit;
	string* node;
	vector<int>** Matrix2;
	int** Matrix;
	int Vexnum;
public:
	void SetMatrix(int N) {
		Vexnum = N;
		Visit = new bool[N];
		node = new string[N];
		Matrix2 = new vector<int>*[N];
		for (int i = 0; i < N; i++)
			Matrix2[i] = new vector<int>[N];
		Matrix = new int*[N];
		for (int i = 0; i < N; i++)
			Matrix[i] = new int[N];
		for (int i = 0; i < Vexnum; i++)
			for (int j = 0; j < Vexnum; j++)
				Matrix2[i][j].push_back(Infinity);
		int M;
		cin >> M;
		while (M--) {
			int u, v, w;
			cin >> u >> v >> w;
			Matrix2[u - 1][v - 1].push_back(w);
			Matrix2[v - 1][u - 1].push_back(w);
		}
		for (int i = 0; i < Vexnum; i++)
			for (int j = 0; j < Vexnum; j++)
				Matrix[i][j] = findmin(Matrix2[i][j]);
	}
	int findmin(vector<int> Matrix2) {
		int min = Matrix2.front();
		for (auto x : Matrix2) {
			if (x < min)
				min = x;
		}
		return min;
	}
	void setVisit() {
		for (int i = 0; i < Vexnum; i++)
			Visit[i] = false;
	}
	void DijAlgorithm() {
		int starti = 0;
		//初始化D,Path,final数组
		int* D = new int[Vexnum];
		bool* final = new bool[Vexnum];
		for (int v = 0; v < Vexnum; v++) {
			D[v] = Matrix[starti][v];
			final[v] = false;
		}
		D[starti] = 0;
		final[starti] = true;
		for (int i = 0; i < Vexnum; i++) {
			int min = Infinity;
			int v = 0;
			for (int w = 0; w < Vexnum; w++) {
				if (!final[w] && D[w] != Infinity)
					if (D[w] < min) {
						v = w;
						min = D[w];
					}
			}
			final[v] = true;
			for (int w = 0; w < Vexnum; w++) {
				if (!final[w] && min + Matrix[v][w] < D[w]) {
					D[w] = min + Matrix[v][w];
				}
			}
		}
		cout << D[Vexnum - 1] << endl;
		delete[]D;
		delete[]final;
	}
};

int main() {
	int N, M;
	while (cin >> N) {
		Map map;
		map.SetMatrix(N);
		map.DijAlgorithm();
	}
	return 0;
}


问题 D: 关键路径-STL版

题目描述

给定有向图无环的边信息,求每个顶点的最早开始时间、最迟开始时间。
// 参考代码

#include <iostream>
#include <vector>
#include <string>
#include <queue>
using namespace std;

class Vertex {
public:
    int indexNo;
    bool hasEnterQueue;
    int early;
    int later;

    Vertex(int indexNo) {
        this->indexNo = indexNo;
        this->hasEnterQueue = false;
        early = -1;
        later = 0x7FFFF;
    }
    void updateEarly(int parentEarly, int edgeValue) {
        int newEarly = parentEarly + edgeValue;
        if (newEarly > this->early)
            this->early = newEarly;
    }
    void updateLater(int childLater, int edgeValue) {
        int newLater = childLater - edgeValue;
        if (newLater < this->later)
            this->later = newLater;
    }
};


class Graph {
public:
    vector<Vertex> vertexes;
    vector<vector<int> > adjMat;
    int n;
public:
    void readVertexes() {
        //TODO: 将顶点数读入成员变量n
        
        //TODO: 从输入初始化vertexes数组
        int i=0;
        for(; i<n; ++i) {
            Vertex v(i);
            this->vertexes.push_back(v);
        }
        
        //为成员变量adjMat创建内存,赋初值
        for(i=0; i<n; ++i) {
            vector<int> row;
            int j=0;
            for(; j<n; ++j) {
                //TODO: 将0增加到row最后
            }
           //TODO: 将row增加到adjMat最后
        }
    }
    void readAdjMatrix() {
        //read the adjacent info into this->adjMat
        int edges;
        cin >> edges;
        int i=0;
        int s, t, w;  //s源顶点编号,t目的顶点编号,w边长
        for(; i<edges; ++i) {
            //TODO: 读入s,t,w,并将adjMat的第s行、第t列的值改为w.
        }
    }

    void updateEarly(int parentNo, queue<int>& earlyQue) {
        int parentEarly = vertexes[parentNo].early;  //读入父结点early值

        int j=0;
        for(; j<n; ++j) {
            int edgeValue = adjMat[parentNo][j];
            if (edgeValue == 0) continue;  //若父结点与结点j没有边相连,pass

            Vertex& child = vertexes[j];
            child.updateEarly(parentEarly, edgeValue); //更新子结点j的early信息

            if(!child.hasEnterQueue) {
                child.hasEnterQueue = true; //将子结点加入队列
                earlyQue.push(j);
            }
        }
    }
    void updateLater(int childNo, queue<int>& laterQue) {
        //TODO:
    }

    int getRoot() {
        //获取入度为0的顶点
        int j=0;
        for(; j<n; ++j) {
            int i=0;
            for(; i<n && adjMat[i][j] == 0; ++i);
            if (i>=n) return j; //j has not any in-edges.
        }
        return -1;  //表示没找到
    }
    int getLeaf() {
        //TODO: 获取出度为0的顶点
    }

    void printEarlyLater(bool isEarly) {
        int i=0;
        for(; i<n; ++i) {
            Vertex& v = vertexes[i];
            if (isEarly)
                cout << v.early << " ";
            else {
                cout << v.later << " ";
            }
        }
        cout << endl;
    }

    void findEarly() {
        //执行关键路径算法,求每个顶点的最早开始时间。
        int r = getRoot();
        Vertex& root = vertexes[r];
        root.hasEnterQueue = true;
        root.early = 0;

        queue<int> que;
        que.push(r);

        while(!que.empty()) {
            int p = que.front();
            que.pop();

            updateEarly(p, que);
        }

        printEarlyLater(true);
    }
    void clearEnterQueue() {
        int i=0;
        for(; i<n; ++i) {
            vertexes[i].hasEnterQueue = false;
        }
    }
    void findLater() {
        //TODO:调用clearEnterQueue,以清除每个顶点的hasEnterQueue=false
        //执行关键路径算法,求每个顶点的最迟开始时间。
    }

    void main() {
        readVertexes();
        readAdjMatrix();
        findEarly();
        findLater();
    }
};


int main() {
    int t=1;
    //cin >> t;
    while (t--) {
        Graph g;
        g.main();
    }
    return 0;
}

输入

第一行图的顶点总数
第二行边的总数
第三行开始,每条边的时间长度,格式为源结点 目的结点 长度

输出

第一行:第个顶点的最早开始时间
第二行:每个顶点的最迟开始时间

样例输入

9
12
0 1 3
0 2 10
1 3 9
1 4 13
2 4 12
2 5 7
3 6 8
3 7 4
4 7 6
5 7 11
6 8 2
7 8 5

样例输出

0 3 10 12 22 17 20 28 33
0 9 10 23 22 17 31 28 33

题解

#include <iostream>
#include <vector>
#include <string>
#include <queue>
using namespace std;

class Vertex {
public:
    int indexNo;
    bool hasEnterQueue;
    int early;
    int later;

    Vertex(int indexNo) {
        this->indexNo = indexNo;
        this->hasEnterQueue = false;
        early = -1;
        later = 0x7FFFF;
    }
    void updateEarly(int parentEarly, int edgeValue) {
        int newEarly = parentEarly + edgeValue;
        if (newEarly > this->early)
            this->early = newEarly;
    }
    void updateLater(int childLater, int edgeValue) {
        int newLater = childLater - edgeValue;
        if (newLater < this->later)
            this->later = newLater;
    }
};


class Graph {
public:
    vector<Vertex> vertexes;
    vector<vector<int> > adjMat;
    int n;
public:
    void readVertexes() {
        //TODO: 将顶点数读入成员变量n
        cin >> n;
        //TODO: 从输入初始化vertexes数组
        int i = 0;
        for (; i < n; ++i) {
            Vertex v(i);
            this->vertexes.push_back(v);
        }

        //为成员变量adjMat创建内存,赋初值
        for (i = 0; i < n; ++i) {
            vector<int> row;
            int j = 0;
            for (; j < n; ++j) {
                //TODO: 将0增加到row最后
                row.push_back(0);
            }
            //TODO: 将row增加到adjMat最后
            adjMat.push_back(row);
        }
    }
    void readAdjMatrix() {
        //read the adjacent info into this->adjMat
        int edges;
        cin >> edges;
        int i = 0;
        int s, t, w;  //s源顶点编号,t目的顶点编号,w边长
        for (; i < edges; ++i) {
            //TODO: 读入s,t,w,并将adjMat的第s行、第t列的值改为w.
            cin >> s >> t >> w;
            adjMat[s][t] = w;
        }
    }

    void updateEarly(int parentNo, queue<int>& earlyQue) {
        int parentEarly = vertexes[parentNo].early;  //读入父结点early值

        int j = 0;
        for (; j < n; ++j) {
            int edgeValue = adjMat[parentNo][j];
            if (edgeValue == 0) continue;  //若父结点与结点j没有边相连,pass

            Vertex& child = vertexes[j];
            child.updateEarly(parentEarly, edgeValue); //更新子结点j的early信息

            if (!child.hasEnterQueue) {
                child.hasEnterQueue = true; //将子结点加入队列
                earlyQue.push(j);
            }
        }
    }
    void updateLater(int childNo, queue<int>& laterQue) {
        //TODO:
        int p = vertexes[childNo].later;        //同理
        int j = 0;
        for (; j < n; ++j)
        {
            int el = adjMat[j][childNo];
            if (el == 0)
                continue;
            Vertex& parent = vertexes[j];
            parent.updateLater(p, el);
            if (!parent.hasEnterQueue)
            {
                parent.hasEnterQueue = true;
                laterQue.push(j);
            }
        }
    }

    int getRoot() {
        //获取入度为0的顶点
        int j = 0;
        for (; j < n; ++j) {
            int i = 0;
            for (; i < n && adjMat[i][j] == 0; ++i);
            if (i >= n) return j; //j has not any in-edges.
        }
        return -1;  //表示没找到
    }
    int getLeaf() {
        //TODO: 获取出度为0的顶点
        int j = 0;
        for (; j < n; ++j)
        {
            int i = 0;
            for (; i < n && adjMat[j][i] == 0; ++i);
            if (i >= n)
                return j;
        }
        return -1;
    }

    void printEarlyLater(bool isEarly) {
        int i = 0;
        for (; i < n; ++i) {
            Vertex& v = vertexes[i];
            if (isEarly)
                cout << v.early << " ";
            else {
                cout << v.later << " ";
            }
        }
        cout << endl;
    }

    void findEarly() {
        //执行关键路径算法,求每个顶点的最早开始时间。
        int r = getRoot();
        Vertex& root = vertexes[r];
        root.hasEnterQueue = true;
        root.early = 0;

        queue<int> que;
        que.push(r);

        while (!que.empty()) {
            int p = que.front();
            que.pop();

            updateEarly(p, que);
        }

        printEarlyLater(true);
    }
    void clearEnterQueue() {
        int i = 0;
        for (; i < n; ++i) {
            vertexes[i].hasEnterQueue = false;
        }
    }
    void findLater() {
        //TODO:调用clearEnterQueue,以清除每个顶点的hasEnterQueue=false
        //执行关键路径算法,求每个顶点的最迟开始时间。
        clearEnterQueue();
        int r = getLeaf();
        Vertex& parent = vertexes[r];
        parent.hasEnterQueue = true;
        parent.later = parent.early;

        queue<int> que;
        que.push(r);

        while (!que.empty())
        {
            int p = que.front();
            que.pop();

            updateLater(p, que);
        }
        printEarlyLater(false);
    }

    void main() {
        readVertexes();
        readAdjMatrix();
        findEarly();
        findLater();
    }
};


int main() {
    int t = 1;
    //cin >> t;
    while (t--) {
        Graph g;
        g.main();
    }
    return 0;
}

0

评论区