同前篇一样，本篇意在总结有关图的一些基本算法

包括有图的最小生成树（Prim，Kruscal），最短路径（Dijkstra，Floyd），拓扑排序等算法

本篇图的数据结构为邻接表表示法

 

首先graph.h

#ifndef __GRAPH_H__#define __GRAPH_H__typedef struct graph *Graph;Graph graph_create(int n);void graph_destroy(Graph);void graph_add_edge(Graph g, char u, char v,unsigned int wt);int graph_vertex_count(Graph);int graph_edge_count(Graph);int graph_out_degree(Graph, char svex);int graph_has_edge(Graph, char svex, char tvex);void graph_foreach(Graph g, char svex,    void (*f)(Graph g, char svex, char tvex, void *data),    void *data);#endif

cpp文件

// 图.cpp : 定义控制台应用程序的入口点。//#include "stdafx.h"#include 
     
      #include
      
       #include 
       
        #include 
        
         #include "graph.h"/* 代码摘自一位yale前辈 */struct graph {    int vexnum;  /* number of vertices */    int edgenum;  /* number of edges */    struct successors {        char vexname;        char is_sorted;        /* true if list is already sorted */        int size;        /* number of successors，即出度数*/        int capacity;    /* number of slots in array，出度数组的长度，当空间不够，它就会两倍增加*/        struct outvexs{            char vex;            unsigned int weight;        } list[1];//出度数组。保存信息有顶点和权值    } *alist[1];//alist数组相当于顶点链表，n个顶点就有n个元素，这里同样是为了动态增加};/* create a new graph with n vertices labeled 0..n-1 and no edges */Graph graph_create(int n){    Graph g;    int i;    //新增一个graph空间和n-1个successors指针，算上graph中的一个successors指针就有n个了    g = (Graph)malloc(sizeof(struct graph) + sizeof(struct successors *) * (n-1));    //程序中大量使用assert，其作用是如果它的条件返回错误，则终止程序执行    assert(g);    g->vexnum = n;    g->edgenum = 0;    for(i = 0; i < n; i++) {        //顶点链表        g->alist[i] = (graph::successors*)malloc(sizeof(graph::successors));        assert(g->alist[i]);        g->alist[i]->vexname = 'A'+i;        g->alist[i]->size = 0;        g->alist[i]->capacity = 1;        g->alist[i]->is_sorted= 1;    }        return g;}/* free all space used by graph */void graph_destroy(Graph g){    int i;    for(i = 0; i < g->vexnum; i++){        free(g->alist[i]);    }    free(g);}//找到vex在g->alist数组中的位置int findVex(Graph g,char vex){    for(int i=0;i
         
          vexnum;i++){        if(g->alist[i]->vexname==vex)            return i;    }    return -1;}/* 为graph添加边,这里是单向边，仅
          
            */void graph_add_edge(Graph g, char u, char v,unsigned int wt){ int s=findVex(g,u); int t=findVex(g,v); assert(s >= 0); assert(s < g->vexnum); assert(t >= 0); assert(t < g->vexnum); /* do we need to grow the list? */ while(g->alist[s]->size >= g->alist[s]->capacity) { g->alist[s]->capacity *= 2;//容量两倍增加的方式 g->alist[s] =(graph::successors*)realloc(g->alist[s], sizeof(graph::successors) + sizeof(graph::successors::outvexs) * (g->alist[s]->capacity - 1)); } /* now add the new sink */ g->alist[s]->list[g->alist[s]->size].vex = v; g->alist[s]->list[g->alist[s]->size++].weight = wt; g->alist[s]->is_sorted = 0; /* bump edge count */ g->edgenum++;}/* return the number of vertices in the graph */int graph_vertex_count(Graph g){ return g->vexnum;}/* return the number of vertices in the graph */int graph_edge_count(Graph g){ return g->edgenum;}/* return the out-degree of a vertex */int graph_out_degree(Graph g, char vex){ int source = findVex(g,vex); assert(source >= 0); assert(source < g->vexnum); return g->alist[source]->size;}/* when we are willing to call bsearch，二分查找 */#define BSEARCH_THRESHOLD (10)static int intcmp(const void *a, const void *b){ return (*(const graph::successors::outvexs *)a).vex - (*(const graph::successors::outvexs*)b).vex;}/* return 1 if edge (source, sink) exists), 0 otherwise */int graph_has_edge(Graph g, char svex, char tvex){ int source=findVex(g,svex);; int sink=findVex(g,tvex); assert(source >= 0); assert(source < g->vexnum); assert(sink >= 0); assert(sink < g->vexnum); //如果该顶点出度数超过10，才使用二分查找 if(graph_out_degree(g, svex) >= BSEARCH_THRESHOLD) { if(! g->alist[source]->is_sorted) { qsort(g->alist[source]->list, g->alist[source]->size, sizeof(graph::successors::outvexs), intcmp); } /* call bsearch to do binary search for us */ graph::successors::outvexs *list=(graph::successors::outvexs *) bsearch(&tvex, g->alist[source]->list, g->alist[source]->size, sizeof(graph::successors::outvexs), intcmp); if(list) return 1; else return 0; } else { /* just do a simple linear search */ /* we could call lfind for this, but why bother? */ for(int i = 0; i < g->alist[source]->size; i++) { if(g->alist[source]->list[i].vex == tvex) return 1; } /* else */ return 0; }}/* invoke f on all edges (u,v) with source u *//* supplying data as final parameter to f *///这里注意回调函数的使用voidgraph_foreach(Graph g, char svex, void (*f)(Graph g, char svex, char tvex, void *data), void *data){ int i; int source=findVex(g,svex); assert(source >= 0); assert(source < g->vexnum); for(i = 0; i < g->alist[source]->size; i++) { f(g, svex, g->alist[source]->list[i].vex, data); }}#define TEST_SIZE (6)//static使得本函数本文件可见 static voidmatch_sink(Graph g, char svex, char tvex, void *data){ assert(data && tvex == (*(graph::successors::outvexs *) data).vex);} //这个函数有什么用?static int node2dot(Graph g){ assert(g != NULL); return 0;}static void print_edge2dot(Graph g,char source, char sink, void *data){ int svex_pos=findVex(g,source); int tvex_pos; for(int i=0;i
           
            alist[svex_pos]->size;i++) if(sink == g->alist[svex_pos]->list[i].vex){ tvex_pos=i; break; } fprintf(stdout,"<%c->%c>:weight:%d\n",source,sink,g->alist[svex_pos]->list[tvex_pos].weight);}//打印所有的边static int edge2dot(Graph g){ assert(g != NULL); int idx = 0; int node_cnt = graph_vertex_count(g); for(idx = 0;idx
            
             alist[idx]->vexname,print_edge2dot,NULL); } printf("\n"); return 0;}int graph2dot(Graph g){ fprintf(stdout,"digraph{ "); node2dot(g); edge2dot(g); fprintf(stdout,"}n"); return 0;}//最小生成树之Prim，Kruscal算法//松弛操作struct EdgeType{ char s,t; unsigned int cost;};void relaxation(Graph g,EdgeType *dist,char vex,bool* visited){ int svex_pos=findVex(g,vex); assert(svex_pos!=-1); for(int j=0;j
             
              alist[svex_pos]->size;j++){ int tvex_pos = findVex(g,g->alist[svex_pos]->list[j].vex); assert(tvex_pos!=-1); if(visited[tvex_pos]==false && g->alist[svex_pos]->list[j].weight
              
               alist[svex_pos]->list[j].weight; dist[tvex_pos].s=vex; dist[tvex_pos].t=g->alist[svex_pos]->list[j].vex; } }}const unsigned int INFINITY = -1;int findMin(EdgeType *dist,bool* visited,int num){ unsigned int min=INFINITY; int pos=-1; for(int i=0;i
               
                dist[i].cost){ min=dist[i].cost; pos=i; } return pos;}//MST之Prim算法void MST_Prim(Graph g,char beg_vex){ EdgeType *dist = (EdgeType*)malloc(sizeof(EdgeType)*g->vexnum);//存放MST的边,MST边 = vexnum-1// memset(dist,0xFF,sizeof(int)*g->vexnum); bool *visited=(bool*)malloc(sizeof(bool)*g->vexnum);//是否已添加 memset(visited,0,sizeof(bool)*g->vexnum);// char *prim_vex=(char*)malloc(g->vexnum+1);//prim_vex数组保存添加的结点 int vexs=0;//记录已加入点的数目// prim_vex[vexs++]=beg_vex; int i=findVex(g,beg_vex); assert(i!=-1); visited[i]=true; vexs++; relaxation(g,dist,beg_vex,visited); while(vexs
                
                 vexnum){ int i=findMin(dist,visited,g->vexnum); assert(i!=-1); visited[i]=true; vexs++; printf("<%c,%c>:%d\n",dist[i].s,dist[i].t,dist[i].cost); relaxation(g,dist,g->alist[i]->vexname,visited); } free(dist); free(visited);}int cmp(const void* a,const void *b){ return (*(EdgeType *)a).cost - (*(EdgeType *)b).cost;}//寻找vex所在树的根结点int findRoot(Graph g,int *root,char vex){ int t=findVex(g,vex); while(root[t]>=0) t=root[t]; return t;}void MST_Kruscal(Graph g){ int k=0; EdgeType *edges = new EdgeType[g->edgenum]; for(int i=0;i
                 
                  vexnum;i++){ for(int j=0;j
                  
                   alist[i]->size;j++){ //有向，因此不考虑
                   
                    和
                    
                     的问题 edges[k].s=g->alist[i]->vexname; edges[k].t=g->alist[i]->list[j].vex; edges[k++].cost=g->alist[i]->list[j].weight; } } //所有边按从小到大排序 qsort(edges,g->edgenum,sizeof(EdgeType),cmp); //root[i]表示顶点i所在的树的根结点 int *root=(int*)malloc(sizeof(int)*g->vexnum);//初始所有点属于不同的连通分量 for(int i=0;i
                     
                      vexnum;i++)//初始化 root[i]=-1; int j=0,i=0; //j表示查找第几条边，i表示顶点 while(j
                      
                       edgenum && i
                       
                        vexnum-1){ //MST边数为顶点数-1 int svex=findRoot(g,root,edges[j].s); int tvex=findRoot(g,root,edges[j].t); if(svex != tvex){ //如果两顶点属于不同的连通分量 root[tvex]=svex; i++; printf("<%c,%c> ",edges[j].s,edges[j].t); } j++; } free(root); delete[] edges; printf("\n");}void relaxation_Dijkstra(Graph g,unsigned int *dist,char** path,char svex,char tvex){ int i=findVex(g,svex); int j=findVex(g,tvex); assert(j!=-1 && i!=-1); for(int k=0;k
                        
                         alist[j]->size;k++){ char tvex_pos=findVex(g,g->alist[j]->list[k].vex); assert(tvex_pos!=-1); if((g->alist[j]->list[k].weight+dist[j])< dist[tvex_pos]){ dist[tvex_pos]=dist[tvex_pos]+g->alist[j]->list[k].weight; int w; for(w=0;path[tvex_pos][w]!=-1;w++)//更新路径 path[tvex_pos][w]=path[j][w]; path[tvex_pos][w]=g->alist[j]->list[k].vex; } }}//sp[vexnum]标记源点到该点是否已是最短路径int findMin_Dijkstra(unsigned int dist[],int length,bool sp[]){ unsigned int min=INFINITY; int pos=-1; for(int i=0;i
                         
                          vexnum); for(int i=0;i
                          
                           vexnum;i++){ sp_path[i]=(char*)malloc(sizeof(char)*g->vexnum); memset(sp_path[i],-1,g->vexnum); } //起始点到其他顶点的距离 unsigned int *sp_dist=(unsigned int*)malloc(sizeof(unsigned int)*g->vexnum); memset(sp_dist,0xFF,sizeof(unsigned int)*g->vexnum); bool *sp_visited=(bool*)malloc(sizeof(bool)*g->vexnum);//标记是否已是最短 memset(sp_visited,0,sizeof(bool)*g->vexnum); int j=findVex(g,source_vex); assert(j!=-1); sp_dist[j]=0; sp_visited[j]=true; relaxation_Dijkstra(g,sp_dist,sp_path,source_vex,source_vex); int rounds=1; while(rounds
                           
                            vexnum){ j=findMin_Dijkstra(sp_dist,g->vexnum,sp_visited); assert(j!=-1); sp_visited[j]=true; rounds++; relaxation_Dijkstra(g,sp_dist,sp_path,source_vex,g->alist[j]->vexname); } for(int i=0;i
                            
                             vexnum;i++){ printf("Shortest Path from %c to %c :%c",source_vex,g->alist[i]->vexname,source_vex); for(j=0;sp_path[i][j]!=-1;j++) printf("%c",sp_path[i][j]); printf("\n",g->alist[i]->vexname); } for(int i=0;i
                             
                              vexnum;i++) free(sp_path[i]); free(sp_path); free(sp_dist); free(sp_visited);}//若P[v][w][u]为TRUE，则u 是从v 到w 当前求得的最短路径上的顶点const int MAX = 10;bool P[MAX][MAX][MAX];unsigned int D[MAX][MAX]; void ShortestPath_Flyod(Graph g){ /* 使用一个n*n的方阵D，D[s][t]表示
                              
                               的最短路径 * 但是为了D[s][t]，需要更新n次D矩阵 * D(k)[s][t]表示经过k次更新后，当前
                               
                                的最短路径，可能最终不是 * D(-1)[s][t]=edges[s][t] * D(k)[s][t]=min{ D(k-1)[s][t],D(k-1)[s][k]+D(k-1)[k][t] } * D(k)的计算是尝试把顶点k加到每对顶点
                                
                                 之间 */ memset(D,0xFF,sizeof(unsigned int)*MAX*MAX); for(int i=0;i
                                 
                                  vexnum;++i){ //初始化D矩阵 for(int t=0;t
                                  
                                   alist[i]->size;++t){ int tvex_pos=findVex(g,g->alist[i]->list[t].vex); assert(tvex_pos!=-1); D[i][tvex_pos]=g->alist[i]->list[t].weight; //D(-1) for(int u=0;u
                                   
                                    vexnum;++u) P[i][tvex_pos][u]=false; if (D[i][tvex_pos]
                                    
                                     vexnum; ++k){ //计算D(k),总共n次，这个循环一定要在最外层 for(int s=0; s
                                     
                                      vexnum; ++s){ //D(k)[s] for(int t=0;t
                                      
                                       alist[s]->size;++t){ //D(k)[s][t] int tvex_pos=findVex(g,g->alist[s]->list[t].vex); assert(tvex_pos!=-1); if(D[s][k]
                                       
                                        最短路径上 D[s][tvex_pos]=D[s][k]+D[k][tvex_pos]; //更新P[s][t]，当前P[s][t]最短路径上有哪些顶点 for(int i=0;i
                                        
                                         vexnum;++i) P[s][tvex_pos][i]=P[s][k][i] || P[k][tvex_pos][i]; } } } } //输入每对顶点的最短路径上的顶点 for(int s=0;s
                                         
                                          vexnum;s++) for(int t=0;t
                                          
                                           alist[s]->size;++t){ printf("The Shortest Path Vertexes of <%c,%c> are:\n",g->alist[s]->vexname,g->alist[s]->list[t].vex); int tvex_pos=findVex(g,g->alist[s]->list[t].vex); assert(tvex_pos!=-1); for(int i=0;i
                                           
                                            vexnum;i++) if(P[s][tvex_pos][i]) printf("%c",g->alist[i]->vexname); printf("\n"); } }int _tmain(int argc, _TCHAR* argv[]){ Graph g; int i; int j; g = graph_create(TEST_SIZE); assert(graph_vertex_count(g) == TEST_SIZE); /* check it's empty */ for(i = 0; i < TEST_SIZE; i++) { for(j = 0; j < TEST_SIZE; j++) { assert(graph_has_edge(g, g->alist[i]->vexname, g->alist[j]->vexname) == 0); } } /* check it's empty again */ for(i = 0; i < TEST_SIZE; i++) { assert(graph_out_degree(g, g->alist[i]->vexname) == 0); graph_foreach(g, g->alist[i]->vexname, match_sink, 0); } /* check edge count */ assert(graph_edge_count(g) == 0); //添加边
                                            
                                             ，if u
                                             
                                              alist[i]->vexname, g->alist[j]->vexname,weight); } } for(i = 0; i < TEST_SIZE; i++) { for(j = 0; j < TEST_SIZE; j++) { assert(graph_has_edge(g, i+'A', j+'A') == (i < j)); } } assert(graph_edge_count(g) == (TEST_SIZE*(TEST_SIZE-1)/2)); //打印图 graph2dot(g); MST_Prim(g,'A'); MST_Kruscal(g); ShortestPath_Dijkstra(g,'A'); ShortestPath_Flyod(g); /* free it * */ graph_destroy(g); return 0;}