图的矩阵表示

图基本算法图的表⽰⽅法邻接矩阵邻接表 要表⽰⼀个图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列到第j行第i列也具有相同的值，表示了节点之间的邻接关系。

主要公式如下：1. 无向图对于一个n个节点的无向图来说，邻接矩阵的元素a[i][j]表示的是节点i和节点j之间是否存在边，其中0表示没有边，1表示有边。

由于是无向图，所以矩阵的上下三角是对称的。

下面是一个无向图的邻接矩阵示例：```0 1 1 01 0 1 01 1 0 10 0 1 0```2. 有向图对于一个n个节点的有向图来说，邻接矩阵的元素a[i][j]表示的是节点i到节点j是否存在有向边，其中0表示没有有向边，1表示有有向边。

下面是一个有向图的邻接矩阵示例：```0 1 0 00 0 1 01 0 0 10 0 1 0```邻接矩阵的优点是方便且易于理解，可以用于表示不同类型的图。

但是在稀疏图中会存在大量的0元素，浪费空间，此时可以使用邻接表优化。

二、度矩阵度矩阵是一个n维的矩阵，表示每个节点的度数情况。

主要公式如下：1. 无向图对于无向图来说，每个节点的度数等于该节点所连的所有边的数量。

度矩阵的第i个对角线元素d[i][i]表示节点i的度数。

下面是一个无向图的度矩阵示例：```2 0 0 00 2 0 00 0 3 00 0 0 1```2. 有向图对于有向图来说，每个节点的入度和出度可以分别计算。

入度是指以节点i为终点的边的数量，出度是指以节点i为起点的边的数量。

度矩阵的第i个对角线元素d[i][i]表示节点i的总度数，即入度与出度之和。

下面是一个有向图的度矩阵示例：```2 1 0 00 0 1 01 0 1 10 1 0 0```度矩阵的优点是可以方便地计算得到每个节点的度数情况，可以用于分析图的特性和性质，如连通性、欧拉图等。

度矩阵邻接矩阵度矩阵和邻接矩阵是图论中比较常见的两种矩阵表示方法。

度矩阵是表示无向图和有向图的一种矩阵，它是一个n*n的矩阵，其中n表示图中顶点的个数。

度矩阵主要表示每个顶点的度数（即与该顶点相邻的边的条数）。

对于无向图来说，度矩阵的对角线上的元素代表各个顶点的度数；对于有向图来说，度矩阵的每个元素代表出度与入度之和。

邻接矩阵是图的一种矩阵表示方式，它是一个n*n的矩阵，其中n表示图中顶点的个数。

邻接矩阵记录了每一对顶点之间是否有边相连，若有则为1，否则为0。

对于无向图来说，邻接矩阵为对称矩阵；对于有向图来说，邻接矩阵则不一定对称。

下面我们将分别介绍度矩阵和邻接矩阵的特点和应用。

一、度矩阵度矩阵主要有以下几个特点：1. 度矩阵是一个对角矩阵，对角线上的元素分别表示每个顶点的度数。

2. 对于无向图来说，度矩阵的对角线上的元素为非负整数；对于有向图来说，度矩阵的每个元素为整数。

3. 度矩阵与邻接矩阵之间可以相互转换。

若邻接矩阵为A，则度矩阵为D=diag(d1,d2,d3,...,dn)，其中di为第i个顶点的度数，即di=sum(A[i,j])。

4. 度矩阵可以用来计算图的一些性质，如图的正则性（若存在一对顶点，它们的度数相同，则称该图是正则图）、图的平均度数等。

5. 度矩阵还可以用来求解拉普拉斯矩阵，进而在谱聚类等领域得到广泛应用。

二、邻接矩阵1. 假设图中有n个顶点，邻接矩阵是一个n*n的方阵。

其中第i行第j列的元素表示顶点i到顶点j是否有一条边相连，若有则为1，否则为0。

2. 对于无向图来说，邻接矩阵是一个对称矩阵；对于有向图则不一定对称。

3. 邻接矩阵可以用来计算一些图的性质，如图的连通性、图的同构性等。

4. 邻接矩阵可以与度矩阵相互转换。

若度矩阵为D，则邻接矩阵为A={(i,j)|i与j 之间有边相连}，其中A[i,j]为1表示i与j之间有边相连，否则为0。

对于无向图来说，A[i,j]=A[j,i]，即邻接矩阵为对称矩阵。

图的表示方法图是一种常用的数据结构，用于描述事物之间的关系或连接。

在计算机科学和信息技术领域，图的表示方法是研究和应用的关键。

本文将介绍图的常见表示方法，并探讨它们的特点和适用场景。

1. 邻接矩阵表示法邻接矩阵是一种使用二维矩阵表示图的方式。

其中矩阵的行和列分别对应图中的顶点，而矩阵的元素表示图中顶点之间的边。

如果两个顶点之间存在边，则矩阵对应位置的元素为1，否则为0。

如果图是有权重的，则可以将权重值存储在矩阵的元素中。

邻接矩阵的优点是简单直观，易于理解和实现。

它可以快速检查两个顶点之间是否存在边，时间复杂度为O(1)。

然而，邻接矩阵的缺点是占用空间较大，特别是对于稀疏图而言，大量的0元素浪费了存储空间。

2. 邻接表表示法邻接表是一种使用链表表示图的方式。

其中每个顶点都对应一个链表，链表中存储与该顶点相邻的顶点。

如果图是有权重的，则链表节点可以包含权重值。

邻接表的优点是占用空间较小，特别适用于表示稀疏图。

它可以快速访问和遍历某个顶点相邻的顶点，时间复杂度为O(k)，其中k是顶点相邻的边的数量。

然而，邻接表的缺点是不方便检查两个顶点之间是否存在边，需要遍历链表。

3. 关联矩阵表示法关联矩阵是一种使用二维矩阵表示图的方式，其中矩阵的行对应顶点，列对应边。

关联矩阵中，如果顶点与边相连，则对应位置元素为1，否则为0。

关联矩阵的优点是可以较为直观地表示图的结构和关系。

它适用于表示有向图和无向图，以及多重图。

然而，关联矩阵的缺点是占用空间较大，尤其对于有大量顶点和边的图而言。

4. 边列表表示法边列表是一种使用列表表示图的方式。

其中列表中的每个元素存储边的信息，包括起点、终点和权重等。

对于有向图，边列表包含有向边的信息。

边列表的优点是比较节省存储空间，特别适合表示稀疏图。

它便于遍历和访问边的信息，但相应地，检查两个顶点之间是否有边的操作较为耗时。

综上所述，图的表示方法有邻接矩阵、邻接表、关联矩阵和边列表等多种形式，每种方法都有自己的特点和适用场景。