图
本章主要介绍了图这个数据结构的相关知识，包含图的基本概念及其关键词、使用不同的数据结构去存储图，算法包括图的遍历、图的拓扑排序、图的最小生成树算法。
可以转载，但请声明源链接：文章源链接justin3go.com(有些latex公式某些平台不能渲染可查看这个网站)
图的关键词
- 完全图
- 无向图需要有n(n-1)/2条边。
- 有向图需要有n(n-1)条弧。
- 邻接点
- 度（有向图还有出度和入度）
- 子图
- 路径
- 路径长度
- 简单路径：顶点不重复出现的路径。
- 回路：第一个顶点和最后一个顶点相同的路径。
- 简单回路：除第一顶点和最后以顶点外，其余顶点不重复出现的回路。
- 权：在图的每条边上加数字作权。
- 网：带权的图称为网。
- 连通：无向图中，如果从顶点v到顶点v
有路径，则称v和v是连通的。 - 连通图：如果图中任意两个顶点都是连通的，则是连通图。
- 连通分量相关：
- 也叫无向图的极大连通子图
- 连通图只有一个连通分量，即其自身
- 非连通的无向图有多个连通分量
- 强连通图：有向图中每一对顶点都存在路径，则称G是强连通图。
- 强连通分量：
- 有向图的极大连通子图称作强连通分量。
- 强连通图的强连通分量是其自身
- 非强连通的有向图可能有多个强连通分量
- 生成树
- 一个连通图的极小连通子图
- 含有图中全部n个顶点，但只有能令图连通的n-1条边
图的存储
邻接矩阵
创建顶点集和创建关系集
//图的邻接矩阵存储 #define NMAX 100 typedef int datatype; typedef struct{ datatype vexes[NMAX+1]; int edge[NMAX+1][NMAX+1]; int n,e }graph; graph *ga;
算法思路：
step1:创建ga的存储空间 step2:输入边数ga->e step3:输入顶点数ga->n step4:初始化顶点集ga->vexes foreach k in (1~ga->n) 输入顶点的数据data ga->vexes[k]=data step5:初始化邻接矩阵ga->edges为全0 step6:创建边集 foreach k in (1~ga->e) 输入边的顶点偶对：（i,j） ga->edges[i][j]=1 ga->edges[j][i]=1 step7:return ga
邻接表
顶点表
边表：边表结点保存着与某顶点关联的另一顶点和指向下一表结点的指针
邻接表结构定义：
#define NMAX 100 //顶点的最大数 typedef struct node{ //边表结点 int vertex; struct node* next; }edgenode; typedef struct{ //顶点表结点 vextype data; edgenode* head; //边表头指针 }vexnode; typedef struct{ //图的定义 vexnode vexes[NMAX+1]; //顶点表 int n, e; //顶点数、边数 }graph; graph *ga;
算法思路：
#初始化顶点表ga->vexes for k in (1~ga->n): # 输入数据data ga->vexes[k].data = data ga->vexes[k].head = NULL #创建边表集 for k in (1~ga->e): # 输入边的顶点对（i，j） # 将顶点j添加到顶点i的边表中 # 生成边表结点p # 结点数据域赋值：p->vertex=j # 在边表中加入结点p # p->next=ga->vertex[i].head # ga->vertex[i].head=p # 将顶点i添加到顶点j的边表中
十字链表
//边表结点 typedef struct arctype{ int tailvex, headvex; struct arctype *hlink,*tlink; }arclink; //顶点表结点 typedef struct vnode{ vertex data; arclink *firstin, *firstout; }ortholistNode ortholistNode graph[NMAX];
边集数组
typedef struct{ int fromvex;//边的起点 int endvex;//边的终点 int weight;//边的权值 }EDGE; EDGE edgeet[MaxEDGEnUM];
图的遍历
要求：无重复、无遗漏。
关键点：
- 图中可能存在回路。
- 顶点可能与其它顶点相通，访问完某顶点后，可能沿着某些边回到曾经访问过的顶点。
- 为避免重复访问，可设辅助数组visited[]
- 将其初始化为0.
- 遍历时，如果某顶点i被访问，将visited[i]置为1。
- 以此防止顶点i被多次访问。
深度优先(递归解法)：
//邻接矩阵： for k in (1~n) visied[i] = 0; DFS(ga, vi){ visit(vi); //访问结点vi visited[vi]=1; for k in (1~n){ if(ga->edges[vi][k] == 1 && !visited[k]) DFS(ga, k); } }
//邻接表： for k in (1~n) visied[i] = 0; DFS(ga, vi){ visit(vi); visited[vi] = 1; p=(ga->vexes[vi]).head; while(p){ if(!visited[p->vertex]) DFS(ga, p->vertex); p=p->next; } }
深度优先（栈）：
step1:设初始状态：图中所有顶点都没被访问过 foreach i in (1~n) visited[i] = 0; step2:初始化栈stack step3:c=r,push(stack,c) //r为出发顶点的编号 step4:访问顶点vc,令visited[c]=1 step5:找到并访问与顶点vc邻接，但未被访问过的顶点v_j for(j:1~n) if(ga[c][j] == 1 and visited[j] == 0) c = j, push(stack, j)转step4 step6:当vc所有的邻接点均被访问过，则退回到最近被访问的前一顶点。 if(!emptystack(stack)) c=pop(stack),转step5 else return;
广度优先：类似于树的层次遍历，使用队列辅助存储。
图的连通性：如果遍历完成时DFS或BFS仅调用一次，则图是连通图；若被调用多次，则图是非连通图，分别访问多个连通分量。
图的拓扑排序
AOV：
- 顶点表示活动，弧表示活动间的先后关系。
- AOV网中不能有回路，回路意味着某项活动以自己为先决条件。
- 死锁。
拓扑排序：
- 把AOV网中各顶点按其活动的先后关系，排列成一个线性序列的过程。
- 拓扑序列
- AOV网用邻接表存储
- 在邻接表的表头结点增加存放顶点入度的域。
- 栈或队列存放入度为零的顶点。
拓扑排序：对有n个顶点的有向图ga，以邻接表方式存储，找出一条拓扑序列。 step1:初始化栈stack，令count=0 step2:创建ga的邻接表，初始化每个顶点的入度为0 step3:将当前可开始的活动入栈 foreach k in 1~n if(ga->vexes[k].indegree==0) push(stack, k) step4:while(!empty(stack)) vi = pop(stack) visit(vi),count++ 将后续活动的入度减1，并记录新的可开始的活动。 p=ga->vexes[vi].head while(p) ga->vexes[p->data].indegree-- if(ga->vexes[p->data].indegree==0) push(stack,p->data) p = p->next; step3:如仍有活动未进行，return FALSE,否则return TRUE if(count<n) return FALSE;
图的最小生成树
生成树
- 连通图G的极小连通子图，称为图的生成树
- 包含图中所有顶点
- 无回路
- n个顶点，只有n-1条边。
- 任意去掉一条边，图将变为非连通图
- 添加一条边，图中将出现回路
- 含n个顶点n-1的图不一定是最小生成树
- 深度优先生成树
- 广度优先生成树
- 图的生成树不是唯一的
- 从不同的顶点出发，可得到不同的生成树。
图的最小生成树
- 连通网络G=（V，E）的各边带权
- 因此其生成树各边带权
- 生成树的权
- 生成树各边权值的和
- 最小生成树（MST）
- 权值最小的生成树
PRIM算法
初始U中含任意一个顶点u0，初始候选边集 
- numv=1
- while(numv=1){
- 从C中选最短边并入边集E，点集U
- numv++
- 调整候选边集C
Kruskal算法
算法思想：权值由小到大开始来连接，连通的不要，直到生成生成树，即最小生成树。
