数据结构学习笔记-图

1.图的存储

（1）邻接矩阵法

#define MaxVertexNum 100    //顶点数目的最大值
typedef struct{
    char Vex[MaxVertexNum];    //顶点表
    int Edge[MaxVertexNum][MaxVertexNum];    //邻接矩阵表，边表
    int vexnum,arcnum;    //图的当前顶点数和边数/弧数
} MGraph;

存储带权的图（网）

#define MaxVertexNum 100    //顶点数目的最大值
#define INFINITY 最大的int值    //宏定义常量“无穷”
typedef char VertexType;    //顶点的数据类型
typedef int EdgeType;    //带权图中边上权值的数据类型
typedef struct{
    VertexType Vex[MaxVertexNum];    //顶点
    EdgeType Edge[MaxVertexNum][MaxVertexNum];    //边的权
    int vexnum,arcnum;    //图的当前顶点数和弧数
}MGraph;

（2）邻接表法（顺序+链式存储）

//“顶点”
typedef struct VNode{
    VertexType data;    //顶点信息
    ArcNode *first;    //第一条边/弧
} VNode,AdList[MaxVertexNum];

//用邻接表存储的图
typedef struct {
    AdList vertice;
    int vexnum,arcnum;
} ALGraph;

//“边/弧”
typedef struct ArcNode{
    int adjvex;    //边/弧指向哪个结点
    struct ArcNode *next;    //指向下一条弧的指针
    //InfoType into;    //边权值
}ArcNode;

无向图的同一条边会指向两次，有向图的一条边只指向一次。

2.图的基本操作

Adjacent(G,x,y):判断图G是否存在边<x,y>或(x,y)。

Neighbors(G,x):列出图G中与结点x邻接的边。

InsertVertex(G,x):在图G中插入顶点x。

DeleteVertex(G,x):从图G中删除顶点x。

AddEdge(G,x,y):若无向边(x,y) 或有向边<x,y>不存在，则向图G中添加该边。

RemoveEdge(G,x,y):若无向边(x,y)或有向边<x,y>存在，则从图G中删除该边。

FirstNeighbor(G,x):求图G中顶点x的第一个邻接点，若有则返回顶点号。若x没有邻接点或图中不存在x，则返回-1。

NextNeighbor(G,x,y):假设图G中顶点y是顶点x的第一个邻接点，返回除y之外顶点x的下一个邻接点的顶点号，若y是x的最后一个邻接点，则返回-1。

Get_edge_value(G,x,y):获取图G中边(x,y)或<x,y>对应的权值。

Set_edge_value(G,x,y,v):设置图G中边(x,y)或<x,y>对应的权值为v。

3.图的广度优先遍历（BFS）

要点：

①找到与一个顶点相邻的所有顶点

②标记哪些顶点被访问过

③需要一个辅助队列

bool visited[MAX_VERTEX_NUM];    //访问标记数组

void BFSTraverse(Graph G){    //对图G进行广度优先遍历
    for(i=0;i<G.vexnum;++i)
        visited[i]=FALSE;    //访问标记数组初始化
    InitQueue(Q);    //初始化辅助队列Q 
    for(i=0;i<G.vexnum;++i)    //从0号顶点开始遍历
        if(!visited[i])    //对每个联通分量调用一次BFS
            BFS(G,i);    //vi未访问过，从vi开始BFS
}

//广度优先遍历
void BFS(Graph G,int v){    //从顶点v出发，广度优先遍历图G
    visit(v);    //访问初始顶点v
    visited[v]=TRUE;    //对v做已访问标记
    Enqueue(Q,v);    //顶点v入队列Q
    while(!isEmpty(Q)){
        DeQueue(Q,v);    //顶点v出队列Q
        for(w=FirstNeighbor(G,v);w>=0;w=NextNeighbor(G,v,w))
            //检测v所有邻接点
            if(!visited[w]){    //w为v的尚未访问的邻接顶点
                visit(w);    //访问顶点w
                visited[w]=TRUE;    //对w做已访问标记
                EnQueue(Q,w);    //顶点w入队列
            }    //if
    }    //while
}

 4.图的深度优先遍历

bool visited[MAX_VERTEX_NUM];    //访问标记数组

void DESTraverse(Graph G){    //对图G进行深度优先遍历
    for(v=0;v<G.vexnum;++v)
        visited[v]=FALSE;    //初始化已访问标记数据
    for(v=0;v<G.vexnum;++v)    //本代码中是从v=0开始遍历
        if(!visited[v])
            DFS(G,v);
}

void DFS(Graph G,int v){    //从顶点v出发，深度优先遍历图G
    visit(v);    //访问顶点v
    visited[v]=TRUE;    //设已访问标记
    for(w=FirstNeighbor(G,v);w>0;w=NextNeighbor(G,v,w))
        if(!visited[w]){    //w为u的尚未访问的邻接顶点
            DFS(G,w);
        }    //if
}

5.最短路径(BFS算法)

//求顶点u到其他顶点的最短路径
void BFS_MIN_Distance(Graph G,int u){
    //d[i]表示从u到i结点的最短路径
    for(i=0;i<G.vexnum;++i){
        d[i]=∞;    //初始化路径长度
        path[i]=-1;    //最短路径从哪个顶点过来
    }
    d[u]=0;
    visited[u]=TRUE;
    EnQueue(Q,u);
    while(!isEmpty(Q)){    //BFS算法主过程
        DeQueue(Q,u);    //队头元素u出队
        for(w=FirstNeighbor(G,u);w>=0;w=NextNeighbor(G,u,w))
            if(!visited[w]){    //w为u的尚未访问的邻接顶点
                d[w]=d[u]+1;    //路径长度加1
                path[w]=u;    //最短路径应从u到w
                visited[w]=TRUE;    //设已访问标记
                EnQueue(Q,w);    //顶点w入队
            }    //if
    }    //while
}