今天学习了数据结构
练习了最小生成树算法kruskal和最短路径dijkstra和floyd算法
#define MAX 10000000
#include<iostream>
using namespace std;
struct Graph
{
int** arc;
char* vex;
int vexnum;
int arcnum;
};
struct Edge {
int start, end, weight;
};
Edge* createdge(Graph* g) {
Edge* edge = new Edge[g->arcnum];
int count = 0;
for (int i = 0; i < g->vexnum - 1; ++i) {
for (int j = i + 1; j < g->vexnum; ++j) {
if (g->arc[i][j] > 0 && g->arc[i][j] < MAX) {
edge[count].weight = g->arc[i][j];
edge[count].start = i;
edge[count].end = j;
count++;
}
}
}
return edge;
}
void sort(Edge* edge,Graph* g) {
Edge tmp;
for (int i = 0; i < g->arcnum; i++) {
for (int j = 0; j < g->arcnum - i - 1; ++j) {
if (edge[j].weight > edge[j + 1].weight) {
tmp = edge[j];
edge[j] = edge[j + 1];
edge[j + 1] = tmp;
}
}
}
}
void kruskal(Graph* g) {
int* connected = new int[g->vexnum];
Edge* edge = createdge(g);
sort(edge,g);
for (int i = 0; i < g->vexnum; ++i) {
connected[i] = i;
}
for (int i = 0; i < g->vexnum; ++i) {
int v1 = edge[i].start;
int v2 = edge[i].end;
if (connected[v1] != connected[v2]) {
cout << 'v' << g->vex[v1] << "->" << 'v' << g->vex[v2] << ' ' << edge[i].weight << endl;
for (int j = 0; j < g->vexnum; ++j) {
if (connected[j] == connected[v2]) {
connected[j] = connected[v1];
}
}
}
}
}
Graph* creatGraph(int* nums,char* vex,int n){
Graph* g = new Graph;
g->arcnum = 0;
g->arc = new int* [n];
g->vex = new char[n];
g->vexnum = n;
for (int i = 0; i < n; ++i)
{
g->vex[i] = vex[i];
g->arc[i] = new int[n];
for (int j = 0; j < n; ++j) {
g->arc[i][j] = nums[i * n + j];
if (g->arc[i][j] > 0 && g->arc[i][j] < MAX)
{
g->arcnum++;
}
}
}
g->arcnum /= 2;
return g;
}
void Dfs(Graph* g,int start,int* index)
{
cout << g->vex[start]<<" ";
index[start] = 1;
for (int i = 0; i < g->vexnum; ++i) {
for (int j = 0; j < g->vexnum; ++j) {
if (g->arc[i][j] > 0 && g->arc[i][j] < MAX && !index[j]) {
Dfs(g, j, index);
}
}
}
}
int main() {
char a[6] = { '1','2','3','4','5','6'};
int index[6] = { 0 };
int arc[6][6] = {
0,6,1,5,MAX,MAX,
6,0,5,MAX,3,MAX,
1,5,0,5,6,4,
5,MAX,5,0,6,2,
MAX,3,6,MAX,0,6,
MAX,MAX,4,2,6,0
};
Graph* g= creatGraph((int*)arc, a, 6);
kruskal(g);
return 0;
}
#define MAX 10000000
#include<iostream>
using namespace std;
struct Graph
{
int** arc;
char* vex;
int vexnum;
int arcnum;
};
Graph* creatGraph(int* nums, char* vex, int n) {
Graph* g = new Graph;
g->arcnum = 0;
g->arc = new int* [n];
g->vex = new char[n];
g->vexnum = n;
for (int i = 0; i < n; ++i)
{
g->vex[i] = vex[i];
g->arc[i] = new int[n];
for (int j = 0; j < n; ++j) {
g->arc[i][j] = nums[i * n + j];
if (g->arc[i][j] > 0 && g->arc[i][j] < MAX)
{
g->arcnum++;
}
}
}
g->arcnum /= 2;
return g;
}
int getmin(int* s,int* d,int n) {
int min = MAX;
int index = -1;
for (int i = 0; i < n; ++i) {
if (d[i] < min && !s[i] && d[i]) {
min = d[i];
index = i;
}
}
return index;
}
void Dijkstra(Graph* g, int start) {
int* s = new int[g->vexnum];//存储是否加入u1集合
int* p = new int[g->vexnum];//存储d数组集合的前驱节点
int* d = new int[g->vexnum];//存储u1集合到u集合的距离
for (int i = 0; i < g->vexnum; ++i) {
d[i] = g->arc[start][i];
p[i] = start;
s[i] = 0;
}
s[start] = 1;
for (int i = 0; i < g->vexnum; ++i) {
int index = getmin(s,d, g->vexnum);
if (index != -1) {
s[index] = 1;
for (int j = 0; j < g->vexnum; ++j) {
if (d[index] + g->arc[index][j] < d[j]) {
d[j] = d[index] + g->arc[index][j];
p[j] = index;
}
}
}
}
for (int i = 0; i < g->vexnum; ++i) {
cout << s[i] << ' ' << p[i] << ' ' << d[i] << endl;//输出最终三个数组
}
}
void Dfs(Graph* g, int start, int* index)
{
cout << g->vex[start] << " ";
index[start] = 1;
for (int i = 0; i < g->vexnum; ++i) {
for (int j = 0; j < g->vexnum; ++j) {
if (g->arc[i][j] > 0 && g->arc[i][j] < MAX && !index[j]) {
Dfs(g, j, index);
}
}
}
}
int main() {
char a[7] = { '1','2','3','4','5','6','7'};
int index[7] = { 0 };
int arc[7][7] = {
0,12,MAX,MAX,MAX,16,14,
12,0,10,MAX,MAX,7,MAX,
MAX,10,0,3,5,6,MAX,
MAX,MAX,3,0,4,MAX,MAX,
MAX,MAX,5,4,0,2,8,
16,7,6,MAX,2,0,9,
14,MAX,MAX,MAX,8,9,0
};
Graph* g = creatGraph((int*)arc, a, 7);
Dijkstra(g, 0);
return 0;
}
#define MAX 10000000
#include<iostream>
using namespace std;
struct Graph
{
int** arc;
char* vex;
int vexnum;
int arcnum;
};
Graph* creatGraph(int* nums, char* vex, int n) {
Graph* g = new Graph;
g->arcnum = 0;
g->arc = new int* [n];
g->vex = new char[n];
g->vexnum = n;
for (int i = 0; i < n; ++i)
{
g->vex[i] = vex[i];
g->arc[i] = new int[n];
for (int j = 0; j < n; ++j) {
g->arc[i][j] = nums[i * n + j];
if (g->arc[i][j] > 0 && g->arc[i][j] < MAX)
{
g->arcnum++;
}
}
}
g->arcnum /= 2;
return g;
}
void Floyd(Graph* g) {
int** d = new int* [g->vexnum];//记录距离
int** p = new int* [g->vexnum];//记录i到j的前驱
for (int i = 0; i < g->vexnum; ++i) {
d[i] = new int[g->vexnum];
p[i] = new int[g->vexnum];
for (int j = 0; j < g->vexnum; ++j) {
d[i][j] = g->arc[i][j];
p[i][j] = i;
if (i == j || g->arc[i][j]==MAX)
{
p[i][j] = -1;
}
}
}
for (int i = 0; i < g->vexnum; ++i) {
for (int j = 0; j < g->vexnum; ++j) {
for (int k = 0; k < g->vexnum; ++k) {
if (d[j][k] > d[j][i] + d[i][k]) {
p[j][k] = p[i][k];
d[j][k] = d[j][i] + d[i][k];
}
}
}
}
for (int i = 0; i < g->vexnum; ++i) {
for (int j = 0; j < g->vexnum; ++j) {
cout << d[i][j] << ' ';
}
cout << endl;
}
cout << endl;
for (int i = 0; i < g->vexnum; ++i) {
for (int j = 0; j < g->vexnum; ++j) {
cout << p[i][j] << ' ';
}
cout << endl;
}
}
void Dfs(Graph* g, int start, int* index)
{
cout << g->vex[start] << " ";
index[start] = 1;
for (int i = 0; i < g->vexnum; ++i) {
for (int j = 0; j < g->vexnum; ++j) {
if (g->arc[i][j] > 0 && g->arc[i][j] < MAX && !index[j]) {
Dfs(g, j, index);
}
}
}
}
int main() {
char a[4] = { '1','2','3','4'};
int index[4] = { 0 };
int arc[4][4] = {
0,1,MAX,3,
1,0,2,2,
MAX,2,0,8,
3,2,8,0
};
Graph* g = creatGraph((int*)arc, a, 4);
Floyd(g);
return 0;
}