图的基本操作，哪位大神进来指导下
#include<stdio.h>#include <malloc.h>
#include<conio.h>
#include <stdlib.h>
#define TRUE 1
#define FALSE 0
#define OK 1
#define ERROR 0
#define INFEASIBLE -1
#define OVERFLOW -2
typedef int Qelemtype;
typedef int Status;
typedef struct Qnode
{
Qelemtype data;
struct Qnode *next;
}Qnode, *Queueptr;
typedef struct
{
Queueptr front;
Queueptr rear;
}Queue;
#define maxvernum 30
int visited[maxvernum];
typedef char vertextype;
typedef struct arcnode
{
int adjvex; //该弧指向的顶点位置
struct arcnode * nextarc; //指向下一个表结点
int info; //权值信息
}arcnode; //边结点类型
typedef struct vnode
{
vertextype data;
int indegree;
arcnode * firstarc;
}vnode, adjlist[maxvernum];
typedef struct
{
adjlist vertices; //邻接表
int vernum, arcnum; //顶点数和弧数
}algraph;
//查找符合的数据在数组中的下标 CreateALGraph
int locatever(algraph g, char u)
{
int i;
for(i = 0; i < g.vernum; i++)
{
if(u == g.vertices[i].data)
return i;
}
if(i == g.vernum)
{
printf("error u!\n");
exit(1);
}
return 0;
}
//常见图的邻接矩阵
void createalgraph(algraph &g)
{
int i, j, k, w;
char v1, v2;
arcnode * p;
printf("输入顶点数和弧数: ");
scanf("%d %d", &g.vernum, &g.arcnum);
printf("请输入顶点!\n");
for(i = 0; i < g.vernum; i++)
{
printf("请输入第 %d 个顶点: \n", i);
fflush(stdin);
scanf("%c", &g.vertices[i].data);
g.vertices[i].firstarc = NULL;
g.vertices[i].indegree = 0;
}
for(k = 0; k < g.arcnum; k++)
{
printf("请输入弧的顶点和相应权值(v1, v2, w): \n");
fflush(stdin); //清空输入缓冲区
scanf("%c %c %d", &v1, &v2, &w);
i = locatever(g, v1);
j = locatever(g, v2);
p = (arcnode *)malloc(sizeof(arcnode));
p->adjvex = j;
p->info = w;
p->nextarc = g.vertices[i].firstarc;
g.vertices[i].firstarc = p;
g.vertices[j].indegree++; //vi->vj, vj入度加1
}
return;
}
int firstadjvex(algraph g,char v)
{
arcnode * p;
int v1;
v1 = locatever(g,v);//v1为顶点v在图G中的序号
p = g.vertices[v1].firstarc;
if (p)
{
return p->adjvex;//p->data.adjvex
}
else
{
return -1;
}
}
int nextadjvex(algraph g,char v,char w)
{
arcnode*p,*s;
for(p=g.vertices[v].firstarc;p!=NULL;p=p->nextarc)
{
if(((p->adjvex)==w)&&(p->nextarc))
{
s=p->nextarc;
return s->adjvex;
}
}
return 0;
}
void dfs(algraph g,char v) //深度优先遍历
{
char w;
printf("%d\n ",v); //访问结点v
visited[v]=true;
// visitfunc(v);
for(w=firstadjvex(g,v);w>=0;w=nextadjvex(g,v,w)) //访问与v相邻的未被访问过的结点
{
if(!visited[w])
dfs(g,w);
}
}
int InitQueue(Queue &Q)
{
Q.front = Q.rear = (Queueptr) malloc (sizeof(Qnode));
if(!Q.front) return (OVERFLOW);
Q.front ->next = NULL;
return OK;
}//构造一个空队列
Status EnQueue(Queue &Q,Qelemtype e)
{
Queueptr p;
p = (Queueptr) malloc (sizeof(Qnode));
if(!p) return(OVERFLOW);
p->data = e;
p->next = NULL;
Q.rear->next = p;
Q.rear = p;
return OK;
}//插入新元素
Status DeQueue(Queue &Q,Qelemtype &e)
{
Queueptr p;
if(Q.front == Q.rear) return ERROR;
p = Q.front->next;
e = p->data;
Q.front->next = p->next;
if(Q.rear == p) Q.rear = Q.front;
free(p);
return OK;
}//删除队头元素
Status Queueempty(Queue Q)
{
if(Q.front == Q.rear) return OK;
else return ERROR;
}//判断队列是否为空
void bfs(algraph g,int v) //广度优先搜索
{
Queue Q;
int u;
char w;
for(v=0;v<g.vernum;++v)
visited[v]=false;
InitQueue(Q);
for(v=0;v<g.vernum;++v)
if(!visited[v])
{
visited[v]=true;
printf("%d\n",v);
EnQueue(Q,v);
while(!Queueempty(Q))
{
DeQueue(Q,u);
for(w=firstadjvex(g,u);w>=0;w=nextadjvex(g,u,w))
if(!visited[w])
{
visited[w]=true;
printf("%d\n ",w);
EnQueue(Q,w);
}//if
}//while
}//if
}
//求图的关键路径函数
void criticalpath(algraph g)
{
int i, k, e, l;
int * ve, * vl;
arcnode * p;
//以下是求时间最早发生时间
ve = new int [g.vernum];
vl = new int [g.vernum];
for(i = 0; i < g.vernum; i++) //前推
ve[i] = 0;
for(i = 0; i < g.vernum; i++)
{
arcnode * p = g.vertices[i].firstarc;
while(p != NULL)
{
k = p->adjvex;
if(ve[i] + p->info > ve[k])
ve[k] = ve[i]+p->info;
p = p->nextarc;
}
}
//以下是求最迟发生时间
for(i = 0; i < g.vernum; i++)
vl[i] = ve[g.vernum-1];
for(i = g.vernum-2; i >= 0; i--) //后推
{
p = g.vertices[i].firstarc;
while(p != NULL)
{
k = p->adjvex;
if(vl[k] - p->info < vl[i])
vl[i] = vl[k] - p->info;
p = p->nextarc;
}
}
for(i = 0; i < g.vernum; i++)
{
p = g.vertices[i].firstarc;
while(p != NULL)
{
k = p->adjvex;
e = ve[i]; //最早开始时间为时间vi的最早发生时间
l = vl[k] - p->info; //最迟开始时间
char tag = (e == l) ? '*' : ' '; //关键活动
printf("(%c, %c), e = %2d, l = %2d, %c\n", g.vertices[i].data, g.vertices[k].data, e, l, tag);
p = p->nextarc;
}
}
delete [] ve;
delete [] vl;
}
void main()
{int i;
algraph g;
createalgraph(g); /*创建图*/
printf("以下是查找图的关键路径的程序。\n");
//criticalpath(g);
for(i=1;i<maxvernum;i++)
visited[i]=0; /*访问数组初始化*/
dfs(g,0); /*调用DFS*/
getch(); /*等待输入*/
for(i=1;i<maxvernum;i++)
visited[i]=0;
bfs(g,1); /*调用BFS*/
printf("以下是查找图的关键路径的程序。\n");
criticalpath(g);
}
