#include <iostream>
#include <fstream>
using namespace std;
#include<iostream>
using namespace std;
const int MVN = 21;
typedef char VexType;//顶点元素类型
typedef int QElemType;
typedef struct QNode
{
QElemType data;
QNode *next;
}*LQueuePtr;
typedef struct ArcNode
{
int adjvex;//弧指向的顶点位置
int adj;//权
ArcNode *nextarc;//指向下一条弧的顶点
}*ArcPtr;
struct VexNode
{
VexType data;//顶点数据
ArcPtr firstarc;//指向第一条依附于该顶点的弧
bool visited;//是否被访问过
};
struct ALGraph
{
VexNode vexs[MVN];
int kind, vexnum, arcnum;//类型，顶点数，弧数
};
struct LQueue
{
LQueuePtr front, rear;//队头指针，队尾指针
};
int LocateVex(ALGraph &G, VexType v);//查找顶点
bool InsertArc(ALGraph &G, VexType u, VexType v, int w = 1);//插入弧
void CreateGraph(ALGraph &G, int Kind, char v[]);
void GraphPrint(ALGraph &G);
void QueueInit(LQueue &Q);
void Enqueue(LQueue &Q, QElemType e);
bool Dequeue(LQueue &Q, QElemType &e);
void visit(VexType u);
bool existroad(ALGraph &G, VexType u, VexType v);
int main()
{
char g[] = "sacdw#sascsdacadcd#";
cout << "序列为 "<< endl<< g<< endl;
int Kind = 3;
ALGraph G;
CreateGraph(G, Kind, g);
GraphPrint(G);
VexType u = 'a';
//VexType v1 = 'c';
VexType v1 = 'w';
bool f1 =existroad(G, u, v1);
cout <<u<<"到"<<v1<<"的路径"<< (f1?"":"不")<<"存在" << endl;
return 0;
}
void QueueInit(LQueue &Q)
{
Q.front = new QNode;
Q.front->next = NULL;
Q.rear = Q.front;
}
void Enqueue(LQueue &Q, QElemType e)
{
LQueuePtr p;
p = new QNode;
p->data = e;
p->next = NULL;
Q.rear->next = p;
Q.rear = p;
}
bool Dequeue(LQueue &Q, QElemType &e)
{
LQueuePtr p;
if (Q.rear == Q.front)
{
return false;
}
p = Q.front;
Q.front = p->next;
e = Q.front->data;
delete p;
return true;
}
void visit(VexType u)
{
cout << u << ",";
}
bool existroad(ALGraph &G, VexType u, VexType v)
{
int i, j, k, m;
ArcPtr p;
LQueue q;
m = LocateVex(G, u);
if (m == 0)
{
return false;
}
if (!G.vexs[m].firstarc)
{
return false;
}
for (i = 1; i <= G.vexnum; i++)
{
G.vexs[i].visited = false;
}
G.vexs[m].visited = true;
QueueInit(q);
Enqueue(q, m);
while (Dequeue(q, j))
{
for (p = G.vexs[j].firstarc; p; p = p->nextarc)
{
k = p->adjvex;
if (G.vexs[k].visited)
{
continue;
}
if (G.vexs[k].data == v)
{
return true;
}
G.vexs[k].visited = true;
Enqueue(q, k);
}
}
return false;
}
int LocateVex(ALGraph &G, VexType v)//查找顶点
{
int i;
for (i = G.vexnum; i > 0 && G.vexs[i].data != v; i--);
return i;
}
bool InsertArc(ALGraph &G, VexType u, VexType v, int w )
{
ArcPtr p;
int i, j;
bool found;
i = LocateVex(G, u);
if (i == 0)
{
return false;
}
j = LocateVex(G, v);
if (j == 0 || j == i)
{
return false;
}
for (found = false, p = G.vexs[i].firstarc; p && !found; p = p->nextarc)
{
if (p->adjvex == j)
{
found = true;
}
}
if (found)
{
return false;
}
G.arcnum++;
p = new ArcNode;
p->adjvex = j;
p->adj = w;
p->nextarc = G.vexs[i].firstarc;
G.vexs[i].firstarc = p;//表头插入弧，假设对弧的次序无要求
if (G.kind <= 2)
{
return true;
}
G.arcnum++;
p = new ArcNode;
p->adjvex = i;
p->adj = w;
p->nextarc = G.vexs[j].firstarc;
G.vexs[j].firstarc = p;
return true;
}
void CreateGraph(ALGraph &G, int Kind, char v[])
{
int i, w;
G.kind = Kind;
G.arcnum = 0;
i = 0;
while (true)
{
if (v[i] == '#')
{
break;
}
i++;
G.vexs[i].data = v[i - 1];
G.vexs[i].firstarc = NULL;
}
G.vexnum = i;
i++;
while (true)
{
if (v[i] == '#')
{
break;
}
if (G.kind == 1 || G.kind == 3)
{
w = 1;
}
else
{
w = v[i + 2] - 48;
}
InsertArc(G, v[i], v[i + 1], w);
i = i + 2;
if (w == 2 || w == 4)
{
i++;
}
}
}
void GraphPrint(ALGraph &G)
{
ArcPtr p;
cout << "邻接表" << endl;
for (int i = 1; i <= G.vexnum; i++)
{
cout << G.vexs[i].data;
for (p = G.vexs[i].firstarc; p; p = p->nextarc)
{
cout << "->" << p->adjvex;
}
cout << endl;
}
}