图(数据结构)

//

// 图.cpp : Defines the entry point for the console application.

//

#include"stdafx.h"

#include

#include

#include

#include

#define MaxVerNum 30 /* 最大顶点数为100 */

typedef struct node

{ /* 表结点表示边或者弧 */

int adjvex; /* 邻接点,一般是顶点的序号或在表头向量中的下标 */

int Info; /*与边(或弧)相关的信息*/

struct node * next; /* 指向下一个邻接点的指针域 */

}EdgeNode;

typedef struct vnode

{ /* 顶点结点 */

int vertex; /* 顶点域 */

EdgeNode * firstedge; /* 边表头指针 */

}VertexNode;

typedef struct

{

VertexNode adjlist[MaxVerNum]; /* 邻接表 */

int n,e; /* 顶点数和边数 */

}ALGraph; /* ALGraph是以邻接表方式存储的图类型 */

//////////////////////////////////////////////////////////////////////

///////////////////////////////////////////////////////邻接表结构定义

void CreateALGraph(ALGraph *G)/* 建立图的邻接表存储 */

{ int i,j,k,a,b,c;

EdgeNode * p;

cout<<"请输入图的顶点数和边数。"<cin>>a>>b;

G->n=a;

G->e=b;

for(i=0;in;i++) /* 建立有n个顶点的顶点表 */

{

cout<<"请输入第"<cin>>c;

G->adjlist[i].vertex=c;

G->adjlist[i].firstedge=NULL;

}

for(k=0;ke;k++ ) /* 建立边表 */

{

cout<<"请输入第"<cin>>i>>j;

p=(EdgeNode*)malloc(sizeof(EdgeNode ) ) ;

p->adjvex=j; /* 邻接点序号为j */

/* 将新边表结点p插入到顶点Vi的链表头部 */

p->next=G->adjlist[i].firstedge;

G->adjlist[i].firstedge=p;

}

} /*CreateALGraph*/

///////////////////////////////////////////////////////////////////////

///////////////////////////////////////////////////////图的邻接表创建

void DestroyALGraph(ALGraph *G)/* 销毁图的邻接表存储 */

{ int i=0,k;

EdgeNode * p,*q;

for(k=0;ke;k++ ) /* 销毁边表 */

{ p=G->adjlist[i].firstedge;

while (p) /* 销毁第i个顶点的边表 */

{ q=p;

p=p->next;

free(q);

}

G->adjlist[i].firstedge=NULL;

}

}

//////////////////////////////////////////////////////////////////

////////////////////////////////////////////////////图的邻接表销毁

#define false 0

#define true 1

int visited[MaxVerNum];

void Visit(ALGraph G,int v)

{

cout<}

int NextAdjVertex (ALGraph G, int v, in

t w)

/* 求图G的第v个顶点的邻接点w的下一个邻接点 （邻接表表示图） */

{ EdgeNode *p;

p=G.adjlist[v].firstedge;

while (p && p-> adjvex != w )

p=p->next; //找第v 结点

if(p==NULL || p->next==NULL)

return -1; //找不到第v 结点或第v 结点无后继

else

return (p->next->adjvex);

}

int FirstAdjVertex(ALGraph G,int v)

/* 求图G的第一个邻接点（邻接表表示图） */

{

if(G.adjlist[v].firstedge!=NULL)

return (G.adjlist[v].firstedge->adjvex);

else

return -1; //无第一个邻接点

}

void DFS(ALGraph G,int v)

/* 从第v个顶点出发深度优先遍历图G */

{

int w;

Visit(G,v); /* 访问第v个顶点 */

visited[v]=true; /* 把 v 顶点置True表访问过 */

for(w=FirstAdjVertex (G,v);w!=-1;w=NextAdjVertex (G,v,w) )

if (!visited[w]) DFS(G,w);/* 对v尚未访问的邻接顶点w递归调用DFS */

}

void DFStraverse(ALGraph G)

/*深度优先遍历图G*/

{ int v;

for(v=0;vvisited[v]=false;/*标志向量初始化*/

//cout<<"请输入从第几个顶点出发深度优先遍历图。"<// cin>>t;

for(v=0;vif(! visited[v])

DFS(G,v);

}/*DFS*/

/////////////////////////////////////////////图的深度优先遍历

//////////////////////////////////////////////////////////////

#define MAX 100

typedef struct{

int data[MAX];

int front,rear;

}SeqQueue,*PSeqQueue;

PSeqQueue Init_SeqQueue()

{

PSeqQueue Q;

Q=(PSeqQueue)malloc(sizeof(SeqQueue));

if(Q)

{

Q->front=0;

Q->rear=0;

}

return Q;

}

void Destroy_SeqQueue(PSeqQueue *Q)

{

if(*Q)

free(*Q);

*Q=NULL;

}

int Empty_SeqQueue(PSeqQueue Q)

{

if(Q&&Q->front==Q->rear)

return(1);

else

return(0);

}

int In_SeqQueue(PSeqQueue Q,int x)

{

if((Q->rear+1)%MAX==Q->front)

{

return 0;

}

else

{

Q->rear=(Q->rear+1)%MAX;

Q->data[Q->rear]=x;

return 1;

}

}

int Out_SeqQueue(PSeqQueue Q,int *x)

{

if (Empty_SeqQueue(Q))

{

return 0;

}

else

{

Q->front=(Q->front+1)%MAX;

*x=Q->data[Q->front];

return 1;

}

}

void BFS(ALGraph G, int v)

{/* 从v0点开始，按广度优先遍历图G*/

int u,w;

PSeqQueue Q; Q=Init_SeqQueue( );

Visit(G,v); visited[v]=true;

In_SeqQueue(Q, v); /* 起始点入队列 */

while(!Empty_SeqQueue(Q))

{ Out_SeqQueue(Q,&u); /* 出队列 v 顶点*/

for(w=FirstAdjVertex(G,v);w!=-1;w=NextAdjVertex(G,v,w))

{ if(!visited[w])

{

Visit(G,w); visited[w]=true;/* 访问w */

In_SeqQueue(Q,w); /* 访问过的w入队列 */

}

}//搜索顶点v 的所有邻接点

}

Destroy_SeqQueue(&Q);

}

void BFStraverse(ALGraph G)

{ /* 广度优先遍历图G的所有顶点 */

int v;

for(v=0;vvisited[v]=false; /* 标志向量初始化 */

//cout<<"请输入从第几个顶点出发广度优先遍历图。"<//cin>>v;

for(v=0;vif(!visited[v]) BFS(G,v);

}

///////////////////////////////////////////////////图的广度优先遍历

//////////////////////////////////////////////////////////////////

/*#define MAXCOST 100

void Prim (int gm[ ][MaxVerNum],int n,int closevertex[ ])

{

int lowcost[100],mincost;

int i,j,k;

for (i=1;i/* {

lowcost[i]=gm[0][i];

closevertex[i]=0;

}//从顶点v0开始构造最小生成树

lowcost[0]=0; /* 从序号为0的顶点出发生成最小生成树 */

/*closevertex[0]=0;//保存最小生成树

for(i=1;i/*{

mincost=MAXCOST; j=1;k=1;

while (j/*{ if (lowcost[j]{

mincost=lowcost[j];

k=j;

}

j++;

}

printf("(%d,%d,%d)\

>vexnum-1 && jedgenum)

{ int s1,s2;

s1=f [ G->edgelist[j].vex1];

s2=f [ G->edgelist[j].vex2];

/*判断顶点s1,s2是否在一个连通分量内,不是产生一条最小边*/

if (s1!= s2)

{

TE[k].vex1= G->edgelist[j].vex1;

TE[k].vex2= G->edgelist[j].vex2;//加入一条边

TE[k].weight= G->edgelist[j].weight;

cout<k++;

for(i=0;ivexnum;i++)

if (f[i]==s2)

f[i]=s1;/*修改连通的编号*/

}

j++;

}

}

///////////////////////////////////图的最小生成树Kruskal算法

////////////////////////////////////////////////////////////

#define INFINITY 30000

typedef struct

{

int vertexs[MaxVerNum]; /* 顶点表 */

int arcs[MaxVerNum][MaxVerNum];/* 邻接矩阵，即边表 */

int n,e; /* 顶点数和边数 */

} MGraph;/* MGragh是以邻接矩阵存储的图 */

/*void ShortestPath_1(MGraph *G,int v0,int P[ ][MaxVerNum], int D[])

{ /*P[v ]表示路径， P[v ][i]=1表示到v0到v点的路径经过i顶点； D[v]表示到达v点的路径长度 */

/*int a,b,c,s,i,j,v,w,min;

cout<<"请输入顶点个数和边个数。"<cin>>a>>b;

G->n=a;

G->e=b;

for(i=0;in;i++)

{

cout<<"请输入第"<cin>>c;

G->vexs[i]=c;

}

for(i=0;in;i++)

for(j=0;jn;j++)

if(i=j)

G->edges[i][j]=0;

else

G->edges[i][j]=INFINITY;

for(s=0;se;s++)

{

cout<<"请输入边的信息，即边的源点、终点、权值。"<cin>>i>>j>>w;

G->edges[i][j]=w;

}

bool final[MaxVerNum]; // 标记已经求出的顶点

for(v=0;vn;++v)

{

final[v]=False; D[v]=G->edges[v0][v];

for(w=0; wn;++w) P[v][w]=0;//设空路径

if (D[v]{

P[v][v0]=1; P[v][v]=1;

} //初始化

D[v0]=0; final[v0]=True; /*开始，v0顶点属于S集*/

/*for(i=1; in; ++i) /*其余G.n-1个顶点*/

/*{

min=INFINITY;

for (w=0;wn;++w)

if (!final[w]&& D[w]/*{

v=w; min=D[w];

}

final[v]=True;

for(w=0;w>G->n;++w) /*更新当前最短路径*/

/* if (!final[w]&&(min+G->edges[v][w]{

D[w]=min+G->edges[v][w];

cout<P[w][0]=P[v][0];

P[w][w]=1;

}

}

}

}/*ShortestPath_1*/

// O(n2)

void ShortestPath_Dij(MGraph *G,int v0,int p[],int d[]) //用于有向图

{ /*起始点v0到其它点的最短路径 p[v]表示v的前驱顶点 d[v]表示v0到顶点v的

最短带

权路径长度 final[v]为1则表明已找到从v0到v的最短路径*/

int a,b,c,s,i,j,v,w,min;

cout<<"请输入顶点个数和边个数。"<cin>>a>>b;

G->n=a;

G->e=b;

for(i=0;in;i++)

{

cout<<"请输入第"<cin>>c;

G->vertexs[i]=c;

}

for(i=0;in;i++)

for(j=0;jn;j++)

{

if(i==j)

G->arcs[i][j]=0;

else

G->arcs[i][j]=INFINITY;

}

for(s=0;se;s++)

{

cout<<"请输入边的信息，即边的源点、终点、权值。"<cin>>i>>j>>w;

G->arcs[i][j]=w;

}

int final[MaxVerNum];

for(v=0;v<=G->n-1;v++) //初始化每个顶点与v0

{

if(v==0) p[v]=-1;/////////////////////////////修改点

else{

final[v]=false;

d[v]=G->arcs[v0][v];

p[v]=-1; //初始化，表示无前驱

if(d[v]p[v]=v0;

}//v0到v有弧 ,v的前驱初始值为v0

}

d[v0]=0;final[v0]=true; //初始时,v0属于S集

//开始主循环 每次求的v0到某个顶点v的最短路径 并加v到S集

for(i=1;i<=G->n;i++) //寻找其余G.vertexNum-1个顶点

{

v=-1;

min=INFINITY;

for(w=0;w<=G->n-1;w++)

if((!final[w])&&(d[w]{

v=w; //v为找到的最近点的下标

min=d[w];

}

if(v==-1)

break;//若v=-1表明所有与v0有通路的顶点均已找到了最短路径 退出主循环

final[v]=true; //将v加入S集

for(w=0;w<=G->n-1;w++) //更新当前最短路径及距离

if(!final[w]&&(min+G->arcs[v][w]{

d[w]=min+G->arcs[v][w];

p[w]=v; //修改w的前驱

}

}

}

//-----------------------------------------------//

void Print_DijPath(MGraph *G,int v0,int p[], int d[])

{ //显示从顶点v0到其余顶点的最短路径及距离

int v,i;

cout<<"The shortest path from "<for(v=0;v<=G->n-1;v++)

{

if(p[v]==-1)

continue; //表明顶点v0到顶点v没有通路

cout<cout<i=v;

while(p[i]!=-1)

{

cout<i=p[i];

}

cout<}

}

int Graph_Operate()

{

cout<<"--------0:选择退出----------"<cout<<"--------1:创建图----------"<cout<<"--------2:销毁图----------"<cout<<"--------3:图的深度优先遍历----------"<cout<<"--------4:图的广度优先遍历----------"<cout<<"--------5:图的最小生成树的Kruskal算法----------"<cout<<"--------6:图的最短路径的Dijkstra算法----------"<cout<<"请输入你要执行的操作序号0-6"<char a;

cin>>a;

ALGraph *h=(ALGraph*)malloc(sizeof(ALGraph));

ELGraph *l=(ELGraph*)malloc(sizeof(ELGraph));

MGraph *k=(MGraph*)malloc(sizeof(MGraph));

while(a)

{

switch(a){

case '0':

return 0;

case '1':

CreateALGraph(h);

cout<<"创建完成!";

break;

case '2':

DestroyALGraph(h);

cout<<"销毁成功!";

break;

case '3':

DFStraverse(*h);

break;

case '4':

BFStraverse(*h);

break;

case '5':

cout<<"输入用Kruskal算法求最小生成树的 无向图 的信息。"<Kruskal(l);

break;

case '6':

cout<<"输入用Dijkstra算法求最短路径的 有向图 的信息。"<int v0=0;

int d[MaxVerNum];

int p[MaxVerNum];

ShortestPath_Dij(k,v0,p,d);

Print_DijPath(k,v0,p,d);

break;

}

cout<<"\

输入你要继续执行的操作序号(0-6)"<cin>>a;

}

return 0;

}

void Show_Main_Menu()

{

cout<<"---------------------------------"<cout<<"-------Enter Main Menu---------"<cout<<"-----Please Choose Operation-----"<cout<<"-------G: Graph Operation---------"<cout<<"------------E:Exit---------------"<cout<<"---------------------------------"<}

int main()

{

Show_Main_Menu();

cout<<"Please input what do you want to operate(g,e)"<char oper;

cin>>oper;

while(oper)

{

switch(oper)

{

case 'e':

return 0;

case 'g':

Graph_Operate();

break;

}

cout<<"输入你要继续执行的操作字符(g,e)"<cin>>oper;

}

return 0;

}