数据结构实验十二 图的遍历及应用

数据结构实验十二 图的遍历及应用

一、【实验目的】

1、 理解图的存储结构与基本操作；

2、熟悉图的深度度优先遍历和广度优先遍历算法

3、掌握图的单源最短路径算法

二、【实验内容】

1.根据下图（图见实验11）邻接矩阵，编程实现该图的深度与广度优先遍历算法，输出遍历序列。

2.单源节点最短路径问题

问题描述:求从有向图的某一结点出发到其余各结点的最短路径。

基本要求:

（1）有向图采用邻接矩阵表示。

（2）单源节点最短路径问题采用Dijkstra算法。

（3）输出有向图中从源结点T到其余各结点的最短路径和最短路径值。

三、实验源代码

//SequenceList.h

typedef struct
{
	ElemType list[MaxSize];
    int size;        
} SequenceList;

//顺序表初始化 
void ListInitialize(SequenceList *L)
{
    L->size = 0;
}

int ListLength(SequenceList L)
{
    return L.size;
}

//顺序表插入操作 
int ListInsert(SequenceList *L, int i, ElemType x)
{
    int j;
    if (L->size >= MaxSize)
    {
        printf("顺序表已满无法插入！\n");
        return 0;
    }
    else if (i < 0 || i > L->size)
    {
        printf("参数i不合法！\n");
        return 0;
    }
    else
    {
        for (j = L->size; j > i; j--)
        {
            L->list[j] = L->list[j-1];
        }
        L->list[i] = x;
        L->size++;
    }
    return 1;
}

int ListDelete(SequenceList *L, int i, ElemType *x)
{
    int j;
    if (L->size <= 0)
    {
        printf("顺序表已空无数据可删！\n");
        return 0;
    }
    else if (i < 0 || i > L->size-1)
    {
        printf("参数i不合法");
        return 0;
    }
    else
    {
        *x = L->list[i];
        for (j = i+1; j < L->size-1; j++) 
        {
            L->list[j-1] = L->list[j];
        }
        L->size--;
        return 1;
    }
}

int ListGet(SequenceList L, int i, ElemType *x)
{
    if (i < 0 || i > L.size-1)
    {
        printf("参数i不合法！\n");
        return 0;
    }
    else
    {
        *x = L.list[i];
        return 1;
    }
}

SequenceQueue.h
//定义循环队列结构体
typedef struct
{
	ElemType queue[MaxQueueSize];
	int rear;
	int front;
	int count;
 } SequenceQueue;

//初始化顺序循环队列 
void QueueInitiate(SequenceQueue *Q)
{
	Q->rear =0;
	Q->front=0;
	Q->count=0; 
}

//判空 
int QueueNotEmpty(SequenceQueue Q)
{
	if(Q.count ==0)
	{
		return 0;
	}
	else
	{
		return 1;
	}
}

//入队 
int QueueAppend(SequenceQueue *Q,ElemType x)
{
	if(Q->count>0&&Q->front==(Q->front+Q->count)%40)
	{
		printf("队列已满无法插入！\n");
		return 0;
	}
	else
	{
		Q->queue[Q->rear] = x;
		Q->rear=(Q->rear+1)%MaxQueueSize;
		Q->count ++;
		
		return 1;
	}
}

//出队 
int QueueDelete(SequenceQueue *Q,int *d)
{
	if(Q->count==0)
	{
		printf("循环队列已空无数据元素出队列！\n");
		return 0;
	}
	else
	{
		*d=Q->queue[Q->front];
		Q->front=(Q->front+1)%MaxQueueSize;
		Q->count--;
		return 1;
	}
}

//12.c
#include<stdio.h>
#include<stdlib.h>
#define MaxSize 100
#define MaxVertices 10
#define MaxEdges 100
#define MaxWeight 10000

#define MaxQueueSize 10

typedef char ElemType;

#include"SequenceList.h" 

typedef struct
{
	SequenceList Vertices;
	int edge[MaxVertices][MaxVertices];
	int numOfEdges;
}MatrixGraph;



typedef struct 
{
	int row;
	int col;
	int weight;
}RCW;

//初始化 
void Initiate(MatrixGraph *G,int n)
{
	int i,j;
	for(i=0;i<n;i++)
	{
		for(j=0;j<n;j++)
		{
			if(i==j)
			{
				G->edge[i][j]=0;
			}
			else
			{
				G->edge[i][j]=MaxWeight;
			}
		}
	}
	G->numOfEdges=0;//边的条数置为0 
	ListInitialize(&G->Vertices);//顺序表初始化 
}

//插入顶点
void InsertVertex(MatrixGraph *G,ElemType vertex)
{
	ListInsert(&G->Vertices,G->Vertices.size,vertex);// 
 } 
 
 //插入边 
 void InsertEdge(MatrixGraph *G,int v1,int v2,int weight)
 {
 	if(v1<0||v1>G->Vertices.size||v2<0||v2>G->Vertices.size)
	{
	 	printf("参数v1或参数v2越界出错！\n");
		return; 
	} 
	G->edge[v1][v2]=weight;
	G->numOfEdges++;
 }

void CreatGraph(MatrixGraph *G,ElemType V[],int n,RCW E[],int e)
{
	int i,k;
	Initiate(G,n);
	for(i=0;i<n;i++)
	{
		InsertVertex(G,V[i]);
	}
	for(k=0;k<e;k++)
	{
		InsertEdge(G,E[k].row,E[k].col,E[k].weight);
	 } 
}

//取第一个邻接顶点
int GetFirstVex(MatrixGraph G,int v,int visited[])
{
	int col;
	if(v<0||v>G.Vertices.size)
	{
		printf("参数v1越界出错！\n");
		return -1;
	}
	for(col=0;col<=G.Vertices.size;col++)
	{
		if(!visited[col])
			if(G.edge[v][col]>0&&G.edge[v][col]<MaxWeight)
			{

				return col;
			}
	}
	return -1;
 } 
 
 //取下一个邻接顶点
 int GetNextVex(MatrixGraph G,int v1,int v2,int visited[])
 {
 	int col;

 	if(v1<0||v1>G.Vertices.size||v2<0||v2>G.Vertices.size)
 	{
 		printf("参数v1或v2越界出错！\n");
 		return -1;
	 }
	 for(col=v2+1;col<=G.Vertices.size;col++)
	 {
		if(!visited[col])
		{
			if(G.edge[v1][col]>0&&G.edge[v1][col]<MaxWeight)
	 		{
	 		return col;
		 	}
		 	
		}
	 }
	 return -1;
  } 

//深度优先遍历
void DepthFSearch(MatrixGraph G,int v,int visited[])
{
	int w;
	printf("%c ",G.Vertices.list[v]);
	visited[v]=1;
	w=GetFirstVex(G,v,visited);
	while(w!=-1) 
	{
		if(!visited[w])
			DepthFSearch(G,w,visited);
		w=GetNextVex(G,v,w,visited);
	}
 } 
 
 //引用顺序队列头文件 
 #include"SequenceQueue.h"
 
 //取第一个邻接顶点
int GetFirstVex2(MatrixGraph G,int v,int visited[])
{
	int col;
	if(v<0||v>G.Vertices.size)
	{
		printf("参数v1越界出错！\n");
		return -1;
	}
	for(col=0;col<=G.Vertices.size;col++)
	{
			if(G.edge[v][col]>0&&G.edge[v][col]<MaxWeight)
			{

				return col;
			}
	}
	return -1;
 } 
 
 //广度优先遍历
 void BroadFSearch(MatrixGraph G,int v,int visited2[])
 {
 	int u,w;
 	SequenceQueue queue;
 	printf("%c ",G.Vertices.list[v]);
 	visited2[v]=1;
 	QueueInitiate(&queue);
 	QueueAppend(&queue,v);
 	while(QueueNotEmpty(queue))
 	{
 		QueueDelete(&queue,&u);//传地址？ 
 
 		w=GetFirstVex2(G,u,visited2);
 		while(w!=-1)
 		{
 			if(!visited2[w])
 			{
 				printf("%c ",G.Vertices.list[w]);
 				visited2[w]=1;
 				QueueAppend(&queue,w);
			 }
			 w=GetNextVex(G,u,w,visited2);
		 }
	 }
  } 
  
//狄克斯特拉算法找最短路径
//带权图G从下标v0顶点到其他顶点的最短距离distance
//和最短路径下标path 
void Dijkstra(MatrixGraph G,int v0,int distance[],int path[]) 
{ 
	int n=G.Vertices.size;
	int *s=(int*)malloc(sizeof(int)*n);
	int minDis,i,j,u;
	for(i=0;i<n;i++)//初始化
	{
		distance[i]=G.edge[v0][i];
		s[i]=0;
		if(i!=v0&&distance[i]<MaxWeight)
			path[i]=v0;
		else
			path[i]=-1;
	 } 
	 s[v0]=1;
	 for(i=1;i<n;i++)
	 {
	 	minDis=MaxWeight;
	 	for(j=0;j<=n;j++)//在还未找到最短路径的顶点集中选有最短距离的顶点u 
	 	{
	 		if(s[j]==0&&distance[j]<minDis)
	 		{
	 			u=j;
	 			minDis=distance[j];
			 }
		 }
		if(minDis==MaxWeight)//当已不存在路径时算法结束 
			return;
		s[u]=1;//标记顶点u已从集合T加入到集合S中 
		for(j=0;j<n;j++)//修改从v0到其他顶点的最短距离和最短路径 
		{
			if(s[j]==0&&G.edge[u][j]<MaxWeight&&distance[u]+G.edge[u][j]<distance[j])
			{
				distance[j]=distance[u]+G.edge[u][j];
				path[j]=u;
			 } 
		 } 
	 }
}

//正序输出最短路径
printfpath(MatrixGraph g1,int path[])
{
	char path2[6];
	int i,j,k;
	for(i=1;i<6;i++)
	{
		printf("\n");
		j=i;
		k=0;
		while(j!=-1)
		{
			path2[k]=g1.Vertices.list[j];
			k++;
			j=path[j];	
		}
		k--;
		printf("%c",path2[k]);
		while(k>0)
		{
			k--;
			printf("->%c",path2[k]);
		}
	 } 
 } 

void main(void)
{
	MatrixGraph g1;
	ElemType a[]={'A','B','C','D','E','F'};
	RCW rcw[]={{0,2,5},{0,3,30},{1,0,2},{1,4,8},{2,1,15},{2,5,7},{4,3,4},{5,3,10},{5,4,18}};
	int n=6,e=9;
	int i,j;
	CreatGraph(&g1,a,n,rcw,e);
	printf("顶点集合为：");
	for(i=0;i<g1.Vertices.size;i++)
	{
		printf("%c  ",g1.Vertices.list[i]);
	 } 
	 printf("\n");
	 printf("邻接矩阵为：\n");
	 for(i=0;i<g1.Vertices.size;i++)
	 {
	 	for(j=0;j<g1.Vertices.size;j++)
	 	{
	 		printf("%5d  ",g1.edge[i][j]);
		}
		printf("\n");
	 }
	printf("深度优先遍历结果为："); 
	int visited[6]={};
	DepthFSearch(g1,0,visited);
	printf("\n");
	int visited2[6]={};
	printf("广度优先遍历结果为：");
	BroadFSearch(g1,0,visited2); 
	printf("\n");
	printf("源结点T到其余各结点的最短路径为：");
	int distance[6];
	int path[6]={-1};
	Dijkstra(g1,0,distance,path);
	printfpath(g1,path);
	printf("\n");
	printf("源结点T到其余各结点的最短路径值为：");
	for(i=0;i<n;i++)
	{
		printf("\n%c->%c:",g1.Vertices.list[0],g1.Vertices.list[i]);
		printf("%d",distance[i]);
	}
}

四、实验结果
在这里插入图片描述

五、实验总结
总结狄克斯特拉算法：
首先，使用 malloc 分配了一个大小为 n 的整型数组 s，用于标记顶点是否已经加入集合 S 中。
然后进行了初始化，初始化了距离数组 distance 和标记数组 s，以及路径数组 path。初始化时，将源顶点 v0 到其他顶点的距离和路径进行了设置。
接下来使用一个循环来依次将未加入集合 S 中的顶点加入，并更新最短路径和最短距离。在每次循环中，首先找到未加入集合 S 中且距离最短的顶点 u，然后将其标记为已加入集合 S 中。
在找到顶点 u 后，再次遍历所有未加入集合 S 中的顶点，更新从源顶点 v0 到其他顶点的最短距离和最短路径。如果通过顶点 u 可以找到更短的路径，就更新距离数组 distance 和路径数组 path。
最终得到的 distance 数组中存储了从源顶点 v0 到各顶点的最短距离，path 数组中存储了相应的最短路径。

本文来自互联网用户投稿，该文观点仅代表作者本人，不代表本站立场。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如若转载，请注明出处：/a/893292.html

如若内容造成侵权/违法违规/事实不符，请联系我们进行投诉反馈qq邮箱809451989@qq.com，一经查实，立即删除！

相关文章

嵌入式开发：STM32 硬件 CRC 使用

嵌入式开发：STM32 硬件 CRC 使用

测试平台&#xff1a;STM32G474系列 STM32硬件的CRC不占用MCU的资源&#xff0c;计算速度快。由于硬件CRC需要配置一些选项&#xff0c;配置不对就会导致计算结果错误&#xff0c;导致使用上没有软件计算CRC方便。但硬件CRC更快的速度在一些有时间资源要求的场合还是非…
阅读更多...
ACM CCS 2024现场直击：引爆通信安全新纪元

ACM CCS 2024现场直击：引爆通信安全新纪元

今天是 ACM CCS 2024即ACM计算机与通信安全会议举办的第四天&#xff01;本届ACM CCS在美国盐湖城召开。从10月14日开始&#xff0c;会议日程紧凑&#xff0c;内容丰富&#xff0c;每一天都充满了精彩的议程和突破性的讨论&#xff0c;为参与者带来了一场知识与灵感的盛宴。 跟…
阅读更多...
自动化测试与敏捷开发的重要性

自动化测试与敏捷开发的重要性

敏捷开发与自动化测试是现代软件开发中两个至关重要的实践&#xff0c;它们相互补充&#xff0c;共同促进了软件质量和开发效率的提升。 敏捷开发的重要性 敏捷开发是一种以人为核心、迭代、循序渐进的软件开发方法。它强调以下几个核心价值观和原则&#xff1a; 个体和交互…
阅读更多...
如何实现MCGS与S7-200SMART PLC以太网多台通信控制？

如何实现MCGS与S7-200SMART PLC以太网多台通信控制？

说到MCGS与S7-200SMART PLC以太网通讯&#xff0c;都是单个单台通讯&#xff0c;如果是多台PLC该如何进行通讯呢&#xff1f;下面就带大家来实现一台MCGS触摸屏如何和两台及以上S7-200SMART PLC进行以太网通讯控制。 一、设备选型 &#xff08;1&#xff09;TPC1570GI触摸屏一…
阅读更多...
【数据结构与算法】LeetCode每日一题

【数据结构与算法】LeetCode每日一题

题目&#xff1a; 解答&#xff1a; 思路第一&#xff0c;什么语言不重要 1.首先&#xff0c;如果是两个正序的&#xff0c;那么我们可以直接两个链表各个位数相加&#xff0c;但是有一个问题&#xff0c;如果有个数是两位数&#xff0c;另一个位是三位数&#xff0c;那个两位…
阅读更多...
shell脚本宝藏仓库（基础命令、正则表达式、shell基础、变量、逻辑判断、函数、数组）

shell脚本宝藏仓库（基础命令、正则表达式、shell基础、变量、逻辑判断、函数、数组）

一、shell概述 1.1 shell是什么 Shell是一种脚本语言 脚本&#xff1a;本质是一个文件&#xff0c;文件里面存放的是特定格式的指令&#xff0c;系统可以使用脚本解析器、翻译或解析指令并执行&#xff08;shell不需要编译&#xff09; Shell既是应用程序又是一种脚本语言&…
阅读更多...
ES6扩展运算符

ES6扩展运算符

1.介绍&#xff1a; ... 扩展运算符能将数组转换为逗号分隔的参数序列&#xff1b; 扩展运算符&#xff08;spread&#xff09;也是三个点&#xff08;...&#xff09;。它好比 rest 参数的逆运算&#xff0c;将一个数组转为用逗号分隔的 参数序列&#xff0c;对数组进…
阅读更多...
Morris算法（大数据作业）

Morris算法（大数据作业）

我只能说&#xff0c;概率证明真的好难啊&#xff01;(&#xff1b;′⌒) 这也证明我的概率论真的学的很差劲&#xff0c;有时间一定要补补/(ㄒoㄒ)/~~ 算法不难证明难&#xff01; 当一个数足够大时&#xff0c;能不能用更少的空间来近似表示这个整数n&#xff0c;于是&…
阅读更多...
用Java爬虫API，轻松获取电商商品SKU信息

用Java爬虫API，轻松获取电商商品SKU信息

在电子商务的精细化运营时代&#xff0c;SKU信息的重要性不言而喻。SKU&#xff08;Stock Keeping Unit&#xff09;信息不仅包含了商品的规格、价格、库存等关键数据&#xff0c;还直接影响到库存管理、价格策略和市场分析等多个方面。如何高效、准确地获取这些信息&#xff0…
阅读更多...
卸载Python

卸载Python

1、查看安装框架位置并删除 Sudo rm -rf /Library/Developer/CommandLineTools/Library/Frameworks/Python3.framework/Versions/3.8 2、查看应用并删除 在 /Applications/Python 3.x 看是否存在&#xff0c;如果存在并删除。 3、删除软连接 ls -l /usr/bin/py* 或 ls -…
阅读更多...
闯关leetcode——110. Balanced Binary Tree

闯关leetcode——110. Balanced Binary Tree

大纲 题目地址内容 解题代码地址 题目 地址 https://leetcode.com/problems/balanced-binary-tree/description/ 内容 Given a binary tree, determine if it is height-balanced. A height-balanced binary tree is a binary tree in which the depth of the two subtrees…
阅读更多...
系统内核分析工具

系统内核分析工具

工具下载地址&#xff1a;系统内核分析工具-32位64位资源-CSDN文库
阅读更多...
PyQt5高级界面控件一

PyQt5高级界面控件一

如何查看widget类及其子类有哪些属性和函数&#xff1a; dir() from PyQt5.QtWidgets import QWidget dir(QWidget)help() from PyQt5.QtWidgets import QWidget help(QWidget)表格与树 表格与树解决的问题是如何在一个控件种有规律地呈现更多的数据。PyQt提供了两种控件类用…
阅读更多...
初识git · 有关模型

初识git · 有关模型

目录 前言&#xff1a; 有关开发模型 前言&#xff1a; 其实文章更新到这里的时候&#xff0c;我们已经学习了可以满足我们日常生活中的基本需求的指令了&#xff0c;但是为什么要更新本篇文章呢&#xff1f;是因为实际生活中我们对于开发工作&#xff0c;运维工作&#xff…
阅读更多...
RISC-V笔记——显式同步

RISC-V笔记——显式同步

1. 前言 RISC-V的RVWMO模型主要包含了preserved program order、load value axiom、atomicity axiom、progress axiom和I/O Ordering。今天主要记录下preserved program order(保留程序顺序)中的Explicit Synchronization(显示同步)。 2. 显示同步 显示同步指的是&#xff1a…
阅读更多...
网络空间指纹：新型网络犯罪研判的关键路径

网络空间指纹：新型网络犯罪研判的关键路径

前言 新型网络犯罪是指利用计算机技术和互联网平台进行犯罪活动的一类犯罪行为。它涵盖了一系列使用网络和数字技术进行非法活动的行为&#xff0c;如网络钓鱼、网络诈骗、恶意软件攻击、黑客入侵、数据泄露、网络色情和社交网络犯罪等。 随着当前打击治理新型网络犯罪博弈态…
阅读更多...
idea中，git提交时忽略某些本地修改.将文件从git暂存区移除

idea中，git提交时忽略某些本地修改.将文件从git暂存区移除

我们有时候在本地调试代码时&#xff0c;某些配置文件需要修改成本地环境中。当改完后&#xff0c;需要提交代码时&#xff0c;这些文件又不能推到git上。如下图&#xff1a; 当出现这种情况&#xff0c;我们每次都需要手动去将不需要提交的文件的对号去掉。文件多了后&#x…
阅读更多...
dlib库-人脸检测

dlib库-人脸检测

文章目录 一、介绍二、与OpenCv对比三、dlib库安装1.直接安装2.dlib库whl文件进行安装 四、代码实现五、总结 一、介绍 dlib库是一个适用于C和Python的第三方库。包含机器学习、计算机视觉和图像处理的工具包&#xff0c;被广泛的应用于机器人、嵌入式设备、移动电话和大型高性…
阅读更多...
STM32L031F6P6基于CubeMX的串口通信调试笔记

STM32L031F6P6基于CubeMX的串口通信调试笔记

用CubeMX创建项目 本实例用的PA14、PA13两个引脚&#xff0c;LPUART1。 对串口参数进行设置&#xff1a; 开启串口中断&#xff1a; 时钟源设置成内部高频时钟&#xff1a; 对项目进行设置&#xff1a; 生成代码&#xff1a; 在串口初始化函数中加入 __HAL_UART_ENA…
阅读更多...
wps图标没有坐标轴标题怎么办？wps表格不能用enter下怎么办？

wps图标没有坐标轴标题怎么办？wps表格不能用enter下怎么办？

目录 wps图标没有坐标轴标题怎么办 一、在WPS PPT中添加坐标轴标题 二、在WPS Excel中添加坐标轴标题 wps表格不能用enter下怎么办 一、检查并修改设置 二、检查单元格保护状态 三、使用快捷键实现换行 wps图标没有坐标轴标题怎么办 一、在WPS PPT中添加坐标轴标题 插入…
阅读更多...
最新文章

Copyright @ 2022~2023