图
Question one
/*
编写程序输出以邻接表为存储结构的无向图的各顶点的度。
*/
/**********************************/
/*文件名称：lab8_01.c */
/**********************************/
#include "ljb.h"
/* 输出以邻接表为存储结构的无向图g的各顶点的度 */
void degree(LinkedGraph g)
{
EdgeNode *p;
int count;//用来保存各个节点的度
int i;
for(i = 0; i < g.n; i ++)
{
count = 0;
p = g.adjlist[i].FirstEdge;//将p放在村储存与该点相邻的点的单链表的头结点上
while(p)
{
count++;
p = p->next;//不断的遍历该链表，来获得其相连的所有的点
}
printf("D(%d) = %d\n",i, count);//输出该点的度即可
}
}
int main()
{ LinkedGraph g;
creat(&g,"g11.txt",0); /*已知g11.txt中存储了图的信息*/
printf("\n The graph is:\n");
print(g);
degree(g);
return 0;
}
Question two
/*
图采用邻接表存储结构，编程对图进行广度优先遍历。
*/
/**********************************/
/*文件名称：lab8_02.c */
/**********************************/
#include "ljb.h"
int visited[M]; /*全局标志向量*/
/*请将本函数补充完整，并进行测试*/
void bfs(LinkedGraph g, int i)
{ /*从顶点i出发广度优先变量图g的连通分量*/
int queue[M], v;
int head = 0, end = 0;//BFS的可以通过数据结构来实现
EdgeNode *p;
queue[end++] = i;//将目前的第一个节点导入的队列
visited[i] = 1;//表示这个的节点已经被看过了
while(head < end)//设置结束条件
{
v = queue[head++];//目前导入当前的结果
printf("%c ",g.adjlist[v].vertex);//输出当前的节点
p = g.adjlist[v].FirstEdge;//p为的指向的周围的节点
while(p)
{
if(visited[p->adjvex] == 0)//如果这个节点没有被探查，就把这个节点加入队列
{
queue[end++] = p->adjvex;
visited[p->adjvex] = 1;
}
p = p->next;//遍历到结果的下一个的
}
}
}
/*函数功能：广度优先遍历图g
函数参数：邻接表g
*/
int BfsTraverse(LinkedGraph g)
{ int i,count=0;
for (i=0;i<g.n;i++)
visited[i]=0; /*初始化标志数组*/
for (i=0;i<g.n;i++)
if (!visited[i]) /*vi未访问过*/
{printf("\n");
count++; /*连通分量个数加1*/
bfs(g,i);
}
return count;
}
int main()
{ LinkedGraph g;
int count;
creat(&g,"g11.txt",0); /*创建图的邻接表*/
printf("\n The graph is:\n");
print(g);
printf("广度优先遍历序列为：\n");
count=BfsTraverse(g); /*从顶点0出发广度优先遍历图g*/
printf("\n该图共有%d个连通分量。\n",count);
return 0;
}
Question three
/*
图采用邻接表存储结构，编程对图进行深度优先遍历。
*/
#include "ljb.h"
int visited[M];
/*请将本函数补充完整，并进行测试*/
void dfs(LinkedGraph g,int i)
{ /*从顶点i开始深度优先遍历图的连通分量*/
EdgeNode *p;
printf("visit vertex: %c \n",g.adjlist[i].vertex);/*访问顶点i*/
visited[i]=1;
p=g.adjlist[i].FirstEdge;
while (p) /*从p的邻接点出发进行深度优先搜索*/
{
if(visited[p->adjvex] == 0)
dfs(g, p->adjvex);
p = p->next;
}
}
/*函数功能：深度优先遍历图
函数参数：图的邻接表g
*/
void DfsTraverse(LinkedGraph g)
{ int i;
for (i=0;i<g.n;i++)
visited[i]=0; /*初始化标志数组*/
for (i=0;i<g.n;i++)
if (!visited[i]) /*vi未访问过*/
dfs(g,i);
}
int main()
{ LinkedGraph g;
creat(&g,"g11.txt",0); /*创建图的邻接表*/
printf("\n The graph is:\n");
print(g);
printf("深度优先遍历序列为：\n");
DfsTraverse(g); /*从顶点0开始深度优先遍历图无向图g*/
}
Question four
/*********************************************/
/* Prim求解最小生成树算法 */
/*********************************************/
#include "ljjz.h"
typedef struct edgedata /*用于保存最小生成树的边类型定义*/
{ int beg,en; /*beg,en是边顶点序号*/
int length; /*边长*/
}edge;
/*函数功能：prim算法构造最小生成树
函数参数：图的邻接矩阵g;边向量edge
*/
void prim(Mgraph g, edge tree[M-1])
{ edge x;
int d,min,j,k,s,v;
/* 建立初始入选点，并初始化生成树边集tree*/
for (v=1;v<=g.n-1;v++)//将所有边分成两类，一类是已经被加入的，另一种是还未被加入的
{
tree[v-1].beg=0;
tree[v-1].en=v;
tree[v-1].length=g.edges[0][v];
}
/*依次求当前(第k条）最小两栖边，并加入TE*/
for (k=0;k<=g.n-3;k++)
{
min=tree[k].length;
s=k;
for (j=k+1;j<=g.n-2;j++)
if (tree[j].length<min)//如果找到了的比当前的值还要小的就直接更新
{
min=tree[j].length;
s=j;
}
v=tree[s].en;
x=tree[s];
tree[s]=tree[k];
/*由于新顶点v的加入，修改两栖边的基本信息*/
for (j=k+1;j<=g.n-2;j++)
{
d=g.edges[v][tree[j].en];
if (d<tree[j].length)
{
tree[j].length=d;
tree[j].beg=v;
}
}
}
/*输出最小生成树*/
printf("\n最小生成树是:\n");/*输出最小生成树*/
for (j=0;j<=g.n-2;j++)
printf("\n%c---%c %d\n",g.vexs[tree[j].beg],g.vexs[tree[j].en],tree[j].length);
printf("\n最小生成树的根是： %c\n", g.vexs[0]);
}
int main()
{
Mgraph g;
edge tree[M-1]; /*用于存放最小生成树的M-1条边*/
creat(&g,"g.txt",0); /*创建无向图的邻接矩阵*/
print(g);
prim(g,tree); /*求解图的最小生成树*/
return 0;
}
Question five
/***************************************************/
/* Dijkstra单源最短路径算法 */
/***************************************************/
#include "ljjz.h" /*引入邻接矩阵创建程序*/
typedef enum{FALSE,TRUE} boolean;/*false为0,true为1*/
typedef int dist[M]; /* 距离向量类型*/
typedef int path[M]; /* 路径类型*/
/*函数功能：Dijkstra算法求解单源最短路径
函数参数：图的邻接矩阵g;源点v0;路径向量p；距离向量d
*/
void dijkstra(Mgraph g,int v0,path p,dist d)
{ boolean final[M]; /*表示当前元素是否已求出最短路径*/
int i,k,j,v,min,x;
/* 第1步 初始化集合S与距离向量d */
for (v=0;v<g.n;v++)//初始化与这个顶点有关的所有的边的距离
{
final[v]=FALSE;
d[v]=g.edges[v0][v];
if (d[v]<FINITY &&d[v]!=0)
p[v]=v0; else p[v]=-1;//表示目前的边没有达到
}
final[v0]=TRUE;
d[v0]=0;//将自己自身边权设置为0
/* 第2步 依次找出n-1个结点加入S中 */
for (i=1;i<g.n;i++)
{
min=FINITY;
for (k=0;k<g.n;k++)
if (!final[k] && d[k]<min)//如果找到了周围的边就更新了
{
v=k;
min=d[k];
}
if (min==FINITY) return ;
final[v]=TRUE;
/*第3步 修改S与V-S中各结点的距离*/
for (k=0;k<g.n;++k)
if (!final[k] && (min+g.edges[v][k]<d[k]))
{
d[k]=min+g.edges[v][k];
p[k]=v;
}
}
}
/*函数功能：输出有向图的最短路径
函数参数：邻接矩阵g；路径向量p；距离向量d
*/
void print_gpd(Mgraph g,path p,dist d)
{
int st[M],i,pre,top=-1;
for (i=0;i<g.n;i++)
{ printf("\nDistancd: %7d , path:" ,d[i]);
st[++top]=i;
pre=p[i];
while (pre!=-1) /*从第i个顶点开始向前搜索最短路径上的顶点*/
{ st[++top]=pre;
pre=p[pre];
}
while (top>0)
printf("%2d",st[top--]);
}
}
/*---------- 主程序 ------------*/
int main()
{ Mgraph g; /* 有向图 */
path p; /* 路径向量 */
dist d; /* 最短路径向量 */
int v0;
creat(&g,"g21.txt",1); /*假设图8.21所示的有向网G21的输入文件为g21.txt */
print(g); /*输出图的邻接矩阵*/
printf("\n");
printf("请输入源点编号：");
scanf("%d",&v0); /*输入源点*/
dijkstra(g,v0,p,d); /*求v0到其他各点的最短距离*/
/*输出V0到其它各点的路径信息及距离*/
print_gpd(g,p,d);
return 0;
}
Question six
/***************************************/
/* 拓扑排序算法 */
/***************************************/
#include<stdlib.h>
#include<stdio.h>
#define M 20
typedef char vertextype;
typedef struct node{ /*边结点类型定义*/
int adjvex;
struct node *next;
}edgenode;
typedef struct de /*带顶点入度的头结点定义*/
{
edgenode* FirstEdge;
vertextype vertex;
int id; /*顶点的入度域*/
}vertexnode;
typedef struct{ /*AOV网络的邻接表结构*/
vertexnode adjlist[M];
int n,e;
}AovGraph;
void creat(AovGraph *g,char *filename) /*建立AOV网络的存储结构*/
{ int i,j,k;
edgenode *s;
FILE *fp;
fp=fopen(filename,"r");
if (fp)
{
fscanf(fp,"%d%d",&g->n,&g->e); /*输入图中的顶点数与边数*/
for(i=0;i<g->n;i++) /*输入顶点值*/
{fscanf(fp,"%1s",&g->adjlist[i].vertex);
g->adjlist[i].FirstEdge=NULL;
g->adjlist[i].id=0; /*入度初始化为0*/
}
for(k=0;k<g->e;k++)
{ fscanf(fp,"%d%d",&i,&j);
s=(edgenode*)malloc(sizeof(edgenode));
s->adjvex=j;
g->adjlist[j].id++; /*顶点j的入度加1*/
s->next=g->adjlist[i].FirstEdge;
g->adjlist[i].FirstEdge=s;
}
}
}
void print(AovGraph g)
{ edgenode *p;
int i;
for (i=0;i<g.n;i++)
{ printf("%c %d ", g.adjlist[i].vertex,g.adjlist[i].id);
p=g.adjlist[i].FirstEdge;
while (p)
{ printf("%d-->",p->adjvex);
p=p->next;
}
printf("\n");
}
}
/*函数功能：拓扑排序
函数参数：AOV网邻接表存储结构变量g
函数返回值：拓扑排序输出的顶点个数
*/
int TopSort(AovGraph g)
{int k=0,i,j,v, flag[M];
int queue[M]; /*队列*/
int h=0,t=0;
edgenode* p;
for (i=0;i<g.n;i++) flag[i]=0; /*访问标记初始化*/
/*先将所有入度为0的结点进队*/
/*将程序补充完整*/
for (i=0;i<g.n;i++)
if (g.adjlist[i].id==0)//如果这个节点没有前驱节点，那么就将这个节点入对
{
queue[t++]=i;
flag[i]=1;//并且将标记更新为1
}
while (h<t)//设置边界条件
{
v=queue[h++];//取出队列的头结点
printf("%c ",g.adjlist[v].vertex);//输出该节点的值
k++;//记录输出的顶点的个数
p=g.adjlist[v].FirstEdge;
while (p)
{
j=p->adjvex;
g.adjlist[j].id--;//指的是j减少了一个前驱结点
if (g.adjlist[j].id==0 && flag[j]==0)//如果这个节点没有被扫描过并且没有前驱
{ queue[t++]=j;
flag[j]=1;
}
p=p->next;
}
}
return k; //返回输出的顶点个数
}
int main()
{ int k=0;
AovGraph g;
creat(&g,"aov.txt"); /*假设图8.25所示的AOV网输入文件为aov.txt*/
printf("\n图8.27所示AOV网的邻接表是：\n");
print(g);
k=TopSort(g);
if(k<g.n) printf("\n该图存在环！\n");
return 0;
}
版权声明：本文为pythpnhh原创文章，遵循CC 4.0 BY-SA版权协议，转载请附上原文出处链接和本声明。