简述了图的操作
void BFSTraverse(OLGraph G){
queue <int> q;
for (int v=0; v<G.vexnum; ++v)
visited[v] = false; //初始化访问标志
//q.InitQueue(); // 置空的辅助队列Q
for ( v=0; v<G.vexnum; ++v )
if ( !visited[v]) { // v 尚未访问
visited[v] = true;
printf("%c",G.xlist[v].data) ;
printf(" "); // 访问u
q.push(v); // v入队列
while (!q.empty()) {
int u;
u=q.front(); // 队头元素出队并置为u
for(int w=firstAdjvex(G, u); w>=0; w=nextAdjvex(G))
if ( ! visited[w]) {
visited[w]=true;
printf("%c",G.xlist[w].data) ;
printf(" "); // 访问u
q.push(w); // 访问的顶点w入队列
} // if
} // while
}
} // BFSTraverse
/************************************************************************/
/* 深度优先搜索—非连通图 */
/************************************************************************/
void DFS(OLGraph G, int v) {
// 从顶点v出发，深度优先搜索遍历连通图 G
visited[v] = true;
//cout<<G.xlist[v].data<<" ";
printf("%c",G.xlist[v].data);
printf(" ");
for(int w=firstAdjvex(G, v);w>=0; w=nextAdjvex(G))
if (!visited[w]) DFS(G, w);
// 对v的尚未访问的邻接顶点w递归调用DFS
}
void DFSTraverse(OLGraph G) {
for (int v=0; v<G.vexnum; ++v)
visited[v] = false; // 访问标志数组初始化
for (v=0; v<G.vexnum; ++v) {
if (!visited[v]) DFS(G, v); // 对尚未访问的顶点调用DFS
}
}
/************************************************************************/
/* 图的深度优先生成树 */
/************************************************************************/
void DFSForest(OLGraph &G,int v,CStree T){
//从第v个定点开始深度遍历图，建立生成树
T=NUll;
CSnode p=NULL;
CSnode q=NULL;
for (int v=0; v<G.vexnum; ++v)
visited[v] = false; // 访问标志数组初始化
visited[v] = true; bool first=true;
for(int w=firstAdjvex(G, v);w>=0; w=nextAdjvex(G))
if(!visited[w]){
p=(CStree) malloc (sizeof(CStree));
p.data=G.xlist[v].data;
p.firstchild=NUll;
p.nextsibling=NUll;
if(!T) T=p;
else q.nextsibling=p;
q=p;
DFSTree(G,v,p);
}
}
void DFStree(OLGraph &G,int v,CStree T)
{
CSnode p;
visited[v] = false;bool first=true;
for(int w=firstAdjvex(G, v);w>=0; w=nextAdjvex(G))
if(!visited[w]){
p=(CStree)malloc (sizeof(CSnode));
p.data=G.xlist[w].data;
p.firstchild=NUll;
p.nextsibling=NULL;
}
if(first){
T.
/************************************************************************/
/* 插入节点 */
/************************************************************************/
void InsertVex(OLGraph &G,vertexType v)
{ /* 初始条件: 有向图G存在,v和有向图G中顶点有相同特征 */
/* 操作结果: 在有向图G中增添新顶点v(不增添与顶点相关的弧,留待InsertArc()去做) */
G.xlist[G.vexnum].data=v;
G.xlist[G.vexnum].firstin=G.xlist[G.vexnum].firstout=NULL;
G.vexnum++;
//printf("成功！");
}
/************************************************************************/
/* 插入弧 */
/************************************************************************/
bool InsertArc(OLGraph &G, vertexType vex1, vertexType vex2){
/* if ((G.xlist[LocateVex(G, vex1)].use==0)||(G.xlist[LocateVex(G, vex2)].use==0))
{
printf("要插入的弧对应的节点不存在！！！");
return false;
}*/
arcBox *arcNode = (arcBox *)malloc(sizeof(arcBox));
if(!arcNode) exit(1);
arcNode->tailvex = LocateVex(G, vex1);
arcNode->headvex = LocateVex(G, vex2);
arcNode->tlink = G.xlist[arcNode->tailvex].firstout;
arcNode->hlink = G.xlist[arcNode->headvex].firstin;
G.xlist[arcNode->tailvex].firstout = G.xlist[arcNode->headvex].firstin = arcNode;
G.arcnum++;
return true;
【知识点详解】
本文主要涉及的是图的理论和操作，图是一种数据结构，它由顶点集合和描述顶点间关系的边集合构成。在图的领域中，有以下几个关键概念和算法：
1. **图的定义**：图G由顶点集合V和边集合E组成，通常表示为G=(V,E)。边可以是有向（弧）或无向的。
2. **无向图与有向图**：无向图中，边没有方向，而有向图中的边有明确的方向，即弧头和弧尾。
3. **完全图**：无向完全图中任何两个顶点间都有一条边，有向完全图中任意两个顶点间存在方向相反的两条弧。
4. **稠密图与稀疏图**：稠密图的边数相对于顶点数较多，稀疏图则较少。
5. **顶点的度**：无向图中，顶点的度是与其相连的边数。在有向图中，分为入度（进入该顶点的弧数）和出度（从该顶点出发的弧数）。
6. **图的遍历**：主要有两种遍历方法，深度优先搜索(DFS)和广度优先搜索(BFS)。DFS从一个顶点出发，递归地访问其所有邻接顶点；BFS则使用队列，先访问最近的顶点，然后逐步扩展。
- **DFS**：从一个未访问过的顶点开始，标记已访问，然后访问其所有邻接顶点，并对这些顶点进行递归调用DFS。
- **BFS**：使用队列，从源顶点开始，将其所有邻接顶点入队，然后逐个出队访问，再将它们的邻接顶点入队，直到队列为空。
7. **图的存储结构**：包括邻接矩阵和邻接表。邻接矩阵用二维数组表示，每个元素表示一对顶点之间是否有边；邻接表则为每个顶点维护一个链表，链表包含所有与之相邻的顶点。
8. **图的连通性**：如果图中任意两个顶点都存在路径相连，那么该图是连通的。连通分量是图中最大的连通子图。
9. **生成树**：在一个连通图中，若选取一部分边，使得这些边构成的子图仍然是连通的且包含所有顶点，这样的子图称为该图的生成树。
10. **插入顶点和边**：`InsertVex`函数用于在图中添加新的顶点，`InsertArc`用于添加新的边。插入时需要注意边的指向和顶点的使用状态。
11. **最短路径**：在图中，找到两个顶点之间的路径，使得路径上的边的权值之和最小，这被称为最短路径问题。解决这类问题的算法有Dijkstra算法、Floyd-Warshall算法等。
以上内容是图论的基础知识，理解和掌握这些概念对于处理复杂数据结构问题至关重要。在实际应用中，例如网络路由、社交网络分析、任务调度等领域，图的理论和技术都发挥着重要作用。
