无向图

• 在无向图中，如果任意两个顶点之间都存在边，则称该图为无向完全图

• 含有n个顶点的五项完全图有n(n-1)/2条边

• 在n+1个顶点的图中，保证在任何情况下都是连通的，最少需要的边树{n(n-1)/2}+1

• 无向图边数的两倍等于各项顶点度数的总和

有向图

• 强连通有向图：从顶点x到顶点y之间都有路径，则称这两个顶点是强连通。
• 若图中的每一对顶点都是强连通的，则称此图为强连通图。
• 拓扑序列存在的条件是图中没有环

存储

• 二维数组也叫做邻接矩阵
• 无向图的邻接矩阵是一个对称矩阵
• 1.顶点的入度是顶点所在这一列的各数之和；出度是顶点所在这一行的各数之和。 2.判定两个顶点是否有边 3.找到某个顶点的所有邻接点
• 稀疏图(|E|远小于|V|2)

typedef struct VNode{	//顶点表结点
	VertexType data; 	//顶点信息
	ArcNode *firstedge; 	//单链表头指针
}VNode,AdjList[MaxVertexNum];
//AdjList是结构体数组类型

#define MaxVertexNum 100 //图中顶点数目的最大值
typedef struct ArcNode{	      //边表结点
	int adjvex;	      //该弧所指向的顶点的位置
	struct ArcNode *next;  //指向下一条弧的指针
}ArcNode;

typedef struct{
	AdjList vertices;    		//邻接表
	int vexnum,arcnum; 	//图的顶点数和弧数
} ALGraph; 			//ALGraph是以邻接表存储的图类型

复制代码

• n个顶点和e条边的无向图邻接矩阵中，零元素个数为个
• 邻接矩阵A，的含义：组合代数知识