海口商城网站建设,淘宝网站建设教程视频,濮阳新闻直播,如何建设网站内容一.邻接矩阵 1.图的特点 任何两个顶点之间都可能存在边#xff0c;无法通过存储位置表示这种任意的逻辑关系。
图无法采用顺序存储结构。 2.如何存储图#xff1f;
将顶点与边分开存储。 3.邻接矩阵#xff08;数组表示法#xff09;
基本思想#xff1a;
用一个一维数…一.邻接矩阵 1.图的特点 任何两个顶点之间都可能存在边无法通过存储位置表示这种任意的逻辑关系。
图无法采用顺序存储结构。 2.如何存储图
将顶点与边分开存储。 3.邻接矩阵数组表示法
基本思想
用一个一维数组存储图中顶点的信息用一个二维数组存储图中各顶点之间的邻接关系。
假设图G有n个顶点则它的邻接矩阵是一个n*n的方阵 4.无向图的邻接矩阵
1.特点
无向图的邻接矩阵是一个对称矩阵主对角线为0 2.如何求顶点i的度
邻接矩阵的第i行非零元素的个数 3.如何判断顶点i和j之间是否存在边
判断arc[i][j]是否为1 4.如何求顶点i的所有邻接点
将数组中第i行元素扫描一遍若arc[i][j]为1则顶点j为顶点i的邻接点 5.有向图的邻接矩阵
有向完全图任意两个顶点之间都有方向相反的弧 1.如何求顶点i的出度
扫描第i行
2.如何求顶点i的入度
扫描第i列 6.网图的邻接矩阵 二.邻接矩阵存储无向图的类 const int MAX_VERTEX10;//图的最大顶点数
template class T
class MGraph{
private:T vertex[MAX_VERTEX];int arc[MAX_VERTEX][MAX_VERTEX];int vertexNum,arcNum;//实际顶点个数边的条数
public:MGraph(T v[],int n,int e);~MGraph();void DFSTraverse(int v);void BFSTraverse(int v);
};
templateclass T
MGraphT::MGraph(T v[],int n,int e){int vi,vj;vertexNumn;arcNume;for(int i0;in;i){vertex[i]v[i];}for(int i0;in;i){//初始化邻接矩阵for(int j0;jn;j){arc[i][j]0;}}for(int i0;ie;i){//依次输入每一条边cinvivj;//输入边依附的两个顶点的编号arc[vi][vj]1;arc[vj][vi]1;}
}
