[数据结构与算法]数据结构-图

图

图的存储结构

邻接矩阵存储无向图

/*
    图的存储结构
    1.可以使用邻接矩阵来储存（包括带权的网，也可以）
    2.邻接表（如果是有向图就需要邻接表和逆邻接表）
    ......
*/
# include<stdio.h>
# include<stdlib.h>

const int MAX = 110;
// 邻接矩阵结构体
typedef struct graph
{
    char vexs[MAX] ; // 图中顶点集合
    int vexnum ; // 图中顶点的个数
    int edgenum ; // 图中边条数
    int matrix[MAX][MAX] ; // 邻接矩阵
}Graph,*Pgraph;

// 建立一个邻接矩阵
Pgraph creat_matrix(Pgraph p)
{
    printf("请输入顶点个数和边的条数：\n");
    int vexn = 0,edgen = 0;
    scanf("%d %d",&vexn,&edgen);
    p->vexnum = vexn;
    p->edgenum = edgen;
    printf("请输入各个点:\n");
    int cnt = 0;
    int n = vexn;
    getchar();
    while(n --)
    {
        scanf("%c",&(p->vexs[cnt ++]));
    }
    n = vexn;
    char a,b;
    printf("请输入相关联的顶点对:（例如{a,b}）\n");
    getchar();
    while (n --)
    {
        scanf("{%c,%c}",&a,&b);
        int i = 0 , j = 0;
        while(p->vexs[i] != a) i ++;
        while(p->vexs[j] != b) j ++;
        p->matrix[i][j] = 1;
    }
    printf("邻接矩阵建立完成！\n");

    return p;
}

int main()
{
    Pgraph pgra = (Pgraph) malloc( sizeof(Graph) );
    pgra = creat_matrix(pgra);

    for(int i = 0 ; i < pgra->vexnum ; i ++)
    {
        for(int j = 0 ; j < pgra->vexnum ; j ++)
        {
            printf("%d ",pgra->matrix[i][j]);
        }
        printf("\n");
    }

    return 0;
}

邻接表存储带权有向图

/*
    邻接表(adjacency list)
    顺序存储+链式存储来存储图
    先建立一个结构体数组，数组存放点和边的关系：
        对于点，使用一个数据域来存放点的名称
        对于点与点的关系（边），使用链表来存储，数组有一个指针域，用来存放该点指向哪个点(这时是以该点作为边的
        起点。可以直接得到该点的出度。可以再加一个逆邻接表，以该点为边的终点来存储关系，这样就可以直接得到该
        点的入度。)
        就是入度/出度结点和邻接点来表示图。
    有向图的邻接表：

*/
# include<stdio.h>
# include<stdlib.h>

const int MAXSIZE = 110;
// 邻接点结构：
typedef struct adja_vex
{
    char vex ;
    int weight ; // 表示顶点到这个邻接点的权值
    adja_vex *next_v ;
}adja_vex ;

// 入度/出度顶点定义
typedef struct Vex
{
    char vex ;
    adja_vex *next_v;
}Vex;

Vex* create_adjalist(Vex* arr)
{
    int vexn,cnt = 0;
    char ch;
    printf("请输入图中结点的个数:");
    scanf("%d",&vexn);
    getchar();
    for(int i = 0 ; i < vexn ; i ++)
    {
        int reln = 0;
        printf("请输入顶点:\n");
        scanf("%c",&((&arr[i])->vex)) ; // arr是数组名，是指针。但是arr[i]就只是一个Vex类型元素 这里可以写成arr[cnt++].vex
        getchar(); // 循环中每个scanf%c之后放一个getchar防止下一次循环到scanf把\n读进去
        (&arr[i])->next_v = NULL ;
        printf("请输入该与该顶点相关联的点的个数:\n");
        scanf("%d",&reln);
        getchar();
        // 设置该点的邻接点
        for(int j = 0 ; j < reln ; j ++)
        {
            printf("请输入与该点下一个相关联的点 及其 权值：") ;
            char relvex ;
            int relweight ;
            scanf("%c %d",&relvex,&relweight);
            getchar();
            adja_vex* newvex = (adja_vex *)malloc(sizeof(adja_vex)) ; 
            newvex->vex = relvex;
            newvex->weight = relweight;
            newvex->next_v = (&arr[i])->next_v ; 
            (&arr[i])->next_v = newvex ;
        }
    }
    (&arr[vexn])->vex = '\0';
    return arr;
}

int main()
{
    Vex arr[MAXSIZE];
    create_adjalist(arr);
    printf("邻接表创建完成！\n");

    system("pause");
    return 0;
}

十字链表

/*
    十字链表(Orthogonal List)是有向图的一种存储形式
*/

# include<stdio.h>
# include<stdlib.h>

const int MAXSIZE = 110 ;
typedef char elemtype ;

// 边表结点
// 如果是网，就可以放一个权值Weight
typedef struct Edgenode
{
    int tailvex ; // 存储弧起点的下标
    int headvex ; // 存储弧终点的下标
    Edgenode *headlink ; // 指向 终点相同 的弧们 中的下一条弧
    Edgenode *taillink ; // 指向 起点相同 的下一条弧 
}Edgenode ;

// 定义顶点结构
typedef struct Vexnode
{
    elemtype vex ; // 顶点的名字
    Edgenode *firstin ; // 指向 该顶点的第一条入边弧
    Edgenode *firstout ; // 指向 该顶点的第一条出边弧
}Vexnodes[MAXSIZE] ;

邻接多重表

/*
    邻接多重表(adjacency multilist)
*/
# include<stdio.h>
# include<stdlib.h>

const int MAXSIZE = 110 ;
typedef char Elemtype ;

// 定义边表结点
typedef struct Edgelist_node
{
    int ivex ; // ivex为点ivex的下标
    Edgelist_node * ilink ; // 指向依附于ivex的下一条边
    int jvex ;
    Edgelist_node * jlink ;
}Edgelist_node ;

// 定义顶点表结构
typedef struct Vex
{
    Elemtype data ;
    Edgelist_node * firstedge ; // 指向依附于此顶点的第一条边
}Vexs[MAXSIZE] ;

图的遍历

深度优先遍历DFS

对于邻接矩阵存储法

/*
    深度优先遍历算法
        分为两步： 1. 无向图的深度遍历 2.无向图的深度优先递归
        深度遍历：首先初始化每一个点的visited状态，然后遍历每一个点如果未曾被遍历就DFS这个点
        DFS：对这个点设置visited状态，看这个依附点的第一条边的终点是否visited了如果是，就下一条边的终点继续判断；
    如果否，DFS这个终点

    邻接矩阵存储的无向图使用深度优先遍历，时间效率是O(n^2)，因为邻接矩阵是n×n，在遍历的时候每一个元素都遍历了的。
*/
# include<stdio.h>
# include<stdlib.h>

const int MAXSIZE = 110 ; 

typedef char elemtype ;
typedef struct Graph
{
    elemtype vex[MAXSIZE] ; // 无向图点集
    int vexnumber ; // 无向图中的点的个数
    int adjtable[MAXSIZE][MAXSIZE] ; // 邻接矩阵
}Graph ,* PGraph ;

int visited[MAXSIZE] ; // visited数组，存储某个点的访问标志 (使用下标让其相关起来)

void DFS(PGraph p , int i)
{
    int j;
    visited[i] = 1 ;
    printf("%c" , p->vex[i]) ; // 输出这个点的信息，也可以是其他操作
    for( j = 0 ; j < p->vexnumber ; j ++ )
    {
        if( p->adjtable[i][j] == 1 && !visited[j] ) // 找下一个可访问点
        DFS(p,j) ;
    }
}

void DFStraversal(PGraph p)
{
    // 初始化visited数组
    for(int i = 0 ; i < p->vexnumber ; i ++)
    visited[i] = 0;
    for(int i = 0 ; i < p->vexnumber ; i ++)
    if( !visited[i] ) DFS(p,i); // 对未访问过的点调用DFS（主要针对非连通图），如果是连通图只执行一次
}

对于邻接表存储法

/*
    邻接表存储的无向图使用深度优先遍历，时间效率是O(n+e) n是点的个数，e是边的条数
    只是一些小小改动其他和邻接矩阵的一模一样
*/
# include<stdlib.h>
# include<stdio.h>

const int MAXSIZE = 110 ;
typedef char elemtype ;

// 边表
typedef struct adja_node
{
    elemtype vex ;
    int idx ; // 该顶点在Vex[]中的下标
    adja_node * next_node ;
}adja_node ;

// 点表
typedef struct Vex
{
    elemtype data ;
    adja_node *firstadja ;
}Vex, *PVex, Vex[MAXSIZE];
int vexnumbers ; // 记录点的数目
int visited[MAXSIZE] ;

// 优先递归
void DFS(Vex *p ,int i)
{
    adja_node *q ;
    visited[i] = 1 ;
    q = p[i]->firstadja ;
    while(q)
    {
        if( !visited[q->idx] )
        DFS(p,q->idx) ; // 对下一个点递归调用
        q = q->next_node ;
    }
}

// 深度遍历
void DFStraverse(Vex * p)
{
    int i ;
    for( i = 0 ; i < vexnumbers ; i ++)
    {
        visited[i] = 0 ;
    }
    for(i = 0 ; i < vexnumbers ; i ++)
    {
        if( !visited[i] ) DFS(p,i) ;
    }
}

骑士周游问题(马踏棋盘问题)

这个是一个对深度优先遍历的一个应用，可以结合深度优先遍历来思考

/*
    骑士周游问题,knight's tour problem（又称马踏棋盘问题）

    回溯算法
    是深度优先遍历的应用。
*/
# include<stdio.h>
# include<stdlib.h>

const int X = 5 ;
const int Y = 5 ; // 这里就跑一个5×5的吧，8×8时间复杂度太大了 8^64种....

int x, y ;
int chess[X][Y] ;

// 判断第count个位置是否可以走
// 这里传入指向x,y的指针，找到下一个点的时候我们直接修改x,y。 传入count因为一共有8中情况，使用switch case直接进行判断，如果失败就再传count + 1
int nexy(int *x,int *y,int count)
{
   // printf("%d\n",step);
    switch(count)
    {
        case 0:
            if(*y+2<=Y-1 && *x-1>=0 && chess[*x-1][*y+2]==0)
            {
                *y+=2;
                *x-=1;
                return 1;
            }
            break;
        case 1:
            if(*y+2<=Y-1 && *x+1<=X-1 && chess[*x+1][*y+2]==0)
            {
                *y+=2;
                *x+=1;
                return 1;
            }
            break;
        case 2:
            if(*y+1<=Y-1 && *x+2<=X-1 && chess[*x+2][*y+1]==0)
            {
                *y+=1;
                *x+=2;
                return 1;
            }
            break;
        case 3:
            if(*y-1>=0 && *x+2<=X-1 && chess[*x+2][*y-1]==0)
            {
                *y-=1;
                *x+=2;
                return 1;
            }
            break;
        case 4:
            if(*y-2>=0 && *x+1<=X-1 && chess[*x+1][*y-2]==0)
            {
                *y-=2;
                *x+=1;
                return 1;
            }
            break;
        case 5:
            if(*y-2>=0 && *x-1>=0 && chess[*x-1][*y-2]==0)
            {
                *y-=2;
                *x-=1;
                return 1;
            }
            break;
        case 6:
            if(*y-1>=0 && *x-2>=0 && chess[*x-2][*y-1]==0)
            {
                *y-=1;
                *x-=2;
                return 1;
            }
            break;
        case 7:
            if(*y+1<=Y-1 && *x-2>=0 && chess[*x-2][*y+1]==0)
            {
                *y+=1;
                *x-=2;
                return 1;
            }
            break;
        default:
            break;
    }
    return 0;
}

// 深度优先遍历棋盘
// 如果找到合法位置就走过去，每走过一个位置就 tag 加一（可以通过递归回溯），返回1
int TraversalChessBoard(int x, int y ,int tag)
{
    // 递归结束条件
    if( X * Y == tag)
    {
        return 1 ;
    }
    // 设置这个点的信息
    int x1 = x , y1 = y ,count = 0 ;
    chess[x][y] = tag ;
    // 找下一个点,并对这个点进行递归
    int flag = 0 ;
    flag = nexy(&x1,&y1,count) ;
    while(!flag && count < 7)
    {
        count += 1 ;
        flag = nexy(&x1,&y1,count) ;
    }
    // 因为递归完这个点之后需要再次接着去找下一个点，所以就把递归直接放在while里
    while(flag) // 找到点就递归这个点的循环
    {
        if(TraversalChessBoard(x1,y1,tag + 1))
        return 1 ;
        // 递归失败就回溯
        
        x1 = x ;
        y1 = y ;
        
        count += 1 ; // 接着去找下一个点
        flag = nexy(&x1,&y1,count) ;
        while(!flag && count < 7) // 有可能这个flag是0，那就并没有找到下一个合适点，所以就再来一个循环找
        {
            count += 1 ;
            flag = nexy(&x1,&y1,count) ;
        }
    }
    // 如果递归失败就回溯
    if(flag == 0)
    chess[x][y] = 0 ;

    printf("(%d,%d)-tag:%d\n",x1,y1,tag) ;
    return 0 ;

}

int main()
{
    // 初始化chess,这里chess是全局变量，就已经自动初始化0了

    // 开始遍历
    if(TraversalChessBoard(2,0,1)) ;
    {
        for(int i = 0 ; i < X ; i ++)
        {
            for(int j = 0 ; j < Y ; j ++)
            {
                printf("%2d ",chess[i][j]) ;
            }
            printf("\n") ;
        } 
    }

    system("pause") ;

    return 0 ;
}

广度优先遍历BFS

/*
    广度优先遍历算法 BFS
    使用广度优先遍历输出各个点
*/
# include<stdio.h>
# include<stdlib.h>

const int MAX = 110;
// 标记数组，访问过就设置为1，否则为0
int visited[MAX] ;
// 邻接矩阵结构体
typedef struct graph
{
    char vexs[MAX] ; // 图中顶点集合
    int vexnum ; // 图中顶点的个数
    int edgenum ; // 图中边条数
    int matrix[MAX][MAX] ; // 邻接矩阵
}Graph,*Pgraph;

// 队列及其操作函数
int queue[MAX] ; // 存储点的下标
int head ,end ;
// 入队 
void queue_en(int e)
{
    // 如果数组满就申请内存等操作已省略
    queue[end ++] = e ;
}
// 出队，返回出队元素
int queue_de(void)
{
    int ch = queue[head ++] ;
    return ch ;
}

// 建立一个邻接矩阵
Pgraph creat_matrix(Pgraph p)
{
    printf("请输入顶点个数和边的条数：\n");
    int vexn = 0,edgen = 0;
    scanf("%d %d",&vexn,&edgen);
    p->vexnum = vexn;
    p->edgenum = edgen;
    for(int i = 0 ; i < vexn ; i ++)
    {
        for(int j = 0 ; j < vexn ; j ++)
        {
            p->matrix[i][j] = 0;
            p->matrix[j][i] = 0;
        }
    }
    printf("请输入各个点:\n");
    int cnt = 0;
    int n = vexn;
    getchar();
    while(n --)
    {
        scanf("%c",&(p->vexs[cnt ++]));
    }
    n = vexn;
    char a,b;
    printf("请输入相关联的顶点对:（例如{a,b}）\n");
    getchar();
    while (n --)
    {
        scanf("{%c,%c}",&a,&b);
        int i = 0 , j = 0;
        while(p->vexs[i] != a) i ++;
        while(p->vexs[j] != b) j ++;
        p->matrix[i][j] = 1;
        p->matrix[j][i] = 1;
    }
    printf("邻接矩阵建立完成！\n");

    return p;
}

// 广度优先遍历
/* 传入指向邻接矩阵的指针 */
void BFStraverse(Pgraph p)
{
    int i , j ;
    // 遍历每一个点
    for(i = 0 ; i < p->vexnum ; i ++)
    {
        if(!visited[i])
        {
            // 放入队列
            queue_en(i) ;
            // 将这个点标记，并输出信息
            visited[i] = 1 ;
            printf("%c-",p->vexs[i]) ;
            while(queue[head] != queue[end])
            {
                // 队头出队，并将出队元素的相邻且未被访问的点放入队列
                int k = queue_de() ;
                for(j = 0 ; j < p->vexnum ; j ++)
                {
                    if(p->matrix[k][j] == 1 && !visited[j])
                    {
                        // 未被访问的相邻点
                        visited[j] = 1 ;
                        printf("%c-" , p->vexs[j]) ;
                        queue_en(j) ;
                    }
                }
            }
        }
    }
}


int main()
{
    Pgraph pgra = (Pgraph) malloc( sizeof(Graph) );
    pgra = creat_matrix(pgra);

    for(int i = 0 ; i < pgra->vexnum ; i ++)
    {
        for(int j = 0 ; j < pgra->vexnum ; j ++)
        {
            printf("%d ",pgra->matrix[i][j]);
        }
        printf("\n");
    }

    BFStraverse(pgra) ;

    printf("\n") ;
    system("pause");
    return 0;
}

最小生成树

prim普里姆算法

/*
    最小生成树 prim 普利姆算法
    主要思路：
    1.初始化，将v0加入最小生成树
    2.循环vexn - 1 次，构造最小生成树
        --->(1).寻找未放入生成树的顶点，其权值最小的顶点的下标k
            (2).打印输出该点的相关信息，并将该点加入到最小生成树
            (3).更新与k点相关的顶点的下标及其之间的权值lowcost adjvex
                --->更新规则：1.未被加入最小生成树的顶点去更新2.权值有更小的才更新
*/
# include<stdio.h>
# include<stdlib.h>

const int MAXSIZE = 110 ;
const int wq = 999 ;
typedef struct Graph
{
    char vex[MAXSIZE] ;
    int vexnumber ;
    int edgenumber ;
    int matrix[MAXSIZE][MAXSIZE] ;
}Graph ,*PGraph;


PGraph creat_matrix()
{
    PGraph p = (PGraph)malloc(sizeof(Graph)) ;
    printf("顶点个数与边条数？\n") ;
    scanf("%d %d",&p->vexnumber,&p->edgenumber) ;
    for(int i = 0 ; i < p->vexnumber ; i ++)
    {
        for(int j = 0 ; j < p->vexnumber ; j ++)
        {
            p->matrix[i][j] = wq ;
        }
    }
    printf("各个顶点？\n") ;
    getchar() ;
    for(int i = 0 ; i < p->vexnumber ; i ++) scanf("%c",&(p->vex[i])) ;
    printf("输入边集和权值如{a,b,4}(表示ab边，权值为4)\n") ;
    getchar() ;
    for(int k = 0 ; k < p->edgenumber ; k ++)
    {
        char a,b ;
        int weight ;
        scanf("{%c,%c,%d}",&a,&b,&weight) ;
        int i = 0 , j = 0 ;
        while(p->vex[i] != a) i ++ ;
        while(p->vex[j] != b) j ++ ;
        p->matrix[i][j] = weight ;
        p->matrix[j][i] = weight ;
    }

    printf("邻接矩阵建立完成\n") ;

    return p ;
}

void prim_tree(PGraph p)
{
    int lowcost[MAXSIZE] ; // 存储相关顶点之间的权值 当lowcost为0的时候就认为我们把这个点已经放入了最小生成树
    int adjvex[MAXSIZE] ; // 存储相关顶点的下标
    int vexn = p->vexnumber ;
    
    // 将v0刚入最小生成树，并进行初始化
    lowcost[0] = 0 ;
    adjvex[0] = 0 ;
    for(int i = 1 ; i < vexn ; i ++)
    {
        lowcost[i] = p->matrix[0][i] ;
        adjvex[i] = 0 ; // 这一步有必要，因为每次都是重新找，就是靠着adjvex和lowcost找的
    }
    // 循环vexn - 1 次构造最小生成树
    for(int i = 1 ; i < vexn ; i ++)
    {
        int min = wq ; // 先设置最小值为无穷
        // 这里要注意了，每次找到的边不一定就是相接着的，v1->v2下一次不一定就是v2->vn。可能是v1->v4
        // 因此必须重新找，根据lowcost和adjvex找
        int k = 0 ; // 用来保存相关顶点下标 

        // 根据lowcost和adjvex去寻找未放入生成树的顶点中权值最小的顶点的下标k
        for(int j = 1 ; j < vexn ; j ++)
        {
            if(lowcost[j] < min && lowcost[j] != 0)
            {
                min = lowcost[j] ;
                k = j ;
            }
        }
        // 退出来就说明找到了最小生成树的一个结点，将这个点打印输出，并做上标记
        // 此时adjvex[k]的值就是与k相关的顶点的下标，或者说上一个生成树结点的下标,k是新找到的生成树结点的下标
        printf("{%c-%c,%d}\n",p->vex[adjvex[k]],p->vex[k],lowcost[k]) ;
        lowcost[k] = 0 ; // 表示k已经加入最小生成树
        // 更新lowcost adjvex
        for(int j = 1 ; j < vexn ; j ++)
        {
            if(lowcost[j] != 0 && p->matrix[k][j] < lowcost[j])
            {
                // 这里找到的j是生成树结点的下标,他们都是和下标为k的顶点相关的（k是刚刚找到的）
                lowcost[j] = p->matrix[k][j] ;
                adjvex[j] = k ;
            }
        }
    }



} 

int main()
{
    PGraph pgra = creat_matrix() ;

    for(int i = 0 ; i < pgra->vexnumber ; i ++)
    {
        for(int j = 0 ; j < pgra->vexnumber ; j ++)
        {
            printf("%4d ",pgra->matrix[i][j]);
        }
        printf("\n");
    }

    prim_tree(pgra) ;

    system("pause") ;
    return 0 ;
}

kruskal 克鲁斯卡尔算法

步骤：

1.将所有的边集数组按权值从小到大进行排序

2.将边集数组依次进行是否乘环判断然后放入到最小生成树中去

核心：对于是否形成环的判断

是否形成了环，通过一个parent数组，还有一个find查询函数来解决。这里用到了并查集思想

先来了解一下并查集思想：

并查集思想：主要思想就是 每一个集合都可以使用一个元素来代表。看到过一个不错的比喻，一个集合算成一个帮派，这个集合的代表元素就是这个帮派的老大。还有一点需要注意一下，每个单独的元素如果不属于某个大集合，那么他是他自己的老大，他属于自己这个集合，如果a的老大是b，b的老大是c，那么a最终的老大是c。

在kruskal算法的parent数组：一个图中有几个点，这个数组就有几个元素，首先把每一个parent[i]都初始化为0，（代表他们的老大是他们自己）。然后在从小到大遍历边集数组的时候，对这个边的两个端点进行查询，查询判断（判断查询后面等下讲）他们的老大是否一样（是否属于同一个集合）:

1>如果属于同一个集合，就说明两个端点已经放进了最小生成树，并且两点之间已经存在路径了，这时如果再把他们俩的直接连线放进去，就会形成环，所以这条边是不行的

2>如果老大不一样（不属于同一个集合，或者都不在一个集合或一个在集合中一个不在），这个时候说明把边加进去并不会形成回路，这样直接把这两个点或一个点直接放入集合(方法等下讲)并加入到最小生成树即可。接着遍历边集数组重复判断即可。

下面说一下怎么判断是否属于同一集合，怎么加入到集合

//首先是find函数，作用是返回某个元素的老大
int Find(int *parent,int e)
{
	while(parent[e] > 0) //parent[e]大于0说明e有上一级
		e = parent[e] ; // 不短通过选择元素的上一级，去找到最终的老大
	return e;
}

//加入到集合
parent[n] = m ;表示n的老大是m

具体的代码：

/*
    克鲁斯卡尔算法 kruskal
    步骤：1.将所有的边集数组按权值从小到大进行排序 2.将边集数组依次进行是否乘环判断然后放入到最小生成树中去
    核心就是对于是否形成环的判断

    代码示例如下：
    1.使用邻接表读入图
    2.使用克鲁斯卡尔算法计算出最小生成树

*/

# include<stdio.h>
# include<stdlib.h>

const int Maxsize = 110 ;

// 定义邻接表
// 邻接表链式结构
typedef struct adja_vex
{
    char vex ; // 点的名字
    int weight ; // 顶点邻接到这个点的边的权值
    adja_vex* nextvex ;
}adja_vex;
//邻接表顺序结构
typedef struct Vex
{
    char vex ;
    adja_vex* nextvex ;
}Vex ;

// 定义边集数组
typedef struct Edge
{
    char begin ;
    char end ;
    int weight ;
}Edge ;

void getgraph(int n,Vex* arr)
{
    int idx = 0 ;
    while(n --)
    {
        printf("依次输入每个点，该点邻接的点的个数\n") ;
        int n_num = 0 ;
        getchar();
        scanf("%c %d",&arr[idx].vex,&n_num) ;
        // 建立存放邻接表的链表
        if(n_num == 0) 
        {
            arr[idx ++].nextvex = NULL ;
            continue ;
        }
        printf("该点的邻接点及其之间的权值？例如：b 4\n");
        n_num -- ;
        adja_vex* adjahead = (adja_vex*)malloc(sizeof(adja_vex)) ;
        getchar();
        scanf("%c %d",&(adjahead->vex),&(adjahead->weight));
        adjahead->nextvex = NULL ;
        
        while(n_num --)
        {
            printf("该点的邻接点及其之间的权值？例如：b 4\n");
            adja_vex* newnode = (adja_vex*)malloc(sizeof(adja_vex)) ;
            getchar();
            scanf("%c %d",&(newnode->vex),&(newnode->weight)) ;
            adjahead->nextvex = newnode ;
            newnode->nextvex = NULL ;
        }
        arr[idx ++].nextvex = adjahead ;
    }
}  

// 邻接表转换成边集数组 返回边集数组的数量 
int transfor(Vex* arr,Edge* edges)
{
    int i = 0,idx = 0 ;
    while(arr[i].vex)
    {
        adja_vex* advex = arr[i].nextvex ; 
        while(advex)
        {
            edges[idx].begin = arr[i].vex ;
            edges[idx].end = advex->vex ;
            edges[idx].weight = advex->weight ;
            advex = advex->nextvex ;
            idx ++ ;
        } 
        i ++ ;
    }
    
    printf("edges ok!\n") ;
    return idx ;
}
void sort(Edge* edges,int l,int r)
{
    if(l >= r) return ;
    int i = l - 1 ,j = r + 1, x = edges[l + r >> 1].weight ;
    while(i < j)
    {
        do i ++ ; while(edges[i].weight < x);
        do j -- ; while(edges[j].weight > x);
        if( i < j )
        {
            int begin = edges[i].begin ;
            int end = edges[i].end ;
            int weight = edges[i].weight ;
            edges[i].begin = edges[j].begin;
            edges[i].end = edges[j].end ;
            edges[i].weight = edges[j].weight ;
        }
        sort(edges,l,j);
        sort(edges,j + 1,r) ;
    }
}

int Find(char* parent, char e)
{
    while(parent[e] != 0) 
    e = parent[e] ;
    return e;
}

// kruskal算法
void kruskal_gettree(Vex* arr)
{
    int i , n , m ;
    Edge edges[Maxsize] ;
    char parent[Maxsize] ={0,0}; // parent数组用于判断是否有环
    // 将邻接矩阵转换成边集数组，并按照权值从小到大排序
    int edges_num = transfor(arr,edges) ;
    sort(edges,0,edges_num - 1) ;
    printf("边集数组：%d 条边\n",edges_num) ;
    for(int i = 0 ; i < edges_num ; i ++) printf("(%c,%c)%d\n",edges[i].begin,edges[i].end,edges[i].weight);
    // 放入最小生成树，同时判断是否有环
    for(int i = 0 ; i < edges_num ; i ++)
    {
        n = Find(parent,edges[i].begin); // 寻找这条边起点这个点的的老大
        m = Find(parent,edges[i].end) ; // 寻找这条边的终点的老大
        if(n != m) // n和m不同，这条边的两个端点的的老大不相同，说明这条边的两个端点没在同一个集合中，说明这条边加进去不会出现环
        {
            parent[n] = m ;//设置n的老大是m，将n和m放到同一个集合中，即顶点已在最小生成树集合中
            // 成功操作：
            printf("最小生成树(%c,%c)边，权值%d\n",edges[i].begin,edges[i].end,edges[i].weight);
        }
    }

}

int main(void)
{
    // 读入
    int n,m;
    printf("输入图：请输入图中有几个点n？\n");
    scanf("%d",&n) ;
    Vex arr[Maxsize] ;
    getgraph(n,arr) ;
    kruskal_gettree(arr) ;

    system("pause") ;
    return 0 ;
}

最短路径

Dijkstra 迪杰斯特拉算法

主要思路在一会儿说，大部分在代码注释之中

这个算法用到了三个数组

final数组：v0到某点是否已经求得最短路的标记

D[vi]表示v0到vi的最短路径的长度和

P[v]是一个路径数组，值表示v的前驱顶点的下标

算法主要思路：

初始化

循环找最短路，循环vexnum次，每循环一次都找到一个点到v0的最短路径（注意这里每次找到的点是一个距离v0是最短路的点，比一定就是按照v1，v2这样的顺序去找的），具体实现在代码中体现

? 循环体的步骤：

? min初始化为∞

? (for)遍历(if)每一个未求得到v0最短路的且到v0的路径小于min的点，(条件为true)遍历到这个点后，后更新min为这个点到v0的路径，把这个点的下标保存为k

? (for)修正遍历，对于(if)未找到最短路的点(final[]=0)若经过(&&)k点到达此点的路径比现在的路径长度更加短就更新当前路径长度

代码：

const int Maxsize = 9 ;
const int Infinity = 65535 ; 

int P[Maxsize] ,D[Maxsize] ;
// P[v]是一个路径数组，值表示v的前驱顶点的下标  D[vi]表示v0到vi的最短路径的长度和

typedef struct graph
{
    char vexs[Maxsize] ; // 图中顶点集合
    int vexnum ; // 图中顶点的个数
    int edgenum ; // 图中边条数
    int matrix[Maxsize][Maxsize] ; // 邻接矩阵
}Graph,*Pgraph;

// Dijkstra算法 传入一个指向图的指针和起点的下标
void Dijkstra(Pgraph graph ,int v0 )
{
    int v,w,k,min ;
    int final[Maxsize] ; // final数组用来记录v0到某个点的最短路径是否已经求出
    // 初始化数据
    for(v = 0 ; v < graph->vexnum ; v ++)
    {
        final[v] = 0 ; // 每个点现在都未求出到v0的最短路径 v0点默认到自己的距离为0 且final[0]为1，后续再去设置
        D[v] = graph->matrix[v0][v] ; // 设置所有和v0相邻的顶点的权值（如果没有直接相连就设置成了65535）
        P[v] = 0 ; // 设置所有点前驱现在是0，初始化路径数组
    } 
    D[v0] = 0 ; //v0点默认到自己的距离为0
    final[v0] = 1 ;//final[0]为1

    // 开始主循环，循环vexnum次，没一次循环都可以找到一个 v0到某个点的最短路径,从1开始即可
    for(v = 1 ; v < graph->vexnum ; v ++)
    {
        min =  Infinity ; // 用来保存当前顶点到v0的最小距离 
        // 寻找距离v0最近的顶点
        for(w = 0 ; w < graph->vexnum ; w ++)
        {
            if( !final[w] && D[w] < min) // 如果有更小距离就更新这个min,并把这个点记下来
            {
                k =  w;
                min = D[w] ;
            }
        }
        final[k] = 1 ;

        // 修正当前点v的邻接点对于v0的路径长度,修正最短路径
        for(w = 0 ; w < graph->vexnum ; w ++)
        {
            // 经过v的路径如果比当前它本身的这条路径短的话，就更新
            // 或者说matrix[k][w]是w到k的距离，min是k到v0的距离，两者之和如果小于D[w]，就更新最短路和距离
            if(!final[w] && min + graph->matrix[k][w] < D[w]) 
            {
                D[w] = min + graph->matrix[k][w] ;
                P[w] = k ; // 因为最短路中,w是通过k到达v0的所以，w的前驱是k 
            }
        }

    }

}

Floyd弗洛伊德算法

dijkstra算法只能求得某一源点到其他点的最短路，若是想要求得每个点到达每个点的最短路就要再加上一个for循环，Floyd算法以简洁的代码给出了求一个连通图中任意一点到任意一点的最短路算法(时间复杂的仍然是n^3)

下面来说弗洛伊德算法，Floyd算法中用到了两个二维数组D[] []和P[] []，D是用来存储两点间最短路权值和矩阵，P来存储最短路,代表对应顶点的最小路径的前驱矩阵

算法的主要思路：

? 首先初始化D、P两个数组，D数组的初始化就是把邻接矩阵的值copy一下，P数组的初始化就是让他们的路径先是直接到达，没有任何中转点，即P[v] [w] = w ;(这一步需要v,w两层迭代循环）

? 然后就是将所有的路径进行修正，当存在更短路径的时候就修正。

? 修正最短路径的时候从一个点到达一个点，可能会用到很多中转点，通过三个嵌套的for循环就能搞定，下面看代码

?

/*
    Floyd弗洛伊德算法

*/
# include<stdio.h>

const int Maxsize = 9 ;
const int Infinity = 65535 ; 

int P[Maxsize][Maxsize] ,D[Maxsize][Maxsize] ;
// D是用来存储两点间最短路权值和矩阵，P来存储最短路,代表对应顶点的最小路径的前驱矩阵

typedef struct graph
{
    char vexs[Maxsize] ; // 图中顶点集合
    int vexnum ; // 图中顶点的个数
    int edgenum ; // 图中边条数
    int matrix[Maxsize][Maxsize] ; // 邻接矩阵
}Graph,*Pgraph;


// 弗洛伊德算法求出g指向的图中的任意两点间最短路径，将结果保存在P、D两个数组之中
void Floyd(Pgraph g)
{
    int v,w,k;
    // 初始化
    for(v = 0 ; v < g->vexnum ; v ++)
    {
        for(w = 0 ; w < g->vexnum ; w ++)
        {
            D[v][w] = g->matrix[v][w] ;
            P[v][w] = w ;
        }
    }

    // 遍历修正
    for(k = 0 ; k < g->vexnum ; k ++)
    {
        for(v = 0 ; v < g->vexnum ; v ++)
        {
            for(w = 0 ; w < g->vexnum ; w ++)
            {
                if(D[v][k] + D[k][w] < D[v][w]) // 如果v从中转点k到达w的路径更短就更新
                {
                    D[v][w] = D[v][k] + D[k][w] ;
                    P[v][w] = P[v][k] ; // 将w的前驱点k记录下来(而k又有它的前驱点，最终找到起点，这就是最短路径)
                }
            }
        }
    }
}

拓扑排序

顶点表示活动、边表示活动间先后关系的有向图称做顶点活动网，简称AOV网。在AOV网中，若不存在回路，则所有活动可排列成一个线性序列，使得每个活动的所有前驱活动都排在该活动的前面，我们把此序列叫做拓扑序列。对于拓扑序列可以这样理解，要做一件事b必须先做一件事a，a->b这样就是一个拓扑序列。一个aov网可以存在多种拓扑序列。

拓扑排序：由aov网构造拓扑序列的过程就是拓扑排序

拓扑排序的思路：在有向图中找到一个入度为0的顶点，将这个顶点输出，然后删除此顶点，再将这个以顶点为弧尾的弧删掉，再找一个入度为0的顶点，。。。。。循环往复直到顶点全部输出或者不存在入度为0的顶点就停止。

拓扑排序涉及到了对边的遍历操作，所以使用邻接表来存储有向图。

在拓扑排序中使用一个栈来存储入度为0的顶点的下标（顶点表结点中的下标）。

代码实现思路：

? 定义邻接表结构（包括边表结点和顶点表结点的定义），定义图结构

? 将所有0度顶点放入到栈中，cnt = 0

? 循环（如果栈不为空）：

? 栈顶元素出栈，将以栈顶元素为下标的顶点（入度为0的顶点）输出，

? cnt++

? 对此顶点的边表进行遍历，将边表上的点的入度都 - 1，如果谁的入度为0就入栈

? 退出循环后如果cnt < 图中顶点数说明存在环 返回ERROR，否则返回OK，成功拓扑排序

/*
    拓扑排序
*/

# include<stdio.h>
# define OK 1
# define ERROR 0 
const int Maxsize = 100 ;



// 边表结点的定义 (链式存储)
typedef struct Edge_node
{
    int adjvex ; // 存储该邻接顶点的下标
    int weight ;
    Edge_node * next ;
}Edge_node ;
// 顶点表结点
typedef struct Vex_node
{
    int in ; // 入度
    int data ; // 存储这个点的信息
    Edge_node * firstedge ; 
}Vex_node ,Adjlist[Maxsize];
// 图
typedef struct Graph
{
    Adjlist adjlist ;
    int Vexnumber ;
    int Edgenumber ;
}Graph ; 
typedef Graph * pgraph ;

int tuopsort(pgraph graph)
{
    Edge_node *e ;
    int i , k , gettop ;
    int top = 0  ; // 存储栈指针下标
    int cnt = 0 ; // 用于统计输出点的个数
    int stack[Maxsize] ; // 栈
    // 将入度为0的顶点入栈 (栈中记录的是顶点的下标)
    for(i = 0 ; i < graph->Vexnumber ; i ++)
    {
        if(graph->adjlist[i].in == 0) 
        {
            stack[++ top] = i ; // 这里++top 栈底元素为stack[1]
        }
    } 
    
    // 栈顶元素出栈，将以栈顶元素为下标的顶点（入度为0的顶点）输出，并对此顶点的边表进行遍历，将边表上的点的入度都 -  1，如果谁的入度为0就入栈
    while(top != 0)
    {
        gettop = stack[top --] ;
        printf("%d->",graph->adjlist[gettop].data); // 打印顶点
        cnt ++ ;
        for(e = graph->adjlist[gettop].firstedge ; e ; e = e->next)
        {
            k = e->adjvex;
            if(!( -- graph->adjlist[k].in)) // 如果删除弧后又有了入度为0的点，就加入栈
            stack[++ top] = k ;
        }
    }
    if(cnt < graph->Vexnumber) return ERROR ;
    else return OK ;
}

该算法时间复杂度为O(n+e)

关键路径

这个先欠着吧(@.@)