无向图邻接表基础操作

### 创建无向图邻接表 为了创建一个无向图的邻接表，首先需要定义两个结构体来表示顶点和边。顶点结构体通常包含指向第一个相邻节点的指针；而边则由弧结点构成，每个弧结点存储下一个连接到相同起点的目标节点的信息。 ```c typedef struct ArcNode { int adjvex; /* 邻接点域 */ struct ArcNode *nextarc; /* 指向下一条弧的指针 */ } ArcNode; typedef struct VNode { char data; ArcNode *firstarc; /* 边表头指针 */ } AdjList[MAX_VERTEX_NUM], ALGraph; ``` 接着初始化图并分配空间给各个顶点[^1]： ```c void CreateALGraph(ALGraph *&G) { G=(ALGraph *)malloc(sizeof(ALGraph)); } ``` 当要添加新的顶点时，只需简单地设置`data`字段并将`firstarc`置为空即可。 对于增加边的操作，则是在对应的源顶点处新增加一个含有目标顶点编号的新弧结点，并将其链接入已有的链表之中[^2]。 ### 打印边链表 通过遍历整个邻接列表可以方便地输出所有的边信息。这涉及到访问每一个顶点及其相连的所有其他顶点。 ```c void PrintArcs(const ALGraph *G){ for (int i=0;i<G->n;++i){ // 对于每个顶点... printf("%d:",i); for(ArcNode* p=G[i].firstarc;p!=NULL;p=p->nextarc) printf(" -> %d",p->adjvex); // 输出其所有邻居 puts(""); } } ``` 上述函数会依次显示每条记录下的关联关系。 ### 深度优先遍历(DFS) 深度优先搜索是从某个未被访问过的起始位置出发尽可能深入探索直到不能再前进为止再回溯的过程。为此，在执行前需标记哪些地方已经被走过以免重复处理同一地点。 ```c static void DFS_Visit(int v, bool visited[], const ALGraph *g); void DFSTraverse(ALGraph *G){ bool visited[G->n]; memset(visited,false,sizeof(bool)*G->n); for(int i=0;i<G->n;i++) if(!visited[i]) DFS_Visit(i,visited,G); } static void DFS_Visit(int v,bool visited[],const ALGraph*g){ printf("%d ",v); visited[v]=true; for(ArcNode*p=g->adjlist[v].firstarc;p!=nullptr;p=p->nextarc) if (!visited[p->adjvex]) DFS_Visit(p->adjvex,visited,g); } ``` 这段代码实现了对整张图表进行完整的深搜扫描。 ### 广度优先搜索(BFS) 不同于DFS,BFS总是先考察离当前最近的一层节点然后再考虑更远距离上的那些。因此需要用到队列辅助完成这一层次化扩展过程。 ```c void BFSTraverse(ALGraph *G){ std::queue<int> q; bool visited[G->n];memset(visited, false, sizeof(bool)*G->n); for(int i=0;i<G->n;i++){ if(!visited[i]){ visited[i]=true;q.push(i); while(!q.empty()){ auto u=q.front();q.pop(); printf("%d ",u); for(auto p=G->adjlist[u].firstarc;p!=nullptr;p=p->nextarc){ if(!visited[p->adjvex]){ visited[p->adjvex]=true; q.push(p->adjvex); } } } } } } ``` 此部分展示了如何利用BFS算法全面覆盖一张连通或不完全联通的地图上所有可达之处。