1、逻辑结构
①定义：G=(V,E)。V是顶点集，E是顶点间二元关系的集合。
（内涵越小，外延越大）
②与树的区别：
①树有特殊的根结点；
②树的结点和关系能分成互不相交的若干子集。
③图的分类：
无向图
有向图
边：二元关系是无序的。
弧：二元关系是有序的。
(vi,vj)：vi,vj互为邻接点
vi,vj：弧头vj、弧尾vi
G1=(V1,E1)
V1={v1,v,v3,v}
E1={(v1,v),(v1,v3),
(v1,v),(v,v3),
(v,v),(v3,v)}
G=(V,E)
V={v1,v,v3,v}
E={v1,v,v,v1,
v,v3,v,v3}
二、基本操作①对顶点的操作：
InsertVex、DeleteVex、GetVex、SetVex
②对弧/边的操作：
InsertArc、DeleteArc、GetArc、SetArc
③对整体的操作(遍历)：
深度遍历DFSTraverse、广度遍历BFSTraverse
三、常见应用①信息的组织：
家庭照片管理（与个人照片管理的差别）
②运输问题：
从南京到泰州，最近的路线？换车最少的路线？
电子邮件的路由选择？
③网络的规划：
小区设店的位置选择？
区域规划、城市规划
计算机网络的规划
④进度组织：
工程进度管理
并行计算问题
四、概念术语思路：考虑图的复杂应用，提供简化问题的思路。
1、图的分类
着眼点：存储结构的选择。
无向完全图
边数：n*(n-1)/
有向完全图
弧数：n*(n-1)
稀疏图
边数≈顶点数
稠密图
边数≈顶点数
带权图
边或顶点带权值
着眼点：图的分解。
子图
V(B)∈V(A)，E(B)∈E(A)，称图B是图A的子图。
、顶点的参数
度
无向图中，依附于某顶点的边数
入度
有向图中，以某顶点为弧尾的弧数
出度
有向图中，以某顶点为弧头的弧数
度的应用：以下哪个图能够一笔画完成？为什么？
一笔画问题的本质：图结构中的边遍历问题。
应用领域：车间/厂房布置、行走路线的安排…
3、有关路径
着眼点：顶点间的联系。
顶点间路径
Vi,……,Vj
顶点间连通
若从Vi到Vj有路径，称Vi到Vj是连通的。
路径长度
路径上边/弧的数目。
简单路径
路径中所有顶点各不相同。
回路
路径中，起点和终点是同一顶点。
简单回路
除起点和终点外，其余顶点各不相同。
、有关连通
着眼点：将不连通图简化为连通图。
连通图
无向图中，任意二个顶点之间是连通的。
强连通图
有向图中,任意二个顶点之间存在来往路径。
第二节图的存储结构存储结构应该包含：
①顶点的信息；
②边/弧的信息；
③权的信息。
一、数组表示法1、存储结构
#defineMAX_VERTEX//最大顶点个数
typedefstructArcCell//边、弧结构
{VRTypeadj;//权值
InfoType*info;//指向更多信息
}ArcCell;
typedefstruct
{VertexTypevexs[MAX_VERTEX];//顶点向量
ArcCellarcs[MAX_VERTEX][MAX_VERTEX];//邻接矩阵
intvexnum,arcnum;//顶点数、边数
}MGraph;//arcs[i][j]：顶点i-顶点j
空间复杂度：O(n*n)。
intcost[N][N]={{0,1,1,0},
{1,0,0,1},
{1,0,0,1},
{0,1,1,0},
};
intcost[N][N]={{0,,,M},
{,0,M,8},
{,M,0,1},
{M,8,1,0},
};
intcost[N][N]={{0,,,M},
{M,0,M,8},
{M,M,0,M},
{M,M,1,0},
};
优缺点：
操作方便，适合稠密图。
无向图的arcs[][]为对称矩阵，空间浪费。
当点多边少时，空间浪费多。
、算法思考
针对以上三图的存储结构，分析：
①在无向图中，如何求顶点i的度？
②在有向图中，如何求顶点i的入度、出度？
二、邻接表1、结构分析
图的变化特征：顶点变化少，关系变化多。
顶点表:顺序结构。边/弧表：动态链表。
typedefstructArcNode//边、弧结构
{intadjvex;//邻接点、弧头的编号
InfoType*info;
structArcNode*nextarc;
}ArcNode;
typedefstructVexNode//顶点结构
{VertexTypedata;
ArcNode*firstarc;//指向出边表
}VexNode;
typedefstruct//图的邻接表结构
{VexNode*vertexes;
intvexnum,arcnum;
}ALGraph;
带权图的邻接表
、建立有向图邻接表的算法
①初始化一个无关系的邻接表结构
voidALGraph_Init(ALGraphG,VertexTypedata[],intn)
{G.vexnum=n;G.arcnum=0;//n为顶点数
G.vertexes=(VexNode*)malloc(n*sizeof(VexNode));
for(i=0;in;i++)//初始化空关系图
{G.vertexes[i].data=data[i];
G.vertexes[i].firstarc=NULL;
}
}
②插入一个弧v1,v
voidALGraph_Insert(ALGraphG,intv1,intv)
{ArcNode*p;
p=(ArcNode*)malloc(sizeof(ArcNode));
p-adjvex=v;
p-nextarc=G.vertexes[v1].firstarc;
G.vertexes[v1].firstarc=p;//首插入
G.arcnum++;
}
提醒：用不同插入方法，得到邻接表不一样。
3、邻接表的简单应用
①在无向图中，求顶点i的度？
在有向图中，求顶点i的出度？
intALGraph_OutDegree(ALGraphG,inti)
{intn;ArcNode*p;
p=G.vertexes[i].firstarc;
for(n=0;p;p=p-nextarc)n++;
return(n);
}
②在有向图中，如何求顶点i的入度？
intALGraph_InDegree(ALGraphG,inti)
{ArcNode*p;intk,n=0;
for(k=0;kG.vexnum;k++)
for(p=G.vertices[k].firstarc;p;p=p-nextarc)
if(p-adjvex==i)n++;
return(n);
}
三、逆邻接表1、结构分析
弧表中的结点是弧尾。
邻接表（出边表）
逆邻接表（入边表）
、算法思考
如何求入度、出度？与邻接表恰好相反
第三节图的遍历图遍历定义：从某顶点出发，对每个顶点访问且仅访问一次。
图遍历与树遍历的比较：
区别：
可能回到起点。因为图不能划分为若干个顶点、关系互不相交的子集。
扩展
对访问过的顶点作标记，并加以识别。
本节以邻接表为基础讨论算法程序。也可采用其他结构。
一、深度优先搜索DFS(DepthFirstSearch)1、算法
①设所有顶点都未曾被访问;(设置一个标记数组)
②从起点v出发，访问此顶点，同时设置访问标记；
③依次从v的未被访问过的邻接点出发进行DFS；
(效果：所有与v连通的顶点都被访问过)
④若所有顶点都已访问，则完成；否则，另择起点v，转至②。
例：已知邻接表，求遍历序列。
以顶点0为起点的DFS：0，1，，3，
以顶点3为起点的DFS：3，1，，，0
、递归程序
类似于树的递归遍历
Booleanvisited[MAX];inttime=0;//用于跟踪程序
//帽子函数
voidDFSTraverse(ALGraphG)
{if(G.vexnum==0)return;
for(v=0;vG.vexnum;v++)visited[v]=FALSE;//实现步骤①
for(v=0;vG.vexnum;v++)//实现步骤④
if(visited[v]==FALSE)DFS(G,v);
}
//核心函数：遍历顶点v所在的连通分量
voidDFS(ALGraphG,intv)//v为起点序号
{ArcNode*p;intw;
printf(v);visited[v]=TRUE;//实现步骤②
//实现步骤③
for(p=G.vertices[v].firstarc;p;p=p-nextarc)
{w=p-adjvex;
if(visited[w]==FALSE)
DFS(G,w);
}
}
思考：
时间复杂度？O(e)e为边/弧数
二、广度优先搜索BFS(breadthfirstsearch)相当于树的层次遍历。
1、算法
①设所有顶点都未曾被访问；
②将起点编号加入队列，同时设置访问标记；
③取队首元素，设为v，访问结点v；
④依次将v的各个未被访问过的顶点加入队列，同时设置访问标记；
⑤若队列不空，则循环执行③④，否则⑥；
⑥若所有顶点都已访问，则完成；否则，另择起点V，转至②。
例：已知邻接表，求遍历序列。
以顶点0为起点的BFS：0，1，3，，
以顶点3为起点的BFS：3，1，0，，
、程序
Booleanvisited[MAX];
//帽子函数
voidBFSTraverse(ALGraphG)
{if(G.vexnum==0)return;
for(v=0;vG.vexnum;v++)visited[v]=FALSE;//实现步骤①
for(v=0;vG.vexnum;v++)//实现步骤⑥
if(visited[v]==FALSE)BFS(G,v);
}
//核心函数：遍历顶点v所在的连通分量
//每个顶点出队列后，被访问
voidBFS(ALGraphG,intv)
{QueueQ;ArcNode*p;
Q_Init(Q);
Q_Enter(Q,v);visited[v]=TRUE;//步骤②
while(!Q_Empty(Q))//步骤⑤
{v=Q_Leave(Q);printf(v);//步骤③
for(p=G.vertices[v].firstarc;p;p=p-nextarc)//步骤④
{w=p-adjvex;
if(visited[w]==FALSE)
{Q_Enter(Q,w);visited[w]=TRUE;}
}
}
}
上机：以邻接表为结构存储图，深度、广度遍历之。
北京哪里治疗白癜风比较好治疗白癜风哪里比较好