1 /* 2 编写程序输出以邻接表为存储结构的无向图的各顶点的度。 3 */ 4 /**********************************/ 5 /*文件名称：lab8_01.c                 */ 6 /**********************************/ 7 #include "ljb.h" 8 /* 输出以邻接表为存储结构的无向图g的各顶点的度 */ 9 void degree(LinkedGraph g)10 {11     EdgeNode *p;12     int i;13     for (i=0; i<g.n; i++)14     {15         printf("%c‘s degree is ",g.adjlist[i].vertex);16         p=g.adjlist[i].FirstEdge;17         int cnt = 0;18         while (p)19         {20             cnt++;21             //printf("-->%d",p->adjvex);22             p=p->next;23         }24         printf("%d\n",cnt);25     }26 27 }28 29 30 int main()31 {32     LinkedGraph g;33     creat(&g,"g11.txt",0);      /*已知g11.txt中存储了图的信息*/34     printf("\n The graph is:\n");35     print(g);36     degree(g);37     return 0;38 }

 1 /* 2 图采用邻接表存储结构，编程对图进行广度优先遍历。 3 */ 4 /**********************************/ 5 /*文件名称：lab8_02.c                 */ 6 /**********************************/ 7 #include "ljb.h" 8 #include <queue> 9 10 using namespace std;11 12 13 int visited[M];                  /*全局标志向量*/14 /*请将本函数补充完整，并进行测试*/15 void bfs(LinkedGraph g, int i)16 {17     visited[i] = true;18     printf("%d ",i);19     EdgeNode *p;20     p=g.adjlist[i].FirstEdge;21     /*从顶点i出发广度优先变量图g的连通分量*/22     queue<int> Q;23     while (p)24     {25         if(!visited[i])26         {27             printf("%d",i);28             Q.push(i);29         }30         p=p->next;31     }32     while(!Q.empty()) {33         int u = Q.front();34         Q.pop();35         bfs(g,u);36     }37 38 }39 40 41 /*函数功能：广度优先遍历图g42   函数参数：邻接表g43 */44 int BfsTraverse(LinkedGraph g)45 {46     int i,count=0;47     for (i=0; i<g.n; i++)48         visited[i]=0;     /*初始化标志数组*/49 50     for (i=0; i<g.n; i++)51         if (!visited[i])  /*vi未访问过*/52         {53             printf("\n");54             count++;            /*连通分量个数加1*/55             bfs(g,i);56         }57     return count;58 }59 60 int main()61 {62     LinkedGraph g;63     int count;64     creat(&g,"g11.txt",0);          /*创建图的邻接表*/65     printf("\n The graph is:\n");66     print(g);67     printf("广度优先遍历序列为：\n");68     count=BfsTraverse(g);         /*从顶点0出发广度优先遍历图g*/69     //printf("\n该图共有%d个连通分量。\n",count);70     return 0;71 }

 1 /* 2     图采用邻接表存储结构，编程对图进行深度优先遍历。 3 */ 4  5 #include "ljb.h" 6 int visited[M]; 7 /*请将本函数补充完整，并进行测试*/ 8  9 void dfs(LinkedGraph g,int i)10 {11     /*从顶点i开始深度优先遍历图的连通分量*/12     EdgeNode *p;13     printf("visit vertex: %c \n",g.adjlist[i].vertex);/*访问顶点i*/14     visited[i]=1;15     p=g.adjlist[i].FirstEdge;16     while (p)                 /*从p的邻接点出发进行深度优先搜索*/17     {18         if(!visited[p->adjvex]) {19            // printf("%d\n",p->adjvex);20             dfs(g,p->adjvex);21         }22         else p = p->next;23     }24 }25 /*函数功能：深度优先遍历图26   函数参数：图的邻接表g27 */28 void DfsTraverse(LinkedGraph g)29 {30     int i;31     for (i=0; i<g.n; i++)32         visited[i]=0;     /*初始化标志数组*/33     for (i=0; i<g.n; i++)34         if (!visited[i])  /*vi未访问过*/35             dfs(g,i);36 }37 38 int main()39 {40     LinkedGraph g;41     creat(&g,"g11.txt",0);              /*创建图的邻接表*/42     printf("\n The graph is:\n");43     print(g);44     printf("深度优先遍历序列为：\n");45     DfsTraverse(g);                    /*从顶点0开始深度优先遍历图无向图g*/46 }

 1 /*********************************************/ 2 /*           Prim求解最小生成树算法          */ 3 /*********************************************/ 4 #include "ljjz.h" 5  6 typedef struct edgedata  /*用于保存最小生成树的边类型定义*/ 7 { 8     int beg,en;     /*beg,en是边顶点序号*/ 9     int length;     /*边长*/10 } edge;11 12 /*函数功能：prim算法构造最小生成树13 函数参数：图的邻接矩阵g;边向量edge14 */15 void prim(Mgraph g, edge tree[M-1])16 {17     edge x;18     int d,min,j,k,s,v;19 20     /* 建立初始入选点，并初始化生成树边集tree*/21     int i;22     int dis[M];23     int vis[M];24     int pre[M];25     for(i=0; i<g.n; i++)26     {27         pre[i] = 0;28         vis[i] = 0;29         dis[i] = FINITY;30         tree[i].length = FINITY;31         tree[i].beg = tree[i].en = -1;32     }33 34     int ans = 0;35     dis[0] = 0;36 37     for(i=0; i<g.n; i++)38     {39         /*依次求当前(第k条）最小两栖边，并加入TE*/40         int tmp = FINITY,k=-1;41         for(j=0; j<g.n; j++)42         {43             if(!vis[j]&&dis[j]<tmp)44             {45                 tmp = dis[j];46                 k = j;47             }48         }49         if(tmp!=0) {50             tree[i-1].length = tmp;51             tree[i-1].beg = pre[k];52             tree[i-1].en = k;53         }54 55         vis[k] = 1;56         ans +=tmp;57         /*由于新顶点v的加入，修改两栖边的基本信息*/58         for(s=0; s<g.n; s++) {59             if(!vis[s]&&dis[s]>g.edges[k][s]) {60                 dis[s] = g.edges[k][s];61                 pre[s] = k;62             }63         }64     }65 66     /*输出最小生成树*/67     printf("\n最小生成树是:\n");/*输出最小生成树*/68     for (j=0; j<=g.n-2; j++)69         printf("\n%c---%c  %d\n",g.vexs[tree[j].beg],g.vexs[tree[j].en],tree[j].length);    //顶点信息70     printf("\n最小生成树的根是： %c\n", g.vexs[0]);71     printf("%d\n",ans);72 }73 74 int  main()75 {76     Mgraph g;77     edge  tree[M-1];  /*用于存放最小生成树的M-1条边*/78     creat(&g,"g.txt",0);  /*创建无向图的邻接矩阵*/79 80     print(g);81     prim(g,tree);        /*求解图的最小生成树*/82     return 0;83 84 }

 1 /***************************************************/ 2 /*          Dijkstra单源最短路径算法               */ 3 /***************************************************/ 4 #include "ljjz.h"   /*引入邻接矩阵创建程序*/ 5 #include "cstring" 6 #include "algorithm" 7  8 using namespace std; 9 10 typedef enum {FALSE,TRUE} boolean; /*false为0,true为1*/11 typedef int dist[M];  /* 距离向量类型*/12 typedef int path[M];  /* 路径类型*/13 14 /*函数功能：Dijkstra算法求解单源最短路径15 函数参数：图的邻接矩阵g;源点v0;路径向量p；距离向量d16 */17 void dijkstra(Mgraph g,int v0,path p,dist d)18 {19     //boolean final[M]; /*表示当前元素是否已求出最短路径*/20     //int i,k,j,v,min,x;21     bool final[M];22     memset(final,0,sizeof(final));23 24     /*  第1步  初始化集合S与距离向量d */25     for(int i=0; i<g.n; i++)26     {27         p[i] = v0;28         d[i] = g.edges[v0][i];29     }30 31     final[v0] = true;32     p[v0] = -1;33 34     for(int i=0; i<g.n-1; i++)35     {36         /* 第2步  依次找出n-1个结点加入S中   */37         int tmp = FINITY,k = v0;38         for(int j=0; j<g.n; j++)39         {40             if(final[j]) continue;41             if(tmp>d[j])42             {43                 tmp = d[j];44                 k = j;45             }46         }47         /*第3步 修改S与V-S中各结点的距离*/48         final[k] = true;49         for(int j=0; j<g.n; j++)50         {51             if(final[j]) continue;52             if(d[j]>d[k]+g.edges[k][j]&&g.edges[k][j]<FINITY)53             {54                 d[j] = d[k]+g.edges[k][j];55                 p[j] = k;56             }57         }58     }59 }60 /*函数功能：输出有向图的最短路径61 函数参数：邻接矩阵g；路径向量p；距离向量d62 */63 void print_gpd(Mgraph g,path p,dist d)64 {65     int st[M],i,pre,top=-1;66     for (i=0; i<g.n; i++)67     {68         printf("\nDistancd: %7d , path:",d[i]);69         st[++top]=i;70         pre=p[i];71         while (pre!=-1)   /*从第i个顶点开始向前搜索最短路径上的顶点*/72         {73             st[++top]=pre;74             pre=p[pre];75         }76         while (top>0)77             printf("%2d",st[top--]);78     }79 }80 /*---------- 主程序 ------------*/81 int main()82 {83     Mgraph g;   /* 有向图 */84     path p;     /* 路径向量 */85     dist d;     /* 最短路径向量 */86     int v0;87     creat(&g,"g21.txt",1); /*假设图8.21所示的有向网G21的输入文件为g21.txt */88     print(g);        /*输出图的邻接矩阵*/89     printf("\n");90     printf("请输入源点编号：");91     scanf("%d",&v0);       /*输入源点*/92     dijkstra(g,v0,p,d);   /*求v0到其他各点的最短距离*/93     /*输出V0到其它各点的路径信息及距离*/94     print_gpd(g,p,d);95 96     return 0;97 }

  1 /***************************************/  2 /*             拓扑排序算法            */  3 /***************************************/  4 #include<stdlib.h>  5 #include<stdio.h>  6 #define M 20  7 typedef char vertextype;  8 typedef struct node       /*边结点类型定义*/  9 { 10     int adjvex; 11     struct node *next; 12 } edgenode; 13 typedef struct de         /*带顶点入度的头结点定义*/ 14 { 15     edgenode* FirstEdge; 16     vertextype vertex; 17     int id;                /*顶点的入度域*/ 18 } vertexnode; 19  20 typedef struct            /*AOV网络的邻接表结构*/ 21 { 22     vertexnode adjlist[M]; 23     int n,e; 24 } AovGraph; 25  26 void  creat(AovGraph *g,char *filename)       /*建立AOV网络的存储结构*/ 27 { 28     int i,j,k; 29     edgenode  *s; 30     FILE *fp; 31     fp=fopen(filename,"r"); 32     if (fp) 33     { 34         fscanf(fp,"%d%d",&g->n,&g->e);  /*输入图中的顶点数与边数*/ 35  36         for(i=0; i<g->n; i++)                      /*输入顶点值*/ 37         { 38             fscanf(fp,"%1s",&g->adjlist[i].vertex); 39             g->adjlist[i].FirstEdge=NULL; 40             g->adjlist[i].id=0;       /*入度初始化为0*/ 41         } 42         for(k=0; k<g->e; k++) 43         { 44             fscanf(fp,"%d%d",&i,&j); 45             s=(edgenode*)malloc(sizeof(edgenode)); 46             s->adjvex=j; 47             g->adjlist[j].id++;    /*顶点j的入度加1*/ 48             s->next=g->adjlist[i].FirstEdge; 49             g->adjlist[i].FirstEdge=s; 50         } 51     } 52 } 53  54 void print(AovGraph g) 55 { 56     edgenode *p; 57     int i; 58     for (i=0; i<g.n; i++) 59     { 60         printf("%c %d   ", g.adjlist[i].vertex,g.adjlist[i].id); 61         p=g.adjlist[i].FirstEdge; 62         while (p) 63         { 64             printf("%d-->",p->adjvex); 65             p=p->next; 66         } 67         printf("\n"); 68     } 69 } 70 /*函数功能：拓扑排序 71 函数参数：AOV网邻接表存储结构变量g 72 函数返回值：拓扑排序输出的顶点个数 73 */ 74 int TopSort(AovGraph g) 75 { 76     int k=0,i,j,v, flag[M]; 77     int queue[M];  /*队列*/ 78     int h=0,t=0; 79     edgenode* p; 80     for (i=0; i<g.n; i++)  flag[i]=0; /*访问标记初始化*/ 81     /*先将所有入度为0的结点进队*/ 82     /*将程序补充完整*/ 83  84     for(int i=0; i<g.n; i++) 85     { 86         for(int j=0; j<g.n; j++) 87         { 88             if(g.adjlist[j].id==0) 89             { 90                 printf("%d ",j); 91                 g.adjlist[j].id = -1; 92                 p=g.adjlist[i].FirstEdge; 93                 while (p) 94                 { 95                     g.adjlist[p->adjvex].id--; 96                     //printf("%d-->",p->adjvex); 97                     p=p->next; 98                 } 99                 break;100             }101         }102     }103 104     return k;  //返回输出的顶点个数105 }106 int main()107 {108     int k=0;109     AovGraph g;110     creat(&g,"aov.txt");    /*假设图8.25所示的AOV网输入文件为aov.txt*/111     printf("\n图8.27所示AOV网的邻接表是：\n");112     print(g);113     k=TopSort(g);114     if(k<g.n) printf("\n该图存在环！\n");115     return 0;116 }