输入:256色位图,输出:所有顶点之间的邻接矩阵。要点:
(1) 线段的两个端点叫顶点,所以对曲线要进行折线化处理;
(2) 可用广度优先遍历算法对每个顶点进行处理;
如a12中应是以下结构:
{
顶点1的坐标及RGB值;
顶点2的坐标及RGB值;
这两顶点之间有连线吗?有几条连线?每条连线的RGB值,所以又有一个子结构体纪录这种连接关系;
附加实例
附加实例
附加实例
(1) 线段的两个端点叫顶点,所以对曲线要进行折线化处理;
(2) 可用广度优先遍历算法对每个顶点进行处理;
如a12中应是以下结构:
{
顶点1的坐标及RGB值;
顶点2的坐标及RGB值;
这两顶点之间有连线吗?有几条连线?每条连线的RGB值,所以又有一个子结构体纪录这种连接关系;
附加实例
附加实例
附加实例
设图G的初态是所有顶点均未访问过。在G中任选一顶点v为源点,则广度优先遍历可以定义为:首先访问出发点v,接着依次访问v的所有邻接点w1,w2,…,wt,然后再依次访问与wl,w2,…,wt邻接的所有未曾访问过的顶点。依此类推,直至图中所有和源点v有路径相通的顶点都已访问到为止。此时从v开始的搜索过程结束。
若G是连通图,则遍历完成;否则,在图C中另选一个尚未访问的顶点作为新源点继续上述的搜索过程,直至G中所有顶点均已被访问为止。
广度优先遍历类似于树的按层次遍历。采用的搜索方法的特点是尽可能先对横向进行搜索,故称其为广度优先搜索(Breadth-FirstSearch)。相应的遍历也就自然地称为广度优先遍历。2、广度优先搜索过程
在广度优先搜索过程中,设x和y是两个相继要被访问的未访问过的顶点。它们的邻接点分别记为x1,x2,…,xs和y1,y2,…,yt。
为确保先访问的顶点其邻接点亦先被访问,在搜索过程中使用FIFO队列来保存已访问过的顶点。当访问x和y时,这两个顶点相继入队。此后,当x和y相继出队时,我们分别从x和y出发搜索其邻接点x1,x2,…,xs和y1,y2,…,yt,对其中未访者进行访问并将其人队。这种方法是将每个已访问的顶点人队,故保证了每个顶点至多只有一次人队。3、广度优先搜索算法
(1)邻接表表示图的广度优先搜索算法
void BFS(ALGraph*G,int k)
{// 以vk为源点对用邻接表表示的图G进行广度优先搜索
int i;
CirQueue Q; //须将队列定义中DataType改为int
EdgeNode *p;
InitQueue(&Q);//队列初始化
//访问源点vk
printf("visit vertex:%e",G->adjlist[k].vertex);
visited[k]=TRUE;
EnQueue(&Q,k);//vk已访问,将其人队。(实际上是将其序号人队)
while(!QueueEmpty(&Q)){//队非空则执行
i=DeQueue(&Q); //相当于vi出队
p=G->adjlist[i].firstedge; //取vi的边表头指针
while(p){//依次搜索vi的邻接点vj(令p->adjvex=j)
if(!visited[p->adivex]){ //若vj未访问过
printf("visitvertex:%c",C->adjlistlp->adjvex].vertex); //访问vj
visited[p->adjvex]=TRUE;
EnQueue(&Q,p->adjvex);//访问过的vj人队
}//endif
p=p->next;//找vi的下一邻接点
}//endwhile
}//endwhile
}//end of BFS
(1) 线段的两个端点叫顶点,所以对曲线要进行折线化处理;
(2) 可用广度优先遍历算法对每个顶点进行处理;
如a12中应是以下结构:
{
顶点1的坐标及RGB值;
顶点2的坐标及RGB值;
这两顶点之间有连线吗?有几条连线?每条连线的RGB值,所以又有一个子结构体纪录这种连接关系;
高手呢????????????
??????????????????
????????
(1) 线段的两个端点叫顶点,所以对曲线要进行折线化处理;
(2) 可用广度优先遍历算法对每个顶点进行处理;
如a12中应是以下结构:
{
顶点1的坐标及RGB值;
顶点2的坐标及RGB值;
这两顶点之间有连线吗?有几条连线?每条连线的RGB值,所以又有一个子结构体纪录这种连接关系;
高手呢????????????
??????????????????
????????