数据结构小学期-算法演示程序实验报告(4)

石家庄铁道大学实习报告

if(j>i && x!=100) { y.Next=j; y.Priority=i; y.Weight=x;

Map.push_back(y); } }

sort(Map.begin(),Map.end(),Com); for(i=1;i<=Top;i++) { Father[i]=i; }

int count=0;

cout<<\树的各组成边有：\ for(i=0;i

if(Find(Map[i].Priority)!=Find(Map[i].Next)) { Union(Map[i].Priority,Map[i].Next); count++;

if(Map[i].Priority>Map[i].Next)

cout<

cout<

//----------------------------------------kruskal算法结束

-----------------------------------------------------------// //----------------------------------------floyd算法

-----------------------------------------------------------------// //图的定义

struct F_MGraph {

int *edges[MAX_VALUE]; //边指针

int Vcount, Ecount; //结点个数、边个数 };

//图的创建

void F_Creategraph(F_MGraph *F_MGraph){ cout << \请输入顶点数和边数\

cin >> F_MGraph->Vcount >> F_MGraph->Ecount;

for (int row = 1; row <= F_MGraph->Vcount; row++){ //初始化为无穷,即不连通

for (int col = 1; col <= F_MGraph->Vcount; col++){ F_MGraph->edges[row][col] = MAX_VALUE; } }

16 / 22

石家庄铁道大学实习报告

cout << \请输入起始结点 最终结点 权重\ int row, col, weight;

for (int i = 1; i <= F_MGraph->Ecount; i++){ //赋值 cin >> row >> col >> weight;

F_MGraph->edges[row][col] = weight; } }

//佛洛依德算法

void Floyd(F_MGraph *F_MGraph, int **iArrPath){ for (int i = 1; i <= F_MGraph->Vcount; i++){ for (int j = 1; j <= F_MGraph->Vcount; j++){ iArrPath[i][j] = i; } }

//初始化路径表

for (int k = 1; k <= F_MGraph->Vcount; k++){ for (int i = 1; i <= F_MGraph->Vcount; i++){ for (int j = 1; j <= F_MGraph->Vcount; j++){

if (F_MGraph->edges[i][k] + F_MGraph->edges[k][j] < F_MGraph->edges[i][j]){

F_MGraph->edges[i][j] = F_MGraph->edges[i][k] + F_MGraph->edges[k][j];

iArrPath[i][j] = iArrPath[k][j]; } } } } }

//打印佛洛依德算法最短路径

void PrintResult(F_MGraph *F_MGraph, int **iArrPath){ cout << \起点 ->终点\\t距离\\t\\t最短路径\ for (int i = 1; i <= F_MGraph->Vcount; i++){ for (int j = 1; j <= F_MGraph->Vcount; j++){ if (i != j){

cout << i << \

if (F_MGraph->edges[i][j] == MAX_VALUE){ cout << \无连通路径\ } else{

cout << F_MGraph->edges[i][j] << \ std::stack stackVertices; int k = j; do {

17 / 22

石家庄铁道大学实习报告

k = iArrPath[i][k]; stackVertices.push(k); } while (k != i);

cout << stackVertices.top(); stackVertices.pop();

unsigned int nLength = stackVertices.size();

for (unsigned int nIndex = 0; nIndex < nLength; nIndex++) {

cout << \ stackVertices.pop(); }

cout << \ } } } } }

//调用弗洛伊德相关代码 void show_floyd(){

int *iArrPath[MAX_VALUE];

for (int i = 0; i < MAX_VALUE; i++){ iArrPath[i] = new int[MAX_VALUE]; }

F_MGraph F_MGraph;

for (int i = 0; i < MAX_VALUE; i++){

F_MGraph.edges[i] = new int[MAX_VALUE]; }

F_Creategraph(&F_MGraph); Floyd(&F_MGraph, iArrPath);

PrintResult(&F_MGraph, iArrPath); }

//--------------------------------------------------floyd算法结束------------------------------------------------------------// //--------------------------------------------------Dijkstra算法-------------------------------------------------------------// //定义边表

struct D_Node {

int adjvex; //邻接点域 该边所指向的顶点的位置 int weight; // 数据域 边的权值 D_Node *next; //链域 下一条边的指针 };

// 定义表头结点表

18 / 22

石家庄铁道大学实习报告

struct HeadNode{

int nodeName; //数据域 顶点信息 int inDegree; //数据域 入度

int d; //数据域 表示当前情况下起始顶点至该顶点的最短路径,初始化为无穷大

bool isKnown; //数据域 表示起始顶点至该顶点的最短路径是否已知,true表示已知，false表示未知

int parent; //数据域 表示最短路径的上一个顶点

D_Node *link; //链域 指向第一条依附该顶点的边的指针 };

//创建图函数

void createGraph(HeadNode *G, int nodeNum, int arcNum) {//G表示指向头结点数组的第一个结点的指针 nodeNum表示结点个数 arcNum表示边的个数

cout << \开始创建图(\ //初始化头结点

for (int i = 0; i < nodeNum; i++) {

G[i].nodeName = i+1; //位置0上面存储的是结点v1,依次类推 G[i].inDegree = 0; //入度为0 G[i].link = NULL; //指针置空 }

//给边赋权值

for (int j = 0; j < arcNum; j++) {

int begin, end, weight; //起点 …… 此处隐藏：2340字，全部文档内容请下载后查看。喜欢就下载吧 ……