第六章学习小结

第六章图

一些需要注意的点：

一、6.1 图的定义和基本术语

1.假设图中有 n 个顶点，e 条边，若边或弧的个数 e<nlogn，则称作稀疏图，否则称作稠密图。

2.和顶点v 关联的边的数目定义为边的度。

3.顶点的出度: 以顶点v为弧尾的弧的数目顶点的入度: 以顶点v为弧头的弧的数目顶点的度(TD)= 出度(OD)+入度(ID)

4.如果它的起止顶点相同，该路径称为“回路”. 如果路径中除起始与终止顶点可以重合外，所有顶点两两不等，则该路径称为简单路径(simple path)。路径上边的数目称作路径长度。

5. 假设一个连通图有 n 个顶点和 e 条边，其中 n-1 条边和 n 个顶点构成一个极小连通子图，称该极小连通子图为此连通图的生成树。

二、6.3 图的ADT定义

数据对象集：一个非空的顶点集合和一个边集合，每条边用对应的一对顶点表示。

操作集：CreateGraph(&G, V, E) //创建

DeatroyGraph(&G)//销毁

InsertEdge(&G, e)//插入

DeleteEdge(&G, e)//删除

DFS(G, v)//深搜

BFS(G, v)//广搜

......

三、6.4 图的存储结构

定义一个数据结构，能够表示图的信息：总顶点数和总边数、点的信息、边依附的顶点及权值；

1.邻接矩阵存储表示无向带权图

//用两个数组分别存储顶点表和邻接矩阵
const int MVNum = 100;      //最大顶点数 
typedef char VerTexType; /假设顶点的数据类型为字符型 
typedef int ArcType;      //假设边的权值类型为整型 
typedef struct{ 
  VerTexType vexs[MVNum];    //顶点表 
  ArcType arcs[MVNum][MVNum]; //邻接矩阵 
  int vexnum,arcnum;          //图的当前点数和边数 
}AMGraph; 
void CreateUDN(AMGraph &G){
  cin>>G.vexnum>>G.arcnum; //输入总顶点数，总边数 
  for(i=0; i<G.vexnum; ++i)    
      cin>>G.vexs[i];      //依次输入点的信息 
  for(i=0; i<G.vexnum; ++i)     
  //初始化邻接矩阵，边的权值均置为极大值
      for(j=0; j<G.vexnum;++j)   
         G.arcs[i][j] = INT_MAX;   
  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; //边<v1, v2>的权值置为w 
      //置<v1, v2>的对称边<v2, v1>的权值为w
      G.arcs[j][i] = G.arcs[i][j];  
   }//for 
}//CreateUDN 
int LocateVex(MGraph G, VertexType u)
 {//存在则返回u在顶点表中的下标;否则返回-1
   int i;
   for(i=0; i<G.vexnum; ++i)
     if(u==G.vexs[i])
       return i;
   return -1;
 }

View Code

因为是无向带权图，边<v1, v2>的权值置为w，而<v1, v2>的对称边<v2, v1>的权值为w

typedef struct { VerTexType data; // 顶点信息 ArcNode *firstarc; // 指向第一条依附该顶点的弧 } VNode, AdjList[MVNUM]; typedef struct ArcNode { int adjvex; //该边所指向的顶点的位置 struct ArcNode *nextarc; //指向下一条边的指针 OtherInfo info; //和边相关的信息，例如权值 } ArcNode; typedef struct { AdjList vertices; int vexnum, arcnum; //顶点数和边数 } ALGraph; void 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; //初始化表头结点的指针域为NULL }//for for(k=0; k<G.arcnum; ++k) { //输入各边，构造邻接表 cin >> v1 >> v2 >> w; //输入边的两个顶点及权值 i = LocateVex(G, v1); j = LocateVex(G, v2); p = new ArcNode; //生成一个新的边结点*p 　　 p->adjvex = j; //邻接点序号为j p->info = w; //权值为w //头插法插入到G.vertices[i].firstarc指向的结点之前　　 p->nextarc = G.vertices[i].firstarc; G.vertices[i].firstarc = p; }//for }//CreateUDG int LocateVex(ALGraph &G, VerTexType u) {//图中搜索顶点u是否存在，存在则返回u在//G.vertices[ ]中的下标;否则返回-1 int i; for(i=0; i<G.vexnum; i++) //i取值为有效下标 if(u==G.vertices[i].data) //查找顶点名字 return i; //返回下标 return -1; //该顶点名字不存在，返回-1 }

void DFS(Graph G, int v) { // 从顶点v出发，深度优先搜索遍历连通图 G visited[v] = TRUE; for(w=FirstAdjVex(G, v); w>=0; w=NextAdjVex(G,v,w)) if (!visited[w]) DFS(G, w); // 对v的尚未访问的邻接顶点w // 递归调用DFS } // DFS

void DFSTraverse(Graph G) { // 对图 G 作深度优先遍历 for (v=0; v<G.vexnum; ++v) visited[v] = FALSE; //访问标志数组初始化 for (v=0; v<G.vexnum; ++v) if (!visited[v]) DFS(G, v); // 对尚未访问的顶点调用DFS }

void BFS (Graph G, int v) { //按广度优先非递归遍历连通图G cout<<v; visited[v] = true; 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进队 }//if }//while }//BFS

相关推荐