prog1.c

图的遍历:图是由顶点集合(vertex)及顶点间的关系集合组成的一种数据结构:Graph＝( V, E ).使用拓扑排序的算法.

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include "mynode.h"
node_ptr *g;
int n_vertices;
void add_edge(int end, int start)
{
    node_ptr new1 = create();
    new1->next = NULL;
    new1->to_vertex = end;
    insert_in_order_node(end, g[start]);
    return;
}

void TopologicalSort () {
    int *indegree;
    int *count;
    int i, j, top = -1;
    node_ptr p = create();
    indegree = malloc(n_vertices * sizeof(int));
    count = malloc(n_vertices * sizeof(int));
    /*结点=顶点*/
    /*入度为零的顶点栈初始化*/
    for(i = 0; i < n_vertices; i++)
        indegree[i] = 0;
    /*计算所有的顶点共有多少边*/
    for(i = 0; i < n_vertices; i++)
        for(p = g[i]->next; p != NULL ; p = p->next)
        {
           indegree[p->to_vertex]++;
        }
    /*入度为零顶点进栈，就是把所有没有边的顶点纪录小来*/
    for ( i = 0; i < n_vertices; i++ )
        if ( indegree[i] == 0 ) { count[i] = top;  top = i; }
    /*Print first 零顶点，没有边的定点*/
    printf("V[%d] ", g[top]->to_vertex);
    /*期望输出n个顶点, soft*/
    for ( i = 0; i < n_vertices; i++ )
    {
        if ( top == -1 ){
            /*中途栈空,转出*/
            printf("wrong\n");
	        return;
        }
        else{
            /*继续拓扑排序, if not worng*/
	        j = top;
            top = indegree[top];
            p = g[j]->next;
            while(p!=NULL)
            {
                j = p->to_vertex;
	            if ( --indegree[j]==0 )
                {
                    indegree[j] = top;
                    top = j;
                    printf("V[%d] ", g[j]->to_vertex);
                }
 	            p = p->next;
            }	        
        }
    }
    return;
}

int main(){
    int graphno=0, i=0, egdeno=0, j=0, egde=0;
    n_vertices=0;
    printf("\nPlease give a number, (max:1000): ");
    scanf("%d",&graphno);/*输入有几个顶点*/
    if (graphno > MAXQUEUE) graphno = MAXQUEUE;
    g = (node_ptr *) malloc(graphno * sizeof(struct node));/*create a emptry array list*/
    /*initialisation*/
    for(i=0;i<graphno;i++){
        g[i] = create();
        g[i]->to_vertex = i;
        g[i]->next=NULL;
        n_vertices++;
    }
    for (i=0;i<graphno;i++){
        printf("\n No : %d:. How many egde you will give? ", i);
        scanf("%d",&egdeno);/*输入有多少边*/
        if (egdeno == 0){
           add_edge(0, i);/*输入为0就initialisation NULL*/
        }
        else{
             for (j=0;j<egdeno;j++){
                 printf("\n No : %d:. Please input a number? ", i);
                 scanf("%d",&egde);
                 add_edge(egde, i);/*创建新的边*/
             }
        }
    }
    printf("\n================================================\n");
    TopologicalSort();/*Topological Sort*/
    scanf("%d",&egdeno);/*not using, just let sysetm stop to watch result*/
    return 0;
}