edgeNode *e1[35]; //第一边表
edgeNode *e2[33]; //第二边表
edgeNode *e3[2]; //第三边表
edgeNode *e4[2]; //第四边表

int i;
for(i=0; i<35; i++) //第一边表初始化，分配内存
{
e1[i] = new edgeNode;
}
for(i=0; i<33; i++) //第二边表初始化，分配内存
{
e2[i] = new edgeNode;
}
for(i=0; i<2; i++) //第三、四边表初始化，分配内存
{
e3[i] = new edgeNode;
e4[i] = new edgeNode;
}

//第一边表数据域，即第一边表顶点号
//A
for(i=0; i<18; i++)
{
e1[i]->eVerIndex = i+1;
}
//修正A
e1[8]->eVerIndex = 33; //A9-->T1
e1[12]->eVerIndex = 34; //A13-->T2
e1[17]->eVerIndex = 0; //A18-->A1

//B
for(i=18; i<18+15; i++)
{
e1[i]->eVerIndex = i+1;
}
//修正B
e1[22]->eVerIndex = 33; //B5-->T1
e1[27]->eVerIndex = 34; //B10-->T2
e1[32]->eVerIndex = 31; //B15-->B14

//T1 T2
e1[33]->eVerIndex = 9; //T1-->A9
e1[34]->eVerIndex = 13; //T2-->A14

//第二边表数据域，即第二边表顶点号
//A
for(i=0; i<18; i++)
{
e2[i]->eVerIndex = i-1;
}
//修正A
e2[0]->eVerIndex = 17; //A1-->A18
e2[9]->eVerIndex = 33; //A10-->T1
e2[13]->eVerIndex = 34; //A14-->T2

//B
for(i=18; i<31; i++)
{
e2[i]->eVerIndex = i;
}
//修正B
e2[22]->eVerIndex = 33; //B6-->T1
e2[27]->eVerIndex = 34; //B11-->T2

//T1 T2
e2[31]->eVerIndex = 8; //T1-->A9
e2[32]->eVerIndex = 12; //T2-->A13

//第三边表数据域，即第三边表顶点号
//T1 T2
e3[0]->eVerIndex = 23; //T1-->B6
e3[1]->eVerIndex = 28; //T2-->B11

//第四边表数据域，即第四边表顶点号
e4[0]->eVerIndex = 22; //T1-->B5
e4[1]->eVerIndex = 27; //T2-->B10

//第一边表指针域
for(i=0; i<18; i++)
{
e1[i]->nextEdge = e2[i];
}
e1[18]->nextEdge = NULL;
for(i=19; i<32; i++)
{
e1[i]->nextEdge = e2[i-1];
}
e1[32]->nextEdge = NULL;

e1[33]->nextEdge = e2[31];
e1[34]->nextEdge = e2[32];

//第二边表指针域
for(i=0; i<33; i++)
{
e2[i]->nextEdge = NULL;
}
e2[31]->nextEdge = e3[0];
e2[32]->nextEdge = e3[1];

//第三边表指针域
e3[0]->nextEdge = e4[0];
e3[1]->nextEdge = e4[1];

//第四边表指针域
e4[0]->nextEdge = NULL;
e4[1]->nextEdge = NULL;

/*************************************************************/

/***完善顶点表数据域和指针域，关联顶点表与第一边表****/

for(i=0; i {
g->adjList[i].verIndex = i; //顶点表数据域
g->adjList[i].firstEdge = e1[i]; //顶点表指针域
}

/***********************************************************/

}

/***打印邻接表信息*******/
#ifdef DEBUG //只在DEBUG模式下打印
void printGraph(graphList *g)
{
int i;
edgeNode *p;

for(i=0; i {
cout << "顶点号：" << i << " 边号：";
p = g->adjList[i].firstEdge;

while(p)
{
cout << p->eVerIndex << " ";
p = p->nextEdge;
}
cout << endl;
}
}
#endif

/***************************************************/

/****BFS广度优先搜索邻接表，找出最短路径***********
参考：
http://blog.163.com/zhoumhan_0351/blog/static/3995422720098711040303/
******************************************************/

//队列链表结点结构，单向链表
typedef struct qNode
{
int qVerIndex; //队列数据域，结点存储的顶点号
struct qNode *nextQNode; //队列指针域，结点指向的下一个队列结点
}qNode; //队列链表结点结构别名为qNode

//队列链表
typedef struct
{
qNode *front; //队列头，删除
qNode *rear; //队列尾，添加
}queue; //队列链表别名queue

//初始化队列，新建队列
void InitQueue(queue *q)
{

q->rear = new qNode; //新建队列结点，赋予队尾
q->front = q->rear; //空队列的队头与队尾为同一单元
/*
if(q->front == NULL) //分配单元失败
{
cout << "InitQueue Error!" << endl;
exit(1);
}
*/
q->front->nextQNode = NULL; //队头的指向下一结点的指针为空
//因为队首队尾为同一单元，则队尾结点的下一结点指针也为空，即q->rear->nextQNode == NULL
}