花 风 城市

邻接矩阵（C++实现）

#define MAXV 10    //最大节点个数
#define INF 32767	//定义无穷大

typedef struct
{
	int no;
	int info;
}VertexType;//存放定点信息 
typedef struct
{
	int edges[MAXV][MAXV];//邻接数组
	int n, e;//顶点数，边数
	VertexType vexs[MAXV];//顶点数组
}MatGraph;//图邻接矩阵类型

void CreatMat(MatGraph &g, int A[MAXV][MAXV], int n, int e){
	g.n = n; g.e = e;
	for(int i = 0; i < n; ++i)
		for(int j = 0; j < n; ++j)
			g.edges[i][j] = A[i][j];
}

void DisplayMat(MatGraph G){
	cout << "邻接矩阵:" << endl;
	for(int i = 0; i < G.n; i++)
	{ 
		for (int j = 0; j < G.n; j++)
		{
			if (G.edges[i][j] == INF)
				cout << "∞   ";
			else
				cout << G.edges[i][j] << "   ";
		}
		cout << endl;
	}
	cout << endl;
}

邻接表（C++实现）

typedef struct Anode
{
	int no;//该节点编号
	int weight;//该边的信息，如权值
	struct Anode *nextarc;//指向下一个节点的指针
}ArcNode;//邻接表边类型 即指向结点的边
typedef struct Vnode
{
	char info;//头结点信息  注意不是结点编号
	ArcNode *firstarc;//指向第一个邻接点的指针
}VNode;//邻接表头节点类型
typedef struct
{
	VNode adjlist[MAXV];//顶点数组  MAXV：最大结点数
	int n, e;//n：顶点数
}AdjGraph;//图邻接表类型

void CreatAdj(AdjGraph *&G, int A[MAXV][MAXV], int n, int e){

G = (AdjGraph *)malloc(sizeof(AdjGraph));
	G->n = n; G->e = e;
	for(int i = 0; i < n; ++i)
		G->adjlist[i].firstarc = NULL;

for(int i = 0; i < n; ++i)
		for(int j = 0; j < n; ++j)
			if(A[i][j] != 0 && A[i][j] != INF){
				ArcNode *p = (ArcNode *)malloc(sizeof(ArcNode));
				p->no = j;//notice**
				p->weight = A[i][j];

ArcNode *r = NULL;
				r = G->adjlist[i].firstarc;

p->nextarc = G->adjlist[i].firstarc;//头插法,顺序和数组是反的 
				G->adjlist[i].firstarc = p;//这里用不了尾插，因为没有头结点 
			}
}

void DisplayAdj(AdjGraph *G){
	cout << "adjacent graph: " << endl;
	for(int i = 0; i < G->n; ++i){
		cout << "node " << i << ": ";
		ArcNode *p = G->adjlist[i].firstarc;
		while(p != NULL){
			cout << p->no << "[weight: "<< p->weight <<"] ";
			p = p->nextarc;
		}
		cout << endl;
	}
	cout << endl;
}

void Destroy(AdjGraph *&G)
{
	ArcNode *q;
	for (int i = 0; i < G->n; i++)
	{
		ArcNode *p = G->adjlist[i].firstarc;

while (p != NULL)
		{
			q = p;
			p = p->nextarc;
			free(q);
			q = NULL;
		}
	}
	free(G);
	G = NULL;
	cout << "Destroy adjacent Graph..." << endl;
}

int maxsize = 100;

void BFS(AdjGraph *G, int v){
	int visit[MAXV] = {0};
	int queue[MAXV], front = 0, rear = 0;
	visit[v] = 1; cout << v << " ";
	rear = (rear + 1) % maxsize;
	queue[rear] = v;
	while(front != rear){
		front = (front + 1) % maxsize;
		int tmp = queue[front];
		ArcNode *p = G->adjlist[tmp].firstarc;
		while(p != NULL){
			if(visit[p->no] == 0){
				cout << p->no << " ";
				visit[p->no] = 1;
				rear = (rear + 1) % maxsize;
				queue[rear] = p->no;
			}
			p = p->nextarc;
		}
	}
}

void DFS(AdjGraph *G, int v){	
	visit_DFS[v] = 1; cout << v << " ";
	ArcNode *p = G->adjlist[v].firstarc;
	while(p != NULL){
		if(visit_DFS[p->no] == 0)
			DFS(G, p->no);
		else//当前结点已访问 
			p = p->nextarc; 
	}
} 

MatGraph g;// Matrix Graph
AdjGraph *G;//Adjacent Graph
int A[MAXV][MAXV] = {
	{0,   5,   INF, 7,   INF, INF},
	{INF, 0,   4,   INF, INF, INF},
	{8,   INF, 0,   INF, INF, 9  },
	{INF, INF, 5,   0,   INF, 6  },
	{INF, INF, INF, 5,   0,   INF},
	{3,   INF, INF, INF, 1,   0  },
};//directed graph
int A2[MAXV][MAXV] = {
	{0, 1,   1,   1},
	{1, 0,   INF, 1},
	{1, INF, 0,   1},
	{1, 1,   1,   0}
};//无向图
int n = 4, e = 5;
CreatMat(g, A2, n, e);
//DisplayMat(g);
CreatAdj(G, A2, n, e);
//DisplayAdj(G);

邻接表（Java实现）

package com.space.algorithm.graph;

import java.util.ArrayList;
import java.util.Stack;

public class AdjGraph {

private static final int INF = 999999999;//表示两点之间没有边

static final int n = 4;
    static final int e = 5;

static class Graph {
        ArrayList<Vnode> adjList;
        int n, e;

Graph(int n, int e, ArrayList<Vnode> adjList) {
            this.n = n;
            this.e = e;
            this.adjList = adjList;
        }
    }

static class Vnode {
        int no;
        ArcNode firstArc;
    }

static class ArcNode {
        int weight;
        int no;
        ArcNode nextArc;

ArcNode(int weight) {
            this.weight = weight;
        }
    }

public static void main(String[] args) {
        int[][] arr = {
                {0, 1, 1, 1},
                {1, 0, INF, 1},
                {1, INF, 0, 1},
                {1, 1, 1, 0}
        };//this is an undirected graph with 4 vertex and 5 edge
        Graph graph = createAdj(arr, 4, 5);
//        displayAdj(graph);
//        dfs(graph, 1);
        bfs(graph, 1);
    }

public static Graph createAdj(int[][] arr, int n, int e) {
        Graph graph = new Graph(n, e, new ArrayList<>());
        for (int i = 0; i < n; ++i) graph.adjList.add(new Vnode());
        for (int i = 0; i < n; ++i) {
            for (int j = 0; j < n; ++j) {
                if (arr[i][j] != INF && arr[i][j] != 0) {
                    ArcNode arcNode = new ArcNode(arr[i][j]);//初始化边
                    arcNode.no = j;
                    if (graph.adjList.get(i).firstArc == null) {
                        graph.adjList.get(i).firstArc = arcNode;
                    } else {
//                        ArcNode p = graph.adjList.get(i).firstArc;
//                        while (p.nextArc != null) p = p.nextArc;
//                        p.nextArc = arcNode;
                        arcNode.nextArc = graph.adjList.get(i).firstArc;
                        graph.adjList.get(i).firstArc = arcNode;
                    }
                }
            }
        }
        return graph;
    }

public static void displayAdj(Graph graph) {
        for (int i = 0; i < graph.n; ++i) {
            System.out.print("no:" + i + " :: ");
            ArcNode arc = graph.adjList.get(i).firstArc;
            while (arc != null) {
                System.out.print("no:" + arc.no + " --> ");
                arc = arc.nextArc;
            }
            System.out.println();
        }
    }

static int[] dfs_visited = new int[n];

public static void dfs(Graph graph, int v){
        dfs_visited[v] = 1;
        System.out.print(v + " ");
        ArcNode arc = graph.adjList.get(v).firstArc;
        while (arc != null){
            if(dfs_visited[arc.no] == 0) dfs(graph, arc.no);
            else arc = arc.nextArc;
        }
    }

public static void bfs(Graph graph, int v) {
        int[] visited = new int[graph.n];
        int[] queue = new int[graph.n];
        int front = 0, rear = 0;
        visited[v] = 1;
        System.out.print(v + " ");
        rear = (rear + 1) % graph.n;
        queue[rear] = v;
        while (front != rear) {
            front = (front + 1) % graph.n;
            int t = queue[front];
            ArcNode arcNode = graph.adjList.get(t).firstArc;
            while (arcNode != null) {
                if (visited[arcNode.no] == 0) {
                    visited[arcNode.no] = 1;
                    System.out.print(arcNode.no + " ");
                    rear = (rear + 1) % graph.n;
                    queue[rear] = arcNode.no;
                } 
                arcNode = arcNode.nextArc;
            }
        }
    }


    static int vn = 0, en = 0;

static int isTree(Graph graph) {

for (int i = 0; i < graph.n; i++) {
            dfs_visited[i] = 0;
        }
        dfs2(graph, 0, vn, en);
        System.out.println();
        System.out.println("vn: " + vn + "  en: " + en);
        if (vn == graph.n && en / 2 == graph.n - 1) return 1;
        else return 0;
    }

static void dfs2(Graph graph, int v, int vn, int en) {
        dfs_visited[v] = 1;
        vn++;

//		System.out.print(v + " ");
        ArcNode a = graph.adjList.get(v).firstArc;
        while (a != null) {
            en++;
            System.out.println("en: " + en);
            if (dfs_visited[a.no] == 0) {
                dfs2(graph, a.no, vn, en);
            } else a = a.nextArc;
        }
    }
}