【图】什么是图?无向图怎么存储?邻接表和邻接矩阵如何用代码存储图?

这篇具有很好参考价值的文章主要介绍了【图】什么是图?无向图怎么存储?邻接表和邻接矩阵如何用代码存储图?。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

目录

一、概念

图是什么

各种图的定义

二、图的存储结构

邻接矩阵

邻接表

三、代码实现图的存储

1.无向图存储

2.邻接矩阵存储图

核心代码

完整代码

3.邻接表存储有向图(不含权重)

核心代码

完整代码


一、概念

图是什么

        图(Graph)是由顶点的有穷非空集合和顶点之间的集合组成,通常表示为:G(V,E),其中,G 表示一个图,V 是图G 中顶点的集合,E 是图G 中边的集合。

各种图的定义

        若顶点v1到V之间的边没有方向,则称这条边为无向边(Edge),用无序偶对(v,vy) 来表示。如果图中任意两个顶点之间的边都是无向边,则称该图为无向图(Undirected graphs)。 下图左图就是一个无向图,由于是无方向的,连接顶点A与D的边,可以表示成无序对(A,D), 也可以写成(D,A)。

        对于左图无向图G1来说,G1= (V,{E1}), 其中顶点集合V1={A,B,C,D};边集合E1={ (A,B) ,(B,C) ,(C,D) ,(D,A) ,(A,C) }。

        有向边:若从顶点 v到的边有方向,则称这条边为有向边,也称为弧(Arc )。用有序偶<vi, v1>来表示称为弧尾(Tail)称为头(Head)。如果图中任意两个顶点之间的边都是有向边,则称该图为有向图(Directed graphs)。图 7-2-3就是一个有向图。连接顶点A到 D的有向边就是A是尾D是头AD表示注意不能写成<D,A>。

邻接矩阵存储图,数据结构,图论
 

        在图中,若不存在顶点到其自身的边,且同一条边不重复出现,则称这样的图为简单图。如下两种图就不属于我们讨论的范围。 

邻接矩阵存储图,数据结构,图论

        在无向图中,如果任意两个顶点之间都存在边,则称该图为无向完全图。含有n个顶点的无向完全图有 n*(n-1)/2 条边。比如图7-2-5 就是无向完全图,因为每个顶点都要与除它以外的顶点连线,顶点A与BCD三个顶点连线,共有四个顶点,自然是4x3,但由于顶点A与顶点B连线后,计算B与A连线就是重复,因此要整体除以2,共有6条边。

邻接矩阵存储图,数据结构,图论

          在有向图中,如果任意两个顶点之间都存在方向互为相反的两条弧,则称改图为有向完全图。含有n个顶点的有向完全图有n*(n-1)条边。如下图所示。

邻接矩阵存储图,数据结构,图论

        有很少条边或弧的图称为稀疏图,反之称为稠密图。这里稀疏和稠密是模糊的概念,都是相对而言的。

        有些图的边或弧具有与它相关的数字,这种与图的边或弧相关的数叫做(Weight)。这些权可以表示从一个顶点到另一个顶点的距离或耗费。这种带权的图通常称为(Network)。下图就是一张带权的图,即标识中国四大城市的直线距离的网,此图中的权就是两地的距离。

邻接矩阵存储图,数据结构,图论

        假设有两个图 G=(V{E})和G`=(V`{E`}),如果V`包含于V且E`包含于E,则称G`为G的子图(Subgraph)(文字描述就是子图的顶点和边都在G图内存在)。例如下图带底纹的图均为左侧无向图与有向图的子图。

邻接矩阵存储图,数据结构,图论

        路径的长度是路径上的边或的数目。下图中左侧路径长为2,右侧路径长度为3。

邻接矩阵存储图,数据结构,图论

        第一个顶点到最后一个顶点相同的路径称为回路(Cycle)。序列中顶点不重复出现的路径称为简单路径。除了第一个顶点和最后一个顶点之外,其余顶点不重复出现的回路,称为简单回路或简单环。

        图中任意两个顶点之间是连通的,有路径的,则称该图为连通图。

        无向图中的极大连通子图称为连通分量。注意连通分量的概念,它强调:

  • 要是子图;
  • 子图要是连通的;
  • 连通子图含有极大顶点数:
  • 具有极大顶点数的连通子图包含依附于这些顶点的所有边。

总结:

  • 1.图按照有无方向分为无向图和有向图。无向图由顶点和边构成,有向图由顶点和弧构成。弧有弧尾和弧头之分。
  • 2.图按照边或弧的多少分稀疏图和稠密图。如果任意两个顶点之间都存在边叫完全图,有向的叫有向完全图。若无重复的边或顶点到自身的边则叫简单图。
  • 3.图中顶点之间有邻接点、依附的概念。无向图顶点的边数叫做,有向图顶点分为入度和出度
    •  什么是邻接? 两个顶点之间有边的连接就成两点为邻接,在下图中g、f 就不邻接:
    • 邻接矩阵存储图,数据结构,图论

    • 入度和出度:

      • 在有向图中,箭头是具有方向的,从一个顶点指向另一个顶点,这样一来,每个顶点被指向的箭头个数,就是它的入度。从这个顶点指出去的箭头个数,就是它的出度

      •  在下图的有向网中,v1的出度:2,入度:0。

        邻接矩阵存储图,数据结构,图论

  • 4.图上的边或弧上带权则称为
  • 5.图中顶点间存在路径,两顶点存在路径则说明是连通的,如果路径最终回到起始点则称为环,当中不重复叫简单路径。若任意两顶点都是连通的,则图就是连通图,有向则称强连通图。图中有子图,若子图极大连通则就是连通分量,有向的则称强连通分量。
  • 6.无向图中连通且n个顶点 n-1条边叫生成树。有向图中一顶点入度为0其余顶点入度为1的叫有向树。一个有向图由若干棵有向树构成生成森林。

二、图的存储结构

        图的存储结构相较线性表与树来说就更加复杂了。首先,我们口头上说的“顶点的位置”或“邻接点的位置”只是一个相对的概念。其实从图的逻辑结构定义来看,图上任何一个顶点都可被看成是第一个顶点,任一顶点的邻接点之间也不存在次序关系。

        比如下图的四张图,仔细观察发现,它们其实是同一个图,只不过顶点的位置不同,就造成了表象上不太一样的感觉。

邻接矩阵存储图,数据结构,图论

邻接矩阵

为什么用邻接矩阵解决?

        考虑到图是由顶点和边或弧两部分组成。合在一起比较困难,那就很自然地考虑到分两个结构来分别存储。顶点不分大小、主次,所以用一个一维数组来存储是很不错的选择。而边或弧由于是顶点与顶点之间的关系,一维搞不定,那就考虑用一个二维数组来存储。于是我们的邻接矩阵的方案就诞生了。

邻接矩阵如何存储?

        图的邻接矩阵(Adjacency Matrix)存储方式是用两个数组来表示图一个一维数组存储图中顶点信息,一个二维数组(称为邻接矩阵)存储图中的边或弧的信息。

        如下,左图为一无向图,右图为根据左图设置的邻接矩阵,如果两顶点之间有边则值为1,无边值为0。某个顶点的度是这个顶点在接矩阵中第i行(或第i列)的元素之和。比如顶点 v1的度就是1+0+1+0=2。

邻接矩阵存储图,数据结构,图论

下图为有向图及其邻接矩阵。

 邻接矩阵存储图,数据结构,图论

邻接表

        邻接矩阵是不错的一种图存储结构,但是对于边数相对顶点较少的图,这种结构是存在对存储空间的极大浪费的。比如说,如果我们要处理下图这样的稀疏有向图,邻接矩阵中除了arc[1][0]有权值外,没有其他弧,其实这些存储空间都浪费掉了。

邻接矩阵存储图,数据结构,图论

         因此,引入同样适用于图的存储的邻接表。

        邻接表( Adjacency List)是数组与链表相结合的存储方法。具体如下:

  1. 顶点用一个一维数组存储,当然,顶点也可以用单链表来存储,不过数组可以较容易地读取顶点信息,更加方便。另外,对于顶点数组中,每个数据元素还需要存储指向第一个邻接点的指针,以便于查找该顶点的边信息。
  2. 图中每个顶点v的所有邻接点构成一个线性表,由于邻接点的个数不定,所以用单链表存储,无向图称为顶点v的边表,有向图则称为顶点v作为弧尾的出边表。例如下图所示的就是一个无向图的邻接表结构。邻接矩阵存储图,数据结构,图论

        从图中我们知道,顶点表的各个结点由data和 firstedge 两个域表示,data是数据域,存储顶点的信息,firstedge 是指针域,指向边表的第一个结点,即此顶点的第一个邻接点。边表结点由adjvex和 next两个域组成。adjvex是邻接点域,存储某顶点的邻接点在顶点表中的下标,next则存储指向边表中下一个结点的指针。比如v1顶点与vo、vz互为邻接点,则在v1的边表中,adjvex 分别为vo的0和vz的2。
        这样的结构,对于我们要获得图的相关信息也是很方便的。比如我们要想知道某个顶点的度,就去查找这个顶点的边表中结点的个数。若要判断顶点v到v是否存在边,只需要测试顶点v的边表中 adjvex是否存在结点v的下标j就行了。若求顶点的所有邻接点,其实就是对此顶点的边表进行遍历,得到的adjvex域对应的顶点就是邻接点。
        若是有向图,邻接表结构是类似的,比如图下图中第一幅图的邻接表就是第二幅图。但要注意的是有向图由于有方向,我们是以顶点为弧尾来存储边表的,这样很容易就可以得到每个顶点的出度。但也有时为了便于确定顶点的入度或以顶点为弧头的弧,我们可以建立一个有向图的逆邻接表,即对每个顶点v都建立一个链接为v为弧头的表。如下图最下面的图所示。

邻接矩阵存储图,数据结构,图论

        此时我们很容易就可以算出某个顶点的入度或出度是多少,判断两顶点是否存在弧也很容易实现。
        对于带权值的网图,可以在边表结点定义中再增加一个 weight的数据域,存储权值信息即可,如下图所示。

邻接矩阵存储图,数据结构,图论文章来源地址https://www.toymoban.com/news/detail-791957.html

三、代码实现图的存储

1.无向图存储

#include<iostream>
using namespace std;
#define SIZE 10
class Graph
{
public:
	Graph();
	~Graph();
	void InsertVertex(char v);
	void InsertEdge(char v1, char v2);
	int GetVertexIndex(char v);
	void ShowGraph();
private:
	int m_MaxVertex; //能存储的最大顶点个数
	int m_NumVertex; //实际存储的个数
	char* m_Vertex;    //存储顶点的一维数组
	int m_Edge[SIZE][SIZE]; //存储边的二维数组
};

Graph::Graph()
{
	m_MaxVertex = SIZE;
	m_NumVertex = 0;
	m_Vertex = new char[m_MaxVertex];
	int i, j;
	for (i = 0; i < m_MaxVertex; i++)
	{
		for (j = 0; j < m_MaxVertex; j++)
			m_Edge[i][j] = 0;
	}
}

Graph::~Graph()
{
	if (m_Vertex != NULL)
	{
		delete[]m_Vertex;
		m_Vertex = NULL;
	}
	m_NumVertex = 0;
}

void Graph::InsertVertex(char v)
{
	if (m_NumVertex >= m_MaxVertex)
	{
		return;
	}
	m_Vertex[m_NumVertex++] = v;
}
void Graph::InsertEdge(char v1, char v2)
{
	int v1index = GetVertexIndex(v1);
	int v2index = GetVertexIndex(v2);
	if (v1index == -1 || v2index == -1)
		return;
	m_Edge[v1index][v2index] = 1;
	m_Edge[v2index][v1index] = 1;
}
int Graph::GetVertexIndex(char v)
{
	int i;
	for (i = 0; i < m_NumVertex; i++)
	{
		if (m_Vertex[i] == v)
			return i;
	}
	return -1; //如果没有找到
}
void Graph::ShowGraph()
{
	int i, j;
	cout << "  ";
	for (i = 0; i < m_NumVertex; i++)
		cout << m_Vertex[i] << " ";
	cout << endl;
	for (i = 0; i < m_NumVertex; i++)
	{
		cout << m_Vertex[i] << " ";
		for (j = 0; j < m_NumVertex; j++)
			cout << m_Edge[i][j] << " ";
		cout << endl;
	}
}

void main()
{
	Graph g;
	g.InsertVertex('a');
	g.InsertVertex('b');
	g.InsertVertex('c');
	g.InsertVertex('d');
	g.InsertEdge('a', 'b');
	g.InsertEdge('a', 'c');
	g.InsertEdge('a', 'd');
	g.InsertEdge('b', 'c');
	g.InsertEdge('c', 'd');
	g.ShowGraph();
}

2.邻接矩阵存储图

核心代码

int Graph::GetVertexIndex(char v)//得到顶点所在下标
{
	int i;
	for (i = 0; i < m_NumVertex; i++)
	{
		if (m_Vertex[i] == v)
			return i;
	}
	return -1; //如果没有找到
}
void Graph::InsertVertex(char v) //插入顶点
{
	if (m_NumVertex >= m_MaxVertex)
	{
		return;
	}
	m_Vertex[m_NumVertex++] = v;
}
void Graph::InsertEdge(char v1, char v2,int w) //插入边
{
	int v1index = GetVertexIndex(v1);
	int v2index = GetVertexIndex(v2);
	if (v1index == -1 || v2index == -1)
		return;
	m_Edge[v1index][v2index] = w;
	m_Edge[v2index][v1index] = w;
}

完整代码

#include<iostream>
using namespace std;

#define SIZE 10
#define MAX_WEIGHT 65535
class Graph
{
public:
	Graph();
	~Graph();
	void InsertVertex(char v);
	void InsertEdge(char v1, char v2,int w);
	void DeleteEdge(char v1, char v2);
	int GetVertexIndex(char v);
	void ShowGraph();
private:
	int m_MaxVertex; //能存储的最大顶点个数
	int m_NumVertex; //实际存储的个数
	char* m_Vertex;    //存储顶点的一维数组
	int m_Edge[SIZE][SIZE]; //存储边的二维数组
};

Graph::Graph()
{
	m_MaxVertex = SIZE;
	m_NumVertex = 0;
	m_Vertex = new char[m_MaxVertex];
	int i, j;
	for (i = 0; i < m_MaxVertex; i++)
	{
		for (j = 0; j < m_MaxVertex; j++)
		{
			if (i == j)
				m_Edge[i][j] = 0;
			else
				m_Edge[i][j] = MAX_WEIGHT;
		}
	}
}

Graph::~Graph()
{
	if (m_Vertex != NULL)
	{
		delete[]m_Vertex;
		m_Vertex = NULL;
	}
	m_NumVertex = 0;
}

void Graph::InsertVertex(char v)
{
	if (m_NumVertex >= m_MaxVertex)
	{
		return;
	}
	m_Vertex[m_NumVertex++] = v;
}
void Graph::InsertEdge(char v1, char v2,int w)
{
	int v1index = GetVertexIndex(v1);
	int v2index = GetVertexIndex(v2);
	if (v1index == -1 || v2index == -1)
		return;
	m_Edge[v1index][v2index] = w;
	m_Edge[v2index][v1index] = w;
}
void Graph::DeleteEdge(char v1, char v2)
{
	int v1index = GetVertexIndex(v1);
	int v2index = GetVertexIndex(v2);
	if (v1index == -1 || v2index == -1)
		return;
	m_Edge[v1index][v2index] = m_Edge[v2index][v1index] = MAX_WEIGHT;
}
int Graph::GetVertexIndex(char v)
{
	int i;
	for (i = 0; i < m_NumVertex; i++)
	{
		if (m_Vertex[i] == v)
			return i;
	}
	return -1; //如果没有找到
}
void Graph::ShowGraph()
{
	int i, j;
	cout << "  ";
	for (i = 0; i < m_NumVertex; i++)
		cout << m_Vertex[i] << " ";
	cout << endl;
	for (i = 0; i < m_NumVertex; i++)
	{
		cout << m_Vertex[i] << " ";
		for (j = 0; j < m_NumVertex; j++)
		{
			if (m_Edge[i][j] == MAX_WEIGHT)
				cout << "* ";
			else
				cout << m_Edge[i][j] << " ";
		}
		cout << endl;
	}
}

void main()
{
	Graph g;
	g.InsertVertex('a');
	g.InsertVertex('b');
	g.InsertVertex('c');
	g.InsertVertex('d');
	g.InsertEdge('a', 'b',5);
	g.InsertEdge('a', 'c',8);
	g.InsertEdge('a', 'd',3);
	g.InsertEdge('b', 'c',6);
	g.InsertEdge('c', 'd',4);
	g.ShowGraph();
	g.DeleteEdge('a', 'd');
	g.ShowGraph();
}

3.邻接表存储有向图(不含权重)

核心代码

int Graph::GetVertexIndex(char v) //得到顶点所在下标
{
	int i;
	for (i = 0; i < m_NumVertex; i++)
	{
		if (m_VerArr[i].m_value == v)
			return i;
	}
	return -1;
}
void Graph::InsertVertex(char v) //插入顶点
{
	if (m_NumVertex >= m_MaxVertex)
		return;
	m_VerArr[m_NumVertex++].m_value = v;
}

void Graph::InsertEdge(char v1, char v2) //插入边
{
	int p1index = GetVertexIndex(v1);
	int p2index = GetVertexIndex(v2);
	if (p1index == -1 || p2index == -1)
		return;
	//v1-v2
	Edge* p = new Edge(p2index);
	p->m_next = m_VerArr[p1index].m_list;
	m_VerArr[p1index].m_list = p;
	//v2-v1
	p = new Edge(p1index);
	p->m_next = m_VerArr[p2index].m_list;
	m_VerArr[p2index].m_list = p;
}

完整代码

#include<iostream>
using namespace std;
#define SIZE 10
class Edge
{
public:
	Edge() :m_next(NULL) {}
	Edge(int index) :m_destindex(index), m_next(NULL) {}
	int m_destindex;
	Edge* m_next;
};
class Vertex
{
public:
	Vertex() :m_list(NULL) {}
	Vertex(char v) :m_value(v), m_list(NULL) {}
	char m_value;
	Edge* m_list;
};
class Graph
{
public:
	Graph();
	~Graph();
	void InsertVertex(char v);
	void InsertEdge(char v1, char v2);
	int GetVertexIndex(char v);
	void ShowGraph();
	void DeleteEdge(char v1, char v2);
	void DeleteVertex(char v);
private:
	int m_MaxVertex;
	int m_NumVertex;
	//Vertex* m_VerArr;
	Vertex m_VerArr[SIZE];
};
void Graph::ShowGraph() //输出图
{
	Edge* p = NULL;
	for (int i = 0; i < m_NumVertex; i++)
	{
		cout << i << " " << m_VerArr[i].m_value << "->";
		p = m_VerArr[i].m_list;
		while (p != NULL)
		{
			cout << p->m_destindex << "->";
			p = p->m_next;
		}
		cout << "nul" << endl;
	}
}
void Graph::DeleteVertex(char v) //删除顶点
{
	int vindex = GetVertexIndex(v);
	if (vindex == -1)
		return;
	Edge* p = m_VerArr[vindex].m_list;
	char destVertex;
	while (p != NULL)
	{
		destVertex = m_VerArr[p->m_destindex].m_value;
		DeleteEdge(v, destVertex);
		p = m_VerArr[vindex].m_list;
	}
	//覆盖
	m_NumVertex--;
	m_VerArr[vindex].m_value = m_VerArr[m_NumVertex].m_value;
	m_VerArr[vindex].m_list = m_VerArr[m_NumVertex].m_list;

	p = m_VerArr[vindex].m_list;
	Edge* q = NULL;
	while (p != NULL)
	{
		int k = p->m_destindex;
		q = m_VerArr[k].m_list;
		while (q != NULL)
		{
			if (q->m_destindex == m_NumVertex)
			{
				q->m_destindex = vindex;
				break;
			}
			q = q->m_next;
		}
		p = p->m_next;
	}
}
void Graph::DeleteEdge(char v1, char v2) //删除边
{
	int p1index = GetVertexIndex(v1);
	int p2index = GetVertexIndex(v2);
	if (p1index == -1 || p2index == -1)
		return;
	//v1-v2
	Edge* pf = NULL;
	Edge* p = m_VerArr[p1index].m_list;
	while (p != NULL && p->m_destindex != p2index)
	{
		pf = p;
		p = p->m_next;
	}
	if (p == NULL)
		return;
	if (pf == NULL)
	{
		m_VerArr[p1index].m_list = p->m_next;
	}
	else
	{
		pf->m_next = p->m_next;
	}
	delete p;
	//v2 - v1
	pf = NULL;
	p = m_VerArr[p2index].m_list;
	while (p->m_destindex != p1index)
	{
		pf = p;
		p = p->m_next;
	}
	if (pf == NULL)
		m_VerArr[p2index].m_list = p->m_next;
	else
		pf->m_next = p->m_next;
	delete p;
	p = NULL;
}
int Graph::GetVertexIndex(char v) //得到顶点所在下标
{
	int i;
	for (i = 0; i < m_NumVertex; i++)
	{
		if (m_VerArr[i].m_value == v)
			return i;
	}
	return -1;
}
void Graph::InsertVertex(char v) //插入顶点
{
	if (m_NumVertex >= m_MaxVertex)
		return;
	m_VerArr[m_NumVertex++].m_value = v;
}
Graph::Graph()
{
	m_MaxVertex = SIZE;
	m_NumVertex = 0;
	//m_VerArr = new Vertex[m_MaxVertex];
}
Graph::~Graph()
{
/*	if (m_VerArr != NULL)
	{
		delete[]m_VerArr;
		m_VerArr = NULL;
	}*/
	m_NumVertex = 0;
}
void Graph::InsertEdge(char v1, char v2) //插入边
{
	int p1index = GetVertexIndex(v1);
	int p2index = GetVertexIndex(v2);
	if (p1index == -1 || p2index == -1)
		return;
	//v1-v2
	Edge* p = new Edge(p2index);
	p->m_next = m_VerArr[p1index].m_list;
	m_VerArr[p1index].m_list = p;
	//v2-v1
	p = new Edge(p1index);
	p->m_next = m_VerArr[p2index].m_list;
	m_VerArr[p2index].m_list = p;
}
void main()
{
	Graph g;
	g.InsertVertex('a');
	g.InsertVertex('b');
	g.InsertVertex('c');
	g.InsertVertex('d');
	g.InsertEdge('a', 'b');
	g.InsertEdge('a', 'c');
	g.InsertEdge('a', 'd');
	g.InsertEdge('b', 'c');
	g.InsertEdge('c', 'd');
    //测试:
	cout << "显示存储信息" << endl;
	g.ShowGraph();
	cout << "删除边后的存储信息" << endl;
	g.DeleteEdge('a', 'c');
	g.ShowGraph();
	cout << "删除顶点" << endl;
	g.DeleteVertex('a');
	g.ShowGraph();
}

到了这里,关于【图】什么是图?无向图怎么存储?邻接表和邻接矩阵如何用代码存储图?的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • 图论01-【无权无向】-图的基本表示-邻接矩阵/邻接表

    https://github.com/Chufeng-Jiang/Graph-Theory/tree/main/src/Chapt01_Adjacency 代码有删减 代码有删减 只需要改动一行 adj = new TreeSet[V]; //构造邻接表, V行,V个LinkedList 代码有删减

    2024年02月07日
    浏览(41)
  • 有向图的邻接表和邻接矩阵

    有向图的邻接表是一种常用的表示方法,用于表示图中各个节点之间的关系。在有向图中,每条边都有一个方向,因此邻接表中的每个节点记录了该节点指向的其他节点。 具体来说,有向图的邻接表由一个由节点和它们的邻居节点列表组成的集合构成。对于每个节点,邻接表

    2024年02月22日
    浏览(37)
  • C++构造无向图,邻接矩阵,深度优先遍历,广度优先遍历

    目录 定义无向图邻接矩阵 构造无向图 打印邻接矩阵 无向图邻接矩阵深度优先遍历(DFS) 无向图邻接矩阵广度优先遍历(BFS) 测试  完整代码 定义无向图邻接矩阵 构造无向图 1、输入总顶点数和总边数 2、依次输入顶点信息存入顶点表 3、 初始化邻接矩阵,使每个权值初始化

    2024年02月06日
    浏览(78)
  • C/C++语言 数据结构 创建邻接表存储的无向图及其邻接表的输出

    目录 1.邻接表相关知识补充  2. 图的邻接存储表示 3.测试输入与输出样例 4.代码实现 4.1 创建无向图邻接表 4.2 输入无向图的邻接表 定义: 对于图中每个顶点 vi,把所有邻接于 vi的顶点(对有向图是将从vi出发的弧的弧头顶点链接在一起)链接成一个带头结点的单链表,将所

    2024年02月05日
    浏览(46)
  • 【图论】Dijkstra 算法求最短路 - 构建邻接矩阵(带权无向图)

    题目链接:1976. 到达目的地的方案数

    2024年03月22日
    浏览(44)
  • 带权无向图的邻接矩阵表示法(C语言实现)

    ​ 定义:所谓邻接矩阵存储,是指用一个一维数组存储图中顶点的信息,用一个二维数组存储图中边的信息(即各顶点之间的邻接关系),存储顶点之间邻接关系的二维数组称为邻接矩阵。 ​ 对于 带权图 而言,若顶点V i 和 V j 之间有边相连,则邻接矩阵中对应项存放着该

    2024年02月16日
    浏览(37)
  • 数据结构几种常见图的邻接矩阵的画法(有向图带权值,有向图不带权值,无向图带权值,无向图不带权值)

    这不马上要期末考试了,复习的时候突然发现了有好几种图的邻接矩阵需要画,在网上找了半天结果发现也没有特别详细的总结,所以经过总结写一下吧,希望对有需要的人,有点帮助吧!!!!(如有不对还请见谅!!!!!~~~~~~) 1,有向图带权值   2.有向图不带权值

    2024年02月13日
    浏览(50)
  • 【三维点云处理】顶点、面片、邻接矩阵、邻接距离矩阵以及稀疏存储概念

    vertices-节点(3是点的三维坐标) Double类型的矩阵。用来存放所有构成mesh的节点,假设该mesh由N个三维节点构成,那么vertices就是一个N*3的矩阵,vertices(i, j) 表示了第i个节点第j维的坐标。 faces-面片(3是构成三角形面片的3个点) Integer类型的矩阵。用来存放节点之间的连接关

    2024年02月16日
    浏览(39)
  • 用邻接矩阵存储图

    邻接矩阵通常采用一个一维数组存储图中节点的信息,采用一个二维数组存储图中节点之间的邻接关系。 邻接矩阵可以用来表示无向图、有向图和网。 1 无向图的邻接矩阵 在无向图中,若从节点 Vi 到节点 Vj 有边,则邻接矩阵 M[i][j] = M[j][i ]= 1,否则 M[i][j] = 0。 无向图的邻接

    2024年02月08日
    浏览(28)
  • 图的存储 —— 邻接矩阵

    图的结构比较复杂,任何两个节点之间都可能有关系。 图的存储分为顺序存储和链式存储。 顺序存储包括邻接矩阵和边集数组, 链式存储包括邻接表、链式前向星、十字链表和邻接多重表。 图的存储 —— 邻接矩阵 邻接矩阵通常采用一个一维数组存储图中节点的信息,采用

    2024年02月06日
    浏览(39)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包