数据结构学习笔记-图

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])    //对每个联通分量调用一次BFSBFS(G,i);    //vi未访问过，从vi开始BFS
}//广度优先遍历
void BFS(Graph G,int v){    //从顶点v出发，广度优先遍历图Gvisit(v);    //访问初始顶点vvisited[v]=TRUE;    //对v做已访问标记Enqueue(Q,v);    //顶点v入队列Qwhile(!isEmpty(Q)){DeQueue(Q,v);    //顶点v出队列Qfor(w=FirstNeighbor(G,v);w>=0;w=NextNeighbor(G,v,w))//检测v所有邻接点if(!visited[w]){    //w为v的尚未访问的邻接顶点visit(w);    //访问顶点wvisited[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出发，深度优先遍历图Gvisit(v);    //访问顶点vvisited[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;    //路径长度加1path[w]=u;    //最短路径应从u到wvisited[w]=TRUE;    //设已访问标记EnQueue(Q,w);    //顶点w入队}    //if}    //while
}