结构
//顶点结构
typedef struct Vnode
{
Vertex data; //顶点信息
ArcNode *firstarc; //指向第一条边
} VNode;
//边头结点结构
typedef struct ANode
{
int adjvex; //该边的终点编号
struct ANode *nextarc; //指向下一条边的指针
InfoType info; //该边的权值等信息
} ArcNode;
//图结构
typedef struct
{
VNode adjlist[MAXV]; //邻接表
int n, e; //图中顶点数n和边数e
} ALGraph;
int Visited[MAXV] = {0};
深度优先搜索
void DFS(ALGraph *G,int v)
{
printf("%d", v);//访问该节点
Visited[v] = 1;//标记该节点被访问
ArcNode* p_EdgeNode = G->adjlist[v].firstarc;//v的第条一相邻边的边头节点
while (p_EdgeNode != NULL)//v访问所有的相邻边
{
int w = p_EdgeNode->adjvex;//v相邻边的定点下标
if (Visited[w] == 0)//w尚未本被访问,递归遍历以w起始部分
DFS(G,w);
p_EdgeNode = p_EdgeNode->nextarc;//指向顶点v的下一条边的边头节点
}
}
广度优先搜索
void BFS(ALGraph *G, int v)
{
ArcNode *p; int w, i;
int queue[MAXV], front = 0, rear = 0; //定义循环队列
int visited[MAXV];
for (int i = 0; i < MAXV; i++)//初始化
visited[i] = 0;
//访问第一个节点
printf("%d\n",v);
visited[v] = 1;
//v进队列
rear = (rear + 1) % MAXV;
queue[rear] = v;
while (rear != front)//queue不空
{
//队头节点出队
front = (front + 1) % MAXV;
w = queue[front];
ArcNode* p = G->adjlist[w].firstarc;//w的相邻节点
while (p != NULL)//层序
{
if (visited[p->adjvex] == 0)//尚未访问
{
//访问
printf("%d\n",p->adjvex);
visited[p->adjvex] = 1;
//入队
rear = (rear + 1) % MAXV;
queue[rear] = p->adjvex;
}
p = p->nextarc; //找下一个邻接顶点
}
}
}
