怎么做点击图片进网站,wordpress 博客模版,社交电商,seo搜索优化公司排名文章目录 邻接表特点邻接矩阵和邻接表表示法的关系 邻接表#xff08;Adjacency List#xff09; 是图的一种链式存储结构。 #includeiostream
using namespace std;#define MVNum 100 //最大顶点数
#define OtherInfo int //权值
#define VerTexType int//顶点的指针… 文章目录 邻接表特点邻接矩阵和邻接表表示法的关系 邻接表Adjacency List 是图的一种链式存储结构。 #includeiostream
using namespace std;#define MVNum 100 //最大顶点数
#define OtherInfo int //权值
#define VerTexType int//顶点的指针域
#define Status inttypedef struct ArcNode { //边结点int adjvex;//该边指向的顶点的位置struct ArcNode* nextarc;//指向下一条边的指针OtherInfo info;//和边相关的信息如权值等
}ArcNode;typedef struct VNode {//顶点信息VerTexType data;ArcNode* firstarc;//指向第一条依附于该顶点的边的指针
}VNode,AdjList[MVNum];//邻接表typedef struct
{AdjList vertices;//图的边结点组成的数组int vexnum, arcnum;//图的边结点的所有顶点数和边数
}ALGraph;int LocateVex(ALGraph G, VerTexType v);//创建无向图
Status CreateALGraph(ALGraph G) {ArcNode* p1,*p2;int i,j;cout请输入邻接表的顶点数和边的数目 endl;cin G.vexnum G.arcnum;cout 请输入邻接表的顶点 endl;for (i 0; i G.vexnum; i) {cin G.vertices[i].data;G.vertices[i].firstarc NULL;//初始化邻接点}for (i 0; i G.arcnum; i) {VerTexType v1, v2;cin v1 v2;i LocateVex(G, v1);j LocateVex(G, v2);//确定v1v2在G中的位置即顶点在G.vertices中的序号p1 new ArcNode;//生成一个新的边结点*p1p1-adjvex j;//邻接点序号jp1-nextarc G.vertices[i].firstarc;G.vertices[i].firstarc p1;//将新结点*p1插入顶点vi的表边结点p2 new ArcNode;//生成另一个对称的新的边结点*p2p2-adjvex i;//邻接结点序号ip2-nextarc G.vertices[j].firstarc;G.vertices[j].firstarc p2;//将新结点插入顶点vj的边表头部}return 1;
}int LocateVex(ALGraph G, VerTexType v) {//返回顶点u在图中的位置int i;for (i 0; i G.vexnum G.vertices[i].data ! v; i) {if (i G.vexnum) {return -1;}else {return i;}}
}void showAdj(ALGraph G) {int i;cout 头结点 邻接点 endl;for (i 0; i G.vexnum; i) {cout G.vertices[i].data ;ArcNode* ptr G.vertices[i].firstarc;while (ptr ! NULL) {cout -- G.vertices[ptr-adjvex].data ;ptr ptr-nextarc;}cout endl;}
}int main() {ALGraph G;CreateALGraph(G);showAdj(G);return 0;
}邻接表特点
方便找任一顶点的所有“邻接点”。节约稀疏图的空间 需要N个头指针2E个结点每个结点2个域。 方便计算任一顶点的“度” 对无向图是的对有向图只能计算“出度”需要构造“逆邻接表”存指向自己的边来方便计算“入度” 不方便检查任意一对顶点间是否存在边。
邻接矩阵和邻接表表示法的关系
区别 1.对于任一确定的无向图邻接矩阵是唯一的行列号与顶点编号一致但邻接表不唯一链接次序与顶点编号无关。 2.邻接矩阵的空间复杂度为On平方而邻接表的空间复杂度为One。 用途 邻接矩阵多用于稠密图而邻接表多用于稀疏图。
