数据结构实验三 图的应用知识讲解

三元图的原理三元图是一种常用的逻辑推理工具，它通过表示事物之间的关系和相互作用，帮助我们理解和解释事物的本质和发展趋势。

三元图由三个部分组成，分别是主题、因素和结果。

主题是我们要研究的对象或问题，因素是影响主题的各种因素，结果是主题在这些因素作用下的表现或发展趋势。

三元图的原理主要包括以下几个方面：关系分析、因果推理、系统思维和综合分析。

首先，三元图通过关系分析来理清主题与因素之间的关系。

在三元图中，主题和因素通过有向边连接起来，边上的箭头指示了因素对主题的影响方向。

这样的表示方式有助于我们直观地了解主题和因素之间的关系，以及它们之间的相互作用。

其次，三元图通过因果推理来揭示主题与因素之间的因果关系。

因果推理是指通过观察事物的发展过程和结果，推断其发生的原因和机制。

在三元图中，结果和因素之间的连接关系可以帮助我们推断因素对结果的影响程度和方式。

这种因果推理的过程有助于我们深入理解主题与因素之间的因果关系，从而找到解决问题的方法和策略。

第三，三元图运用系统思维来分析主题与因素的复杂关系。

系统思维是一种将问题看作整体系统，理解其各个部分之间相互作用和联动关系的思维方式。

三元图的主题、因素和结果三个部分构成了一个相互关联的系统，通过对系统整体特征和内在机制的分析，可以帮助我们全面把握主题与因素之间的关系，找到潜在的驱动因素和发展规律。

最后，三元图通过综合分析来全面评估主题与因素的影响和结果的表现。

综合分析是指将多个因素综合考虑，全面评估其对主题的影响和结果的表现。

在三元图中，不同的因素通过边的连接关系形成一个网络，我们可以通过对这个网络进行综合分析，综合考虑各个因素的重要性、相互关系和组合效应，进而得出对主题的评估和预测。

综上所述，三元图通过关系分析、因果推理、系统思维和综合分析等原理，帮助我们理解和解释事物的本质和发展趋势。

它是一种重要的逻辑推理工具，在科学研究、决策分析和问题解决等领域有着广泛的应用。

数据结构实验报告图的遍历讲解一、引言在数据结构实验中，图的遍历是一个重要的主题。

图是由顶点集合和边集合组成的一种数据结构，常用于描述网络、社交关系等复杂关系。

图的遍历是指按照一定的规则，挨次访问图中的所有顶点，以及与之相关联的边的过程。

本文将详细讲解图的遍历算法及其应用。

二、图的遍历算法1. 深度优先搜索（DFS）深度优先搜索是一种常用的图遍历算法，其基本思想是从一个顶点出发，沿着一条路径向来向下访问，直到无法继续为止，然后回溯到前一个顶点，再选择此外一条路径继续访问。

具体步骤如下：（1）选择一个起始顶点v，将其标记为已访问。

（2）从v出发，选择一个未被访问的邻接顶点w，将w标记为已访问，并将w入栈。

（3）如果不存在未被访问的邻接顶点，则出栈一个顶点，继续访问其它未被访问的邻接顶点。

（4）重复步骤（2）和（3），直到栈为空。

2. 广度优先搜索（BFS）广度优先搜索是另一种常用的图遍历算法，其基本思想是从一个顶点出发，挨次访问其所有邻接顶点，然后再挨次访问邻接顶点的邻接顶点，以此类推，直到访问完所有顶点。

具体步骤如下：（1）选择一个起始顶点v，将其标记为已访问，并将v入队。

（2）从队首取出一个顶点w，访问w的所有未被访问的邻接顶点，并将这些顶点标记为已访问，并将它们入队。

（3）重复步骤（2），直到队列为空。

三、图的遍历应用图的遍历算法在实际应用中有广泛的应用，下面介绍两个典型的应用场景。

1. 连通分量连通分量是指图中的一个子图，其中的任意两个顶点都是连通的，即存在一条路径可以从一个顶点到达另一个顶点。

图的遍历算法可以用来求解连通分量的个数及其具体的顶点集合。

具体步骤如下：（1）对图中的每一个顶点进行遍历，如果该顶点未被访问，则从该顶点开始进行深度优先搜索或者广度优先搜索，将访问到的顶点标记为已访问。

（2）重复步骤（1），直到所有顶点都被访问。

2. 最短路径最短路径是指图中两个顶点之间的最短路径，可以用图的遍历算法来求解。

实验四 图的的操作及应用实验课程名： 图的的操作及应用专业班级： 11计科（1） 学 号： 姓 名：实验时间： 2012. 12.11 实验地点： 指导教师：一、实验目的1、理解图的基本概念及术语；2、掌握图的两种存储结构(邻接矩阵和邻接表)的表示方法；3、熟练掌握图的两种遍历(深度优先搜索遍历和广度优先搜索遍历)的算法思想、步骤，并能列出在两种存储结构上按上述两种遍历算法得到的序列；4、理解最小生成树的概念，能按Prim算法构造最小生成树；领会并掌握拓扑排序、关键路径、最短路径的算法思想。

二、实验的内容和步骤1、构造图的邻接矩阵存储结构或邻接表存储结构。

代码：# include <iostream.h># include <malloc.h># include <conio.h># define INFINITY 1000# define MAX_VERTEX_NUM 20# define OK 1#define STARTS "********************************"typedef enum{DG,DN,UDG,UDN} GraphKind;typedef int EType;typedef int InfoType;typedef int VertexType;typedef struct ArcCell //define structure MGraph{ EType adj;InfoType *info;}ArcCell,AdjMatrix[MAX_VERTEX_NUM][MAX_VERTEX_NUM];typedef struct{ VertexType vexs[MAX_VERTEX_NUM];AdjMatrix arcs;int vexnum,arcnum;GraphKind kind;}MGraph;int CreatUDN(MGraph &G) //CreatUDN() sub-function{int IncInfo,i,j,k,v1,v2,w;cout<<endl<<"Please input the number of G.vexnum (eg,G.vexnum=4): ";cin>>G.vexnum; //input the number of vexcout<<"Please input the number of G.arcnum (eg,G.arcnum=4): ";cin>>G.arcnum; //input the number of arc: ";cout<<"Please input IncInfo (0 for none)cin>>IncInfo;for(i=0;i<G.vexnum;++i)for(j=0;j<G.vexnum;++j){ G.arcs[i][j].adj=INFINITY; //initial G.arcs[i][j].adj//initial G.arcs[i][j].infoG.arcs[i][j].info=NULL;}cout<<"Plese input arc(V1-->V2), For example: (V1=1,V2=3),(V1=2,V2=4)..."<<endl;for(k=0;k<G.arcnum;++k) //input arc(v1,v2){cout<<endl<<"Please input the "<<k+1<<"th arc's v1 (0<v1<G.vexnum) :";cin>>v1; //input v1cout<<"Please input the "<<k+1<<"th arc's v2 (0<v2<G.vexnum) :";cin>>v2; //input v2:";cout<<"Please input the "<<k+1<<"th arc's weightcin>>w; //input weighti=v1;j=v2;//if (v1,v2) illegal,againwhile(i<1||i>G.vexnum||j<1||j>G.vexnum){cout<<"Please input the "<<k+1<<"th arc's v1 (0<v1<G.vexnum) :";cin>>v1;cout<<"Please input the "<<k+1<<"th arc's v2 (0<v1<G.vexnum) :";cin>>v2;:";cout<<"Please input the "<<k+1<<"th arc's weightcin>>w;i=v1;j=v2;} //while endi--;j--;G.arcs[i][j].adj=G.arcs[j][i].adj=w; //weightcout<<"G.arcs["<<i+1<<"]["<<j+1<<"].adj="<<"G.arcs["<<j+1<<"]["<<i+1<<"].adj="<<w<<e ndl;if(IncInfo){ cout<<"Please input the "<<k+1<<"th arc's Info :";cin>>*G.arcs[i][j].info;}} //for endreturn (OK);} //CreatUDN() end打印邻接矩阵void Gprintf(MGraph G) //{cout<<"邻接矩阵数组为：\n";for(int i=0;i<G.vexnum;i++){for(int k=0;k<G.vexnum;k++)cout<<G.arcs[i][k].adj<<"\t";cout<<endl;}}/*邻接表*/typedef struct ArcNode //define structure ALGraph{ int adjvex;struct ArcNode *nextarc;InfoType *info;}ArcNode;typedef struct VNode{ VertexType data;ArcNode *firstarc;}VNode,AdjList[MAX_VERTEX_NUM];typedef struct{ AdjList vertices;int vexnum,arcnum;int kind;}ALGraph;int CreateDG(ALGraph &G) //CreateDG() subfunction{ int IncInfo,i,j,k,v1,v2,w;cout<<endl<<"Please input the number of G.vexnum (eg,G.vexnum=4): "; cin>>G.vexnum; //input the number of vexcout<<"Please input the number of G.arcnum (eg,G.arcnum=4): ";cin>>G.arcnum; //input the numbe of arc: ";cout<<"Please input the number of IncInfo (0 for none)cin>>IncInfo; //if no information, input 0for(i=0;i<G.vexnum;++i){ G.vertices[i].data=i; //initial G.vertices[i].data//initial G.vertices[i].firstarcG.vertices[i].firstarc=NULL;}cout<<"Plese input arc(V1-->V2), For example: (V1=1,V2=3),(V1=2,V2=4)..."<<endl; for(k=0;k<G.arcnum;++k) //input arc(v1,v2){ cout<<endl<<"Please input the "<<k+1<<"th arc's v1 (0<v1<G.vexnum): ";cin>>v1;cout<<"Please input the "<<k+1<<"th arc's v2 (0<v2<G.vexnum0: ";cin>>v2;i=v1;j=v2;while(i<1||i>G.vexnum||j<1||j>G.vexnum) //if (v1,v2) illegal{ cout<<endl<<"Please input the "<<k+1<<"th arc's v1 (0<v1<G.vexnum): ";cin>>v1;cout<<"Please input the "<<k+1<<"th arc's v2 (0<v2<G.vexnum): ";cin>>v2;i=v1;j=v2;} //while endi--;j--;ArcNode *p;p=(ArcNode *)malloc(sizeof(ArcNode)); //allocate memoryif(!p){ cout<<"Overflow!";return (0);}p->adjvex=j; //assign p->adjvexp->nextarc=G.vertices[i].firstarc;p->info=NULL;G.vertices[i].firstarc=p;if(IncInfo){ cout<<"Please input the info :";//input informationcin>>*(p->info);}} //for endreturn (OK);} //CreateDG() endint main(){MGraph MG;ALGraph AG;int a=-1;while(a!=0){cout<<STARTS<<STARTS<<endl;cout<<"1)邻接矩阵(无向网)\t"<<"2)邻接表(有向图)\t"<<"3)退出"<<endl;cout<<"选择存储方式:";cin>>a;switch(a){case 1: {CreatUDN(MG);Gprintf(MG);break;}case 2: CreateDG(AG);break;case 3: a=0;break;选择错误\n"<<endl;default:cout<<"}}return 0;}运行结果：2.按照建立一个带权有向图的操作需要，编写在邻接矩阵或邻接表存储结构下，带权有向图基本操作的实现函数（如初始化图、在图中插入一个结点、在图中插入一条边、在图中寻找序号为v的结点的第一个邻接结点、在图中寻找序号为v1结点的邻接结点v2的下一个邻接结点、图的深度优先遍历、图的广度优先遍历等）。

中原工学院《数据结构》实验报告学院：计算机学院专业：计算机科学与技术班级：计科112姓名：康岩岩学号：201100814220 指导老师：高艳霞2012-11-22实验五图的基本操作一、实验目的1、使学生可以巩固所学的有关图的基本知识。

2、熟练掌握图的存储结构。

3、熟练掌握图的两种遍历算法。

二、实验内容[问题描述]对给定图，实现图的深度优先遍历和广度优先遍历。

[基本要求]以邻接表为存储结构，实现连通无向图的深度优先和广度优先遍历。

以用户指定的结点为起点，分别输出每种遍历下的结点访问序列。

【测试数据】由学生依据软件工程的测试技术自己确定。

三、实验前的准备工作1、掌握图的相关概念。

2、掌握图的逻辑结构和存储结构。

3、掌握图的两种遍历算法的实现。

四、实验报告要求1、实验报告要按照实验报告格式规范书写。

2、实验上要写出多批测试数据的运行结果。

3、结合运行结果，对程序进行分析。

【设计思路】【代码整理】#include "stdafx.h"#include <iostream>#include <malloc.h>using namespace std;typedef int Status;#define OK 1#define ERROR 0#define OVERFLOW -1#define MAX_SIZE 20typedef enum{DG,DN,UDG,UDN}Kind;typedef struct ArcNode{int adjvex; //顶点位置struct ArcNode *nextarc; //下一条弧int *info; //弧信息};typedef struct{char info[10]; //顶点信息ArcNode *fistarc; //指向第一条弧}VNode,AdjList[MAX_SIZE];typedef struct{AdjList vertices;int vexnum,arcnum; //顶点数，弧数int kind; //图的种类，此为无向图}ALGraph;//这是队列的节点，仅用于广度优先搜索typedef struct Node{int num;struct Node* next;};//队列的头和尾typedef struct{Node * front;Node *rear;}PreBit;int LocateV ex(ALGraph G,char info[]);//定位顶点的位置Status addArcNode(ALGraph &G,int adjvex); //图中加入弧Status CreatGraph(ALGraph&G);//创建图的邻接表Status DFSTraverse(ALGraph G);//深度优先搜索Status BFSTraverse(ALGraph G);//广度优先搜索Status DFS(ALGraph G,int v);//深度优先搜索中的数据读取函数，用于递归bool visited[MAX_SIZE]; // 访问标志数组//初始化队列Status init_q(PreBit&P_B){P_B.front=P_B.rear=(Node*)malloc(sizeof(Node));if(!P_B.front){exit(OVERFLOW);}P_B.front->next=NULL;}//将数据入队Status en_q(PreBit & P_B,int num){Node *p=(Node*)malloc(sizeof(Node));if(!p){exit(OVERFLOW);}p->num=num;p->next=NULL;P_B.rear->next=p;P_B.rear=p;return OK;}//出队Status de_q(PreBit & P_B){if(P_B.front==P_B.rear){return ERROR;}Node* p=P_B.front->next;P_B.front->next=p->next;if(P_B.rear==p){P_B.rear=P_B.front;}free(p);return OK;}Status CreatGraph(ALGraph&G){cout<<"请输入顶点数目和弧数目"<<endl;cin>>G.vexnum>>G.arcnum;//依次输入顶点信息for(int i=0;i<G.vexnum;i++){cout<<"请输入顶点名称"<<endl;cin>>G.vertices[i].info;G.vertices[i].fistarc=NULL;}//依次输入弧信息for(int k=1;k<=G.arcnum;k++){char v1[10],v2[10]; //用于表示顶点名称的字符数组int i,j; //表示两个顶点的位置BACK: //返回点cout<<"请输入第"<<k<<"条弧的两个顶点"<<endl;cin>>v1>>v2;i=LocateV ex(G,v1); //得到顶点v1的位置j=LocateV ex(G,v2); //得到顶点v2的位置if(i==-1||j==-1){ //头信息不存在则返回重输cout<<"不存在该节点!"<<endl;goto BACK; //跳到BACK 返回点}addArcNode(G,i); //将弧的顶点信息插入表中addArcNode(G,j);}return OK;}//倒序插入弧的顶点信息Status addArcNode(ALGraph &G,int adjvex){ArcNode *p; //弧节点指针p=(ArcNode*)malloc(sizeof(ArcNode));p->adjvex=adjvex;p->nextarc=G.vertices[adjvex].fistarc;//指向头结点的第一条弧G.vertices[adjvex].fistarc=p; //头结点的第一条弧指向p，即将p作为头结点的第一条弧return OK;}//定位顶点的位置int LocateV ex(ALGraph G,char info[]){for(int i=0;i<G.vexnum;i++){if(strcmp(G.vertices[i].info,info)==0){ //头结点名称与传入的信息相等，证明该头节点存在return i; //此时返回位置}}return -1;}//深度优先搜索Status DFSTraverse(ALGraph G){for(int v=0;v<G.vexnum;v++){visited[v]=false;}char v1[10];int i;BACK:cout<<"请输入首先访问的顶点"<<endl;cin>>v1;i=LocateV ex(G,v1);if(i==-1){cout<<"不存在该节点!"<<endl;goto BACK;}DFS(G,i);return OK;}//深度优先搜索递归访问图Status DFS(ALGraph G,int v){visited[v]=true;cout<<G.vertices[v].info<<" ";//输出信息ArcNode *p;p=G.vertices[v].fistarc; //向头节点第一条while(p) //当弧存在{if(!visited[p->adjvex]){DFS(G,p->adjvex); //递归读取}p=p->nextarc;}return OK;}//广度优先搜索Status BFSTraverse(ALGraph G){for(int v=0;v<G.vexnum;v++){visited[v]=false;}char v1[10];int v;BACK:cout<<"请输入首先访问的顶点"<<endl;cin>>v1;v=LocateV ex(G,v1);if(v==-1){cout<<"不存在该节点!"<<endl;goto BACK;}PreBit P_B;init_q(P_B);ArcNode *p;visited[v]=true;cout<<G.vertices[v].info<<" ";//输出信息en_q(P_B,v); //将头位置v入队while(P_B.front!=P_B.rear){//当队列不为空时，对其进行访问int w=P_B.front->next->num;//读出顶点位置de_q(P_B);//顶点已经访问过，将其出队列p=G.vertices[w].fistarc;//得到与顶点相关的第一条弧while(p){if(!visited[p->adjvex]){en_q(P_B,p->adjvex);//将弧入队，但不读取，只是将其放在队尾}p=p->nextarc;}}return OK;}int _tmain(int argc, _TCHAR* argv[]){ALGraph G;CreatGraph(G);cout<<"深度优先搜索图:"<<endl;DFSTraverse(G);cout<<endl;cout<<"广度优先搜索图:"<<endl;BFSTraverse(G);cout<<endl;system("pause");return 0;}。

实验七图结构及其应用一、实验目的1.掌握图类的邻接矩阵存储结构的实现；2.掌握图的基本操作，包括图的建立、广度优先遍历和深度优先遍历算法；3.掌握求最短路径的Dijkastra算法。

二、实验要求1.复习课本中第7章关于图的相关知识内容；2.用C+叫言完成算法和程序设计并且调试通过；三、实验题目与要求1.图的遍历详细描述：利用以提供的源程序素材，实现对不多于30个结点的图的建立以及广度优先和深度优先遍历算法。

具体功能要求：从键盘中输入网中顶点的个数，以及顶点的数据值，并以顶点的输入次序作为顶点的编号输入顶点与顶点之间的邻接边的权值（注:若为无向图，则每条边可由两条方向相反的有向边构成）；若无边相连则已设定的权值最大值MaxWeight=100O弋替。

利用顶点与边的信息建立网的邻接矩阵，并第一个输入的顶点为原点对网进行深度优先和广度优先遍历，并输入遍历的顶点序列。

例：如下图7-1图所示，则输入为：6ABCDEF18A B 34A E 12B A 34B C 46B F 19C B 46C D 17C F 25D C 17D E 38D F 25E A 12E D 38E F 26F B 19F D 25F C 25F E 26在提供的程序模板中，完成以下函数，实现上述功能；(1)DFSTraverse (MGraph G)功能描述：对网进行深度优先遍历，网可以非连通(2)BFSTraverse (MGraph G)功能描述：对网进行广度优先遍历，网可以非连通2.最短路径求解详细描述：在第一题的基础上，Dijkastra算法求解从第A个顶点到其余各个顶点的最短路径的所经过的顶点以及路径的长度。

例：如图7-1所示，则该求出顶点A0其余个顶点的最短路径所经过的顶点，以及路径的长度；输出如下所示：A->B: A B 34A->C: A E F C 63A->D: A E D 50A->E: A E 12A->F: A E F 38在提供的程序模板中，完成以下函数，实现上述功能;void dijkstra(MGraph G, int vs )3.验证练习先对下图7-2和7-3进行深度和广度优先遍历，并求出以A作为源点求最短路径的结果。

数据结构图数据结构图1·概述数据结构是计算机科学中的重要概念之一，用于组织和管理数据的方式。

图是一种常见的数据结构，它由节点和边组成，用来表示不同实体之间的关系。

本文将详细介绍图的基本概念、表示方法以及常见的图算法。

2·图的基本概念2·1 节点（顶点）节点是图的基本单元，用来表示实体或对象。

每个节点可以有一个或多个相连的边。

2·2 边边是节点之间的连接线，用来表示不同节点之间的关系。

边可以是有向的或无向的。

2·3 有向图与无向图有向图中的边有方向性，表示一个节点到另一个节点的单向连接关系。

无向图中的边没有方向性，表示两个节点之间的双向连接关系。

2·4 权重图中的边可以带有权重，用来表示节点之间的距离或代价。

3·图的表示方法3·1 邻接矩阵邻接矩阵是使用二维数组表示图的方法。

数组的行与列表示节点，矩阵中的元素表示节点之间的连接关系或权重。

3·2 邻接表邻接表是使用链表表示图的方法。

每个节点使用一个链表存储与之相连的节点。

4·常见的图算法4·1 深度优先搜索（DFS）深度优先搜索是一种遍历图的方法，从一个起始节点开始，沿着一条路径一直深入到没有未访问过的节点，然后返回并尝试其他路径。

4·2 广度优先搜索（BFS）始，首先访问其相邻节点，然后依次访问相邻节点的相邻节点，以此类推，直到访问完所有节点。

4·3 最短路径算法最短路径算法用于查找图中两个节点之间的最短路径。

常见的最短路径算法有迪杰斯特拉算法和弗洛伊德算法。

4·4 最小树算法最小树算法用于在连通图中找到一棵包含所有节点的树，并且树的边权重之和最小。

常见的最小树算法有普里姆算法和克鲁斯卡尔算法。

附件: 无法律名词及注释:●邻接矩阵：图的表示方法之一，使用二维数组表示节点之间的连接关系。

●邻接表：图的表示方法之一，使用链表表示节点之间的连接关系。

辽宁师范大学上机实验报告计算机与信息技术学院计算机科学与技术专业课程名称：数据结构—用C语言描述实验题目：图的存储结构及各种运算的实现班级：2010级6班学号：********************指导教师：黄*完成时间：2011.11.11一．实验目的：1、掌握图的逻辑结构及其常用的存储表示方法，建立图的邻接表与邻接矩阵。

2、熟练掌握图的深度与广度优先搜索算法的基本思想，能在不同存储结构上实现算法。

3、深入理解最小生成树的定义，掌握Prim算法和Kruskar算法构造最小生成树的基本思想，并实现Prim算法。

4、掌握用DIJKSTTRA算法求解单源最短路径的基本过程和算法。

三．实验内容及要求：1、建立图的邻接表与邻接矩阵，并在不同存储结构上实现深度与广度优先搜索算法。

2、用Prim算法构造带权网络的最小生成树。

3、用DIJKSTTRA算法求解单源最短路径。

选做部分：4、求拓朴序列和关键路径。

四．概要设计：第一题：（1）输入顶点信息：a b c d顶点对序号为：1 0；2 0；2 1；3 0；3 1；DFSL序列为（起点序号为1）：b d a cBFSL序列为（起点序号为0）：a d c b(2) 输入顶点信息：a b c d顶点对序号为：1 0；2 0； 2 1；3 0；3 1；邻接矩阵为：a b c da 0 1 1 1b 1 0 1 1c 1 1 0 0d 1 1 0 0DFS序列为（起点序号为1）：b a c dBFS序列为（起点序号为2）：c a b d第二题：输入顶点信息：a b c d e f顶点对序号及权值：0 1 6；0 2 1；0 3 5；1 4 3；1 2 5；2 4 5；2 5 4；3 5 2；4 5 6；2 3 7；最小生成树：1—>3：13—>6：46—>4：23—>5：55—>2：3第三题：输入的顶点信息：1 2 3 4 5输入的顶点对和权值：0 1 10；0 3 30；0 4 100；1 2 50；2 4 10；3 2 20；3 4 60 起始结点：4单元最短路径：max 1max 220 3<—40 430 5<—3<—4DIJKSTRA动态执行情况循环红点集S K+1 D[0]~D[4] P[0]~P[4] 初始化{4} —max max 20 0 60 0 0 4 0 41 {4,3} 3 max max 20 0 30 0 0 4 0 32 {4,3,5} 2 max max 20 0 30 0 0 4 0 33 {4,3,5,1} 1 max max 20 0 30 0 04 0 34 {4,3,5,1} 2 max max 20 0 30 0 0 4 0 3 五．实验结果分析及程序代码：第一题邻接表#include<stdio.h>#include<malloc.h>#define true 1#define false 0#define max 60#define n 4#define e 5typedef struct node{int adjvex;struct node *next;}edgenode;typedef struct{char vertex;edgenode *link;}vexnode;vexnode ga[n];int visited[max];int q[max];creatadjlist(vexnode ga[]){int i,j,k;edgenode *s;printf("请输入顶点信息:\n");for(i=0;i<n;i++){ga[i].vertex=getchar();ga[i].link=NULL;}printf("请输入顶点对的序号:\n");for(k=0;k<e;k++){scanf("%d%d",&i,&j);s=malloc(sizeof(edgenode));s->adjvex=j;s->next=ga[i].link;ga[i].link=s;s=malloc(sizeof(edgenode));s->adjvex=i;s->next=ga[j].link;ga[j].link=s;}}DFSL(int i){edgenode *p;printf("node:%c\n",ga[i].vertex);visited[i]=1;p=ga[i].link;while(p!=NULL){if(!visited[p->adjvex])DFSL(p->adjvex);p=p->next;}}BFSL(int k){int i;edgenode *p;int rear,front;front=-1;rear=-1;printf("node:%c\n",ga[k].vertex);visited[k]=1;rear++;q[rear]=k;while(front!=rear){front++;i=q[front];p=ga[i].link;while(p!=NULL){if(!visited[p->adjvex]){printf("node:%c\n",ga[p->adjvex].vertex);visited[p->adjvex]=1;rear++;q[rear]=p->adjvex;}p=p->next;}}}void main(){int j,i,k;creatadjlist(ga);for(j=0;j<n;j++)visited[j]=0;printf("请输入开始搜索的节点序号:\n");scanf("%d",&i);printf("邻接表图的深度优先搜索结果是:\n");DFSL(i);for(j=0;j<n;j++)visited[j]=0;printf("请输入开始搜索的节点序号:\n");scanf("%d",&k);printf("邻接表图的广度优先搜索结果是:\n");BFSL(k);}第一题邻接矩阵#include<stdio.h>#include<malloc.h>#define FALSE 0#define TRUE 1#define max 10typedef char vextype;typedef int adjtype;typedef struct{vextype vexs[max];adjtype arcs[max][max];}graph;graph g;int n,e;int visited[max];int Q[max];void creategraph(graph *ga){ int i,j,k;printf("请输入顶点数和边数，中间用空格间隔:");scanf("%d%d",&n,&e);printf("请输入顶点信息:"); getchar();for(i=0;i<n;i++) ga->vexs[i]=getchar();getchar();for(i=0;i<n;i++)for(j=0;j<n;j++)ga->arcs[i][j]=0;printf("请输入边，两个序号之间用空格，每组输完用回车:");for(k=0;k<e;k++){ scanf("%d%d",&i,&j);ga->arcs[i][j]=ga->arcs[j][i]=1;}}void DFS(int i){int j;printf("node:%c\n",g.vexs[i]);visited[i]=1;for(j=0;j<n;j++)if((g.arcs[i][j]==1)&&(!visited[j]))DFS(j);}BFS(int m){int i,j;int rear=-1,front=-1;printf("node:%c\n",g.vexs[m]);visited[m]=1;rear++;Q[rear]=m;while(front!=rear){front++;i=Q[front];for(j=0;j<n;j++)if((g.arcs[i][j]==1)&&(!visited[j])){printf("node:%c\n",g.vexs[j]);visited[j]=1;rear++;Q[rear]=j;}}}void main(){ int i,j,k,m;creategraph(&g);printf("顶点信息: ");for(i=0;i<n;i++)printf("%c",g.vexs[i]);printf("\n");printf("图的邻接矩阵是:\n");for(i=0;i<n;i++){ for(j=0;j<n;j++)printf(" %d",g.arcs[i][j]);printf("\n");}for(i=0;i<n;i++)visited[i]=0;printf("请输入深度优先搜索的开始结点序号:\n");scanf("%d",&k);printf("深度优先搜索的结果是:\n");DFS(k);for(i=0;i<n;i++)visited[i]=0;printf("请输入广度优先搜索的开始结点序号:\n");scanf("%d",&m);printf("广度优先搜索的结果是:\n");BFS(m);}第二题最小生成树#include<stdio.h>#include<malloc.h> #define FALSE 0#define TRUE 1#define max 10 typedef char vextype;typedef int adjtype;typedef struct{vextype vexs[max];adjtype arcs[max][max];}graph;typedef struct{int fromvex,endvex;int length;}edge;edge T[max-1];graph g;int n,e;int visited[max];//建立无向图的邻接矩阵;void creategraph(graph *ga){ int i,j,k,w;printf("请输入顶点数和边数，中间用空格间隔:");scanf("%d%d",&n,&e);printf("请输入顶点信息:"); getchar();for(i=0;i<n;i++) ga->vexs[i]=getchar();getchar();for(i=0;i<n;i++)for(j=0;j<n;j++)ga->arcs[i][j]=100;printf("请输入边和权值，用空格间隔，每组输完用回车:\n");for(k=0;k<e;k++){ scanf("%d%d%d",&i,&j,&w);ga->arcs[i][j]=ga->arcs[j][i]=w;}}//最小生成树prim算法;prim(){int j,k,m,v,min,nmax=1000;int d;edge e;for(j=1;j<n;j++){T[j-1].fromvex=1;T[j-1].endvex=j+1;T[j-1].length=g.arcs[0][j];}for(k=0;k<n-1;k++){min=nmax;for(j=k;j<n-1;j++)if(T[j].length<min){min=T[j].length;m=j;}e=T[m];T[m]=T[k];T[k]=e;v=T[k].endvex;for(j=k+1;j<n-1;j++){d=g.arcs[v-1][T[j].endvex-1];if(d<T[j].length){T[j].length=d;T[j].fromvex=v;}}}}void main(){ int i,j;creategraph(&g);printf("顶点信息: ");for(i=0;i<n;i++)printf("%c",g.vexs[i]);printf("\n");printf("图的邻接矩阵是:\n");for(i=0;i<n;i++){ for(j=0;j<n;j++)printf(" %d",g.arcs[i][j]);printf("\n");}printf("最小生成树是:\n");prim();for(i=0;i<n-1;i++)printf("\t%d->%d:%d\n",T[i].fromvex,T[i].endvex,T[i].length);printf("\n");}第三题#include <stdio.h> #include <malloc.h> #define true 1#define false 0#define nmax 10#define MAX 1000typedef char vextype;typedef int adjtype;typedef struct {vextype vexs[nmax];adjtype arcs[nmax][nmax];} graph;typedef struct{ int fromvex,endvex;int length;} edge;graph g;int n,e;int visited[nmax];void creategraph(graph *ga){ int i,j,k,w;printf("请输入顶点数和边数:");scanf("%d%d",&n,&e);printf("请输入顶点信息:"); getchar();for(i=0;i<n;i++) ga->vexs[i]=getchar();getchar();for(i=0;i<n;i++)for(j=0;j<n;j++)ga->arcs[i][j]=MAX;printf("请输入顶点对序号和权值:");for(k=0;k<e;k++){ scanf("%d%d%d",&i,&j,&w);ga->arcs[i][j]=w;}}void dijkstra(int C[][nmax],int v){ int D[nmax];int P[nmax],S[nmax];int i,j,k,v1,pre;int min;v1=v-1;for(i=0;i<n;i++){ D[i]=C[v1][i];if(D[i]!=MAX) P[i]=v;else P[i]=0;}for(i=0;i<n;i++) S[i]=0;S[v1]=1; D[v1]=0;for(i=0;i<n;i++){ min=MAX+1;for(j=0;j<n;j++)if((!S[j]) && (D[j]<min)){ min=D[j]; k=j; }S[k]=1;for(j=0;j<n;j++)if((!S[j]) && (D[j]>D[k]+C[k][j])){ D[j]=D[k]+C[k][j];P[j]=k+1;}}for(i=0;i<n;i++){ printf("%d\t%d",D[i],i+1);pre=P[i];while(pre!=0){ printf("<--%d",pre);pre=P[pre-1];}printf("\n");}}void main(){ int i,j;creategraph(&g);printf("顶点信息: ");for(i=0;i<n;i++)printf("%c",g.vexs[i]);printf("\n");printf("邻接矩阵:\n");for(i=0;i<n;i++){ for(j=0;j<n;j++)printf("%d\t",g.arcs[i][j]);printf("\n");}printf("请输入起点:");scanf("%d",&i);printf("单元最短路径是: \n");dijkstra(g.arcs,i);printf("\n");}。

数据结构实验报告图一、实验目的本次实验的主要目的是深入理解和掌握图这种数据结构的基本概念、存储结构和相关算法，并通过实际编程实现来提高对图的操作和应用能力。

二、实验环境本次实验使用的编程语言为C+＋，开发工具为Visual Studio 2019。

三、实验内容（一）图的存储结构1、邻接矩阵邻接矩阵是用一个二维数组来表示图中顶点之间的关系。

如果顶点i 和顶点 j 之间有边相连，则数组中对应的元素值为 1；否则为 0。

这种存储结构简单直观，适用于顶点数较少且边数较多的稠密图。

2、邻接表邻接表是为图的每个顶点建立一个单链表，链表中存储的是与该顶点相邻的顶点信息。

这种存储结构在存储空间上比较节省，适用于顶点数较多且边数较少的稀疏图。

（二）图的遍历算法1、深度优先遍历（DepthFirst Search，简称 DFS）从图中的某个顶点出发，沿着一条路径尽可能深地访问顶点，直到无法继续前进，然后回溯到上一个未完全访问的顶点，继续进行深度优先搜索。

2、广度优先遍历（BreadthFirst Search，简称 BFS）从图中的某个顶点出发，先访问其所有相邻的顶点，然后再依次访问这些相邻顶点的相邻顶点，以此类推，逐层向外扩展。

（三）图的最短路径算法1、迪杰斯特拉（Dijkstra）算法用于求解单源最短路径问题，即从一个给定的源顶点到图中其他所有顶点的最短路径。

2、弗洛伊德（Floyd）算法用于求解任意两个顶点之间的最短路径。

四、实验步骤（一）邻接矩阵的实现｀｀｀cppinclude ＜iostream>using namespace std;const int MAX_VERTEX_NUM ＝ 100;class Graph ｛private:int vertexNum;int edgeNum;int adjMatrixMAX_VERTEX_NUMMAX_VERTEX_NUM;public:Graph(int vNum) ｛vertexNum ＝ vNum;edgeNum ＝ 0;for （int i ＝ 0; i ＜ vertexNum; i+＋）｛for （int j ＝ 0; j ＜ vertexNum; j+＋）｛adjMatrixij ＝ 0;｝｝｝void addEdge(int i, int j) ｛if （i ＞＝ 0 ＆＆ i ＜ vertexNum ＆＆ j ＞＝ 0 ＆＆ j ＜ vertexNum) ｛adjMatrixij ＝ 1;adjMatrixji ＝ 1;edgeNum+＋；｝｝void printGraph(）｛for （int i ＝ 0; i ＜ vertexNum; i+＋）｛for （int j ＝ 0; j ＜ vertexNum; j+＋）｛cout ＜＜ adjMatrixij ＜＜＂＂；｝cout ＜＜ endl;｝｝｝；int main(）｛Graph g(5)；gaddEdge(0, 1)；gaddEdge(0, 2)；gaddEdge(1, 2)；gaddEdge(2, 3)；gaddEdge(3, 4)；gprintGraph(）；return 0;｝｀｀｀（二）邻接表的实现｀｀｀cppinclude ＜iostream>include ＜vector>using namespace std;const int MAX_VERTEX_NUM ＝ 100; class Graph ｛private:int vertexNum;vector<int> adjListMAX_VERTEX_NUM;public:Graph(int vNum) ｛vertexNum ＝ vNum;｝void addEdge(int i, int j) ｛if （i ＞＝ 0 ＆＆ i ＜ vertexNum ＆＆ j ＞＝ 0 ＆＆ j ＜ vertexNum) ｛adjListipush_back(j)；adjListjpush_back(i)；｝｝void printGraph(）｛for （int i ＝ 0; i ＜ vertexNum; i+＋）｛cout ＜＜ i ＜＜＂：＂；for （int j ＝ 0; j ＜ adjListisize(）； j+＋）｛cout ＜＜ adjListij ＜＜＂＂；｝cout ＜＜ endl;｝｝｝；int main(）｛Graph g(5)；gaddEdge(0, 1)；gaddEdge(0, 2)；gaddEdge(1, 2)；gaddEdge(2, 3)；gaddEdge(3, 4)；gprintGraph(）；return 0;｝｀｀｀（三）深度优先遍历的实现｀｀｀cppinclude ＜iostream>include ＜vector>using namespace std;const int MAX_VERTEX_NUM ＝ 100;class Graph ｛private:int vertexNum;vector<int> adjListMAX_VERTEX_NUM;bool visitedMAX_VERTEX_NUM;public:Graph(int vNum) ｛vertexNum ＝ vNum;for （int i ＝ 0; i ＜ vertexNum; i+＋）｛visitedi ＝ false;｝｝void addEdge(int i, int j) ｛if （i ＞＝ 0 ＆＆ i ＜ vertexNum ＆＆ j ＞＝ 0 ＆＆ j ＜ vertexNum) ｛adjListipush_back(j)；adjListjpush_back(i)；｝｝void DFS(int v) ｛visitedv ＝ true;cout ＜＜ v ＜＜＂＂；for （int i ＝ 0; i ＜ adjListvsize(）； i+＋）｛int u ＝ adjListvi;if （！visitedu) ｛DFS(u)；｝｝｝void DFSTraversal(）｛for （int v ＝ 0; v ＜ vertexNum; v+＋）｛if （！visitedv) ｛DFS(v)；｝｝｝｝；int main(）｛Graph g(5)；gaddEdge(0, 1)；gaddEdge(0, 2)；gaddEdge(1, 2)；gaddEdge(2, 3)；gaddEdge(3, 4)；gDFSTraversal(）；return 0;｝｀｀｀（四）广度优先遍历的实现｀｀｀cppinclude ＜iostream>include ＜queue>include ＜vector>using namespace std;const int MAX_VERTEX_NUM ＝ 100; class Graph ｛private:int vertexNum;vector<int> adjListMAX_VERTEX_NUM; bool visitedMAX_VERTEX_NUM; public:Graph(int vNum) ｛vertexNum ＝ vNum;for （int i ＝ 0; i ＜ vertexNum; i+＋）｛visitedi ＝ false;｝｝void addEdge(int i, int j) ｛if （i ＞＝ 0 ＆＆ i ＜ vertexNum ＆＆ j ＞＝ 0 ＆＆ j ＜ vertexNum) ｛adjListipush_back(j)；adjListjpush_back(i)；｝｝void BFS(int v) ｛queue<int> q;visitedv ＝ true;qpush(v)；while （！qempty(））｛int u ＝ qfront(）；qpop(）；cout ＜＜ u ＜＜＂＂；for （int i ＝ 0; i ＜ adjListusize(）； i+＋）｛int w ＝ adjListui;if （！visitedw) ｛visitedw ＝ true;qpush(w)；｝｝｝｝void BFSTraversal(）｛for （int v ＝ 0; v ＜ vertexNum; v+＋）｛if （！visitedv) ｛BFS(v)；｝｝｝｝；int main(）｛Graph g(5)；gaddEdge(0, 1)；gaddEdge(0, 2)；gaddEdge(1, 2)；gaddEdge(2, 3)；gaddEdge(3, 4)；gBFSTraversal(）；return 0;｝｀｀｀（五）迪杰斯特拉算法的实现｀｀｀cppinclude ＜iostream>include ＜climits>include ＜vector>using namespace std;const int MAX_VERTEX_NUM ＝ 100; const int INFINITY ＝ INT_MAX; class Graph ｛private:int vertexNum;int adjMatrixMAX_VERTEX_NUMMAX_VERTEX_NUM;int distanceMAX_VERTEX_NUM;bool visitedMAX_VERTEX_NUM;public:Graph(int vNum) ｛vertexNum ＝ vNum;for （int i ＝ 0; i ＜ vertexNum; i+＋）｛for （int j ＝ 0; j ＜ vertexNum; j+＋）｛adjMatrixij ＝ INFINITY;｝distancei ＝ INFINITY;visitedi ＝ false;｝｝void addEdge(int i, int j, int weight) ｛if （i ＞＝ 0 ＆＆ i ＜ vertexNum ＆＆ j ＞＝ 0 ＆＆ j ＜ vertexNum) ｛adjMatrixij ＝ weight;adjMatrixji ＝ weight;｝｝int minDistance(）｛int min ＝ INFINITY;int minIndex ＝－1;for （int v ＝ 0; v ＜ vertexNum; v+＋）｛if （！visitedv ＆＆ distancev ＜＝ min) ｛min ＝ distancev;minIndex ＝ v;｝｝return minIndex;｝void dijkstra(int src) ｛distancesrc ＝ 0;for （int count ＝ 0; count ＜ vertexNum 1; count+＋）｛int u ＝ minDistance(）；visitedu ＝ true;for （int v ＝ 0; v ＜ vertexNum; v+＋）｛if （！visitedv ＆＆ adjMatrixuv!＝ INFINITY ＆＆ distanceu!＝INFINITY ＆＆ distanceu ＋ adjMatrixuv ＜ distancev) ｛distancev ＝ distanceu ＋ adjMatrixuv;｝｝｝for （int i ＝ 0; i ＜ vertexNum; i+＋）｛cout ＜＜＂源点＂＜＜ src ＜＜＂到顶点＂＜＜ i ＜＜＂的最短距离为: ＂＜＜ distancei ＜＜ endl;｝｝｝；int main(）｛Graph g(5)；gaddEdge(0, 1, 2)；gaddEdge(0, 2, 4)；gaddEdge(1, 2, 1)；gaddEdge(1, 3, 7)；gaddEdge(2, 3, 3)；gaddEdge(3, 4, 5)；gdijkstra(0)；return 0;｝｀｀｀（六）弗洛伊德算法的实现｀｀｀cppinclude ＜iostream>include ＜climits>using namespace std;const int MAX_VERTEX_NUM ＝ 100; const int INFINITY ＝ INT_MAX; class Graph ｛private:int vertexNum;int adjMatrixMAX_VERTEX_NUMMAX_VERTEX_NUM;int distanceMAX_VERTEX_NUMMAX_VERTEX_NUM;public:Graph(int vNum) ｛vertexNum ＝ vNum;for （int i ＝ 0; i ＜ vertexNum; i+＋）｛for （int j ＝ 0; j ＜ vertexNum; j+＋）｛adjMatrixij ＝ INFINITY;｝｝｝void addEdge(int i, int j, int weight) ｛if （i ＞＝ 0 ＆＆ i ＜ vertexNum ＆＆ j ＞＝ 0 ＆＆ j ＜ vertexNum) ｛adjMatrixij ＝ weight;｝｝void floyd(）｛for （int i ＝ 0; i ＜ vertexNum; i+＋）｛for （int j ＝ 0; j ＜ vertexNum; j+＋）｛distanceij ＝ adjMatrixij;｝｝for （int k ＝ 0; k ＜ vertexNum; k+＋）｛for （int i ＝ 0; i ＜ vertexNum; i+＋）｛for （int j ＝ 0; j ＜ vertexNum; j+＋）｛if （distanceik!＝ INFINITY ＆＆ distancekj!＝ INFINITY ＆＆distanceik ＋ distancekj ＜ distanceij) ｛distanceij ＝ distanceik ＋ distancekj;｝｝｝｝for （int i ＝ 0; i ＜ vertexNum; i+＋）｛for （int j ＝ 0; j ＜ vertexNum; j+＋）｛if （distanceij ＝＝ INFINITY) ｛cout ＜＜＂顶点＂＜＜ i ＜＜＂到顶点＂＜＜ j ＜＜＂的距离为: 无穷大" ＜＜ endl;｝ else ｛cout ＜＜＂顶点＂＜＜ i ＜＜＂到顶点＂＜＜ j ＜＜＂的距离为: ＂＜＜ distanceij ＜＜ endl;｝｝｝｝｝；int main(）｛Graph g(4)；gaddEdge(0, 1, 5)；gaddEdge(0, 3, 10)；gaddEdge(1, 2, 3)；gaddEdge(2, 3, 1)；gfloyd(）；return 0;｝｀｀｀五、实验结果分析（一）邻接矩阵和邻接表的比较邻接矩阵的优点是可以快速判断两个顶点之间是否有边相连，时间复杂度为O(1)。