#include
using namespace std;
const int MaxSize=10;
class ALraph
{
public:
ALraph();
~ALraph(){}
void DEFSTraverse(int v);
void BEFSTraverse(int v);
void dingdian();
void juzhen();
private:
int vertexNum,arcNum;
int visited[MaxSize];
int visit[MaxSize];
int arc[MaxSize][MaxSize];
char vertex[MaxSize];
};
ALraph::ALraph()
{
char a[MaxSize];
int n,e,i,j,k;
cin>>n>>e;
for(i=0;i { cin>>a[i]; } vertexNum=n; arcNum=e; for(i=0;i vertex[i]=a[i]; for(i=0;i { for(j=0;j { arc[i][j]=0; } } for(k=0;k { cin>>i>>j; arc[i][j]=1; arc[j][i]=1; } for(i=0;i { visited[i]=0; } for(k=0;k { visit[k]=0; } } void ALraph::dingdian() { int i; for(i=0;i { cout< } cout< } void ALraph::juzhen() { int i,j; for(i=0;i { for(j=0;j { cout< } cout< } } void ALraph::DEFSTraverse(int v) { int i,j; cout< visited[v]=1; for(j=0;j { if(arc[v][j]==1 && visited[j]==0) { DEFSTraverse(j); } } for(i=0;i { if(visited[i]!=1) { DEFSTraverse(i); } } } void ALraph::BEFSTraverse(int v) { int front ,rear,j,i; int Q[MaxSize]; for(i=0;i { if(visit[i]!=1) { v=i; front=rear=-1; cout< visit[v]=1; while(front!=rear) { v=Q[++front]; for(j=0;j { if(arc[v][j]==1 && visit[j]==0) { cout< visit[j]=1; Q[++rear]; } } } } } } int main() { ALraph m; int x; x=0; m.dingdian(); m.juzhen(); m.DEFSTraverse(x); cout< m.BEFSTraverse(x); cout< return 0; } 图的邻接矩阵和邻接表相互转换 图的邻接矩阵存储方法具有如下几个特征:1)无向图的邻接矩阵一定是一个对称矩阵。 2)对于无向图的邻接矩阵的第i 行非零元素的个数正好是第i 个顶点的度()i v TD 。3)对于有向图,邻接矩阵的第i 行非零元素的个数正好是第i 个顶点的出度()i v OD (或入度 ()i v ID ) 。4)用邻接矩阵方法存储图,很容易确定图中任意两个顶点之间是否有边相连;但是,要确定图中有多少条边,则必须按行、按列对每个元素进行检测,所发费得时间代价大。 邻接表是图的一种顺序存储与链式存储相结合的存储方法。若无向图中有n 个顶点、e 条边,则它的邻接表需n 个头结点和2e 个表结点。显然,在边稀疏的情况下,用邻接表表示图比邻接矩阵存储空间。在无向图的邻接表中,顶点i v 的度恰好是第i 个链表中的结点数,而在有向图中,第i 个链表中结点个数是顶点i v 的出度。 在建立邻接表或邻逆接表时,若输入的顶点信息即为顶点的编号,则建立临接表的时间复杂度是)(e n O +;否则,需要通过查找才能得到顶点在图中位置,则时间复杂度为)*(e n O 。在邻接表上容易找到任意一顶点的第一个邻接点和下一个邻接点,但要判断任意两个顶点之间是否有边或弧,则需要搜索第i 个或第j 个链表,因此,不及邻接矩阵方便。 邻接矩阵和邻接表相互转换程序代码如下: #include #include 实习报告——“邻接矩阵表示的带权有向图”演示程序 (一)、程序的功能和特点 主要实现的功能:1.使用邻接矩阵表示带权有向图; 2.查找指定顶点序号; 3.判断图是否为空; 4.判断图是否满; 5.取得顶点数、边数、一条边的权值; 6.插入一个顶点、边; 7.删除一个顶点、边; (二)、程序的算法设计 “邻接矩阵的表示”算法: 1.【逻辑结构与存储结构设计】 逻辑结构:非线性结构——网状结构 存储结构:内存中连续的存储结构,邻接矩阵 2.【基本操作设计】 按指定输入,生成图并打印该图 删除一个顶点并打印 删除一条边并打印 3. 【算法设计】 插入一个顶点的算法: 首先判断该图是否已满,若已满:插入失败; 否则进行插入:1.顶点表增加一个元素 2.邻接矩阵增加一行一列 删除一个顶点的算法: A F E D C B 判断要删除顶点的存在性,若不存在:出错; 否则:1.修改顶点表,即在顶点数组中删除 该点; 2.修改邻接矩阵,即需要统计与该顶 点相关联的边,并将这些边也删除4.【高级语言代码】 public class Graph { static int MaxEdges=50; static int MaxVertices=10; static int MaxValue=9999;//无穷大 //存放顶点的数组 private char VerticesList[]=new char[MaxVertices]; //邻接矩阵(存放两个顶点的权值) private int Edge[][]=new int[MaxVertices][MaxVertices]; private int CurrentEdges;//现有边数 private int CurrentVertices;//现有顶点数 //构造函数:建立空的邻接矩阵 public Graph(){ for(int i=0;i 数学与计算机学院 课程设计说明书 课程名称: 数据结构与算法课程设计 课程代码: 6014389 题目: 无向图的邻接矩阵存储结构 年级/专业/班: 2018级软件4班 学生姓名: 吴超 学号: 312018********* 开始时间: 2018年12月9日 完成时间: 2018年12月30日 课程设计成绩: 指导教师签名:年月日 数据结构课程设计任务书 学院名称:数学与计算机学院课程代码:__6014389______ 专业:软件工程年级: 2018 一、设计题目 无向图的邻接矩阵存储结构 二、主要内容 图是无向带权图,对下列各题,要求写一算法实现。 1)能从键盘上输入各条边和边上的权值; 2)构造图的邻接矩阵和顶点集。 3)输出图的各顶点和邻接矩阵 4)插入一条边 5)删除一条边 6)求出各顶点的度 7)判断该图是否是连通图,若是,返回1;否则返回0. 8)使用深度遍历算法,输出遍历序列。 三、具体要求及应提交的材料 用C/C++语言编程实现上述内容,对每个问题写出一个算法实现,并按数学与计算机学院对课程设计说明书规范化要求,写出课程设计说明书,并提交下列材料: 1>课程设计说明书打印稿一份 2>课程设计说明书电子稿一份; 3>源程序电子文档一份。 四、主要技术路线提示 用一维数组存放图的顶点信息,二维数组存放各边信息。 五、进度安排 按教案计划规定,数据结构课程设计为2周,其进度及时间大致分配如下: [1] 严蔚敏,吴伟民.数据结构.清华大学出版社出版。 [2] 严蔚敏,吴伟民. 数据结构题集(C语言版> .清华大学出版社.2003年5月。 [3]唐策善,李龙澎.数据结构(作C语言描述> .高等教育出版社.2001年9月 [4] 朱战立.数据结构(C++语言描述><第二版本).高等出版社出版.2004年4月 [5]胡学钢.数据结构(C语言版> .高等教育出版社.2004年8月 指导教师签名日期年月日 系主任审核日期年月日 目录 有向图的邻接矩阵 设有向图,,。令为邻接到的边的条数,称为D的邻接矩阵,记作。 为图7.12的邻接矩阵,不难看出: (1)(即第i行元素之和为的出度),。 (2)(即第j列元素之和为的入度), 。 (3)由(1),(2)可知,为D中边的总数,也可看成是D中长度为1的通路总数,而为D中环的个数,即D中长度为1的回路总数。 D中长度大于等于2的通路数和回路数应如何计算呢? 为此,先讨论长度等于2的通路数和回路数。 在图D中,从顶点到顶点的长度等于2的通路,中间必经过一顶点。对于任意的k,若有通路,必有且,即。反之,若D中不存在通路,必有或,即。于是在图D中从顶点到顶点的长度等于2的通路数为: 由矩阵的乘法规则知,正好是矩阵中的第i 行与第j列元素,记,即就是从顶点到顶点的长度等于2的通路数,时,表示从顶点到顶点的长度等于2的回路数。 因此,即矩阵中所有元素的和为长度等于2的通路总数(含回路),其中对角线的元素和为长度等于2的回路总数。 根据以上分析,则有下面的推论。 定义有向图,,D中长度为的通路数和回路数可以用矩阵(简记)来表示,这里,其中 , 即 则为顶点到顶点长度为的通路数,为到自身长度为的回路数。中所有元素之和为D中长度为的通路数,而中对角线上元素之和为D中始于(终于)各顶点的长度为的回路数。 在图7.12中,计算,,如下: 观察各矩阵发现,,,。于是,D中到长度为2的通路有3条,长度为3的通路有4条,长度为4的通路有6条。由, ,可知,D中到自身长度为的回路各有1条(此时回路为 复杂的)。由于,所以D中长度为2的通路总数为10,其中有3条回路。 从上述分析,可得下面定理。 定理7.5设为有向图D的邻接矩阵,,则中元素 为到长度为的通路数,为D中长度为的通路总数,其中 为D中长度为的回路总数。 若再令矩阵 , /*邻接矩阵表示图,先深遍历和先广遍历*/ #include #include<> #include<> #define max 20 #define digit 1 #define zero 0 typedef struct{ int num; char data; }Vertex; typedef struct{ int n; exdata=ch; alg->ve[i].firstarc=NULL; } printf("输入弧的信息(弧的两端点):\n"); for(i=0;i 上机实验报告 学院:计算机与信息技术学院 专业:计算机科学与技术(师范)课程名称:数据结构 实验题目:图的邻接矩阵 班级序号:师范1班 学号:201421012731 学生姓名:邓雪 指导教师:杨红颖 完成时间:2015年12月25号 一、实验目的: 1﹒掌握图的基本概念和邻接矩阵存储结构。 2﹒掌握图的邻接矩阵存储结构的算法实现。 3 .加深理论知识,提高实际编程能力及程序调试能力。 二、实验环境: Windows 8.1 Microsoft Visval c++ 6.0 三、实验内容及要求: 图是无向带权图,要求写一算法实现; 1)能从键盘上输入各条边和边上的权值; 2)构造图的邻接矩阵和顶点集; 3)输出图的各顶点和邻接矩阵; 四、概要设计: 邻接矩阵存储方法也就是数组存储方法,采用两个数组来完成对图的信息的存储。假设一个图G拥有n个顶点,首先定义一个具有n个元素的一维数组V[0,1…n-1]用来存放各个顶点的数据信息,然后定义一个二维数组E[n][n],用来表示各个顶点的边的情况,这个二维数组就叫做邻接矩阵。对于无向图,如果顶点i和顶点j之间存在边,则E[i][j]= E[j][i]=1,否则E[i][j]= E[j][i]=0;对于有向图,如果存在由顶点i到顶点j的边,则E[i][j] =1,否则E[i][j] =0。对于网络,当顶点i和顶点j之间存在边且权值为Wij 时,将E[i][j]赋值为Wij,否则将其赋值为无穷大,表示顶点i和j之间是不连接的。五、代码: #include 按给定的任一连通无向图构造邻接矩阵,再进行深度优先遍历和广度优先遍历。 #include #include "stdlib.h" #include "stdio.h" #define MAX_VERTEX_NUM 10 /*最多顶点个数*/ #define INFINITY 32768 /*表示极大值,即∞*/ #define True 1 #define False 0 #define Error -1 #define Ok 1 typedefenum{DG, DN, UDG, UDN} GraphKind; /*图的种类:DG表示有向图, DN表示有向网, UDG表示无向图, UDN表示无向网*/ typedef char VertexData; /*假设顶点数据为字符型*/ typedefstructArcNode { intadj; /*对于无权图,用1或0表示是否相邻;对带权图,则为权值类型*/ } ArcNode; typedefstruct { VertexDatavexs[MAX_VERTEX_NUM]; /*顶点向量*/ ArcNode arcs[MAX_VERTEX_NUM][MAX_VERTEX_NUM]; /*邻接矩阵*/ intvexnum,arcnum; /*图的顶点数和弧数*/ GraphKind kind; /*图的种类标志*/ }AdjMatrix; /*(Adjacency Matrix Graph)*/ intLocateVertex(AdjMatrix *G,VertexData v) /*求顶点位置函数*/ { int j=Error,k; for(k=0;k 1.设计一个算法将无向图的邻接矩阵转为对应邻接表的算法。 typedef struct {int vertex[m]; int edge[m][m];}gadjmatrix; typedef struct node1{int info;int adjvertex; struct node1 *nextarc;}glinklistnode; typedef struct node2{int vertexinfo;glinklistnode *firstarc;}glinkheadnode; void adjmatrixtoadjlist(gadjmatrix g1[ ],glinkheadnode g2[ ]) { int i,j; glinklistnode *p; for(i=0;i<=n-1;i++) g2[i].firstarc=0; for(i=0;i<=n-1;i++) for(j=0;j<=n-1;j++) if (g1.edge[i][j]==1) { p=(glinklistnode *)malloc(sizeof(glinklistnode));p->adjvertex=j; p->nextarc=g[i].firstarc; g[i].firstarc=p; p=(glinklistnode *)malloc(sizeof(glinklistnode));p->adjvertex=i; p->nextarc=g[j].firstarc; g[j].firstarc=p; } } 设计判断两个二叉树是否相同的算法。 typedef struct node {datatype data; struct node *lchild,*rchild;} bitree; int judgebitree(bitree *bt1,bitree *bt2) { if (bt1==0 && bt2==0) return(1); else if (bt1==0 || bt2==0 ||bt1->data!=bt2->data) return(0); else return(judgebitree(bt1->lchild,bt2->lchild)*judgebitree(bt1->rchild,bt2->rchild)); } 1.设计两个有序单链表的合并排序算法。 void mergelklist(lklist *ha,lklist *hb,lklist *&hc) { lklist *s=hc=0; while(ha!=0 && hb!=0) if(ha->data 邻接矩阵表示的图的基本操作的实现 //采用邻接矩阵完成无权无向及有向图的"建立、输出、深度遍历、广度遍历"操作 #include } MGraph; //队列初始化 Status InitLinkQueue(LinkQueue *Q) { QNode *p; p=(QNode*)malloc(sizeof(QNode));//开辟头结点空间 if(p!=NULL) { p->next=NULL; Q->front=Q->rear=p; return OK; } else return ERROR; } //链式队列的入队操作,在已知队列的队尾插入一个元素e,修改队尾指针rear。 Status InsertLinkQueue(LinkQueue *Q,ElemType e) { QNode *p; p=(QNode*)malloc(sizeof(QNode)); if(p==NULL) return ERROR;//申请新结点空间失败,返回错误标志 else { p->data=e;//存入新结点数据 p->next=NULL; Q->rear->next=p;//新结点插入到队尾 Q->rear=p;//新插入结点成为新的队尾 return OK;图的邻接矩阵和邻接表相互转换
用邻接矩阵表示法创建有向图(数据结构)
邻接矩阵表示的带权有向图
数据结构实验报告无向图邻接矩阵存储结构
有向图的邻接矩阵
C++邻接矩阵表示无向图
将一个无向图的邻接表转换为邻接矩阵算法
图的邻接矩阵
无向图构造邻接矩阵
邻接矩阵创建有向图
设计一个算法将无向图的邻接矩阵转为对应邻接表的算法
邻接矩阵表示的图的基本操作的实现