图的创建(邻接表存储结构):建立图的邻接表存储并在此基础上实现图的深度优先遍历和广度优先遍历。使用c语言
时间: 2024-06-18 12:05:35 浏览: 126
在邻接表存储结构中,我们可以采用一个一维数组和一个链表数组来表示图。其中,一维数组的每个元素表示一个顶点,链表数组则用于表示该顶点所连向的其他顶点。因此,我们可以定义如下结构体:
```
typedef struct EdgeNode{
int adjvex; // 邻接点域,存储该顶点对应的下标
struct EdgeNode *next; // 链域,指向下一个邻接点
}EdgeNode;
typedef struct VertexNode{
int data; // 顶点域,存储顶点信息
EdgeNode *first_edge; // 边表头指针
}VertexNode, AdjList[MAX_VERTEX_NUM];
typedef struct{
AdjList adj_list; // 图的邻接表
int vex_num, edge_num; // 图的当前顶点数和边数
}GraphAdjList;
```
建立图的邻接表存储结构需要先创建一个空表,然后再逐个插入各个顶点及其相邻顶点。具体操作如下:
```
void CreateGraph(GraphAdjList *G){
int i, j, k;
EdgeNode *e;
printf("请输入图的顶点数和边数:");
scanf("%d %d", &G->vex_num, &G->edge_num);
printf("请输入每个顶点的值:");
for(i=0; i<G->vex_num; i++){
scanf("%d", &G->adj_list[i].data);
G->adj_list[i].first_edge = NULL; // 将边表头指针初始化为空
}
printf("请输入每条边依附的两个顶点序号:\n");
for(k=0; k<G->edge_num; k++){
scanf("%d %d", &i, &j);
e = (EdgeNode*)malloc(sizeof(EdgeNode));
e->adjvex = j;
e->next = G->adj_list[i].first_edge;
G->adj_list[i].first_edge = e;
e = (EdgeNode*)malloc(sizeof(EdgeNode));
e->adjvex = i;
e->next = G->adj_list[j].first_edge;
G->adj_list[j].first_edge = e;
}
}
```
至于深度优先遍历和广度优先遍历的实现,可以参考以下代码:
```
int visited[MAX_VERTEX_NUM];
void DFS(GraphAdjList G, int v){
EdgeNode *e;
visited[v] = 1;
printf("%d ", G.adj_list[v].data);
e = G.adj_list[v].first_edge;
while(e){
if(!visited[e->adjvex]){
DFS(G, e->adjvex);
}
e = e->next;
}
}
void DFSTraverse(GraphAdjList G){
int i;
for(i=0; i<G.vex_num; i++){
visited[i] = 0;
}
for(i=0; i<G.vex_num; i++){
if(!visited[i]){
DFS(G, i);
}
}
}
void BFSTraverse(GraphAdjList G){
int i, j;
EdgeNode *e;
Queue Q;
for(i=0; i<G.vex_num; i++){
visited[i] = 0;
}
InitQueue(&Q);
for(i=0; i<G.vex_num; i++){
if(!visited[i]){
visited[i] = 1;
printf("%d ", G.adj_list[i].data);
EnQueue(&Q, i);
while(!QueueEmpty(Q)){
DeQueue(&Q, &j);
e = G.adj_list[j].first_edge;
while(e){
if(!visited[e->adjvex]){
visited[e->adjvex] = 1;
printf("%d ", G.adj_list[e->adjvex].data);
EnQueue(&Q, e->adjvex);
}
e = e->next;
}
}
}
}
}
```
阅读全文