下载文档原格式
邻接矩阵dfs c语言邻接矩阵是一种表示图的常见方式，而深度优先搜索（DFS）是一种常用的图遍历算法。
在C语言中，我们可以使用邻接矩阵来实现DFS算法来遍历图。
首先，我们需要定义一个邻接矩阵来表示图，然后编写DFS算法来遍历这个邻接矩阵。
首先，让我们来定义一个简单的邻接矩阵来表示图。
假设我们有一个包含n个顶点的图，我们可以用一个二维数组来表示邻接矩阵。
例如，一个nn的二维数组adjacencyMatrix[i][j]可以表示顶点i到顶点j是否有边相连，如果有边相连则为1，否则为0。
这样我们就可以用邻接矩阵来表示图的结构。
接下来，我们需要编写DFS算法来遍历这个邻接矩阵。
DFS算法通常使用递归的方式来实现。
我们可以从图中的任意一个顶点开始，访问它的所有邻居顶点，然后递归地访问这些邻居顶点的邻居顶点，以此类推，直到所有顶点都被访问过。
在C语言中，我们可以使用递归函数来实现DFS算法。
下面是一个简单的C语言代码示例，用邻接矩阵表示图，并实现DFS算法来遍历图：c.#include <stdio.h>。
#define MAX_NODES 100。
int visited[MAX_NODES];int adjacencyMatrix[MAX_NODES][MAX_NODES];int numNodes;void dfs(int v) {。
visited[v] = 1;printf("Visited node: %d\n", v);for (int i = 0; i < numNodes; i++) {。
if (adjacencyMatrix[v][i] && !visited[i]) {。
dfs(i);}。
}。
}。
int main() {。
// 读入图的顶点数。
printf("Enter the number of nodes: "); scanf("%d", &numNodes);// 读入邻接矩阵。
图的邻接矩阵和邻接表相互转换图的邻接矩阵存储方法具有如下几个特征：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<iostream.h>#define MAX 20//图的邻接表存储表示typedef struct ArcNode{int adjvex; //弧的邻接定点 char info; //邻接点值struct ArcNode *nextarc; //指向下一条弧的指针}ArcNode;typedef struct Vnode{ //节点信息char data;ArcNode *link;}Vnode,AdjList[MAX];typedef struct{AdjList vertices;int vexnum; //节点数int arcnum; //边数}ALGraph;//图的邻接矩阵存储表示typedef struct{int n; //顶点个数char vexs[MAX]; //定点信息int arcs[MAX][MAX]; //边信息矩阵}AdjMatrix;/***_____________________________________________________***///函数名：AdjListToMatrix(AdjList g1,AdjListMatrix &gm,int n)//参数：（传入）AdjList g1图的邻接表,（传入）int n顶点个数，（传出）AdjMatrix gm图的邻接矩阵//功能：把图的邻接表表示转换成图的邻接矩阵表示void AdjListToAdjMatrix(ALGraph gl,AdjMatrix &gm){int i,j,k;ArcNode *p;gm.n=gl.vexnum;for(k=0;k<gl.vexnum;k++)gm.vexs[k]=gl.vertices[k].data;for(i=0;i<MAX;i++)for(j=0;j<MAX;j++)gm.arcs[i][j]=0;for(i=0;i<gl.vexnum;i++){p=gl.vertices[i].link; //取第一个邻接顶点while(p!=NULL){ //取下一个邻接顶点gm.arcs[i][p->adjvex]=1;p=p->nextarc;}}}/***________________________________________________***///函数名：AdjMatrixToAdjListvoid AdjMatrixToAdjList(AdjMatrix gm,ALGraph &gl){int i,j,k,choice;ArcNode *p;k=0;gl.vexnum=gm.n;cout<<"请选择所建立的图形是无向图或是有向图：";cin>>choice;for(i=0;i<gm.n;i++){gl.vertices[i].data=gm.vexs[i];gl.vertices[i].link=NULL;}for(i=0;i<gm.n;i++)for(j=0;j<gm.n;j++)if(gm.arcs[i][j]==1){k++;p=new ArcNode;p->adjvex=j;p->info=gm.vexs[j];p->nextarc=gl.vertices[i].link;gl.vertices[i].link=p;}if(choice==1)k=k/2;gl.arcnum=k;}void CreateAdjList(ALGraph &G){int i,s,d,choice;ArcNode *p;cout<<"请选择所建立的图形是有向图或是无向图：";cin>>choice;cout<<"请输入节点数和边数："<<endl;cin>>G.vexnum>>G.arcnum;for(i=0;i<G.vexnum;i++){cout<<"第"<<i<<"个节点的信息：";cin>>G.vertices[i].data;G.vertices[i].link=NULL;}if(choice==1){for(i=0;i<2*(G.vexnum);i++){cout<<"边----起点序号，终点序号：";cin>>s>>d;p=new ArcNode;p->adjvex=d;p->info=G.vertices[d].data;p->nextarc=G.vertices[s].link;G.vertices[s].link=p;}}else{for(i=0;i<G.vexnum;i++){cout<<"边----起点序号，终点序号：";cin>>s>>d;p=new ArcNode;p->adjvex=d;p->info=G.vertices[d].data;p->nextarc=G.vertices[s].link;G.vertices[s].link=p;}}}void CreateAdjMatrix(AdjMatrix &M){int i,j,k,choice;cout<<"请输入顶点个数：";cin>>M.n;cout<<"请输入如顶点信息:"<<endl;for(k=0;k<M.n;k++)cin>>M.vexs[k];cout<<"请选择所建立的图形是无向图或是有向图：";cin>>choice;cout<<"请输入边信息："<<endl;for(i=0;i<M.n;i++)for(j=0;j<M.n;j++)M.arcs[i][j]=0;switch(choice){case 1:{for(k=0;k<M.n;k++){cin>>i>>j;M.arcs[i][j]=M.arcs[j][i]=1;}};break;case 2:{for(k=0;k<M.n;k++){cin>>i>>j;M.arcs[i][j]=1;}};break;}}void OutPutAdjList(ALGraph &G){int i;ArcNode *p;cout<<"图的邻接表如下："<<endl;for(i=0;i<G.vexnum;i++){cout<<G.vertices[i].data;p=G.vertices[i].link;while(p!=NULL){cout<<"---->("<<p->adjvex<<" "<<p->info<<")";p=p->nextarc;}cout<<endl;}}void OutPutAdjMatrix(AdjMatrix gm){cout<<"图的邻接矩阵如下："<<endl;for(int i=0;i<gm.n;i++){。
数据结构—统计有向图中每个顶点的出度和⼊度（以邻接矩阵和邻接表两种⼊式实现）⼊、邻接矩阵实现假设不带权有向图采⼊邻接矩阵 g 存储，设计实现以下功能的算法：（1）求出图中每个顶点的⼊度。
（2）求出图中每个顶点的出度。
（3）求出图中出度为 0 的顶点数。
#include#include#includeusing namespace std;#define INFINITY 65535#define MAX_VERTEX_NUM 100typedef char VertexType;typedef struct {VertexType vexs[MAX_VERTEX_NUM];顶点 //数组int arcs[MAX_VERTEX_NUM][MAX_VERTEX_NUM];邻接矩 //阵int v, e; 图顶点//和边的数量} MGraph;int num=0;全局变量负责统计出度为 0 的顶点个数void CreateMGraph(MGraph &G){int i,j,k,w;printf("输⼊顶点数和边数:\n");scanf("%d%d",&G.v,&G.e);//for(i=0;iG.arcs[i][j]=INFINITY;初始化邻接//矩阵for(k=0;k{printf("输⼊边（i，j）上的下标 i，j 和权 w\n");scanf("%d%d%d",&i,&j,&w);G.arcs[i][j]=w;}}void indu(MGraph G){int n=0;printf("⼊度：\n");for(int i=0;i//scanf("%c",G.vexs[i]);for(i=0;i{for(int j=0;j} if(n==0) num++; printf("%d ",n); n=0; } } int main() { MGraph G; CreateMGraph(G); { indu(G); if(G.arcs[j][i]!=INFINITY) printf("\n"); n++; outdu(G); } printf("\n"); printf("%d ",n); printf("出度为 0 的顶点个数：%d",num); n=0; return 0; } } } #include#include#includeusing namespace std;#define INFINITY 65535#define MAX_VERTEX_NUM 100typedef int VertexType;int num=0;n++;⼊、邻接表void outdu(MGraph G) 要 不 //要加引⼊，有时候需要仔细考虑⼊下 { 假设不带权有向图采⼊邻接表 G 存储，设计实现以下功能的算法： int n=0;（1） 求出图中每个顶点的⼊度。
实现图的邻接矩阵和邻接表存储1．需求分析对于下图所示的有向图G，编写一个程序完成如下功能：1．建立G的邻接矩阵并输出之2．由G的邻接矩阵产生邻接表并输出之3．再由2的邻接表产生对应的邻接矩阵并输出之2．系统设计1．图的抽象数据类型定义：ADT Graph{数据对象V：V是具有相同特性的数据元素的集合，称为顶点集数据关系R：R={VR}VR={<v,w>|v,w∈V且P(v,w),<v,w>表示从v到w的弧，谓词P(v,w)定义了弧<v,w>的意义或信息}基本操作P：CreatGraph(&G,V,VR)初始条件：V是图的顶点集，VR是图中弧的集合操作结果：按V和VR的定义构造图GDestroyGraph(&G)初始条件：图G存在操作结果：销毁图GInsertVex(&G,v)初始条件：图G存在，v和图中顶点有相同特征操作结果：在图G中增添新顶点v……InsertArc(&G,v,w)初始条件：图G存在，v和w是G中两个顶点操作结果：在G中增添弧<v,w>，若G是无向的则还增添对称弧<w,v>……DFSTraverse(G,Visit())初始条件：图G存在，Visit是顶点的应用函数操作结果：对图进行深度优先遍历，在遍历过程中对每个顶点调用函数Visit一次且仅一次。
一旦Visit()失败，则操作失败BFSTraverse(G,Visit())初始条件：图G存在，Visit是顶点的应用函数操作结果：对图进行广度优先遍历，在遍历过程中对每个顶点调用函数Visit一次且仅一次。
一旦Visit()失败，则操作失败}ADT Graph2．主程序的流程：调用CreateMG函数创建邻接矩阵M；调用PrintMatrix函数输出邻接矩阵M调用CreateMGtoDN函数，由邻接矩阵M创建邻接表G调用PrintDN函数输出邻接表G调用CreateDNtoMG函数，由邻接表M创建邻接矩阵N调用PrintMatrix函数输出邻接矩阵N3．函数关系调用图：3．调试分析（1）在MGraph的定义中有枚举类型typedef enum{DG,DN,UDG,UDN}GraphKind;//{有向图,有向网,无向图,无向网}赋值语句G.kind(int)=M.kind(GraphKind);是正确的，而反过来M.kind=G.kind则是错误的，要加上那个强制转换M.kind=GraphKind(G.kind);枚举类型enum{DG,DN,UDG,UDN}会自动赋值DG=0；DN=1，UDG=2，UDN=3；可以自动从GraphKind类型转换到int型，但不会自动从int型转换到GraphKind类型（2）算法的时间复杂度分析：CreateMG、CreateMGtoDN、CreateDNtoMG、PrintMatrix、PrintDN的时间复杂度均为O(n2) n为图的顶点数，所以main：T(n)= O(n2)4．测试结果用需求分析中的测试数据输入：输出：5、用户手册（1）输入顶点数和弧数；（2）输入顶点内容；（3）按行序输入邻接矩阵，输入各弧相应权值（4）回车输出邻接矩阵M、邻接表G和邻接矩阵N6、附录源程序：#include <stdio.h>#include <stdlib.h>#define MAX_VERTEX_NUM 20typedef int VRType;typedef int InfoType;typedef int VertexType;typedef enum{DG,DN,UDG,UDN}GraphKind;//{有向图,有向网,无向图,无向网} typedef struct ArcCell{VRType adj;//VRType是顶点关系类型，对无权图用1或0表示是否相邻；//对带权图则为权值类型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;void CreateMG(MGraph &M){int i,j;M.kind=DN;printf("输入顶点数:");scanf("%d",&M.vexnum);printf("输入弧数:");scanf("%d",&M.arcnum);printf("输入顶点:\n");for(i=0;i<M.vexnum;i++)scanf("%d",&M.vexs[i]);printf("建立邻接矩阵:\n");for(i=0;i<M.vexnum;i++)for(j=0;j<M.vexnum;j++)scanf("%d",&M.arcs[i][j].adj);printf("输入相应权值:\n");for(i=0;i<M.vexnum;i++)for(j=0;j<M.vexnum;j++)if(M.arcs[i][j].adj){scanf("%d",&M.arcs[i][j].info);}}typedef struct ArcNode{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;void PrintDN(ALGraph G){int i;ArcNode *p;printf("顶点:\n");for(i=0;i<G.vexnum;++i)printf("%2d",G.vertices[i].data);printf("\n弧:\n");for(i=0;i<G.vexnum;++i){p=G.vertices[i].firstarc;while(p){printf("%d→%d(%d)\t",i,p->adjvex,p->info);p=p->nextarc;}printf("\n");}//for}void CreateMGtoDN(ALGraph &G,MGraph M){//采用邻接表存储表示,构造有向图G(G.kind=DN)int i,j;ArcNode *p;G.kind=M.kind;G.vexnum=M.vexnum;G.arcnum=M.arcnum;for(i=0;i<G.vexnum;++i){//构造表头向量G.vertices[i].data=M.vexs[i];G.vertices[i].firstarc=NULL;//初始化指针}for(i=0;i<G.vexnum;++i)for(j=0;j<G.vexnum;++j)if(M.arcs[i][j].adj==1){p=(ArcNode*)malloc(sizeof(ArcNode));p->adjvex=j;p->nextarc=G.vertices[i].firstarc;p->info=M.arcs[i][j].info;G.vertices[i].firstarc=p;}}void CreateDNtoMG(MGraph &M,ALGraph G){int i,j;ArcNode *p;M.kind=GraphKind(G.kind);M.vexnum=G.vexnum;M.arcnum=G.arcnum;for(i=0;i<M.vexnum;++i)M.vexs[i]=G.vertices[i].data;for(i=0;i<M.vexnum;++i){p=G.vertices[i].firstarc;while(p){M.arcs[i][p->adjvex].adj=1;p=p->nextarc;}//whilefor(j=0;j<M.vexnum;++j)if(M.arcs[i][j].adj!=1)M.arcs[i][j].adj=0;}//for}void PrintMatrix(MGraph M){ int i,j;for(i=0;i<M.vexnum;++i){for(j=0;j<M.vexnum;++j) printf("%2d",M.arcs[i][j].adj); printf("\n");}}void main(){MGraph M,N;ALGraph G; CreateMG(M);PrintMatrix(M); CreateMGtoDN(G,M); PrintDN(G); CreateDNtoMG(N,G); PrintMatrix(N);}。
有向图的邻接矩阵有向图的邻接矩阵设有向图，，。
令为邻接到的边的条数，称为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中长度为的回路总数。
若再令矩阵，，……，上面定理有下面推论。
推论设，则中元素为D中到长度小于等于的通路数，为D中长度小于等于的通路总数，其中为D中长度小于等于的回路总数。
图结构（设计性）4.1 实验目的1．熟练掌握图的两种存储结构（邻接矩阵和邻接表）的表示方法。
2．掌握图的基本运算及应用。
3．加深对图的理解，逐步培养解决实际问题的编程能力。
4.2 实验要求1 •对图的各项操作一定要编写成为C （C++ ）语言函数，组合成模块化的形式，每个算法的实现要从时间复杂度和空间复杂度上进行评价。
2．将本算法中的各个操作实现。
3．保存程序的运行结果，并结合程序进行分析。
4．上机过程中，能够熟练运用高级语言的程序调试器DEBUG 调试程序。
5．上机后，认真整理源程序及其注释，完成实验报告（包括源程序、实验结果、算法分析、心得体会等）。
4.3 实验内容在VC++环境下编写调试图深度优先和广度优先遍历的算法和函数，或者把已布置作业中的算法改成程序，进行运行。
问题描述：输入每条边的顶点u和v及其权值w,然后建立用邻接矩阵表示的图。
其相关操作如下：1. 创建一个可以随机确定结点数和弧（有向或无向）数的图。
2. 根据图结点的序号，得到该结点的值。
3. 根据图结点的位置的第一个邻接顶点的序号，以及下一个邻接顶点的序号。
4. 实现从第v 个顶点出发对图进行深度优先递归遍历。
5. 实现对图作深度优先遍历。
6. 编写主程序，实现对各不同的算法调用。
4.4 实验清单#include <stdio.h>#define MAX_VERTEX_NUM 10 /* 最多顶点个数*/#define INFINITY 32768 /* 表示极大值，即*/#define True 1#define False 0#define Error -1#define Ok 1typedef enum{DG, DN, UDG, UDN} GraphKind; /* 图的种类：DG 表示有向图,DN表示有向网,UDG表示无向图,UDN表示无向网*/typedef char VertexData; /* 假设顶点数据为字符型*/typedef struct ArcNode{// AdjType adj; /*对于无权图，用1或0表示是否相邻；对带权图，则为权值类型*/// OtherInfo info;int adj;} ArcNode;typedef struct{VertexData vexs[MAX_VERTEX_NUM]; /*顶点向量*/ArcNode arcs[MAX_VERTEX_NUM][MAX_VERTEX_NUM]; /*邻接矩阵*/int vexnum,arcnum; /*图的顶点数和弧数*/GraphKind kind; /*图的种类标志*/}AdjMatrix; /*(Adjacency Matrix Graph)*/int LocateVertex(AdjMatrix *G ,VertexData v) /*求顶点位置函数*/{int j=Error,k;for(k=0;k<G->vexnum;k++)if(G->vexs[k]==v){j=k;break;}return(j);}int CreateDN(AdjMatrix *G) /*创建一个有向网*/{int i,j,k,weight;VertexData v1,v2;printf(" 输入图的弧数和顶点数\n");fflush(stdin);scanf("%d,%d",&G->arcnum,&G->vexnum); /* 输入图的顶点数和弧数*/ for(i=0;i<G->vexnum;i++) /*初始化邻接矩阵*/for(j=0;j<G->vexnum;j++)G->arcs[i][j].adj=INFINITY;for(i=0;i<G->vexnum;i++){printf(" 输入图的顶点\n"); fflush(stdin); scanf("%c",&G->vexs[i]); /* 输入图的顶点*/ } for(k=0;k<G->arcnum;k++){printf(" 输入一条弧的两个顶点及权值\n"); fflush(stdin);scanf("%c,%c,%d",&v1,&v2,&weight);/* 输入一条弧的两个顶点及权值*/i=LocateVertex(G,v1);j=LocateVertex(G,v2);G->arcs[i][j].adj=weight; /*建立弧*/}return(Ok);}void printf_adjmatrix(AdjMatrix *G){int i,j;printf(" ");for(i=0;i<G->vexnum;i++) {printf("%c",G->vexs[i]);printf(" ");} printf("\n");for(i=0;i<G->vexnum;i++) {printf("%c",G->vexs[i]);for(j=0;j<G->vexnum;j++){if(G->arcs[i][j].adj == INFINITY)printf(” x ")；elseprintf("%-4d", G->arcs[i][j].adj);}printf("\n");}}void main(){AdjMatrix G;CreateDN(&G);printf_adjmatrix(&G);4.5运行结果4.6实验心得对图结构和矩阵之间的概念和关系还不是很了解，在写程序是出现了很多错误我自己对输出图结构这方面还不是很了解，通过慢慢摸索，写出了程序，有很大的成就。
图基本算法图的表⽰⽅法邻接矩阵邻接表 要表⽰⼀个图G=(V,E)，有两种标准的表⽰⽅法，即邻接表和邻接矩阵。
这两种表⽰法既可⽤于有向图，也可⽤于⽆向图。
通常采⽤邻接表表⽰法，因为⽤这种⽅法表⽰稀疏图（图中边数远⼩于点个数）⽐较紧凑。
但当遇到稠密图（|E|接近于|V|^2）或必须很快判别两个给定顶点⼿否存在连接边时，通常采⽤邻接矩阵表⽰法，例如求最短路径算法中，就采⽤邻接矩阵表⽰。
图G=<V，E>的邻接表表⽰是由⼀个包含|V|个列表的数组Adj所组成，其中每个列表对应于V中的⼀个顶点。
对于每⼀个u∈V，邻接表Adj[u]包含所有满⾜条件（u，v）∈E的顶点v。
亦即，Adj[u]包含图G中所有和顶点u相邻的顶点。
每个邻接表中的顶点⼀般以任意顺序存储。
如果G是⼀个有向图，则所有邻接表的长度之和为|E|，这是因为⼀条形如（u，v）的边是通过让v出现在Adj[u]中来表⽰的。
如果G是⼀个⽆向图，则所有邻接表的长度之和为2|E|，因为如果（u，v）是⼀条⽆向边，那么u会出现在v的邻接表中，反之亦然。
邻接表需要的存储空间为O（V+E）。
邻接表稍作变动，即可⽤来表⽰加权图，即每条边都有着相应权值的图，权值通常由加权函数w：E→R给出。
例如，设G=<V，E>是⼀个加权函数为w的加权图。
对每⼀条边（u，v)∈E，权值w（u，v）和顶点v⼀起存储在u的邻接表中。
邻接表C++实现:1 #include <iostream>2 #include <cstdio>3using namespace std;45#define maxn 100 //最⼤顶点个数6int n, m; //顶点数，边数78struct arcnode //边结点9 {10int vertex; //与表头结点相邻的顶点编号11int weight = 0; //连接两顶点的边的权值12 arcnode * next; //指向下⼀相邻接点13 arcnode() {}14 arcnode(int v,int w):vertex(v),weight(w),next(NULL) {}15 arcnode(int v):vertex(v),next(NULL) {}16 };1718struct vernode //顶点结点，为每⼀条邻接表的表头结点19 {20int vex; //当前定点编号21 arcnode * firarc; //与该顶点相连的第⼀个顶点组成的边22 }Ver[maxn];2324void Init() //建⽴图的邻接表需要先初始化，建⽴顶点结点25 {26for(int i = 1; i <= n; i++)27 {28 Ver[i].vex = i;29 Ver[i].firarc = NULL;30 }31 }3233void Insert(int a, int b, int w) //尾插法，插⼊以a为起点，b为终点，权为w的边，效率不如头插，但是可以去重边34 {35 arcnode * q = new arcnode(b, w);36if(Ver[a].firarc == NULL)37 Ver[a].firarc = q;38else39 {40 arcnode * p = Ver[a].firarc;41if(p->vertex == b) //如果不要去重边，去掉这⼀段42 {43if(p->weight < w)44 p->weight = w;45return ;46 }47while(p->next != NULL)48 {49if(p->next->vertex == b) //如果不要去重边，去掉这⼀段50 {51if(p->next->weight < w);52 p->next->weight = w;53return ;54 }55 p = p->next;56 }57 p->next = q;58 }59 }60void Insert2(int a, int b, int w) //头插法，效率更⾼，但不能去重边61 {62 arcnode * q = new arcnode(b, w);63if(Ver[a].firarc == NULL)64 Ver[a].firarc = q;65else66 {67 arcnode * p = Ver[a].firarc;68 q->next = p;69 Ver[a].firarc = q;70 }71 }7273void Insert(int a, int b) //尾插法，插⼊以a为起点，b为终点，⽆权的边，效率不如头插，但是可以去重边74 {75 arcnode * q = new arcnode(b);76if(Ver[a].firarc == NULL)77 Ver[a].firarc = q;78else79 {80 arcnode * p = Ver[a].firarc;81if(p->vertex == b) return; //去重边，如果不要去重边，去掉这⼀句82while(p->next != NULL)83 {84if(p->next->vertex == b) //去重边，如果不要去重边，去掉这⼀句85return;86 p = p->next;87 }88 p->next = q;89 }90 }91void Insert2(int a, int b) //头插法，效率跟⾼，但不能去重边92 {93 arcnode * q = new arcnode(b);94if(Ver[a].firarc == NULL)95 Ver[a].firarc = q;96else97 {98 arcnode * p = Ver[a].firarc;99 q->next = p;100 Ver[a].firarc = q;101 }102 }103void Delete(int a, int b) //删除以a为起点，b为终点的边104 {105 arcnode * p = Ver[a].firarc;106if(p->vertex == b)107 {108 Ver[a].firarc = p->next;109 delete p;110return ;111 }112while(p->next != NULL)113if(p->next->vertex == b)114 {115 p->next = p->next->next;116 delete p->next;117return ;118 }119 }120121void Show() //打印图的邻接表（有权值）122 {123for(int i = 1; i <= n; i++)124 {125 cout << Ver[i].vex;126 arcnode * p = Ver[i].firarc;127while(p != NULL)128 {129 cout << "->(" << p->vertex << "," << p->weight << ")";130 p = p->next;131 }132 cout << "->NULL" << endl;133 }134 }135136void Show2() //打印图的邻接表(⽆权值）137 {138for(int i = 1; i <= n; i++)140 cout << Ver[i].vex;141 arcnode * p = Ver[i].firarc;142while(p != NULL)143 {144 cout << "->" << p->vertex;145 p = p->next;146 }147 cout << "->NULL" << endl;148 }149 }150int main()151 {152int a, b, w;153 cout << "Enter n and m：";154 cin >> n >> m;155 Init();156while(m--)157 {158 cin >> a >> b >> w; //输⼊起点、终点159 Insert(a, b, w); //插⼊操作160 Insert(b, a, w); //如果是⽆向图还需要反向插⼊161 }162 Show();163return0;164 }View Code 邻接表表⽰法也有潜在的不⾜之处，即如果要确定图中边（u,v）是否存在，只能在顶点u邻接表Adj[u]中搜索v，除此之外没有其他更快的办法。
邻接矩阵的实验原理及应用实验原理邻接矩阵是一种图的表示方法，通过矩阵的形式记录图中各个顶点之间的连接关系。
邻接矩阵可以用于描述有向图和无向图。
无向图的邻接矩阵无向图的邻接矩阵是一个方阵，其中的每个元素表示图中两个顶点之间是否存在边。
如果顶点i和顶点j之间存在边，则邻接矩阵的第i行第j列和第j行第i列的元素值都为1；否则，为0。
邻接矩阵的对角线上的元素表示各个顶点的度数。
有向图的邻接矩阵有向图的邻接矩阵同样是一个方阵，其中的每个元素表示从顶点i到顶点j是否存在边。
如果顶点i到顶点j存在边，则邻接矩阵的第i行第j列的元素值为1；否则，为0。
邻接矩阵的表示方法邻接矩阵可以用二维数组来表示，数组的大小为n×n，其中n为图中顶点的个数。
数组的下标表示顶点的编号，而数组中的元素表示邻接关系。
应用邻接矩阵在图的算法和应用领域有重要的应用。
图的遍历使用邻接矩阵可以进行图的遍历操作，包括深度优先遍历和广度优先遍历。
通过对邻接矩阵的遍历，可以访问图中所有的顶点和边。
最短路径算法邻接矩阵可以作为最短路径算法的基本数据结构。
通过邻接矩阵，可以方便地计算两个顶点之间的最短路径。
最小生成树算法最小生成树算法可以使用邻接矩阵作为数据结构。
通过构建邻接矩阵，并使用Prim算法或Kruskal算法，可以生成图的最小生成树。
图的连通性判断邻接矩阵可以用来判断图的连通性。
通过对邻接矩阵进行深度优先搜索或广度优先搜索，可以确定图中的连通分量。
图的可达性分析邻接矩阵可以用于分析图中顶点之间的可达性。
通过对邻接矩阵进行矩阵运算，可以得到图中任意两个顶点之间的可达性。
总结邻接矩阵是一种表示图的方法，通过矩阵的形式记录图中各个顶点之间的连接关系。
邻接矩阵具有简单、直观、易于操作等优点，在图的算法和应用中有广泛的应用。
通过对邻接矩阵的遍历、最短路径算法、最小生成树算法、连通性判断和可达性分析等操作，可以解决各种与图相关的问题。
以上就是邻接矩阵的实验原理及应用，希望对你有所帮助。
c语言邻接矩阵C语言邻接矩阵概述邻接矩阵是一种表示图的数据结构，它将图中的节点和边存储在一个二维数组中。
在C语言中，我们通常使用二维数组来实现邻接矩阵。
邻接矩阵的优点是可以快速地查找两个节点之间是否存在边，因为只需要访问矩阵中的一个元素即可。
但是，如果图非常大且稀疏，那么邻接矩阵会浪费很多空间。
实现首先，我们需要定义一个结构体来表示图：```ctypedef struct {int numVertices; // 节点数int **adjMatrix; // 邻接矩阵} Graph;```其中，`numVertices`表示节点数，`adjMatrix`是一个指向指针的指针，用于存储邻接矩阵。
然后，在创建图时，我们需要动态分配内存来存储邻接矩阵：```cGraph *createGraph(int numVertices) {Graph *graph = malloc(sizeof(Graph));graph->numVertices = numVertices;graph->adjMatrix = malloc(sizeof(int *) * numVertices);for (int i = 0; i < numVertices; i++) {graph->adjMatrix[i] = calloc(numVertices, sizeof(int));}return graph;}```在这段代码中，我们首先分配一个`Graph`结构体的内存，然后分配一个指向指针的指针来存储邻接矩阵。
接着，我们使用循环来为每一行分配内存，并将所有元素初始化为0。
接下来，我们可以定义一些函数来操作邻接矩阵。
例如，我们可以添加边：```cvoid addEdge(Graph *graph, int src, int dest) {graph->adjMatrix[src][dest] = 1;graph->adjMatrix[dest][src] = 1;}```在这个函数中，我们将`src`和`dest`之间的边设置为1。
图的邻接矩阵实现用邻接矩阵存放图中顶点的关系，实现无向图的邻接矩阵存储。
1）图的建立，删除（添加，删除边/顶点）2）广度和深度优先遍历3）prim最小生成树1，成员变量，构造函数，以及数组扩展实现策略：维护一个顶点的数组，以及一个二维的数组来表示顶点之间的关系，维护2个基本变量记录顶点和边的数量。
重点是：1）可以动态扩展顶点数组，并保持数组的连续性，这意味着删除顶点时后面的顶点要前移，那么顶点的编号也变了，关系矩阵也要改变。
2）关系矩阵也动态维护，随时保持和顶点数组一样大。
顶点数组的长度为VNodes.length，实际存放了顶点的位置只到了size()处，对应的，关系矩阵的大小为int[VNodes.length][VNodes.length]，实际有效地区域也只在左上角的int[size()][size()]范围内。
/*总是将关系矩阵保持和顶点数组大小对应，顶点数组不一定放满，关系矩阵也只* 在左上角放满，顶点数组放满的大小为size（），关系矩阵也只到size（）*/private VNode[] VNodes;private int[][] M;private int nodeCount;private int edgeCount;public MatUnDirectedGraph(){VNodes = new VNode[5];M = new int[5][5];nodeCount = 0;edgeCount = 0;}public void expand(){VNode[] larger = new VNode[VNodes.length * 2];//顶点数组扩大int[][] M_larger = new int[larger.length][larger.length];//关系矩阵也要扩展for(int i = 0;i < VNodes.length;i++){larger[i] = VNodes[i];for(int j = 0;j < VNodes.length;j++)M_larger[i][j] = M[i][j];}VNodes = larger;M = M_larger;}复制代码2，建图，删图相关方法分析用邻接矩阵存储表示顶点之间的关系果然比邻接表在代码实现上简单很多1）添加边，只需要在关系矩阵M的两个位置上赋值即可，而在邻接表实现中，要在2个顶点的边链表的最后都添加上一个边2）删除边，1）的逆过程，将那2个位置的值置为0即可，而在邻接表的实现中，也是要到边链表中去删（还要记录被删边得前缀）3）添加顶点，直接在顶点数组中添加一个，注意如果满的话，要扩展，在扩展方法中，已经实现了同时扩展关系矩阵（将矩阵变大了，左上角有效区域还是不变）。
在邻接表中这个稍微简单点，因为邻接表直接扩展数组即可，关系不用动。
4）删除顶点，无论哪种方式，删除顶点都是最麻烦的，在邻接表的实现中，删除顶点要先删除所有跟顶点关联的边，然后后面的顶点前移以保证顶点数组连续，移动会导致原来的顶点的边链表的信息变化（边的端点），所以在移动前我们先将所有边链表中的边得信息调整好，再来移动数组使它保持连续。
在邻接矩阵中，删除了一个顶点也要将顶点数组前移来保持顶点数组连续，结果会导致关系矩阵也要变（假设删除的顶点下标是position，那么左上角M[position][position]大小范围内的矩阵不需要变，从这个边界到M[size][size]范围的矩阵值要向内紧缩---也是因为顶点移动导致顶点下标变了，具体怎么去向内收缩，见代码及注释）添加和删除边：public void addEdge(int start,int end,int len){ //在两个指定下标的节点之间添加一条边M[start][end] = len;M[end][start] = len;edgeCount++;}//在图中2个顶点之间删除一条边public void removeEdge(int start,int end){ //删除两个指定下标顶点之间的边M[start][end] = 0;M[end][start] = 0;edgeCount--;}复制代码添加顶点：public void addVNode(Object element){ //添加顶点VNode node = new VNode(element);if(size() == VNodes.length)expand(); //扩展方法时同时扩展了关系矩阵VNodes[nodeCount++] = node;}复制代码上面三个方法都很简单，最复杂的仍然是删除顶点：弄清楚矩阵是怎么向左上角紧缩的public Object removeVNode(int position){ //删除顶点VNode result = VNodes[position];//先调整关系矩阵for(int i = 0;i < size();i++)for(int j = 0;j < size();j++) //将关系矩阵向内紧缩（顶点将要移动）{if(i > position && j > position)M[i-1][j-1] = M[i][j];else if(i > position)M[i-1][j] = M[i][j];else if(j > position)M[i][j-1] = M[i][j];}for(int i = 0;i < size();i++) //紧缩以后，最后一个顶点已经没有意义了（移到倒数第二个了） {M[size()-1][i] = 0;M[i][size()-1] = 0;}//再调整顶点数组for(int i = position;i < size()-1;i++)//保证数组连续性VNodes[i] = VNodes[i+1];VNodes[size()-1] = null;nodeCount--;return result;}复制代码3，广度优先遍历和深度优先遍历拿广度优先遍历来说，顶点A每次从遍历队列出来的时候要将其未被访问的关联顶点添加到遍历队列，这就需要求得A在顶点数组里的位置，然后在关系矩阵里找跟它关联且没有被访问的顶点。
深度优先一样。
仅贴出广度优先，深度优先的实现只需要把遍历队列改成遍历栈即可：//广度优先遍历图public Iterator GraphBFS(int position){ //可以遍历多个联通分量的BFSLinkedQueue queue = new LinkedQueue();BFSorder(position,queue);for(int i = 0;i < size();i++) //注意是size，不是VNodes.length,下面的BFSorder也是if(VNodes[i].getVisited() == false)BFSorder(i,queue);return queue.iterator();}public Iterator SingleBFS(int position){ //只遍历position所在连通域的BFSLinkedQueue queue = new LinkedQueue();BFSorder(position,queue);return queue.iterator();}private void BFSorder(int position,LinkedQueue queue){//按照广度规则从position开始将po sition所在连通分量顶点进队LinkedQueue tempqueue = new LinkedQueue();tempqueue.enqueue(VNodes[position]);VNodes[position].setVisited(true);while(!tempqueue.isEmpty()){VNode node = (VNode) tempqueue.dequeue();queue.enqueue(node);int index = 0;for(int i = 0;i < size();i++)if(VNodes[i] == node)index = i;//node在数组里的下标for(int i = 0;i < size();i++)if(M[index][i] != 0 && VNodes[i].getVisited() == false){tempqueue.enqueue(VNodes[i]);VNodes[i].setVisited(true);}}}复制代码4，prim最小生成树用邻接表写过之后，prim的思想也就很熟悉了，用邻接矩阵写也比较顺利，很容易就写成功了。
这里可以直接在关系矩阵M里去找最小值，简单一点，不像邻接表实现需要那么多的支持方法。
直接贴出代码：1//prim最小生成树2public Edge[] getEdges(int position){3 Edge[] Edges = new Edge[size()-1];4 VNodes[position].setVisited(true);5for(int i = 0;i < Edges.length;i++)6 Edges[i] = getMinEdge(VNodes);7return Edges;8 }910private Edge getMinEdge(VNode[] VNodes){ //从当前分割的两个顶点集合之间找最小边1112 //直接在关系矩阵中找就可以了(逻辑简单点，也可以从顶点数组去循环查找)13 Edge min = null;14for(int i = 0;i < size();i++)15for(int j = 0;j < size();j++)16if(VNodes[i].getVisited() && !VNodes[j].getVisited() && M[i][j] != 0) 17 {18if(min == null)19 min = new Edge(i,j,M[i][j]);20else21if(M[i][j] < min.getLen())22 min = new Edge(i,j,M[i][j]);23//VNodes[j].setVisited(true);24 }25 VNodes[min.getEnd()].setVisited(true);26return min;27 }28复制代码5，完整清单及测试MatUnDirectedGraph只贴出最小生成树的结果：仍然构造上节中的最小生成树---关系矩阵为：0 6 1 5 0 06 0 5 0 5 01 5 0 5 6 45 0 5 0 0 20 5 6 0 0 60 0 4 2 6 0输出最小生成树的边:边：V1---V3 长度：1 边：V3---V6 长度：4 边：V6---V4 长度：2 边：V3---V2 长度：5 边：V2---V5 长度：5。
