图（概念多，算法较为复杂）

1. 图的定义与术语

   1. 按方向区分：

      1. 有向图（顶点+弧 [弧头弧尾] ）
         1. 邻接：入度+出度
         2. 强连通图：顶点间存在路径
         3. 有向树：一个入度为0，其余出度为1
         4. 生成森林：若干棵有向树
      2. 无向图（顶点+边）
         1. 邻接：度
         2. 连通图：存在路径
         3. 生成树：连通 + n个顶点 + n-1条边

   2. 环：首尾同顶点

   3. 网（带权图）：边/弧上带权

   4. 按边/弧的数量区分（路径长度）：稀疏图、稠密图

2. 图的五种存储结构

   1. 邻接矩阵

      1. 结构定义：

         1. 一维数组：保存 ==顶点== 的信息
         2. 二维数组：保存 ==边/弧== 的信息（行出列入）

         1 2 3 4 5 6 7

         #define INFINITY 65535; //∞ typedef struct { char vexs[MAXSIZE]; //一维数组（顶点表） int arc[MAXVEV][MAXVEX]; //二维数组（邻接矩阵） int numNodes,numEdges; //记录当前顶点数，边数 }MGraph;

      2. 邻接矩阵作用：

         1. 判断邻接：根据邻接矩阵获取邻接点信息
         2. 求度：v_i在第i行（或i列）的元素之和
         3. 求邻接：循环遍历第i行元素，arc[i][j] == 1为邻接点

      3. 网的邻接矩阵：邻接点多加一个权值W_ij，自身为0（对角线），其他为∞

         1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34

         /* 1.输入顶点数、边数 2.按顶点数循环：输入顶点 3.初始化邻接矩阵：双层循环结构遍历行/列，全部元素置为∞ 4.按边数循环： (1)输入依附的顶点i，j，权值w (2)权值赋值到邻接矩阵对应i，j位置 (3)按照邻接矩阵对角线对称性：i行j 列赋值 j行i列 */ void CreatMGraph(MGraph *G) { int i,j,k,w; printf("输入顶点数、边数："); scanf(%d %d,&G->numNodes,&G->numEdges); //1 for(i=0 ; i<G->numNodes ; i++) //2 { printf("输入顶点信息存入顶点表："); scanf(&G->vexs[i]); } for(i=0;i<G->numNodes;i++) //双层循环：初始化 { for(j=0;j<G->numNodes;j++) { G->arc[i][j]=INFINITY; //3 } } for(k=0 ; k<G->numEdges ; k++ ) //4 { printf("输入边(Vi,Vj)依附的顶点i，顶点j，权值w"); scanf(%d %d %d,&i,&j,&w) //4.1 G->arc[i][j] = w; //4.2 G->arc[j][i] = G->arc[i][j]; //4.3 } }

   2. 邻接表（数组+链表）

      1. 结构定义：

         1. 一维数组：==顶点==（data） + ==指向第一个邻接点的指针==（firstedge）
         2. 线性链表：==所有邻接点==构成【无向图：边表】；==以顶点为弧尾==的上一个顶点构成【有向图：出边表】；（逆邻接表）==以顶点为弧头==的上一个顶点构成【有向图：入边表】

         1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18

         //（单链）结点结构 typedef struct EdgeNode { int adjvex; //点域 char info; //权 struct EdgeNode *next; //指针域 } //一维数组 typedef struct VertextNode { VertexType data; //数据域 EdgeNode *firstedge; //表头指针域 }VertextNode,AdjList[MAXSIZE]; typedef struct { AdjList adjList; int numNodes,numEdges; //边数&顶点数 }GraphAdjList;

      2. 无向图邻接表创建：O(n+e)

         1. 创建初始化顶点表
         2. 头插法建立边表：生成单链表

         1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29

         void CreateALGraph(GraphAdjList *G) { int i,j,k; EdgeNode *e; //建立初始化顶点表 |data|firstedge=NULL| printf("输入顶点数和边数：\n"); scanf("%d,%d",&G->numNodes,&G->numEdges); for(i = 0;i < G->numNodes ; i++) { scanf(&G->adjList[i].data); G->adjList[i].firstedge=NULL; //1 } //头插法建边表 |adjvex|(weight)|next| for(k=0;k<G<numEdges;k++) { printf("输入边（Vi，Vj）上的顶点序号：\n"); scanf("%d %d",&i,&j); /*************头插入左端i结点*************/ e=(EdgeNode *)malloc(sizeof(EdgeNode)); e->adjvex = j; e->next = G->adjList[i].firstedge; G->adjList[i].firstedge = e; /*************头插右端j结点**************/ e=(EdgeNode *)malloc(sizeof(EdgeNode)); e->adjvex = i; e->next = G->adjList[j].firstedge; G->adjList[j].firstedge = e; } }

   3. 十字链表（较难理解）（邻接表+逆邻接表）

      1. 一维数组：顶点 + 指向第一个头 + 指向第一个尾
      2. 出入邻接表：（出边表） == 弧尾在顶点的下标【tailvex】 + 弧尾相同的下一条边指针域【taillink】 +（入边表） == 弧头在顶点的下标【headvex】 + 弧头相同的下一条边指针域【headlink】

   4. 多重邻接表（无向图：方便对边操作的改进版邻接表）

      1. 一维数组：data + firstedge
      2. 改进邻接链表：
         1. ivex、jvex：某条边依附的两个顶点下标（ilink指向的结点的jvex 一定要和本身的ivex值相同）
         2. ilink、jlink：依附于顶点i、j的下一条边

   5. 边集数组（两个一维数组）

      1. 顶点：data
      2. 边：起点下标（begin）、终点下标（end）、权值（weight）

      1 2 3 4 5 6

      typedef struct { int begin; int end; int weight; }Edge;

3. 图的遍历

   1. 深度优先遍历DFS（递归回溯：一条路到底，层层回退）

      1. 邻接矩阵DFS

         1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30

         //深度优先递归算法 Boolean visited[MAXVEX]; void DFS(MGraph G,int i) { int j; visited[i] = TRUE; //TRUE:已访问 printf("%c",G.vexs[i]); for(j=0;j<G.numVertexes;j++) { if(G.arc[i][j] == 1 && !visited[j]) { DFS(G,j); //未访问结点递归调用DFS } } } void DFSTraverse(MGraph G) //初始化所有结点为未访问状态FALSE int i; for(i=0;i<G.numVertexes;i++) { visited[i]=FALSE; } //DFS遍历 for(i=0;i<G.numVertexes;i++) { if(!visited[i]) { DFS(G,i); } }

      2. 邻接表DFS

         1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30

         void DFS(GraphAdjList GL,int i) { EdgeNode *p; visited[i] = TRUE; printf("%c",GL->adjList[i].data); p=GL->adjList[i].firstedge; while(p) { if(!visited[p->adjvex]) { DFS(GL,p->adjvex); } p=p->next; } } void DFSTraverse(GraphAdjList GL) { int i; for(i=0;i<GL->numVertexes;i++) { visited[i]= FALSE; } for(i=0;i<GL->numVertexes;i++) { if(!visited[i]) { DFS(GL,i); } } }

   2. 广度优先遍历BFS（队列：遍历顶点邻接）

      1. 邻接矩阵BFS
      2. 邻接表DFS

4. 图的应用

   1. 最小生成树

      1. 普里姆算法prim：从一点出发，逐步找已知顶点依附的最小权值边

         1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37

         void MiniSpanTree_Prim(MGraph G) { int min,i,j,k; int adjvex[MAXSIZE]; int lowcost[MAXSIZE]; lowcost[0]=0; adjvex[0]=0; for(i=1;i<G.numVertexes;i++) { lowcost[i]=G.arc[0][i]; adjvex[i]=0; } for(i=1;i<G.numVertexes;i++) { min=INFINITY; j=1;k=0; while(j<G.numVertexes) { if(lowcost[j]!=0 && lowcost[j]<min) { min=lowcost[j]; k=j; } j++; } printf("(%d,%d)\n",adjvex[k],k); lowcost[k]=0; for(j=1;j<G.numVertexes;j++) { if(lowcost[j]!=0 && G.arc[k][j]<lowcost[j]) { lowcost[j] = G.arc[k][j]; adjvex[j] = k; } } } }

      2. 克鲁斯卡尔算法kruskal：把图中最短边一个个挑出来（上帝/全局视角）

         1 2 3 4

         void MiniSpanTree_Kruskal(MGraph G) { }

   2. 最短路径（源点到终点权值之和最小的路径）

      1. 迪杰斯特拉算法dijkstra（单源顶点查找）

         1. 结构定义：

            1 2 3 4 5 6 7 8

            typedef struct { int vexs[MAXVEX]; int arc[MAXVEX][MAXVEX]; int numVertexes,numEdges; }MGraph; typedef int Patharc[MAXVEX]; //存储存储最短路径下标的数组 typedef int ShortPathTable[MAXVEX]; //各点最短路径的权值和

         2. dijkstra算法：

            1. P[]：该位顶点依附最短权的上一位顶点
            2. D[]：V₀到V_该点的最短路径长度
            3. final[]：标记数组。0为位置最短路长，1为已知最短路长

            1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35

            void ShortestPath_Dijkstra(MGraph G,int v0,Patharc *P,ShortPathTable *D) { int v,w,k,min; int final[MAXVEX]; for(v=0;v<G.numVertexes;v++) { final[v]=0; (*D)[v]=G.arc[v0][v]; (*P)[v]=-1; } (*D)[v0]=0; final[v0]=1; /***********主循环，每次求得v0到某个顶点v的最短路径***************/ for(v=1;v<G.numVertexes;v++) { min=INFINITY; for(w=0;w<G.numVertexes;w++) { if(!final[w] && (*D)[w]<min) { k=w; min=(*D)[w]; } } final[k]=1; for(w=0;w<G.numVertexes;w++) { if(!final[w] && (min+G.arc[k][w]<(*D)[w])) { (*D)[w]=min + G.arc[k][w]; (*P)[w]=k; } } } }

      2. 弗洛伊德算法floyd：（应用矩阵的变化）二重循环初始化 + 三重循环修正 【适合：求所有顶点到任意顶点】

         1. 二维数组：D^-1（Data）：存放最短路径权值（初始化：-1）
         2. 二维数组：P^-1（Path）：存放路径信息（初始化：-1）

         1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30

         typedef int Patharc[MAXVEX][MAXVEX]; typedef int ShortPathTable[MAXVEX][MAXVEX]; void ShortPath_Floyd(MGraph G,Patharc *P,ShortPathTable *D) { int v,w,k; //二重循环初始化 for(v=0;v<G.numVertexes;++v) { for(w=0,w<G.numVertexes;++w) { (*D)[v][w]=G.arc[v][w]; (*P)[v][w]=w; } } //三重循环修正 for(k=0;k<G.numVertexes;++k) { for(v=0;v<G.numVertexes;++v) { for(w=0;k<G.numVertexes;++w) { if((*D)[v][w]>(*D)[v][k]+(*D)[k][w]) { (*D)[v][w]=(*D)[v][k]+(*D)[k][w]; (*P)[v][w]=(*P)[v][k]; } } } } }

      3. 最短路径显示：遍历矩阵

         1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16

         for(v=0;v<G.numVertexes;++v) { for(w=v+1;w<G.numVertexes;w++) { printf("v%d-v%d weight:%d",v,w,D[v][w]); //遍历打印矩阵D k=P[v][w]; //k索引矩阵P printf("path:%d",v); //打印源点 while(k!=w) { printf("-> %d",k); //打印路径顶点 k=P[k][w]; } printf("->%d\n",w); //打印终点 } printf("\n"); }

   3. 工程规划（有向无环图）

      1. 边表结构：（有向 + weight）

         1 2 3 4 5 6 7

         //边表结点 typedef struct EdgeNode { int adjvex; //邻接点域 int weight; //权值 struct EdgeNode *next; //下一个邻接点链域 }EdgeNode;

      2. 顶点表结构：

         1 2 3 4 5 6 7

         //顶点表结点 typedef struct VertexNode { int in; //顶点入度 int data; //顶点数据域 EdgeNode *firstedge; //边表头指针 }VertexNode,AdjList[MAXVEX];

      3. 拓扑排序（AOV网）

         1. 顶点：活动

         2. 弧：活动间的优先关系

            1 2 3 4 5

            typedef struct { AdjList adjList; int numVertexes,numEdges; //记录顶点数、边数 }graphAdjList,*GraphAdjList;

         3. 进行拓补排序的辅助数据结构：栈【用来存储处理过程中入度为0的顶点】

            1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38

            //O(n+e) Status ToplpgicalSort(GraphAdjList GL) { EdgeNode *e; int i,k,gettop; int top=0; int count=0; int *stack; stack=(int *)malloc(GL->numVertexes * sizeof(int)); fot(i=0;i<GL->numVertexes;i++) { if(0==GL->adjList[i].in) //入度为0顶点入栈 { stack[++top]=i; } while(top!=0) { gettop=stack[top--]; //弹栈，取除栈顶，top-- printf("%d->",GL->adjList[gettop].data); count++; for(e=GL->adjList[gettop].firstedge ; e ; e=e->next) { k=e->adjvex; if(!(--GL->adjList[k].in)) { stack[++top]=k } } } if(count < GL->numVertexes) { return ERROR; } else { return OK; } }

      4. 关键路径（AOE网）（带权有向图）

         1. 顶点 V_k：事件【最早：etv ；最晚：ltv】
         2. 弧（有向边）a_k：活动【最早：ete ； 最晚：lte】
         3. 弧上权值：活动持续时间

         1 2 3 4

         int *etv,*ltv; //（顶点）事件最早发生和最迟发生时间数组 int *stack2; //存储拓补序列的栈 int top2; //栈顶指针 /*********用stack2进行拓补排序************/

         1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41

         //O(n+e) void CriticalPath(GraphAdjList GL) { EdgeNode *e; int i,gettop,k,j; int ete,lte; //（弧）活动最早发生时间，活动最迟发生时间 TopologicalSort(GL); ltv=(int *)malloc(GL->numVertexes * sizeof(int)); //初始化ltv for(i=0;i<GL->numVertexes;i++) { ltv[i]=etv[GL->numVertexes-1]; } //计算事件最迟ltv while(top2!=0) { gettop=stack2[top--]; for(e=GL->adjList[gettop].firstedge;e;e=e->next) { k=e->adjvex; if(ltv[k] - e->weight < ltv[gettop]) { ltv[gettop] = ltv[k] - e->weight; } } } //求ete,lte,关键活动 for(j=0;j<GL->numVertexes;j++) { for(e=GL->adjList[j].firstedge; e ;e=e->next) { k=e->adjvex; ete=etv[j]; lte=ltv[k] - e->weight; if(ete == lte) //活动最早最晚相等，意味活动中没有空闲时间，即关键路径 { printf("<v%d - v%d> length: %d \n",GL->adjList[j],data,GL->adjList[k].data,e->weight); //打印关键路径 } } } }