#include
#include
using namespace std;
#define MVNum 100 //最大顶点数
#define OK 1
typedef string VerTexType; //顶点信息
typedef int OtherInfo; //和边相关的信息
//- - - - -图的邻接表存储表示- - - - -
typedef struct ArcNode { //边结点
int adjvex; //该边所指向的顶点的位置
struct ArcNode *nextarc; //指向下一条边的指针
OtherInfo info; //和边相关的信息
} ArcNode;
typedef struct VNode {
VerTexType data; //顶点信息
ArcNode *firstarc; //指向第一条依附该顶点的边的指针
} VNode, AdjList[MVNum]; //AdjList表示邻接表类型
typedef struct {
AdjList vertices; //邻接表
int vexnum, arcnum; //图的当前顶点数和边数
} Graph;
//得到顶点i的数据
VerTexType Vertexdata(const Graph &g, int i)
{
return g.vertices[i].data;
}
int LocateVex(const Graph &g, VerTexType v)
{
//确定点v在G中的位置
for(int i = 0; i < g.vexnum; ++i)
if(g.vertices[i].data == v)
return i;
return -1;
}//LocateVex
//返回v的第一个邻接顶点。若顶点在G中没有邻接表顶点,则返回-1。
int FirstAdjVex(const Graph &g, int v)
{
if(g.vertices[v].firstarc!=NULL){
return g.vertices[v].firstarc->adjvex;
}
return -1;
}
// 返回v的(相对于w的)下一个邻接顶点。
int NextAdjVex(const Graph &g, int v, int w)
{
ArcNode*p=g.vertices[v].firstarc;
while(p->nextarc){
if(p->adjvex==w){
return p->nextarc->adjvex;
}
else{
p=p->nextarc;
}
}
return -1;
}
//对每个顶点的链表排序,按顶点编号从小到大排列
void sort(ArcNode *arclist)
{
ArcNode *p=arclist;
ArcNode *q=p->nextarc;
int a,t=0;
while(p){
if(p->adjvex>q->adjvex){
a=p->adjvex;
p->adjvex=q->adjvex;
q->adjvex=a;
t=0;
}
p=p->nextarc;
q=p->nextarc;
if(p->nextarc==NULL&&t==0){
t=1;
p=arclist;
}
}
}
int CreateUDG(Graph &g)
{
//采用邻接表表示法,创建无向图G
VerTexType v1,v2;
cin>>g.vexnum>>g.arcnum;
for(int i=0;i<g.vexnum;++i){
cin>>g.vertices[i].data;
g.vertices[i].firstarc=NULL;
}
for(int k=0;k<g.arcnum;++k){
cin>>v1>>v2;
int i=LocateVex(g,v1);int j=LocateVex(g,v2);
ArcNodep1=new ArcNode;
p1->adjvex=j;
ArcNodep2=new ArcNode;
p2->adjvex=i;
p2->nextarc=g.vertices[j].firstarc;
g.vertices[j].firstarc=p2;
}
for(int i = 0; i < g.vexnum; ++i) {
sort(g.vertices[i].firstarc); ////保证有序,不依赖输入次序
}//for
return OK;
}//CreateUDG
void DestroyUDG(Graph &g)
{
//you should do this
}
int main()
{
Graph g;
CreateUDG(g);
//输出各个顶点的邻接点
for(int i = 0; i < g.vexnum; i++) {
cout << Vertexdata(g, i) << ":";
for(int w = FirstAdjVex(g, i); w >= 0; w = NextAdjVex(g, i, w)) {
cout << ' ' << Vertexdata(g, w);
}
cout << endl;
}
DestroyUDG(g);
return 0;
}