#include <stdio.h>
#include <stack>
#include <queue>
#include<iostream>
#define MAX 999
#define maxsize 100
using namespace std;
typedef class ArcNode {
public:
int weight;
int adjvex; // 该边所指向的顶点的位置
ArcNode *nextarc; // 指向下一条边的指针
int *info; // 该边相关信息的指针
}ArcNode;
typedef class VNode {
public:
char data; // 顶点信息
ArcNode *firstarc; // 指向第一条依附该顶点的边
}VNode,AdjList[maxsize];
class ALGraph{
public:
AdjList vertices; //顶点
int vexnum, arcnum; // 图的当前顶点数和边数
};
class listgraph
{
ArcNode *nextnode;
bool visited[100];
bool found;
int prev[100];//prev[v]表示从源s到顶点v的最短路径上顶点的前驱顶点。
bool P[100][100]; //p[i][w]为true时w为v到i当前求的最短路径上的顶点
int D[100];
public:
int locateALG(ALGraph g,char v);
int GraphExist(ALGraph G,int i,int j);
int ExistG(ALGraph g);
int CreateADG(ALGraph &g);
void printGra(ALGraph G);
int FirstAdjVex(ALGraph g,int i);
int NextAdjVex(ALGraph g,int i);
void visitvex(ALGraph g,int i);
void DFS(ALGraph & graph,int v);
void DFSTraverse(ALGraph & graph);
int GraphAdd(ALGraph &G);
int NodeAdd(ALGraph &G);
int delArc(ALGraph &G,int i,int j);
int GraphDel(ALGraph &G);
int NodeDel(ALGraph &G);
int getWei(ALGraph G,int i,int j);
void ShortestPath(ALGraph G,int v);
void printPath(ALGraph G,int v);
void AllShortestPath(ALGraph G);
void menu();
void BFSTraverse(ALGraph & graph);
};
int listgraph::locateALG(ALGraph g,char v){
for(int i=0;i<g.vexnum;i++){
if(g.vertices[i].data==v)
return i;
}
return -1;
}
int listgraph::GraphExist(ALGraph G,int i,int j){
ArcNode *s;
s=G.vertices[i].firstarc;
while(s&&s->adjvex!=j)
s=s->nextarc;
if(s) return 1;
else return 0;
}
int listgraph::ExistG(ALGraph g){
if(g.vexnum<0){
printf("图不存在,请先创建图\n");
return 0;
}
return 1;
}
int listgraph::CreateADG(ALGraph &g){
int i,j,k,l,n;
ArcNode *p;
char v1,v2;
char c;
cout<<"请输入顶点数:";
cin>>g.vexnum;
while(g.vexnum>maxsize){
cout<<"\n请重新输入:";
cout<<"\n请输入顶点数：";
cin>>g.vexnum;
}
i=g.vexnum*(g.vexnum-1);
cout<<"请输入边数:";
cin>>g.arcnum;
while(g.arcnum>i){
cout<<"\n请重新输入:";
cout<<"请输入边数:";
cin>>g.arcnum;
}
cout<<"请输入顶点:";
for(i=0;i<g.vexnum;i++){
getchar();
cin>>c;
l=locateALG(g,c);
if(l>=0){
cout<<"请重新输入:";
i--;
continue;
}
g.vertices[i].data=c;
g.vertices[i].firstarc=NULL;
}
for(k=0;k<g.arcnum;k++){
getchar();
cout<<"请输入第"<<k+1<<"边的起点与终点和权值：";
cin>>v1>>v2;
i=locateALG(g,v1);
j=locateALG(g,v2);
if(i<0||j<0||i==j||GraphExist(g,i,j)){
cout<<"请重新输入:";
k--;
continue;
}
p=new ArcNode;
if(!p) return -1;
cin>>n;
p->adjvex=j;
p->nextarc=g.vertices[i].firstarc;
g.vertices[i].firstarc=p;
p->weight=n;
}
cout<<"创建成功\n";
return 1;
}
void listgraph::printGra(ALGraph G){
ArcNode *p;
int i;
cout<<"图中有"<<G.vexnum<<"个顶点,"<<G.arcnum<<"条边\n";
for(i=0;i<G.vexnum;i++){
p=G.vertices[i].firstarc;
cout<<G.vertices[i].data<<" ";
while(p){
cout<<"<"<<G.vertices[i].data<<","<<G.vertices[p->adjvex].data<<","<<p->weight<<"> ";
p=p->nextarc;
}
printf("\n");
}
}
int listgraph::FirstAdjVex(ALGraph g,int i){
ArcNode *p;
p=g.vertices[i].firstarc;
if(!p) return -1;
nextnode=p->nextarc;
return (p->adjvex);
}
int listgraph::NextAdjVex(ALGraph g,int i){
if(!nextnode) return -1;
int m=nextnode->adjvex;
nextnode=nextnode->nextarc;
return m;
}
void listgraph::visitvex(ALGraph g,int i){
cout<<g.vertices[i].data<<" ";
}
void listgraph::DFS(ALGraph & graph, int v)
{
visited[v] = true;
cout << graph.vertices[v].data << " ";
ArcNode * p = graph.vertices[v].firstarc;
while (p)
{
if (!visited[p->adjvex])
DFS(graph, p->adjvex);
p = p->nextarc;
}
}
void listgraph::DFSTraverse(ALGraph & graph)
{
for (int i = 0; i < graph.vexnum; i++)
visited[i] = false;
for (int i = 0; i < graph.vexnum; i++)
{
if (!visited[i])
DFS(graph, i);
}
}
int listgraph::GraphAdd(ALGraph &G){
int n,k,i,j,w;
ArcNode *p;
char v1,v2;
k=G.vexnum*(G.vexnum-1)-G.arcnum;
getchar();
cout<<"请输入要增加的边的起点与终点和权值：";
cin>>v1>>v2;
i=locateALG(G,v1);
j=locateALG(G,v2);
if(i<0||j<0||i==j||GraphExist(G,i,j)){
cout<<"\n请重新输入:";
}
cin>>w;
p=new ArcNode;
p->adjvex=j;
p->weight=w;
p->nextarc=G.vertices[i].firstarc;
G.vertices[i].firstarc=p;
G.arcnum++;
cout<<"插入成功\n";
return 1;
}
int listgraph::NodeAdd(ALGraph &G){
int i,l,n;
char c;
getchar();
cout<<"请输入要增加的顶点:";
cin>>c;
l=locateALG(G,c);
if(l>=0){
cout<<"\n请重新输入:";
}
G.vertices[G.vexnum].data=c;
G.vertices[G.vexnum].firstarc=NULL;
G.vexnum++;
cout<<"添加成功\n";
return 1;
}
int listgraph::delArc(ALGraph &G,int i,int j){
ArcNode *p,*q;
p=G.vertices[i].firstarc;
if(p->adjvex==j){
G.vertices[i].firstarc=p->nextarc;
free(p);
}
else{
while(p->nextarc&&p->nextarc->adjvex!=j)
p=p->nextarc;
if(p){
q=p->nextarc;
p->nextarc=q->nextarc;
free(q);
}
}
G.arcnum--;
return 1;
}
int listgraph::GraphDel(ALGraph &G){
int n,k,i,j;
char v1,v2;
getchar();
cout<<"请输入要删除的边的起点与终点：";
cin>>v1>>v2;
i=locateALG(G,v1);
j=locateALG(G,v2);
if(i<0||j<0||i==j||(!GraphExist(G,i,j))){
cout<<"\n请重新输入:";
}
delArc(G,i,j);
return 1;
}
int listgraph::NodeDel(ALGraph &G){
int i,l,n,k;
char c;
ArcNode *p;
getchar();
cout<<"请输入要删除的顶点：";
cin>>c;
l=locateALG(G,c);
if(l<0){
cout<<"\n请重新输入:";
}
for(i=0;i<G.vexnum;i++){
if(GraphExist(G,i,l)){
delArc(G,i,l);
}
if(GraphExist(G,l,i)){
delArc(G,l,i);
}
p=G.vertices[i].firstarc;
while(p){
if(p->adjvex>l){ p->adjvex--;
}
p=p->nextarc;
}
}
for(i=l;i<G.vexnum-1;i++){
G.vertices[i]=G.vertices[i+1];
}
G.vexnum--;
cout<<"删除成功";
return 1;
}
int listgraph::getWei(ALGraph G,int i,int j){
ArcNode *s;
s=G.vertices[i].firstarc;
while(s&&s->adjvex!=j){
s=s->nextarc;
}
if(s) return s->weight;
else return MAX;
}
void listgraph::ShortestPath(ALGraph G,int v){
int i=0,j,v0,w,min;
bool final[100];
for(v0=0;v0<G.vexnum;v0++){
prev[v0]=-1;
final[v0]=false;
D[v0]=getWei(G,v,v0);
for(w=0;w<G.vexnum;++w) P[v0][w]=false;
if(D[v0]<MAX){
prev[v0]=v;
P[v0][v]=true;
P[v0][v0] =true;
}
}
D[v]=0;
final[v]=true;
for(i=1;i<G.vexnum;++i){
min=MAX;
for(w=0;w<G.vexnum;++w){
if(!final[w])
if(D[w]<min){
v0=w; min=D[w];
}
}
if(v0==G.vexnum){
break;
}
final[v0]=true;
for(w=0;w<G.vexnum;++w)
if(!final[w]&&(min+getWei(G,v0,w)<D[w])){
prev[w]=v0;
D[w]=min+getWei(G,v0,w);
for(j=0;j<G.vexnum;j++) P[w][j]=P[v0][j];
P[w][w]=true;
}
}
}
void listgraph::printPath(ALGraph G,int v){
int i,k;
stack<char> s;
char a;
for(i=0;i<G.vexnum;i++){
if(i!=v){
if(D[i]!=MAX){
cout<<G.vertices[v].data<<"到"<<G.vertices[i].data<<"的最短路径长度为:"<<D[i]<<endl;
cout<<G.vertices[v].data<<"到"<<G.vertices[i].data<<"的最短路径为:";
cout<<"\n";
a=G.vertices[i].data;
s.push(a);
for(k=prev[i];k>-1;k=prev[k]){
a=G.vertices[k].data;
s.push(a);
}
while(!s.empty()){
cout<<s.top()<<" ";
s.pop();
}
cout<<"\n";
}
else
cout<<G.vertices[v].data<<"到"<<G.vertices[i].data<<"没有最短路径\n";
}
}
}
void listgraph::AllShortestPath(
数据结构.rar （16个子文件） 
test1 seqlist 
seqlist.cpp 2KB expr expr.cpp 2KB test7 road road.cpp 990B meeting meeting.cpp 2KB test3 step step.cpp 1KB sort sort.cpp 918B test2 sllist sllist.cpp 8KB queue queue.cpp 4KB test4 GeneralTree GeneralTree.cpp 6KB huffman huffman.cpp 7KB huffman.h 4KB BinaryTree BinaryTree.cpp 7KB test5 btwid btwid.cpp 2KB pearl pearl.cpp 798B test6 GraphList GraphList.cpp 11KB GraphMatrix GraphMatrix.cpp 7KB资源评论
