第二十七天(数据结构:图)

发布于:2025-08-08 ⋅ 阅读:(19) ⋅ 点赞:(0)
图:是一种非线性结构
    形式化的描述:   G={V,R}
        V:图中各个顶点元素(如果这个图代表的是地图,这个顶点就是各个点的地址)
        R:关系集合,图中顶点与顶点之间的关系(如果是地图,这个关系集合可能就代表的是各个地点之间的距离)

    在顶点与顶点之间的关系上面加上一个权值(w),这种权值代表的意义可能会不一样
        如果没有权值,顶点与顶点之间可能只有是否能到达的情况,但是不知道到达它需要的"距离"

    图是一个二元组:描述V(顶点的代号,我们需要一个"数组") 描述R(可能是两点之间的距离,我们也需要一个"数组"去描述)


    图分为两种
        1 有向图:关系是有方向的(你可以想象是一个单行道)
                有去不一定有来
                在画图的时候,关系是有箭头指向的
        2 无向图:关系是没有方向的(你可以想象是小区的小道,你过去是走这一条,回来的时候也是走的这一条)
                有去一定有来
                在画图的时候,关系是没有箭头指向的

    网:带权值的图我们就叫网

    顶点的度:有出度也有入度
        如果图是有向图,这个顶点有出度不一定有入度,有入度不一定有出度
            如果图是无向图,这个顶点有出度一定有入度
        一般图里面算度的数量的时候分别都要算入度和出度的数量
            出度:拓扑  --> 找一个没有入度的顶点出发
                通过出度到达另外一个顶点,然后将这个点的入度全部删除
                然后从下一个点继续开始,如果最后能将图里面的所有的顶点都遍历一遍
                那个这个图就叫拓扑有序,否则就叫拓扑无序
            入度:逆拓扑 -> 跟上面的是反的

    图:里面主要要搞定一个叫路径的问题
        1 最短路径 --- 最短的那一条
        2 关键路径 --- 在覆盖所有的工作流程里面找最短的那些路径
            这些路径里面最长的那条路径就叫关键路径


计算机里面描述图
    图是一个二元组,因此需要用至少两个东西分别描述顶点元素集合,关系集合
        假设你的顶点是ABCDEFG -> 我们开一个char[]就可以描述了
        假设你的顶点是"长沙" "武汉"... -> char *[]描述
        假设你的关系集合为距离 -> int [][]

    我们有几种方式去做图的保存
        "数组表示法" -> 邻接矩阵
        "链表表示法" -> 邻接表(逆邻接表) 十字链表 邻接多重表
        
    邻接矩阵:通过顶点元素数组和关系集合数组来描述
        通过画图可以看出,邻接矩阵适合稠密图

    邻接表:通过顶点元素数组和关系链表来描述(有向图无向图都能做)
    十字链表:主要搞定有向图(可以快速反应这个点的入度与出度)
    邻接多重表:主要搞定无向图(有去必有来,因此可以少建立很多的关系)
        通过画图可以看出,链表表示法适合稀松图


图的遍历
    1 深度优先DFS:树里面的先序遍历的扩展
        图里面的任何一个顶点都可能是出发点
            从出发点开始,将其遍历,然后以深度优先的方式继续遍历它的邻接点(和它有直接关系的点
                在画图的时候有一根线和它连起来了,这个点就是它的邻接点)
            邻接点遍历完毕继续以深度优先遍历它的邻接点的邻接点
                这个点有去也有可能有来,遍历的时候就可能会遇到刚刚遍历过点
                因此我们需要一个辅助向量来表明这个顶点是不是已经被遍历过了
            char V[10];
            visit[10] -> visit[0]表示V[0]是不是已经被访问 visit[1]表示V[1]是不是已经被访问.....
                0没有被遍历,1表示遍历过了
            if(visit[i] == 0)
            {              
                访问V[i]
                visit[i] = 1;//标记已经被访问过
                DFS(V[i]的邻接点) //以相同的规则去访问这个邻接点
            }
        访问w;
        for(v = 从w第一个邻接点开始;v邻接点存在;v = w下一个邻接点)
        {
            if(visit[v] == 0)
            {
                //访问v
                visit[v] == 1;
                DFS(v);
            }
        }


    2 广度优先BFS:树里面的层次遍历的扩展
        利用队列来进行每一层每一层的遍历
                    入队访问出队访问都可以
            从起点开始,将它入队
                出队,转向它的下一辈(它所有的邻接点(前面有可能已经被访问过,访问过的要排除))
        为了确保孤岛也能被访问,我们需要将每一个点都要以BFS的形式走一遍

        BFS(v)
        {
            //将顶点入队
            queue_push(v);
            while(队列不为空)
            {
                v = queue_front();
                queue_pop();
                for(i = v的所有邻接点)
                {
                    if(visit[i] == 0) //这些邻接点没有被访问你才需要去访问
                    {
                        visit[i] = 1;
                        queue_push(i);
                    }
                }
                
            }
        }

        for(i < 顶点个数个数)//防止有孤岛  所以每一个点都要试一次BFS
        {
            if(visit[i] == 0)
            {
                BFS(i);
            }

        }


//输入格式
ABCDEFG ->所有的顶点元素
AB3     ->边以及权值
BC5
...
##-1退出
//你的图里面最多可以容纳的顶点个数
#define VMaxNum 1000

//这个值代表一个无法到达的权值
#define VERYBIG 65535

//弄的是邻接矩阵

//你现在需要一个图的类型
typedef struct 
{
    char _V[VMaxNum];//顶点元素的数组
    int _R[VMaxNum][VMaxNum];//顶点与顶点之间的关系集合
    int _vexnum;//真正顶点的个数
    int _arcnum;//边(关系线)的个数  无向的叫边  有向的叫弧
}Graph;
#include "Graph.h"

//建立邻接矩阵
Graph * GraphInit(void)
{
    return (Graph *)calloc(1,sizeof(Graph));
}


//获取顶点元素的下标 -1表示失败
int GetVIndex(Graph * g,char v)
{
    for(int i = 0;i < g ->_vexnum;i++)
    {
        if(v == g ->_V[i])
            return i;
    }
    return -1;
}


//从键盘获取顶点元素以及边
void GetGraph(Graph * g)
{
    if(!g)
        return;
    printf("请输入所有的顶点元素:");
    scanf("%s",g ->_V);
    getchar();
    g ->_vexnum = strlen(g ->_V);//实际顶点个数为这么多
    //关系集合里面什么玩意儿都没有 不能是0
    for(int i = 0;i < g ->_vexnum;i++)
    {
        for(int j = 0;j < g ->_vexnum;j++)
        {
            g ->_R[i][j] = VERYBIG;//用VERYBIG将关系集合初始化一遍
        }
    }
    char start,stop;
    int w;
    while(1)
    {
        printf("请输入边和权值(AB2):");
        if(scanf("%c%c%d",&start,&stop,&w) != 3)
        {
            printf("\t\t输入有误,请重新输入\n");
            char buf[1024];
            fgets(buf,1024,stdin);
            continue;
        }
        getchar();//输入成功在后面会多一个\n 你需要拿走
        if('#' == start || '#' == stop || -1 == w)
        {
            break;
        }
        //printf("%c  %c  %d\n",start,stop,w);
        int start_index = GetVIndex(g,start);
        int stop_index = GetVIndex(g,stop);
        if(-1 == start_index || -1 == stop_index)
        {
            printf("\n边有问题,请重新输入\n");
        }
        //为了避免重复
        if(g ->_R[start_index][stop_index] == VERYBIG)
            g ->_arcnum++;
        g ->_R[start_index][stop_index] = w;//这个东西代表的是start到stop有w远
        printf("%d   %d\n",start_index,stop_index);
        g ->_R[stop_index][start_index] = w;//无向图就可以多这一步    
    }
}


//打印邻接矩阵
void PrintGraph(Graph * g)
{
    if(!g)
        return;
    for(int i = 0;i < g ->_vexnum;i++)
    {
        printf("\t%c",g ->_V[i]);
    }
    printf("\n");
    for(int i = 0;i < g ->_vexnum;i++)
    {
        printf("%c",g ->_V[i]);
        for(int j = 0;j < g ->_vexnum;j++)
        {
            if(g ->_R[i][j] == VERYBIG)
                printf("\t\\");
            else
                printf("\t%d",g ->_R[i][j]);
        }
        printf("\n");
    }
}


//获取v的第一个邻接点 v这一行里面第一个不是VERYBIG的
//失败返回-1
int GetFirstIndex(Graph * g,int v)
{
    for(int i = 0;i < g ->_vexnum;i++)
    {
        if(g ->_R[v][i] != VERYBIG)
            return i;
    }
    return -1;
}
//获取v的w的下一个邻接点 v这一行里面w列后面第一个不是VERYBIG的
//失败返回-1
int GetNextIndex(Graph * g,int v,int w)
{
    for(int i = w + 1;i < g ->_vexnum;i++)
    {
        if(g ->_R[v][i] != VERYBIG)
            return i;
    }
    return -1;
}

//遍历的向量
int visit[VMaxNum];//visit[i]表示顶点V[i]是否被访问 0表示没有  1表示访问过了

//这里用的v是下标
static void DFS(Graph * g,int v)
{
    if(!g || visit[v])//已经访问过就不用访问了
        return;
    printf("%c ",g ->_V[v]);
    visit[v] = 1;
    for(int w = GetFirstIndex(g,v);w > -1;w = GetNextIndex(g,v,w))
    {
        if(visit[w] == 0)
        {
            DFS(g,w);
        }
    }
}



//DFS 深度优先 从v开始进行DFS  v是顶点
void DFS_search(Graph * g,char v)
{
    //初始化visit
    memset(visit,0,g ->_vexnum *sizeof(visit[0]));

    printf("DFS:");
    //先弄一个遍v开始的DFS
    DFS(g,GetVIndex(g,v));
    printf("\n");
    //所有再遍历来一遍
    for(int i = 0;i < g ->_vexnum;i++)
    {
        if(visit[i] == 0)
        {
            DFS(g,i);
            printf("\n");
        }
    }
}


//请你实现BFS
static void BFS(Graph * g,int v)
{
    if(!g || visit[v])//图不存在或者v被访问过都无需访问
        return;
    
    //队列要存在
    ArrayQueue * qu = ArrayQueue_init(100);
    //将顶点入队
    ArrayQueue_push(qu,v);
    visit[v] = 1;
    while(!ArrayQueue_empty(qu))
    {
        v = ArrayQueue_front(qu);
        printf("%c ",g ->_V[v]);
        ArrayQueue_pop(qu);
        //for(int i = GetFirstIndex(g,v);i > -1;i = GetNextIndex(g,v,i))
        for(int i = 0;i < g ->_vexnum;i++)
        {
            if(g ->_R[v][i] != VERYBIG)
            {
                if(visit[i] == 0) //这些邻接点没有被访问你才需要去访问
                {
                    visit[i] = 1;
                    ArrayQueue_push(qu,i);
                }
            }
        }      
    }

    ArrayQueue_destory(&qu,NULL);
}

//BFS 广度优先 从v开始进行BFS  v是顶点
void BFS_search(Graph * g,char v)
{
    //初始化visit
    memset(visit,0,g ->_vexnum *sizeof(visit[0]));

    printf("BFS:");
    //先弄一个遍v开始的BFS
    BFS(g,GetVIndex(g,v));
    printf("\n");
    //所有再遍历来一遍
    for(int i = 0;i < g ->_vexnum;i++)//防止孤岛
    {
        if(visit[i] == 0)
        {
            BFS(g,i);
            printf("\n");
        }  
    }

}


网站公告

今日签到

点亮在社区的每一天
去签到