欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

图的邻接矩阵实现

程序员文章站 2022-06-03 21:07:03
...

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

设图G有n个顶点,则邻接矩阵是一个n*n的方阵,定义为:
图的邻接矩阵实现

我们来看一个实例,图7-4-2的左图就是一个无向图。
图的邻接矩阵实现

我们再来看一个有向图样例,如图7-4-3所示的左图。
图的邻接矩阵实现

在图的术语中,我们提到了网的概念,也就是每条边上都带有权的图叫做网。那些这些权值就需要保存下来。

设图G是网图,有n个顶点,则邻接矩阵是一个n*n的方阵,定义为:
图的邻接矩阵实现

如图7-4-4左图就是一个有向网图。

图的邻接矩阵实现

下面示例无向网图的创建代码:(改编自《大话数据结构》)
————————————————

#include<iostream>


#define MAXVEX 10/*最大顶点数*/
#define INFINITY 65656/*表示权值无穷*/ 
using namespace std;
typedef int EdgeType;
typedef char VertexType;

typedef struct
{
 VertexType vexs[MAXVEX];
 EdgeType arc[MAXVEX][MAXVEX];
 int numNodes,numEdges;//图中当前顶点和边数	
}MGraph; 

/*建立无向图的邻接矩阵表示*/ 
void CreateMGraph(MGraph *Gp)
{
	int i,j,k,w;
	cout<<"请输入顶点数和边数(空格分隔):"<<endl;
	cin>>Gp->numNodes>>Gp->numEdges;
	cout<<"请输入顶点信息"<<endl; 
	for(i=0;i<Gp->numNodes;i++)  //输入顶点 
 	   cin>> Gp->vexs[i];
	for(i=0;i<Gp->numNodes;i++)  //初始化邻接矩阵 
	{
		for(j=0;j<Gp->numNodes;j++)
		{
			if(i==j)
			    Gp->arc[i][j]=0;//顶点没有到自己的边
			else
 				Gp->arc[i][j]=INFINITY;//初始化边为无穷 
		}
	}
	/*输入边的上下标和权值*/ 
	for(k=0;k<Gp->numEdges;k++)
	{
		cout<<"请输入"<<Gp->numEdges<<"个边(Vi,Vj)的上标、下标和权值w(空格分隔)"<<endl; 
		cin>>i>>j>>w;
		Gp->arc[i][j]=w;
	 	Gp->arc[j][i]=Gp->arc[i][j];//对称矩阵 
 	}
}



int main(void)
{
    MGraph MG;
    CreateMGraph(&MG);

    return 0;
}
相关标签: