图的术语总结

开场前首先介绍一下图中的基本术语：

    图的分类：有向图和无向图。无向图有顶点和边构成，有向图由顶点和弧构成（弧有分为弧尾和弧头）

    图按照边或弧的多少分为稀疏图和稠密图

    如果任意两个顶点之间都存在边，叫做完全图。 （有向的叫做有向完全图）

    若无重复的边或顶点到自身的边，叫做简单图。

    无向图顶点的边数，叫做度。有向图分为入度和出度。

    图上的边或弧上带权，叫做网。

    图中顶点之间有存在路径，两顶点存在路径则说明是连通的，如果路径最终回到起点，称之为环。当中不重复叫简单路径。

    若任意两个顶点都是连通的，叫做连通图。（有向的称之为强连通图）。

    图中有子图，若子图极大连通则就是连通分量，有向的称之为强连通分量。

    无向图中连通，且有n个顶点 n-1 条边，称为生成树。

    有向图中一顶点入度为0，其余顶点入度为1的，称为有向树。

    一个有向图有若干颗有向树构成森林。

邻接矩阵

         邻接矩阵的存储方式是用两个数组表示图。一个一维数组存储图中顶点信息。一个二维数组（邻接矩阵）存储图中的边或弧的信息。

无向图的邻接矩阵

 特点：

          1、很容易判断任意两个顶点是否有边无边。

          2、想要知道某个顶点的度，其实就是这个点点 Vi 在邻接矩阵中第 i 行（或第 i 列）的元素之和。

          3、求顶点 Vi 的所有邻接点就是将矩阵中第 i 行元素扫描一遍。

有向图的邻接矩阵

 特点：

          1、有向图讲究入度和出度，顶点 Vi 的入度是 第 i 列各元素之和，出度是 第 i 行的个数之和。

          2、同无向图一样，求 Vi 的所有邻接点就是将矩阵第 i 行元素扫描一遍。

带权的图——网

以网为例，建立邻接矩阵。

#include<iostream>
using namespace std;
#define INFINITY 65535;
#define maxvex 5

typedef struct 
{
	char vexs[maxvex];   //顶点表
	int arc[maxvex][maxvex];   //邻接矩阵
	int numvertex;              //图中当前的顶点数和边数
	int numedge;      
}MGraph;

void CreateMGaph(MGraph &g)
{
	int i, j, k, w;
	cout << "请输入顶点数和边数：" << endl;
	cin >> g.numvertex;
	cin >> g.numedge;
	cout << "请输入结点的信息" << endl;
	
        //读入顶点信息，建立顶点结点
	for (i = 0;i < g.numvertex;i++)
            cin >> &(g.vexs[i]);
        
        //邻接矩阵初始化
	for (i=0;i<g.numvertex;i++)
	{
		for (j = 0;j < g.numvertex;j++)
			g.arc[i][j] = INFINITY;
	}
	//建立邻接矩阵
	for (k=0;k<g.numedge;k++)
	{
		cout << "输入边（vi,vj）上的下标i，下标j和权w:\n";
		cin >> i >> j >> w;
		g.arc[i][j] = w;
		g.arc[j][i] = g.arc[i][j];    //因为是无向图，所以矩阵对称
	}
}
void print(MGraph *mg)
{
      cout<<"邻接矩阵："<<endl;
      for (int i=0;i<mg->numvertex;i++)
	{
		for (int j = 0;j < mg->numvertex;j++)
			cout << mg->arc[i][j]<<"   ";
		cout << endl;
	}
}
int main()
{
	MGraph mg;
	CreateMGaph(mg);
	print(&mg);
}

总结：

       邻接矩阵占用的空间比较大，优点是直观明了，缺点是：当是稀疏矩阵，边数相对较少的图，这种结构就是存储空间就显得极为浪费。这里就要用另外一种存储结构：邻接表。