数据结构-图的基本知识.

中原工学院《数据结构》实验报告学院：计算机学院专业：计算机科学与技术班级：计科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. 队列队列也是一种特殊的线性表，它只能在表的两端进行插入和删除操作。

队列有一个被称为队头和队尾的元素，只能在队头进行删除操作，只能在队尾进行插入操作。

队列也有两种经典的存储结构，分别是顺序队列和链式队列。

顺序队列是利用数组来实现队列的存储和操作，而链式队列则是利用链表来实现队列的存储和操作。

4. 串串是线性表的一种特殊形式，它是由零个或多个字符构成的有限序列。

串的存储结构有两种常见的形式，分别是顺序存储结构和链式存储结构。

顺序存储结构是利用数组来存储串的字符序列，而链式存储结构是利用链表来存储串的字符序列。

二、非线性结构1. 树树是一种非线性结构，它是由n (n ≥ 1) 个节点组成的有限集合，这些节点之间存在着明确的层次关系。

树的存储结构通常有两种形式，分别是双亲表示法和孩子表示法。

双亲表示法通过数组来存储树的节点和节点之间的关系，而孩子表示法则通过链表来存储树的节点和节点之间的关系。

树有许多种特殊形式，如二叉树、平衡二叉树、多路查找树等。

其中，二叉树是一种特殊的树，它的每个节点最多有两个子节点，这两个子节点被称为左子树和右子树。

2. 图图是一种非线性结构，它是由一组顶点和一组边组成的数据结构。

图的知识点总结归纳图是计算机科学中常用的数据结构之一，它由节点和边组成。

在图论中，图被用于描述各种实际问题，如社交网络、路线规划、电子电路等。

本文将对图的基本概念、表示方法、遍历算法和常见应用进行总结和归纳。

一、基本概念1. 节点（Vertex）：图中最基本的元素，也称为顶点。

每个节点可以有零个或多个与之相连的边。

2. 边（Edge）：连接节点的线段，表示节点之间的关系。

边可以有方向，即有向边，也可以无方向，即无向边。

3. 路径（Path）：通过一系列节点和边依次连接起来的序列，用于描述节点间的连通性。

4. 路径长度（Path Length）：路径上经过的边的数量。

若路径上没有重复节点，则路径长度即为路径经过的节点数量减一。

5. 环（Cycle）：起点和终点相同的路径，也称为回路。

6. 连通图（Connected Graph）：图中任意两个节点之间都存在路径的图。

7. 强连通图（Strongly Connected Graph）：有向图中，任意两个节点之间都存在双向路径的图。

8. 网络（Network）：带有权值的图，边上的权值代表节点间的相关程度或距离。

二、表示方法1. 邻接矩阵（Adjacency Matrix）：使用二维数组来表示节点之间的关系。

矩阵中的元素表示边的存在与否，可以是布尔值或权值。

2. 邻接表（Adjacency List）：使用链表等数据结构来表示每个节点相邻节点的集合。

每个节点存储一个指向相邻节点的指针。

三、遍历算法1. 深度优先搜索（Depth First Search，DFS）：从起始节点开始，不断沿着一条路径探索直到无法继续，然后回溯到前一个节点继续探索其他路径。

2. 广度优先搜索（Breadth First Search，BFS）：从起始节点开始，逐层遍历相邻节点，保证先访问离起始节点近的节点。

四、常见应用1. 最短路径算法：用于寻找两个节点之间路径长度最短的算法，如迪杰斯特拉算法（Dijkstra's Algorithm）和弗洛伊德算法（Floyd's Algorithm）。

数据结构知识点总结一、数据结构基础概念数据结构是指数据元素之间的关系，以及对数据元素进行操作的方法的总称。

数据结构是计算机科学中非常基础的概念，它为计算机程序的设计和实现提供了基础架构。

数据结构的研究内容包括数据的逻辑结构、数据的存储结构以及对数据进行操作的算法。

1.1 数据结构的分类数据结构可以根据数据的逻辑关系和数据的物理存储方式进行分类，常见的数据结构分类包括线性结构、树形结构、图结构等。

1.2 数据结构的基本概念（1）数据元素：数据结构中的基本单位，可以是原子类型或者复合类型。

（2）数据项：数据元素中的一个组成部分，通常是基本类型。

（3）数据结构的逻辑结构：指数据元素之间的逻辑关系，包括线性结构、树形结构、图结构等。

（4）数据结构的存储结构：指数据元素在计算机内存中的存储方式，包括顺序存储结构和链式存储结构等。

1.3 数据结构的特点数据结构具有以下几个特点：（1）抽象性：数据结构是对现实世界中的数据进行抽象和模型化的结果。

（2）实用性：数据结构是在解决实际问题中得出的经验总结，是具有广泛应用价值的。

（3）形式化：数据结构具有精确的数学定义和描述，可以进行分析和证明。

（4）计算性：数据结构是为了使计算机程序更加高效而存在的。

二、线性结构线性结构是数据元素之间存在一对一的关系，是一种最简单的数据结构。

常见的线性结构包括数组、链表、栈和队列等。

2.1 线性表线性表是数据元素之间存在一对一的关系的数据结构，可以采用顺序存储结构或者链式存储结构实现。

（1）顺序存储结构：线性表采用数组的方式进行存储，数据元素在内存中连续存储。

（2）链式存储结构：线性表采用链表的方式进行存储，数据元素在内存中非连续存储，通过指针将它们进行连接。

2.2 栈栈是一种特殊的线性表，只允许在一端进行插入和删除操作，这一端称为栈顶。

栈的操作遵循后进先出（LIFO）的原则。

2.3 队列队列也是一种特殊的线性表，允许在一端进行插入操作，另一端进行删除操作，这两端分别称为队尾和队首。

第5章图●图的定义①图由顶点集V和边集E组成，记为G=（V，E），V(G)是图G中顶点的有穷非空集合，E(G)是图G中顶点之间变得关系集合，|V|表示顶点个数，也称图的阶，|E|表示边数（线性表和树都可以是空的，但图可以只有一个顶点没有边）②有向图：弧是顶点的有序对，记为<v,w>，v,w是顶点,v是弧尾，w是弧头，从顶点v到顶点w的弧。

无向图：边是顶点的无序对，记为(v,w)③简单图：一个图满足：不存在重复边；不存在顶点到自身的边。

多重图相对于简单图定义④完全图：无向图中，任意两顶点之间存在边，称为完全无向图。

N个顶点的无向完全图有n(n-1)/2条边。

在有向图中，任意两顶点之间存在方向相反的两条弧，称为有向完全图，N 个顶点的有向完全图有n(n-1)条边。

⑤连通图：在无向图中任意两顶点都是连通的。

无向图中的极大连通子图称为连通分量。

极大要求连通子图包含其所有的边和顶点，极小连通子图既要保持图连通，又要保持边数最少⑥在有向图中任意两顶点v,w，存在从顶点v到顶点w和从顶点w到顶点v两条路径，这种图称为强连通图。

有向图的极大强连通子图称为有向图的强连通分量。

⑦生成树：①包含图中所有顶点n，②生成树有n-1条边, ③任意两点连通。

对生成树而言，砍去一条边变成非连通图，加上一条边形成一个回路。

在非连通图中，连通分量的生成树构成了非连通图的生成森林。

⑧顶点的度：以该顶点为端点的边的数目。

无向图的全部顶点的度之和等于边数的两倍。

有向图的度等于出度和入度之和，入度是以该顶点为终点的有向边的数目，出度是以该顶点为起点的有向边的数目。

有向图的全部顶点的入度之和和出度之和相等且等于边数。

⑨图中每条边可以标上具有某种含义的数值，该数值称为边的权值。

带有权值的图称为网。

○10对于无向图G=(V, {E})，如果边(v，v’)∈E，则称顶点v，v’互为邻接点，即v，v’相邻接。

边(v，v’)依附于顶点v 和v’，或者说边(v, v’)与顶点v 和v’相关联。