图的思维导图

重要概念

图的定义

• 图G是由两个集合V和E组成，记为G=(V,E)，其中V是顶点的有限集合，记为V(G),E是连接V中两个不同顶点（顶点对）的边的有限集合，记为E(G)。

图的基本术语

• 端点和邻接点
• 顶点的度、入度和出度
• 完全图
• 稠密图和稀疏图
• 子图
• 路径和路径长度
• 回路或环
• 连通、连通图和连通分量
• 强连通图和强连通分量
• 权和网

图的基本算法

• 创建图的运算算法

void CreateAdj(AdjGreph * &G, int A[MAXV][MAXV], int n, int e) {
	int i, j;
	ArcNode* p;
	G = (AdjGraph*)malloc(sizeof(AdjGraph));
	for (i = 0; i < n; i++)
		G->adjlist[i].firstarc = NULL;
	for(i=0;i<n;i++)
		for(j=n-1;j>=0;j--)
			if (A[i][j] != 0 && A[i][j] != INF) {
				p= (ArcNode*)malloc(sizeof(ArcNode));
				p->adjvex = j;
				p->weight = A[i][j];
				p->nextarc = G->adjlist[i].firstarc;
				G->adjlist[i].firstarc = p;
			}
	G->n = n; G->e = e;
}

• 输出图的运算算法

void DispAdj(AdjGraph* G) {
	int i;
	ArcNode* p;
	for (i = 0; i < G->n; i++) {
		p = G->adjlist[i].firstarc;
		printf("%3d: ", i);
		while (p != NULL) {
			printf("%3d[%d->", p->adjvex, p->weight);
			p = p->nextarc;
		}
		printf("^\n");
	}
}

• 销毁图的运算算法

void DestroyAdj(AdjGraph*& G) {
	int i;
	ArcNode* pre, * p;
	for (i = 0; i < G->n; i++) {
		pre = G->adjlist[i].firstarc;
		if (pre != NULL) {
			p = pre->nextarc;
			while (p != NULL) {
				free(pre);
				pre = p; p = p->nextarc;
			}
			free(pre);
		}
	}
	free(G);
}

图的遍历

• 深度优先遍历
• 广度优先遍历
• 用图遍历方法求解迷宫问题

typedef struct ANode {
	int i, j;
	struct ANode* nextarc;
}ArcNode;                       //边结点类型
typedef struct Vnode {
	ArcNode* firstarc;          //指向第一个相邻可走方块
}VNode;
typedef struct {
	VNode adjlist[M + 2][N + 2];//头结点数组
}AdjGraph;                      //迷宫图的邻接表类型

构造最小生成树的准则

• 必须只使用该图中的边来构造最小生成树；
• 必须使用且仅使用（n-1)条边来连接图中的n个顶点；
• 不能使用产生回路的边。

拓扑排序方法

• 从有向图中选择一个没有前驱(即 人度为0)的顶点并且输出它。
• 从图中删去该顶点,并且删去从该顶点发出的全部有向边。
• 重复上述两步，直到剩余的图中不再存在没有前驱的顶点为止。

疑难问题

-Kruskal的堆排序