无向图的邻接表

链表（存相邻顶点下标）的类

class Edge
{
public:Edge() :m_next(nullptr) {}Edge(int v) :m_destindex(v), m_next(nullptr) {}int m_destindex;//下标Edge* m_next;//下一个邻接顶点的结点
};

数组里放的顶点

class Vertex
{
public:Vertex() :m_list(nullptr) {}Vertex(int v) :m_VerValue(v), m_list(nullptr) {}char m_VerValue;//顶点值Edge* m_list;//指针指向邻接顶点的链表
};

邻接表（操作）

插入顶点，插入边，删除顶点，删除边，获取顶点在数组中的下标（前面的操作需要用）

#define SIZE 10
class GraphLink
{
public:GraphLink();~GraphLink();void InsertVertex(char v);//插顶点void InsertEdge(char v1, char v2);//插边void PrintGraph();//打印void DelVertex(char v);//删顶点void DelEdge(char v1, char v2);//删边int GetVertexIndex(char v);//获取顶点下标
private:int m_MaxVertex;//最多结点数int m_NumVertex;//当前结点数int m_NumEdge;//边数Vertex* m_VerArr;//存顶点的数组（指针指向数组头）
};

构造和析构（创建销毁邻接表）

创建：给m_VerArr指针new最大顶点数m_MaxVertex个顶点Vertex大小的空间；

销毁：释放指向数组起始的指针的空间。

GraphLink::GraphLink() :m_MaxVertex(SIZE), m_NumVertex(0), m_NumEdge(0)
{m_VerArr = new Vertex[m_MaxVertex];
}
GraphLink::~GraphLink()
{if (m_VerArr != nullptr){delete[]m_VerArr;m_VerArr = nullptr;}
}

插入顶点

首先确定顶点数（不能超过设定的最大顶点数）。

若可插：将顶点值赋到数组中最后一个位置m_VerArr[m_NumVertex]，顶点个数++。

void GraphLink::InsertVertex(char v)
{if (m_NumVertex >= m_MaxVertex)return;m_VerArr[m_NumVertex++].m_VerValue = v;
}

插入边

插入顶点v1到顶点v2的边时，由于链表中记录的是顶点的下标，所有首先需要有一个获取下标的函数：

获取下标

遍历数组记录下标，找到顶点即可找到下标返回，若没找到：返回-1。

int GraphLink::GetVertexIndex(char c)
{for (int i = 0; i < m_NumVertex; i++){if (m_VerArr[i].m_VerValue == c)return i;}return -1;
}

插v1、v2之间的边

注意：无向图插一条边需要改两个表。

获取下标后，插入方法与链表头插相同。

void GraphLink::InsertEdge(char v1, char v2)
{int p1 = GetVertexIndex(v1);int p2 = GetVertexIndex(v2);if (p1 == -2 || p2 == -1)return;//v1->v2 既是在v1的边链表中插入值为p2的边节点Edge* edge = new Edge(p2);edge->m_next = m_VerArr[p1].m_list;m_VerArr[p1].m_list = edge;//v2->v1edge = new Edge(p1);edge->m_next = m_VerArr[p2].m_list;m_VerArr[p2].m_list = edge;m_NumEdge++;
}

删除顶点

用覆盖删除的方法：数组最后一个顶点覆盖要删的，并修改链表内受影响下标的值。

void GraphLink::DelVertex(char v)
{int p = GetVertexIndex(v);if (p == -1)return;Edge* pp = m_VerArr[p].m_list;char destvalue;while (pp){destvalue = m_VerArr[pp->m_destindex].m_VerValue;DelEdge(v, destvalue);pp = m_VerArr[p].m_list;}//覆盖m_NumVertex--;m_VerArr[p].m_VerValue = m_VerArr[m_NumVertex--].m_VerValue;//修改Edge* q = nullptr;pp = m_VerArr[p].m_list;while (pp != nullptr){int k = pp->m_destindex;q = m_VerArr[k].m_list;while (q){if (q->m_destindex == m_NumVertex){q->m_destindex = p;break;}q = q->m_next;}pp = pp->m_next;}
}

删除边

void GraphLink::DelEdge(char v1, char v2)
{int p1 = GetVertexIndex(v1);int p2 = GetVertexIndex(v2);if (p1 == -2 || p2 == -1)return;//在p1里面删p2Edge* pf = m_VerArr[p1].m_list;if (m_VerArr[p1].m_list->m_destindex == p2){m_VerArr[p1].m_list = m_VerArr[p1].m_list->m_next;delete pf;pf = nullptr;}else{while (pf->m_next->m_destindex != p2 && pf != nullptr){pf = pf->m_next;}if (pf == nullptr)return;Edge* p = pf->m_next;pf->m_next = p->m_next;delete p;p = nullptr;}//v2->v1pf = m_VerArr[p2].m_list;if (m_VerArr[p2].m_list->m_destindex == p1){m_VerArr[p2].m_list = m_VerArr[p2].m_list->m_next;delete pf;pf = nullptr;}else{while (pf->m_next->m_destindex != p1 && pf != nullptr){pf = pf->m_next;}if (pf == nullptr)return;Edge* p = pf->m_next;pf->m_next = p->m_next;delete p;p = nullptr;}m_NumEdge--;
}

输出：


void GraphLink::PrintGraph()
{Edge* p = nullptr;for (int i = 0; i < m_NumVertex; i++){cout << i << " " << m_VerArr[i].m_VerValue << " ";p = m_VerArr[i].m_list;while (p){cout << p->m_destindex << "->";p = p->m_next;}cout << "nul" << endl;}cout << endl;
}