package examples;
import adjlist.AdjList;
import adjlist.OpAdjList;
public class Example7_9 {
public static void main(String[] args) {
        AdjList g;                    
        int p;
        int i;
        int m[][] = {{0,1,1,0,0},{1,0,0,1,1},{1,0,0,0,0},{0,1,0,0,1},{0,1,0,1,0}};
        g = OpAdjList.CreateGraph(m, 5);
        System.out.printf("\n1:\n");
        OpAdjList.DispGraph(g);                    
        System.out.printf("\n\n\n2:\n");
        for(i=0;i<g.vexs;i++)
        {
            p=OpAdjList.GetFirst(g,i);
            if(p!=-1)    
                System.out.printf("\nLine%d\t[%d]",i,p);
            else    
                System.out.printf("\nLine%d",i);
            while(p!=-1)
            {
                p=OpAdjList.GetNext(g,i,p); 
                if(p!=-1)    
                    System.out.printf("\t[%d]",p);
            }
        }
    }
}

package adjlist;

/* 邻接表类型 */
public class AdjList {
    public static final int MAXVEX = 50;

    /* 顶点表 */
    public VexNode lists[] = new VexNode[MAXVEX ];
    /* 边数，顶点数 */
    public int edges, vexs;
}

/* 边表结点类型 */
class ArcNode {
    /* 顶点序号 */
    int adjvex = 0;
    /* 指向下一个邻接点 */
    ArcNode next;
}

/* 顶点表结点类型 */
class VexNode {
    /* 顶点信息 */
    int data;
    /* 边表头指针 */
    ArcNode head ;
}

package adjlist;

public class OpAdjList {

/*    public static AdjList CreateGraph(int m[][], int n) {
        return CreateGraph(m, n);
    }*/

    public static boolean DispGraph(AdjList g) {
        return DispGraph1(g);
    }

    public static int GetFirst(AdjList g, int k) {
        return GetFirst(g, k);
    }
    public static int GetNext(AdjList g, int k, int u) {
        return  GetNext1(g, k, u) ;
    }

    /* 算法7-9创建邻接表 */
public static AdjList CreateGraph(int m[][], int n) {
        int i, j;
        ArcNode p;
        AdjList g = new AdjList();

        g.edges = 0;
        g.vexs = n;
        for (i = 0; i < n; i++) {
            g.lists[i].head = null;

            for (j = n - 1; j >= 0; j--) {
                if (m[i][j] != 0) {
                    p = new ArcNode();
                    p.adjvex = j;
                    p.next = g.lists[i].head;
                    g.lists[i].head = p;
                    g.edges++;
                }
            }
        }
        return g;
    }

    /* 算法7-10显示邻接表 */
    private static boolean DispGraph1(AdjList g) {
        int i;
        ArcNode p;
        for (i = 0; i < g.vexs; i++) {
            System.out.printf("\nLine%d:\t", i);
            p = g.lists[i].head;
            while (p != null) {
                System.out.printf("[%d]\t", p.adjvex);
                p = p.next;
            }
        }
        return true;
    }

    /* 算法7-11第一个邻接点 */
    private static int GetFirst1(AdjList g, int k) {
        if (k < 0 || k > g.vexs) {
            System.out.printf("参数k超出范围！\n");
            return -1;
        }
        if (g.lists[k].head == null)
            return -1;
        else
            return g.lists[k].head.adjvex;
    }

    /* 算法7-12下一个邻接点 */
    private static int GetNext1(AdjList g, int k, int u) {
        ArcNode p;
        if (k < 0 || k > g.vexs || u < 0 || u > g.vexs) {
            System.out.printf("参数k或u超出范围！\n");
            return -1;
        }

        p = g.lists[k].head;
        while (p.next != null && p.adjvex != u)
            p = p.next;
        if (p.next == null)
            return -1;
        else
            return p.next.adjvex;
    }
}