[图] 0 总结 - 记忆版

基本操作

CreateGraph(&G, v, VR) //按定义(v,VR)构造图
DestroyGraph(&G) //销毁图
LocateVex(G, u) //返回u的位置
GetVex(G, v) //返回v的值
PutVex(&G, v, value) //赋值
FirstAdjVex(G, v) //v的第一个邻边
NextAdjVex(G, v, w) //v相对于w的下一个邻接点
InsertVex(&G, v) //新顶点v
DeleteVex(&G, v) //删除v和相关弧
InsertArc(&G, v, w) //添加弧v,w
DeleteArc(&G, v, w) //删除
DFSTraverse(G, v, Visit())
BFSTraverse(G, v, Visit())

存储结构

邻接矩阵

//简单版
char vertex[5] = {'A','B','C','D','E'}; //顶点信息
float Edge[5][5]; //边
for (int i=0; i<5; ++i)
	for (int j=0; j<5; ++j)
		Edge[i][j] = MAX;

// 严书
typedef struct ArcCell { // 弧的定义
     VRType  adj;    // VRType是顶点关系类型
             // 对无权图，用1或0表示相邻否；
             // 对带权图，则为权值类型。
     InfoType  *info;  // 该弧相关信息的指针
} ArcCell, AdjMatrix[MAX_VERTEX_NUM][MAX_VERTEX_NUM];
typedef struct { // 图的定义
     VertexType vexs[MAX_VERTEX_NUM];   // 顶点信息
     AdjMatrix    arcs;     			// 弧的信息                     
     int    vexnum, arcnum; 			// 顶点数，弧数      
     GraphKind   kind; 				 // 图的种类标志             
} MGraph;

邻接表

typedef struct ArcNode{
	int adjV; //这条边所指的顶点
	struct ArcNode *next; //指向下一个边
}ArcNode; //边
typedef struct{
	int data;  // 顶点信息
	ArcNode* first; // 指向第一条依附该顶点的弧
}VNode,AdjList[MAX_VERTEX_NUM]; //顶点
typedef struct{
	AdjList vertices;
	int vexnum, arcnum;
	int kind; //图的种类
}ALGraph; //图

有向图的十字链表

//边 start->end
typedef struct ArcBox {
	int headvex; //弧的头
	int tailvex; //弧的尾
	struct ArcBox *hlink; //headvex的下一条出边
    struct ArcBox  *tlink; //tlink下一条入边
}ArcNode; //弧的结构表示
typedef struct VexNode { 
	VertexType  data;
	ArcBox  *firstin; //第一个入边
	ArcBox *firstout; //第一个出边
}VexNode; // 顶点的结构表示
typedef struct { 
	VexNode  xlist[MAX_VERTEX_NUM]; // 顶点结点
	int	vexnum; //当前顶点树
	int arcnum; //弧数
}OLGraph; //有向图十字链表

无向图的邻接多重表

//边i-j
typedef struct EBox { //
	VisitIf       mark; // 访问标记
	InfoType     *info; //信息指针   
	int ivex; //i结点
	struct EBox* inext; //i结点的下一条边
	int jvex; //j结点
	struct EBox* jnext; //j结点的下一条边
}EBox;
//顶点
typedef struct VexBox {
   VertexType  data;
   EBox  *first; //该结点的第一条边
}VexBox;
//邻接多重表
typedef struct {
    VexBox  adjmulist[MAX_VERTEX_NUM];
    int   vexnum, edgenum; //顶点数、边树    
} AMLGraph;

图

1. 极大：通俗理解就是不能再大，再大就不满足条件了