图的定义和术语
图是一种较线性表和树更为复杂的数据结构。在线性表中数据元素之间仅有线性关系，在树形结构中数据元素有着明显的层次关系，在图形结构中数据元素之间的关系可以是任意的。
在图中的数据元素通常称为顶点（Vertex）,顶点之间的没有方向关系叫做边（edge），有方向的关系叫做弧，没有方向的图称为无向图，有方向的图称为有向图。 对于无向图而言，两个相连的顶点称为邻接点，他们之间的边依附于两个顶点，顶点的度是和顶点相关联的边的数目。 路径，从顶点A到顶点B的路径是一个顶点序列。若是有向图，那么路径也是有向的，路径长度是路径上的边或弧的数目。第一个顶点和最后一个顶点相同的路径称为环或回路，序列中不重复顶点不重复出现的路径称为简单路径，除第一个顶点，和最后一个顶点，其他顶点不重复出现的回路，称为简单回路或简单环。 在无向图中，如果顶点A到顶点B是有路径的，则称A和B是连通的，如果对于图中任意两个顶点都是连通的，则称图为连通图，连通分量，指的是无向图中的极大连通子图。 在有向图中，对于每一对连通的顶点A-B都有B-A，则称图为强连通图，有向图中的极大强连通子图称作有向图的强连通分量。 一个连通图的生成树是一个极小连通子图
图的存储结构
因为图的结构无法使用顺序存储结构，但可以使用二维数组来表示元素之间的存储结构，另一方面可以使用邻接表（链表形式），数据域存储顶点，指针域指向邻接点。
数组表示法
用两个结构体分别存储图的信息，和边的信息，边中的信息最终放到图的邻接矩阵中，在邻接矩下面是图的存储结构：
//邻接矩阵
typedef struct _graph
{
char vexs[MAX]; //顶点集合
int vexnum; //顶点数
int edgnum; //边数
int matrix[MAX][MAX]; //邻接矩阵
}Graph,*PGraph;
//边的结构体
typedef struct _EdgeData
{
char star; //边的起点
char end; //边的终点
int weight; //边的权重
}EData;
邻接表表示法
用两个链表来存储顶点信息以及顶点的邻接点，再用一个结构体来存储图的信息，顶点信息最终存储在图中的邻接表中，下面是邻接表的存储结构：
//邻接表中表对应的链表顶点
typedef struct _ENode
{
int ivex; //该边所指向的顶点的的位置
int weight; //该边的权
struct _ENode *next_edge; //指向下一条弧的指针
}ENode,*PENode;
//邻接表中表的顶点
typedef struct _VNode{
char data; //顶点信息
ENode *first_edge; //指向第一条依附该顶点的的弧
}VNode;
//邻接表
typedef struct _LGraph{
int vexnum; //图的顶点数目
int edgnum; //图的边的数目
VNode vexs[MAX]; //邻接表
}LGraph;
图的初始化
在图的初始化之前还需要函数实现返回顶点在矩阵的位置，对于邻接表来说还需要实现构建邻接表的顶点时需要把邻接点的信息插入到顶点中。下面分别说明这些函数：
返回顶点在矩阵中的位置
static int get_postition(Graph g, char ch)
{
int i;
for(i = 0; i < g.vexnum; i++){
if(g.vexs[i] == ch)
return i;
}
return -1;
}
static int get_postition(LGraph g, char ch)
{
int i;
for(i = 0; i < g.vexnum; i++){
if(g.vexs[i].data == ch)
return i;
}
return -1;
}
上述分别是邻接矩阵，和邻接表的函数，其实现方法都一样，遍历整个顶点集合，按照在顶点顺序返回在矩阵中的位置。
将邻接点链接到上一邻接点的末尾
这个连接仅仅是对于每个顶点后的邻接表插入而言的，仅需要上一邻接点的next指针域指向下一邻接点，下面是连接的实现，：
//将node链接到list末尾
static void link_last(ENode *list,ENode *node){
ENode *p = list;
while(p->next_edge)
p = p->next_edge;
p->next_edge = node;
}
创建图，首先初始化顶点数和边数，初始化顶点，初始化边，初始化权重，完成对图的创建，其中还有一个函数实现读取字符，下面说明创建图：
static char read_char()
{
char ch;
do {
ch = getchar();
} while(!isLetter(ch));
return ch;
}
//创建图
Graph* create_graph(){
char c1,c2;
int v,e; //顶点与边
int i,j,p1,p2,weight;
Graph* pG;
//输入顶点数和边数
printf("输入顶点数");
scanf("%d",&v);
printf("输入边数");
scanf("%d",&e);
if(v < 1 || e < 1 || (e > (v * (v - 1)))){ //符合要求的变数和顶点数
printf("input error\n");
return NULL;
}
if((pG = (Graph*)malloc(sizeof(Graph))) == NULL)
return NULL;
memset(pG,0, sizeof(Graph));
//初始化顶点数和边数
pG->vexnum = v;
pG->edgnum = e;
//初始化顶点
for(i = 0;i < pG->vexnum; i++){
printf("vertex(%d): ",i + 1);
pG->vexs[i] = read_char();
}
//初始化"边"的权值
for (int i = 0; i < pG->vexnum; ++i) {
for (j = 0; j < pG->vexnum; ++j) {
if(i == j){
pG->matrix[i][j] = 0;
} else
pG->matrix[i][j] = INF;
}
}
//初始化边
for(i = 0; i < pG->edgnum; i++){
//读取边的起始位置和结束顶点
printf("edge(%d):",i + 1);
c1 = read_char();
c2 = read_char();
printf("weight(%d):",i + 1);
scanf("%d",&weight);
p1 = get_postition(*pG,c1);
p2 = get_postition(*pG,c2);
if(p1 == -1 || p2 == -1){
printf("input error\n");
free(pG);
return NULL;
}
pG->matrix[p1][p2] = weight;
pG->matrix[p2][p1] = weight;
}
return pG;
}
LGraph* create_lgraph()
{
char c1, c2;
int v, e;
int i, p1, p2;
int weight;
ENode *node1, *node2;
LGraph* pG;
// 输入"顶点数"和"边数"
printf("input vertex number: ");
scanf("%d", &v);
printf("input edge number: ");
scanf("%d", &e);
if ( v < 1 || e < 1 || (e > (v * (v-1))))
{
printf("input error: invalid parameters!\n");
return NULL;
}
if ((pG=(LGraph*)malloc(sizeof(LGraph))) == NULL )
return NULL;
memset(pG, 0, sizeof(LGraph));
// 初始化"顶点数"和"边数"
pG->vexnum = v;
pG->edgnum = e;
// 初始化"邻接表"的顶点
for(i=0; i<pG->vexnum; i++)
{
printf("vertex(%d): ", i);
pG->vexs[i].data = read_char();
pG->vexs[i].first_edge = NULL;
}
// 初始化"邻接表"的边
for(i=0; i<pG->edgnum; i++)
{
// 读取边的起始顶点,结束顶点,权
printf("edge(%d): ", i);
c1 = read_char();
c2 = read_char();
scanf("%d", &weight);
p1 = get_position(*pG, c1);
p2 = get_position(*pG, c2);
// 初始化node1
node1 = (ENode*)malloc(sizeof(ENode));
node1->ivex = p2;
node1->weight = weight;
// 将node1链接到"p1所在链表的末尾"
if(pG->vexs[p1].first_edge == NULL)
pG->vexs[p1].first_edge = node1;
else
link_last(pG->vexs[p1].first_edge, node1);
// 初始化node2
node2 = (ENode*)malloc(sizeof(ENode));
node2->ivex = p1;
node2->weight = weight;
// 将node2链接到"p2所在链表的末尾"
if(pG->vexs[p2].first_edge == NULL)
pG->vexs[p2].first_edge = node2;
else
link_last(pG->vexs[p2].first_edge, node2);
}
return pG;
}
上面是邻接矩阵的创建，下面是邻接表的创建，二者顺序一样，只是因为结构不同，因此在细微的地方有所不同。其中在邻接表的边的创建中，不仅仅是要把边存储在邻接表中，还需要把邻接点的信息插入到顶点中去。
打印图
对于邻接矩阵图的打印很简单，因为图的信息已经存储在邻接矩阵当中，设置两个for循环进行输出就好，下面是邻接矩阵的打印图：
//打印矩形队列图
void print_graph(Graph G)
{
int i,j;
printf("Martix Graph:\n");
for(i = 0; i < G.vexnum; i++){
for(j = 0; j < G.vexnum; j++){
printf("%d",G.matrix[i][j]);
}
printf("\n");
}
}
对于邻接表而言，打印起来不是很方便，因为他的图存储在了顶点集合当中,只能依次打印顶点结合中每个顶点的邻接点，下面说明打印图：
/*
* 打印邻接表图
*/
void print_lgraph(LGraph G)
{
int i,j;
ENode *node;
printf("List Graph:\n");
for (i = 0; i < G.vexnum; i++)
{
printf("%d(%c): ", i, G.vexs[i].data);
node = G.vexs[i].first_edge;
while (node != NULL)
{
printf("%d(%c) ", node->ivex, G.vexs[node->ivex].data);
node = node->next_edge;
}
printf("\n");
}
}
遍历所有顶点，先打印顶点数据元素，在依次打印邻接点的数据元素。
图的遍历
和树的遍历类似，我们希望从图的某一个顶点出发访问图中的其余定点，且使每一个顶点仅访问过一次。这个过程就叫做图的遍历。图的遍历算法是求解图的连通性问题，拓扑排序问题，和求关键路径等算法的基础。 通常有两条遍历图的路径：深度优先搜索和广度优先搜索。他们对有向图和无向图都适用。
深度优先搜索（DFS）
深度优先搜索遍历类似于树的先根遍历，是树的先根遍历的推广，假设初始状态视图中所以顶点未曾访问，则深度优先搜索可以从图中莫个顶点v出发，访问此定点，然后依次从v的未被访问的邻接点出发深度优先遍历图，直到所有和v邻接的顶点都被访问，此时图中若有顶点未被访问，则重复上述操作，直到图中所有顶点都被访问。 实际操作当中，从顶点v出发开始遍历图，到了顶点v的邻接点，重复上述操作，就是采用递归的方式进行搜索。 在实现邻接矩阵的深度优先搜索算法之前我们还需要两个函数实现求得顶点的邻接顶点，以及顶点相对于某个顶点的下一个邻接顶点。 下面分别说明两个函数：
//返回顶点V的第一个邻接顶点的索引，失败返回-1
static int first_vertex(Graph G,int v){
if(v < 0 || v > (G.vexnum - 1))
return -1;
for(int i = 0; i < G.vexnum; i++){ //遍历顶点V的边
if(G.matrix[v][i] == 1)
return i;
}
return -1;
}
先对v判断是否是最后一个顶点，之后遍历整个顶点集合，找到顶点v的邻接点。
//返回顶点V相对于w的下一个邻接顶点的索引，失败返回-1
static int next_vertix(Graph G,int v,int w){
if(v < 0 || v > (G.vexnum - 1) || w < 0 || w > (G.vexnum - 1) )
return -1;
for(int i = w + 1 ; i < G.vexnum; i++){
if(G.matrix[v][i] == 1)
return i;
}
return -1;
}
同理先对v和w判断是否是最后一个顶点，之后从w的位置开始遍历顶点集合，找到下一个邻接顶点。
需要两个函数来实现一个对顶点集合深度优先搜索，另一个对顶点和他的邻接顶点深度优先搜索。
//深度优先搜索遍历图的递归实现
static void DFS(Graph G,int i,int *visited)
{
int w;
visited[i] = 1;
printf("%c ",G.vexs[i]);
//遍历该顶点的所有邻接结点，没有访问过则继续往下走
for(w = first_vertex(G,i); w >= 0; w = next_vertix(G,i,w)){ //所有的结点visvited值为1
if(!visited[w])
DFS(G,w,visited);
}
}
//深度优先搜索遍历图
void DFSTraverse(Graph G){
int i;
int visited[MAX]; //顶点访问标记
//初始化所有的顶点都没有被访问
for(i = 0; i < G.vexnum; i++){
visited[i] = 0;
}
printf("DFS: ");
for (i = 0; i < G.vexnum; i++){
if(!visited[i]){
DFS(G,i,visited);
}
}
printf("\n");
}
在深度优先搜索遍历图的时候，首先需要设置一个数组来记录顶点是否被访问。初始化为都没有被访问，之后递归顶点集合深度优先所有顶点就好。 下面说明邻接表的DFS：
/*
* 深度优先搜索遍历图的递归实现
*/
static void DFS(LGraph G, int i, int *visited)
{
int w;
ENode *node;
visited[i] = 1;
printf("%c ", G.vexs[i].data);
node = G.vexs[i].first_edge;
while (node != NULL)
{
if (!visited[node->ivex])
DFS(G, node->ivex, visited);
node = node->next_edge;
}
}
/*
* 深度优先搜索遍历图
*/
void DFSTraverse(LGraph G)
{
int i;
int visited[MAX]; // 顶点访问标记
// 初始化所有顶点都没有被访问
for (i = 0; i < G.vexnum; i++)
visited[i] = 0;
printf("DFS: ");
for (i = 0; i < G.vexnum; i++)
{
if (!visited[i])
DFS(G, i, visited);
}
printf("\n");
}
同理在邻接表中使用同样的方法，进行深度优先搜索。
广度优先搜索
广度优先搜索类似树的层次遍历，访问顶点集合中每个顶点的所有邻接点。广度优先搜索使用了一个队列进行存储待访问的顶点，下面说明广度优先搜索：
/*
* 广度优先搜索（类似于树的层次遍历）
*/
void BFS(LGraph G)
{
int head = 0;
int rear = 0;
int queue[MAX]; // 辅组队列
int visited[MAX]; // 顶点访问标记
int i, j, k;
ENode *node;
for (i = 0; i < G.vexnum; i++)
visited[i] = 0;
printf("BFS: ");
for (i = 0; i < G.vexnum; i++)
{
if (!visited[i])
{
visited[i] = 1;
printf("%c ", G.vexs[i].data);
queue[rear++] = i; // 入队列
}
while (head != rear)
{
j = queue[head++]; // 出队列
node = G.vexs[j].first_edge;
while (node != NULL)
{
k = node->ivex;
if (!visited[k])
{
visited[k] = 1;
printf("%c ", G.vexs[k].data);
queue[rear++] = k;
}
node = node->next_edge;
}
}
}
printf("\n");
}
void BFS(Graph G){
int head = 0;
int rear = 0;
int queue[MAX]; //辅助队列
int visited[MAX]; //顶点访问标记
int i,j,k;
for(i = 0;i < G.vexnum; i++){ //初始化访问数组
visited[i] = 0;
}
printf("BFS: ");
for(i = 0;i < G.vexnum;i++){
if(!visited[i]){
visited[i] = 1;
printf("%c",G.vexs[i]);
queue[rear++] = i; //入队列
}
while (head != rear){
j = queue[head++]; //出队列
for(k = first_vertex(G,j); k >= 0;k = next_vertix(G,j,k)) //k是访问的邻接结点
{
if(!visited[k]){
visited[k] = 1;
printf("%c",G.vexs[k]);
queue[rear++] = k;
}
}
}
}
printf("\n");
}
上面分别是邻接表和邻接矩阵的BFS。
最小生成树
图的生成树是它的一颗含有其所有顶点的无环连通子图,一幅加权图的最小生成树(MST)是它的一颗权值(树中的所有边的权值之和)最小的生成树。下面介绍两种最小生成树的算法，普里姆算法（prim），克鲁斯卡尔（kruskal）。
prim算法
首先就是从图中的一个起点a开始，把a加入U集合，然后，寻找从与a有关联的边中，权重最小的那条边并且该边的终点b在顶点集合：（V-U）中，我们也把b加入到集合U中，并且输出边（a，b）的信息，这样我们的集合U就有：{a,b}，然后，我们寻找与a关联和b关联的边中，权重最小的那条边并且该边的终点在集合：（V-U）中，我们把c加入到集合U中，并且输出对应的那条边的信息，这样我们的集合U就有：{a,b,c}这三个元素了，一次类推，直到所有顶点都加入到了集合U。 算法的实现需要一个索引，和两个数组，一个存放最小生成树的顶点集合，一个存放边的权值。下面是prim算法的实现：
void prim(Graph G,int start)
{
int min,i,j,k,m,n,sum;
int index = 0; //prim最小生成树索引
char prims[MAX]; //最小生成树结果
int weights[MAX]; //顶点间边的权值
//prim最小生成树中第一个数是图中第start个顶点，因为是从start开始的
prims[index++] = G.vexs[start];
//初始化"顶点的权值数组"
//将每个顶点的权值初始化为第start个顶点到该顶点的权值
for (int i = 0; i < G.vexnum; ++i) {
weights[i] = G.matrix[start][i];
}
//将start到start设置为0
weights[start] = 0;
for (int i = 0; i < G.vexnum; ++i) {
//由于从start开始，因此不需要在对第start个顶点处理。
if(start == i){
continue;
}
j = 0;
k = 0;
min = INF;
//在未被加入到最小生成树的顶点中，找出权值最小的顶点
while(j < G.vexnum){
//若weights【j】 = 0，意味着第j个顶点已经被排序过（或者说已经加入了最小生成树）
if (weights[j] != 0 && weights[j] < min){
min = weights[j];
k = j;
}
j++;
}
//经过上面的处理后，在为被加入最小生成树的顶点中，权值最小的定点是第k个顶点
//将k个顶点加入到最小生成树的结果数组中
prims[index++] = G.vexs[k];
//将第k个顶点的权值标记为0，意味着第k个顶点已经排序过了
weights[k] = 0;
//当第k个顶点被加入到最小生成树的结果数组中之后，更新其他的顶点权值
for (int j = 0; j < G.vexnum; ++j) {
//当第j个结点没有被处理，并且需要实时更新
if (weights[j] != 0 && G.matrix[k][j] < weights[j])
weights[j] = G.matrix[k][j];
}
}
//计算最小生成树的权值
sum = 0;
for (int i = 1; i < index; ++i) {
min = INF;
//获取prims[i]在G中的位置
n = get_postition(G,prims[i]);
//在vexs【0.。。i】中，找出到j的权值最小的顶点
for (int j = 0; j < i; ++j) {
m = get_postition(G,prims[i]);
if(G.matrix[m][n] < min)
min = G.matrix[m][n];
}
sum += min;
}
//打印最小生成树
printf("PRIM(%c) = %d: ",G.vexs[start],sum);
for (int i = 0; i < index; ++i) {
printf("%c",prims[i]);
}
printf("\n");
}
/*
* prim最小生成树
*
* 参数说明：
* G -- 邻接表图
* start -- 从图中的第start个元素开始，生成最小树
*/
void prim(LGraph G, int start)
{
int min,i,j,k,m,n,tmp,sum;
int index=0; // prim最小树的索引，即prims数组的索引
char prims[MAX]; // prim最小树的结果数组
int weights[MAX]; // 顶点间边的权值
// prim最小生成树中第一个数是"图中第start个顶点"，因为是从start开始的。
prims[index++] = G.vexs[start].data;
// 初始化"顶点的权值数组"，
// 将每个顶点的权值初始化为"第start个顶点"到"该顶点"的权值。
for (i = 0; i < G.vexnum; i++ )
weights[i] = get_weight(G, start, i);
for (i = 0; i < G.vexnum; i++)
{
// 由于从start开始的，因此不需要再对第start个顶点进行处理。
if(start == i)
continue;
j = 0;
k = 0;
min = INF;
// 在未被加入到最小生成树的顶点中，找出权值最小的顶点。
while (j < G.vexnum)
{
// 若weights[j]=0，意味着"第j个节点已经被排序过"(或者说已经加入了最小生成树中)。
if (weights[j] != 0 && weights[j] < min)
{
min = weights[j];
k = j;
}
j++;
}
// 经过上面的处理后，在未被加入到最小生成树的顶点中，权值最小的顶点是第k个顶点。
// 将第k个顶点加入到最小生成树的结果数组中
prims[index++] = G.vexs[k].data;
// 将"第k个顶点的权值"标记为0，意味着第k个顶点已经排序过了(或者说已经加入了最小树结果中)。
weights[k] = 0;
// 当第k个顶点被加入到最小生成树的结果数组中之后，更新其它顶点的权值。
for (j = 0 ; j < G.vexnum; j++)
{
// 获取第k个顶点到第j个顶点的权值
tmp = get_weight(G, k, j);
// 当第j个节点没有被处理，并且需要更新时才被更新。
if (weights[j] != 0 && tmp < weights[j])
weights[j] = tmp;
}
}
// 计算最小生成树的权值
sum = 0;
for (i = 1; i < index; i++)
{
min = INF;
// 获取prims[i]在G中的位置
n = get_position(G, prims[i]);
// 在vexs[0...i]中，找出到j的权值最小的顶点。
for (j = 0; j < i; j++)
{
m = get_position(G, prims[j]);
tmp = get_weight(G, m, n);
if (tmp < min)
min = tmp;
}
sum += min;
}
// 打印最小生成树
printf("PRIM(%c)=%d: ", G.vexs[start].data, sum);
for (i = 0; i < index; i++)
printf("%c ", prims[i]);
printf("\n");
}
上面的是邻接表，下面是邻接矩阵的最小生成树。 首先在最小生成树的中添加起始顶点，初始化顶点间的权值数组（是到起始顶点的全职），遍历顶点集合，在未被加入到最小生成树的顶点当中，找出权值最小的顶点，把最小的权值顶点加入到最下生成树的结果数组当中，将加入到最小生成树的顶点权值设置为0，代表该顶点已经被排序了，之后更新其他顶点的权值，找到没有被处理的顶点，只要当前未被处理的顶点，若在加入最小生成树的顶点到其他顶点在邻接矩阵中的权重小于其他节点到最小生成树集合的权重，则更新权重。 计算最小生成树的权重：遍历整个最小生成树集合，在该顶点之前的最小生成树集合当中寻找权值最小的顶点，并把权值加到最小生成树权值上。 在邻接表中获取顶点之间的权值需要额外地函数实现，下面说明：
/*
* 获取G中边<start, end>的权值；若start和end不是连通的，则返回无穷大。
*/
int get_weight(LGraph G, int start, int end)
{
ENode *node;
if (start==end)
return 0;
node = G.vexs[start].first_edge;
while (node!=NULL)
{
if (end==node->ivex)
return node->weight;
node = node->next_edge;
}
return INF;
}
克鲁斯卡尔算法
把图中各个顶点，堪称一棵树的根节点，从图中选择权值最小的边，若该边的两个顶点分别属于不同的树，则将其加入子图，把这两棵树合并成一棵树，若该边的两个顶点已经落在同一棵树上则选择下一条权值最小的边，直到森林中只有一颗树，也即子图中含有顶点数-1条边为止。 在实现克鲁斯卡尔算法之前需要三个辅助函数，分别获取图中的边，边的权值按照权值大小排序，获取顶点的终点。还有一个边的存储结构，下面说明辅助函数和边的结构体：
// 边的结构体
typedef struct _edata
{
char start; // 边的起点
char end; // 边的终点
int weight; // 边的权重
}EData;
//边的结构体
typedef struct _EdgeData
{
char star; //边的起点
char end; //边的终点
int weight; //边的权重
}EData;
邻接表和邻接矩阵边的结构体是一样的，只需要起点，终点，以及权重。接下来就是对边的初始化，虽然在一开始已经初始化了，但现在需要一个边的集合。下面就是获取图中的边：
/*
* 获取图中的边
*/
EData* get_deges(Graph G){
int i,j;
int index = 0;
EData *edges;
edges = (EData*)malloc(G.vexnum * sizeof(EData));
for (int i = 0; i < G.vexnum; ++i) {
for (int j = i + 1; j < G.vexnum; ++j) {
if(G.matrix[i][j] != INF){
edges[index].star = G.vexs[i];
edges[index].end = G.vexs[j];
edges[index].weight = G.matrix[i][j];
index++;
}
}
}
return edges;
}
/*
* 获取图中的边
*/
EData* get_edges(LGraph G)
{
int i,j;
int index=0;
ENode *node;
EData *edges;
edges = (EData*)malloc(G.edgnum*sizeof(EData));
for (i=0; i<G.vexnum; i++)
{
node = G.vexs[i].first_edge;
while (node != NULL)
{
if (node->ivex > i)
{
edges[index].start = G.vexs[i].data; // 起点
edges[index].end = G.vexs[node->ivex].data; // 终点
edges[index].weight = node->weight; // 权
index++;
}
node = node->next_edge;
}
}
return edges;
}
上面是获取邻接矩阵的边，下面是获取邻接表的边，方式基本一致，遍历整个邻接矩阵，或者邻接表，对每个顶点读取其相邻结点以及权重。 下面就是把边按照权值大小进行排序（由小到大）
void sorted_edges(EData* edges, int elen)
{
int i,j;
for (int i = 0; i < elen; ++i) {
for (int j = i + 1; j < elen; ++j) {
if (edges[i].weight > edges[j].weight){
//交换"第i条边"和"第j条边"
EData tmp = edges[i];
edges[i] = edges[j];
edges[j] = tmp;
}
}
}
}
邻接表的，原理类似冒泡排序这里就不过多的进行赘述。
/*
* 对边按照权值大小进行排序(由小到大)
*/
void sorted_edges(EData* edges, int elen)
{
int i,j;
for (i=0; i<elen; i++)
{
for (j=i+1; j<elen; j++)
{
if (edges[i].weight > edges[j].weight)
{
// 交换"第i条边"和"第j条边"
EData tmp = edges[i];
edges[i] = edges[j];
edges[j] = tmp;
}
}
}
}
邻接矩阵的，原理同冒牌排序这里不进行过多的赘述。 下面说明获取顶点的终边：
/*
* 获取i的终点
*/
int get_end(int vends[],int i){
while(vends[i] != 0){
i = vends[i];
}
return i;
}
/*
* 获取i的终点
*/
int get_end(int vends[], int i)
{
while (vends[i] != 0)
i = vends[i];
return i;
}
实现很简单，获取终边是在一定条件下的，参数vends是保存已有最小生成树中每个顶点在该最小生成树中的终点，参数i指的是顶点在图中顶点集合的序号。 下面说明克鲁斯卡尔算法的实现：
/*
* 克鲁斯卡尔（Kruskal)最小生成树
*/
void kruskal(LGraph G)
{
int i,m,n,p1,p2;
int length;
int index = 0; // rets数组的索引
int vends[MAX]={0}; // 用于保存"已有最小生成树"中每个顶点在该最小树中的终点。
EData rets[MAX]; // 结果数组，保存kruskal最小生成树的边
EData *edges; // 图对应的所有边
// 获取"图中所有的边"
edges = get_edges(G);
// 将边按照"权"的大小进行排序(从小到大)
sorted_edges(edges, G.edgnum);
for (i=0; i<G.edgnum; i++)
{
p1 = get_position(G, edges[i].start); // 获取第i条边的"起点"的序号
p2 = get_position(G, edges[i].end); // 获取第i条边的"终点"的序号
m = get_end(vends, p1); // 获取p1在"已有的最小生成树"中的终点
n = get_end(vends, p2); // 获取p2在"已有的最小生成树"中的终点
// 如果m!=n，意味着"边i"与"已经添加到最小生成树中的顶点"没有形成环路
if (m != n)
{
vends[m] = n; // 设置m在"已有的最小生成树"中的终点为n
rets[index++] = edges[i]; // 保存结果
}
}
free(edges);
// 统计并打印"kruskal最小生成树"的信息
length = 0;
for (i = 0; i < index; i++)
length += rets[i].weight;
printf("Kruskal=%d: ", length);
for (i = 0; i < index; i++)
printf("(%c,%c) ", rets[i].start, rets[i].end);
printf("\n");
}
邻接矩阵的克鲁斯卡尔算法： 先获取图中的边以结构体指针的形式存储，并对其权值按照大小进行排序，遍历整个边集合，判断每条边的两个顶点是否在已有最小生成树的环路上，若在则寻找下一条最小权值的边，若不在把该边的顶点信息存储到“已有最小生成树”中每个顶点在该最小树的终点数组当中，并把该边保存到最小生成树的边集合当中，之后求得最小生成树的权值，打印最小生成树：输出最小生成树边集合中两个顶点。
/*
* 克鲁斯卡尔最小生成树
*/
void kruskal(Graph G){
int i,m,n,p1,p2;
int lenght;
int index = 0; //rets数组的索引
int vends[MAX] = {0}; //用于保存 “已有最小生成树”中每个顶点在该最小树的终点
EData rets[MAX]; //对于结果数组保存kruskal最小生成树的1边
EData *edges; //图对应的所有边
//获取图中所有边
edges = get_deges(G);
//按照权值从小到大排序
sorted_edges(edges,G.edgnum);
for (int i = 0; i < G.edgnum; ++i) {
p1 = get_postition(G,edges[i].star); //获取第i条边的起点序号
p2 = get_postition(G,edges[i].end); //获取第i条边的终点序号
m = get_end(vends,p1); //获取p1在最小生成树的终点
n = get_end(vends,p2); //获取p2早最小生成树的终点
//如果m不等于n意味着边i与最小生成树的顶点没有形成环路
if(m != n){
vends[m] = n; //设置m在最小生成树的终点为n
rets[index++] = edges[i]; //保存结果
}
}
free(edges);
//统计并打印克鲁斯卡尔最小生成树的结果
lenght = 0;
for (int i = 0; i < index; ++i) {
lenght += rets[i].weight;
}
printf("Kruskal=%d: ",lenght);
for (int i = 0; i < index; ++i) {
printf("(%c%c)",rets[i].star,rets[i].end);
printf("\n");
}
}
对于邻接表的克鲁斯卡尔和邻接矩阵的一直，这里不进行过多的赘述。
最短路径
最短路径，顾名思义，求图中顶点到其他各个顶点的最短路径。 首先需要在设置三个数组分别存储前驱顶点，以及最短路径的长度，并设置为函数参数还有一个哨兵数组，用来判断顶点到其他顶点的最短路径是否已经获取。先对上述三个数组进行初始化，其中长度数组初始化时使用获取权重函数，其前驱顶点数组只需设置为0即可代表顶点的前驱没有获取，哨兵数组同样全部初始化为0，代表到所有顶点的最短路径没有获取。同时初始化要求顶点的哨兵数组为1，自身到自身的权重为0。接下来遍历整个顶点集合，每次找出一个顶点的最短路径：遍历整个顶点集合，在未获取最短路径的顶点当中，找到距离要求顶点最近的顶点，并标记哨兵数组，该最近顶点已经获取到最短路径。更新当前最短路径，以及前驱顶点：再次遍历整个顶点集合，获取最近顶点到其他顶点的权值，若该权值小于所求顶点到其他顶点的权值，赋值给最短路径的长度数组中其他顶点到所求顶点的权值（就是更新其他顶点到所求顶点的权值），并把其他节点的前驱设置为最近顶点。在遍历完所有顶点，对每一个加入到最短路径的顶点都更新后，确保最终的最短路径是整个图中权值最小的路径，下面是邻接表的最短路径实现：
/*
* Dijkstra最短路径。
* 即，统计图(G)中"顶点vs"到其它各个顶点的最短路径。
*
* 参数说明：
* G -- 图
* vs -- 起始顶点(start vertex)。即计算"顶点vs"到其它顶点的最短路径。
* prev -- 前驱顶点数组。即，prev[i]的值是"顶点vs"到"顶点i"的最短路径所经历的全部顶点中，位于"顶点i"之前的那个顶点。
* dist -- 长度数组。即，dist[i]是"顶点vs"到"顶点i"的最短路径的长度。
*/
void dijkstra(LGraph G, int vs, int prev[], int dist[])
{
int i,j,k;
int min;
int tmp;
int flag[MAX]; // flag[i]=1表示"顶点vs"到"顶点i"的最短路径已成功获取。
// 初始化
for (i = 0; i < G.vexnum; i++)
{
flag[i] = 0; // 顶点i的最短路径还没获取到。
prev[i] = 0; // 顶点i的前驱顶点为0。
dist[i] = get_weight(G, vs, i); // 顶点i的最短路径为"顶点vs"到"顶点i"的权。
}
// 对"顶点vs"自身进行初始化
flag[vs] = 1;
dist[vs] = 0;
// 遍历G.vexnum-1次；每次找出一个顶点的最短路径。
for (i = 1; i < G.vexnum; i++)
{
// 寻找当前最小的路径；
// 即，在未获取最短路径的顶点中，找到离vs最近的顶点(k)。
min = INF;
for (j = 0; j < G.vexnum; j++)
{
if (flag[j]==0 && dist[j]<min)
{
min = dist[j];
k = j;
}
}
// 标记"顶点k"为已经获取到最短路径
flag[k] = 1;
// 修正当前最短路径和前驱顶点
// 即，当已经"顶点k的最短路径"之后，更新"未获取最短路径的顶点的最短路径和前驱顶点"。
for (j = 0; j < G.vexnum; j++)
{
tmp = get_weight(G, k, j);
tmp = (tmp==INF ? INF : (min + tmp)); // 防止溢出
if (flag[j] == 0 && (tmp < dist[j]) )
{
dist[j] = tmp;
prev[j] = k;
}
}
}
// 打印dijkstra最短路径的结果
printf("dijkstra(%c): \n", G.vexs[vs].data);
for (i = 0; i < G.vexnum; i++)
printf(" shortest(%c, %c)=%d\n", G.vexs[vs].data, G.vexs[i].data, dist[i]);
}
对于邻接矩阵同理，下方说明邻接矩阵的最短路径：
/*
* Dijkstra最短路径。
* 即，统计图(G)中"顶点vs"到其它各个顶点的最短路径。
*
* 参数说明：
* G -- 图
* vs -- 起始顶点(start vertex)。即计算"顶点vs"到其它顶点的最短路径。
* prev -- 前驱顶点数组。即，prev[i]的值是"顶点vs"到"顶点i"的最短路径所经历的全部顶点中，位于"顶点i"之前的那个顶点。
* dist -- 长度数组。即，dist[i]是"顶点vs"到"顶点i"的最短路径的长度。
*/
void dijkstra(Graph G, int vs, int prev[], int dist[])
{
int i,j,k;
int min;
int tmp;
int flag[MAX]; // flag[i]=1表示"顶点vs"到"顶点i"的最短路径已成功获取。
// 初始化
for (i = 0; i < G.vexnum; i++)
{
flag[i] = 0; // 顶点i的最短路径还没获取到。
prev[i] = 0; // 顶点i的前驱顶点为0。
dist[i] = G.matrix[vs][i];// 顶点i的最短路径为"顶点vs"到"顶点i"的权。
}
// 对"顶点vs"自身进行初始化
flag[vs] = 1;
dist[vs] = 0;
// 遍历G.vexnum-1次；每次找出一个顶点的最短路径。
for (i = 1; i < G.vexnum; i++)
{
// 寻找当前最小的路径；
// 即，在未获取最短路径的顶点中，找到离vs最近的顶点(k)。
min = INF;
for (j = 0; j < G.vexnum; j++)
{
if (flag[j]==0 && dist[j]<min)
{
min = dist[j];
k = j;
}
}
// 标记"顶点k"为已经获取到最短路径
flag[k] = 1;
// 修正当前最短路径和前驱顶点
// 即，当已经"顶点k的最短路径"之后，更新"未获取最短路径的顶点的最短路径和前驱顶点"。
for (j = 0; j < G.vexnum; j++)
{
tmp = (G.matrix[k][j]==INF ? INF : (min + G.matrix[k][j])); // 防止溢出
if (flag[j] == 0 && (tmp < dist[j]) )
{
dist[j] = tmp;
prev[j] = k;
}
}
}
// 打印dijkstra最短路径的结果
printf("dijkstra(%c): \n", G.vexs[vs]);
for (i = 0; i < G.vexnum; i++)
printf(" shortest(%c, %c)=%d\n", G.vexs[vs], G.vexs[i], dist[i]);
}
