数据结构学习笔记(21)"/>
C语言数据结构学习笔记(21)
/*
AOV网拓扑排序
输出结果：
请输入图的顶点和弧的个数: 6 7
请输入第1个顶点的信息: V0
请输入第2个顶点的信息: V1
请输入第3个顶点的信息: V2
请输入第4个顶点的信息: V3
请输入第5个顶点的信息: V4
请输入第6个顶点的信息: V5
请输入第1条弧对应的弧尾和弧头下标及弧的权值: 0 1 1
请输入第2条弧对应的弧尾和弧头下标及弧的权值: 0 2 4
请输入第3条弧对应的弧尾和弧头下标及弧的权值: 0 3 2
请输入第4条弧对应的弧尾和弧头下标及弧的权值: 1 2 3
请输入第5条弧对应的弧尾和弧头下标及弧的权值: 2 4 6
请输入第6条弧对应的弧尾和弧头下标及弧的权值: 4 3 5
请输入第7条弧对应的弧尾和弧头下标及弧的权值: 5 2 7
邻接表:
0 V0-->3 2-->2 4-->1 1-->NULL
1 V1-->2 3-->NULL
3 V2-->4 6-->NULL
2 V3-->NULL
1 V4-->3 5-->NULL
0 V5-->2 7-->NULL
DFS:V0 V3 V2 V4 V1 V5
BFS:V0 V3 V2 V1 V4 V5
拓扑排序:V5 V0 V1 V2 V4 V3
请按任意键继续. . .
*/
# include <stdio.h>
# include <stdlib.h>
# define VEXMAX 20
# define SIZE 5
typedef int EdgeType;
typedef char VertexType[SIZE];
typedef struct EdgeNode{
int adjvex;//对应顶点下标
EdgeType info;//权值
struct EdgeNode * next;//指向下一个邻接点
}EdgeNode;
typedef struct VertexNode{
int in;//顶点的入度个数
VertexType data;//顶点的数据
EdgeNode * firstedge;//边表指针
}VertexNode, AdjList[VEXMAX];
typedef struct GraphAdjList{
AdjList adjList;//顶点表
int vexNum, edgeNum;//顶点及弧的个数
}GraphAdjList;
int visited[VEXMAX];//标志是否已经访问过
void CreataGraphAdjList(GraphAdjList * G);//创建有向网图
void PrintGraphAdjList(GraphAdjList G);//打印邻接表
void DFSTraverse(GraphAdjList G);//深度优先遍历图
void DFS(GraphAdjList G, int i);//深度优先递归
void BFSTraverse(GraphAdjList G);//广度优先遍历图
void BFS(GraphAdjList G, int start);//广度遍历
void TopologicalSort(GraphAdjList G);//拓扑排序
void DestoryGraphAdjList(GraphAdjList * G);//销毁图
int main(void)
{
GraphAdjList G;
CreataGraphAdjList(&G);
PrintGraphAdjList(G);
DFSTraverse(G);
BFSTraverse(G);
TopologicalSort(G);
DestoryGraphAdjList(&G);
system("pause");
return 0;
}
void CreataGraphAdjList(GraphAdjList * G)
{
int i, j, k, w;
printf("请输入图的顶点和弧的个数: ");
scanf("%d %d", &G->vexNum, &G->edgeNum);
for(i = 0; i < G->vexNum; i++)
{
printf("请输入第%d个顶点的信息: ", i+1);
scanf("%s", &G->adjList[i].data);
G->adjList[i].firstedge = NULL;
G->adjList[i].in = 0;
}
for(k = 0; k < G->edgeNum; k++)
{
printf("请输入第%d条弧对应的弧尾和弧头下标及弧的权值: ", k+1);
scanf("%d %d %d", &i, &j, &w);
EdgeNode * New = (EdgeNode*)malloc(sizeof(EdgeNode));
New->adjvex = j;
New->info = w;
New->next = G->adjList[i].firstedge;
G->adjList[i].firstedge = New;
G->adjList[j].in++;
}
}
void PrintGraphAdjList(GraphAdjList G)
{
printf("邻接表:\n");
for(int i = 0; i < G.vexNum; i++)
{
printf("%d ", G.adjList[i].in);
printf("%s-->", G.adjList[i].data);
EdgeNode * p = G.adjList[i].firstedge;
while(p)
{
printf("%d %d-->", p->adjvex, p->info);
p = p->next;
}
printf("NULL\n");
}
}
void DFSTraverse(GraphAdjList G)
{
printf("DFS:");
int i;
for(i = 0; i < G.vexNum; i++)
visited[i] = 0;
for(i = 0; i < G.vexNum; i++)
if(!visited[i])
DFS(G, i);
printf("\n");
}
void DFS(GraphAdjList G, int i)
{
visited[i] = 1;
printf("%s ", G.adjList[i].data);
EdgeNode * p = G.adjList[i].firstedge;
while(p)
{
if(!visited[p->adjvex])
DFS(G, p->adjvex);
p = p->next;
}
}
void BFSTraverse(GraphAdjList G)
{
printf("BFS:");
int i;
for(i = 0; i < G.vexNum; i++)
visited[i] = 0;
for(i = 0; i < G.vexNum; i++)
if(!visited[i])
BFS(G, i);
printf("\n");
}
void BFS(GraphAdjList G, int start)
{
int i;
EdgeNode * p = NULL;
int Queue[VEXMAX];
int front = 0, rear = 0;
for(i = start; i < G.vexNum; i++)
{
if(!visited[i])
{
printf("%s ", G.adjList[i].data);
visited[i] = 1;
rear = (rear + 1) % VEXMAX;
Queue[rear] = i;
while(rear != front)
{
front = (front + 1) % VEXMAX;
i = Queue[front];
//printf("%s ", G.adjList[i].data);
p = G.adjList[i].firstedge;
while(p)
{
if(!visited[p->adjvex])
{
printf("%s ", G.adjList[p->adjvex].data);
visited[p->adjvex] = 1;
rear = (rear + 1) % VEXMAX;
Queue[rear] = p->adjvex;
}
p = p->next;
}
}
}
}
}
void TopologicalSort(GraphAdjList G)
{
printf("拓扑排序:");
int i;
int cnt = 0;
EdgeNode * p = NULL;
int Stack[VEXMAX];
int top = -1;
for(i = 0; i < G.vexNum; i++)
{
if(!G.adjList[i].in)
Stack[++top] = i;
}
while(top != -1)
{
i = Stack[top--];
printf("%s ", G.adjList[i].data);
cnt++;
p = G.adjList[i].firstedge;
while(p)
{
G.adjList[p->adjvex].in--;
if(0 == G.adjList[p->adjvex].in)
Stack[++top] = p->adjvex;
p = p->next;
}
}
if(cnt < G.vexNum)
printf("有回路，不是AOV网\n");
else
printf("\n");
}
void DestoryGraphAdjList(GraphAdjList * G)
{
for(int i = 0; i < G->vexNum; i++)
{
EdgeNode * p = G->adjList[i].firstedge;
while(p)
{
G->adjList[i].firstedge = p->next;
free(p);
p = G->adjList[i].firstedge;
}
G->adjList[i].firstedge = NULL;
}
}
更多推荐
C语言数据结构学习笔记(21)
发布评论