数据结构——图（1）很详细

大家好，欢迎来到IT知识分享网。

1>基本概念

定义

有向图，弧(有向边)

无向图，边（无向边）

由顶点集合与边的集合组成的图称为无向图。

举个栗子

(a,b)表示a,b互为邻接点，(a,b)依附于a和b, (a,b)与a和b相互关联。

完全图（无向）

有n个顶点和n(n-1)/2条边的无向图称为完全图。

有向完全图

有n个顶点和n(n-1)条弧的有向图称为有向完全图。

网

子图

对图G=(V,VR)和G’=(V’,VR’),若V’ ⊆ V且VR’ ⊆ VR,则称G’是G的一个子图。

如图，G1,G2,G3为G的子图，G4不是。

度

出度

入度

连通性术语

连通图及连通分量（无向图G）

强连通图及强连通分量（有向图G）

若在图G中每对顶点Vi,Vj之间，从Vi到Vj且从Vj到Vi都存在路径，则称G是强连通图。
若图G’是G的一个极大连通子图，则称G’是G的强连通分量。强连通图的强连通分量是自身。

G1,G2是G的强连通分量。

生成树

图的操作

2>图的存储

数组表示法

举个栗子

对与有向网和无向网，需要在邻接矩阵中加上关系的权值，如果两个顶点间有邻接关系，就用权值代替原来的1，否则用∞代替0。

举个栗子

数组表示法的数据类型定义

code(伪)

#define MAX_VERTEX_NUM 20 typedef enum{ 
   DT, DN, UDG, UDN }GraphKind; typedef struct{ 
    VertexTpye vexs[MAX_VERTEX_NUM]; VRType arcs[MAX_VERTEX_NUM][MAX_VERTEX_NUM]; int vexnum,arcnum; GraphKind kind; }Mgraph; 

邻接表表示法

这是一种顺序 + 链式的物理存储结构，通过头结点数组保存所有的信息，用单链表保存顶点之间的关系。

无向图的邻接表

为图G的每个顶点建立一个单链表，第i个单链表中的结点表示依附于顶点的Vi的边。

有向图的邻接表

有向图的逆邻接表表示法

有向网的邻接表

表结点表示边或弧，所以就对表结点扩充一个属性域，表结点至少包含顶点序号、权值和下一个表结点指针3个属性。

由此终于可以得出邻接表是如何定义的了

code(伪)

#define MAX_VERTEX_NUM 20 typedef struct ArcNode{ 
   //表结点类型定义，对网需要加权值属性 int adjvex;//顶点位置编号 struct ArcNode *nextarc;//下一结点指针 InfoType *info; }ArcNode; typedef struct VNode{ 
   //头结点及其数组类型定义 VertexType data;//顶点信息 ArcNode *firstarc;//指向第一条弧  }VNode,AdjList[MAX_VERTEX_NUM]; typedef struct { 
   //邻接表的类型定义 AdjList vertice;//头结点数组 int vexnum,arcnum;//顶点数，弧数 GraphKind kind;//图的类型  }ALGraph;

有向图的十字链表

tailvex:弧尾的位置
headvex:弧头的位置
hlink:指向下一条弧头相同的弧
tlink:指向下一条弧尾相同的弧
2）每个顶点有一个顶点结点

data：顶点信息
firstin：指向以该顶点为弧头的第一条弧
firstout：指向以该顶点为弧尾的第一条弧

以邻接图为基础，扩展结点的属性成起止结点序号
再添加逆邻接表的信息


这个图的画法还是有技巧的，眼尖的同学可能注意到了，我在每个弧结点的下方有有标记，邻接表的指向和标记的顺序是相同的，AB就是AB，而逆邻接表刚好和标记相反，AB则为BA。

code(伪)

#define MAX_VERTEXT_NUM 20 typedef struct ArcBox{ 
    int tailvex,headvex; //该弧的尾和头顶点位置 struct ArcBox *hlink,*tlink;//分别为弧头相同和弧尾相同的弧的链域  }ArcBox; typedef struct VexNode{ 
    VertexType data; ArcBox *firstin,*firstout;//分别指向该顶点的第一条入弧和出弧  }VexNode; typedef struct{ 
    VexNode xlink[MAX_VERTEXT_NUM];//表头变量 int vexnum,arcnum;//有向图的当前顶点数和弧数  }OLGraph;

无向图邻接多重表

1）每个顶点有一个头结点

data：顶点信息
firstedge：指向第一条依附于该顶点的边

mark：标志域，可以标记该边是否被搜索过
ivex，jvex：值该边依附的两个顶点在顶点数组的位置
ilink：指向下一条依附于顶点vi的边
jlink：指向下一条依附于顶点vj的边

code(伪)

//无向图邻接多重表  #define MAX_VERTEXT_NUM 20 typedef enum{ 
    unvisited,visited}visitedIf; typedef struct EBox{ 
    visitedIf mark;//访问标记 int ivex,jvex;//该边依附的两个顶点的位置 struct EBox *ilink,*jlink;//分别指向依附与这两个顶点的下一条边  }EBox; typedef struct VexBox{ 
    VertexType data; EBox *firstedge;//指向第一条依附于该顶点的边  }VexBox; typedef struct{ 
    VexBox adjmulist[MAX_VERTEXT_NUM]; int vexnum,edgenum;//无向图的当前顶点数和边数  }AMLGraph;

3>图的遍历

图的深度遍历

从V1出发，访问一个未访问过的V1的邻接点V2，以V2作为新的出发点，继续深度优先搜索，直到把与V1相连通的点都被访问，如果还有未访问的点，需要在其中选择一个作为新的起点，继续进行深度优先搜索，直到所有顶点都被访问到。

code(伪)

//深度优先遍历  boolean visited [MAX] void DFDTraverse(Graph G, Status (*visit)()) { 
    for(v=0;v<G.vesnum;v++)//初始化各顶点未访问状态 visited[v]=false; for(v=0;v<G.vexnum;v++) if(!visit[v])//从一个未访问的顶点开始 DFS(G,v,visit); } void DFS(Graph G,int v,Status (*visit)()) { 
    visited[v]=true;visited(v);//标记顶点，并且访问顶点  for(w=FirstAdjVex(G,v),w>0;w=NextAdjVex(G,v,w))//查找与顶点v相邻并且没有访问过的顶点  if(!visited[w])//处理所有未访问的邻接顶点  DFS(G,w,visited); //递归，继续深度优先遍历  }

图的广度优先遍历

假定从V1出发，先访问V1，再访问所有未被访问过的V1的邻结点，访问次序满足：先被访问过的顶点的邻接点的访问先于后被访问过的顶点的邻结点的访问。
直到与V1相连通的点都被访问。如果还有未被访问过的顶点，选择其中一个作为出发点，继续广度优先搜索，直到所有的顶点被访问。

举个栗子

code(伪)

//广度优先遍历 void BFSTraverse(Graph G,Status (*visit)()) { 
    for(v=0;v<G.vexnum;v++) visited[v]=false; //初始化visited数组  InitQueue(Q);//初始化队列 for(v=0;v<G.vexnum;v++) //按顶点位置序号依次选择顶点 if(!visited[v]){ 
   //遇到未访问过的顶点开始遍历 visited[v]=true;visit(v);EnQueue(Q,v);//标记顶点，并访问顶点，把顶点加入到队列 Q中  while(!QueueEmpty(Q)){ 
   //如果队列非空，进行出队操作  DeQueue(Q,u);//出队顶点为u  for(w=FirstAdjVex(G,u),w>=0;w=NextAdjVex(G,u,w))//对u的相邻顶点进行分析  if(!visited[w]){ 
   //如果某个相邻顶点w没有被访问过  visited[w]=true;//标记顶点  visited(w);//开始访问  EnQueue(Q,w);//把w入队  } } } } 

4>图的连通性问题

无向图的连通分量和生成树

遍历几次就有几个连通分量
DFS生成树
对一个无向连通图，进行DFS遍历时，遍历过程中经过的点和边组成的图，称为DFS生成树。

BFS生成树

DFS生成森林
对一个非连通图，由于需要多次遍历才能访问到所有顶点，每次DFS遍历都得到一课树所以得到一个深度优先生成森林。

BFS生成森林
对一个非连通图，由于需要多次遍历才能访问到所有顶点，每次BFS遍历都得到一课树所以得到一个广度优先生成森林。

有向图的强连通分量

网的最小生成树

MST性质

普里姆算法(prime算法)，求最小生成树（code伪）

怎么用计算思维表达这一过程，接着就是借助邻接矩阵和closedge这样一个结构体数组。

图终于画完了，接着给出伪代码

//图的最小生成树，prime算法  struct{ 
    VertexType adjvex; //最小权值的边，在U中依附的顶点  VRType lowcost; //记录最小权值lowcost  }closedge[MAX_VERTEXT_NUM]; void Prime(MGraph G, VertexType u) { 
    k=LocateVex(G,u); //确定起始顶点u的位置序号 for(j=0;j<G.vexnum;j++)//初始化最短边权值和依附顶点值  if(j!=k) closedge[j]={ 
   u,G.arcs[k][j].adj} closedge[k].lowcost=0;//选定起点u到U中  for(i=1;i<G.vexnum;i++){ 
   //依次加入n-1个顶点、n-1条边  k=minimum(closedge);//选择下一条最短边对应的顶点序号 printf(closedge[k].adjvex,G.vexs[k]);//输出生成树的边 closedge[k].lowcost=0; //顶点k加入到U中 for(j=0;j<G.vexnum;j++) //替换最小权值的依附顶点  if(G.arcs[k][j].adj<closedge[j].lowcost) closedge[j]={ 
   G.vexs[k],G.arcs[k][j].adj} } } //算法适合边稠密的无向连通图 ，T(n,e)=O(n*n)

5>

学习进度到了图这一课，本来我是打算把数据结构从头到尾整理一遍，但刚好学到了图，就打算先把图的笔记先写出来。

从单链表到树，搞懂之后觉得数据结构学起来很爽，直到我遇见了图，图这玩意太难了，这篇笔记写着写着让我想要放弃，但写了这么多，不写了实在可惜。

看一下字数：

写还不是最难的，举例子是要画图的，做图又不会做，盗图又不会盗，就只能靠一笔一画去画这种东西，才能勉强举的了栗子这样子。

这么多东西自己都写不下去了，让大家怎么看，于是我先写了前4节，后面再写有向无环图及其应用和最短路径。

已经尽力去学了，如果有些错误，还请包涵并指出。