数据结构 C语言算法图

数据结构

发布日期: 2022-11-17

文章字数: 2.4k

阅读时长: 9 分

数据结构之图

图的定义和术语

图：G=(V,E)
V:顶点的有穷非空集合；
E：边的有穷集合；

无向图：每条边都是无方向的
有向图：每条边都是有方向的

完全图：任意两个点都有一条边相连

稀疏图：有很少边或者弧的图
稠密图：有较多边或弧的图
网：边、弧带权的图
邻接：有边、弧相连的两个顶点之间的关系
存在(vi，vj)，则称vi和vj互为邻接点
存在<vi，vj>，则称vi邻接到vj，vj邻接于vi
**关联(依附)**：边、弧与顶点之间的关系，存在(vi，vj)/<vi，vj>,则称该边/弧关联于vi和vj

顶点的度：与该顶点相关联的边的数目，记为TD(v)

在有向图中，顶点的度等于该顶点的入度与出度之和，顶点v的入度是以v为终点的有向边的条数，记为ID(v)；顶点的出度是以v为始点的有向边的条数，记作OD(v)

路径：接续的边构成的顶点序列
路径长度：路径上边或弧的数目/权值之和
回路：第一个顶点和最后一个顶点相同的路径
简单路径：除路径起点和终点可以相同外，其余顶点均不相同
简单回路：除路径起点和终点相同外，其余顶点均不相同

连通图(强联通图)
任意两个顶点都存在路径

权与网：图中边或弧所具有的相关数称为权，表明从一个顶点到顶一个顶点的距离或耗费
子图：

**连通分量(强连通分量)**：
无向图

有向图：
有向图的极大连通子图称为其强连通分量

极小连通子图：该子图是G的连通子图，在该子图中删除任意一条边会使子图不再连通
生成树：包含无向图G所有顶点的极小连通子图
生成森林：对非连通图，由各个连通分量的生成树的集合

图的存储结构

1.数组表示法（邻接矩阵）
2.链式存储结构：邻接表、邻接多重表、十字链表

数组表示法（邻接矩阵）

建立一个顶点表（记录各个顶点信息）和一个邻接矩阵（表示各个顶点之间的关系）

无向图的邻接矩阵表示法

有向图的邻接矩阵表示法

网（有权图）的邻接矩阵表示法

邻接矩阵的存储表示

用两个数组分别存储顶点表和邻接矩阵

#define MaxInt 32767 //表示极大值
#define MVNum 100 //最大顶点数
typedef char VerTexType;//设定点的数据类型为字符型 
typedef int ArcType;//假设边的权值类型为整型  

typedef struct {
    VerTexType vexs[MVNum];//顶点表
    ArcType arcs[MVNum][MVNum]; //邻接矩阵
    int vexnum,arcnum;//图的当前点数和边数
}AMGraph;

算法1 采用邻接矩阵表示法创建无向图

Status CreateUND(AMGragh &G){
   cin>>G.vexnum>>G.arcnum;//输入总顶点数、总边数  
   for(i=0;i<G.vexnum;++i){
    cin>>G.vex[i];//依次输入点的信息
   }
   for(i=0;i<G.vexnum;++i)
    for(j=0;j<G.vexnum;++j)
     G.arcs[i][j]=Maxint;//边的权值均置为极大值
   
   for(k=0;k<G.arcnum;++k){
    //构造邻接矩阵
    cin>>v1>>v2>>w;//输入一条边所依附的顶点及边的权值  
    i=LocateVex(G,v1);
    j=LocateVex(G,v2);//确定v1和v2在G的位置
     G.arcs[i][j]=w;
     G.arcs[j][i]=G.arcs[i][j];//边<v1,v2>的权值设置为w，置对称边权值为w
   }
   return OK;
}

补充算法在图中查找顶点

int LocateVex(AMGraph G,VertexType u){
    //在图G查找顶点u，返回顶点下标
    int i;
    for(i=0;i<G.vexnum;++i){
        if(u==G.vex[i])return i;
    }
    return -1;
}

邻接矩阵的优缺

优点：

缺点：

邻接表表示法(链式)

无向图：

有向图：

邻接表的存储表示

顶点的结点结构

typedef struct VNode{
    VerTexType data;//顶点信息
    ArcNode *firstarcs; //指向第一条依附该顶点的边的指针
}VNode,AdjList[MVNum];

例如AdjList v;相当于：VNode v[MVNum];

边结点结构

#define MVNum 100//最大顶点数
typedef struct ArcNode{
    //边结点
    int adjvex//该边所指向的顶点位置
    struct ArcNode *nextarc;//指向下条边的指针
    OtherInfo info; //和边相关的信息
}ArcNode;

图的结构定义

typedef struct {
    AdjList vertices;//vertices--vertex的复数
    int vexnum,arcnum;//图的当前顶点数和弧数
}ALGraph;

邻接表操作举例说明：

采用邻接表表示法创建无向图

Status CreateUDG(ALGraph &G) {
    //采用邻接表表示法，创建无向图G
    cin>>G.vexnum>>G.arcnum;
    for(i=0;i<G.vexnum;++i){
        cin>>G.vertices[i].data;
        G.vertices[i].firstarc=NULL;
    }
    for(k=0;k<G.arcnum;++k){
        cin>>v1>>v2;
        i=LocateVex(G,v1);
        j=LocateVex(G,v2);
        p1=new ArcNode;
        p1->adjvex=j;
        p1->nexrarc=G.vertices[i].firstarc;
        G.vertices[i].firstarc=p1;
        p2=new ArcNode;
        p2->adjvex=i;
        p2->nexrarc=G.vertices[j].firstarc;
        G.vertices[j].firstarc=p2;
    }
    return OK;
}

邻接表的优缺

邻接矩阵与邻接表的关系

可供选择的其他存储结构

十字链表

顶点结点：

firstin:第一条入弧
firstout:第一条出弧

弧结点：

tailvex:弧尾位置
headvex:弧头位置
hlink:弧头相同的下一条弧
tlink:弧尾相同的下一条弧

邻接多重表

图的遍历-深度优先

定义：从已给的连通图中某一顶点出发，沿着一些边访遍图中的所有顶点，且使每个顶点仅被访问一次

遍历实质：找到邻接点

图的特点：
图中可能存在回路，且图的任一顶点都可能与其他顶点相通，在访问完某个顶点之后可能会沿着某些边又回到曾经访问过的顶点，如何避免？

邻接矩阵表示的无向图深度遍历实现

void DFS(AMGraph G,int v){
    //图G为邻接矩阵类型
    cout<<v;
    visited[v]=true;//访问第v个顶点
    for(w=0;w<G.vexnum;w++)//依次检查邻接矩阵v所在的行
    if((G.arcs[v][w]!=0)&&(!visited[w]))DFS(G,w);
    //w是v的邻接点，如果w未访问，则递归调用DFS
}

深度遍历效率

非连通图的深度优先遍历

图的遍历-广度优先

邻接表表示的无向图广度遍历实现

利用队列实现

F：队头指针 R：队尾指针

void BFS(Graph G,int v){
    //按广度优先非递归遍历图G
    cout<<v;
    visited[v]=true;//访问第v个顶点
    InitQueue(Q);//辅助队列Q初始化，置空  
    EnQueue(Q,v);//v进队  
    while(!QueueEmpty(Q)){//队列非空
        DeQueue(Q,u);//队头元素出队并置为u
        for(w=FirstAdjVex(G,u);w>=0;w=NextAdjVex(G,u,w))
        if(!visited[w]){
            //w为u的尚未访问的邻接顶点
            cout<<w;visited[w]=true;
            EnQueue(Q,w);//w进队
        }
    }
}