图形是由以下两个组件组成的数据结构： 1. 一组有限的顶点，也称为节点。 2. 称为边的（u，v）形式的有序对的有限集。该对是有序的，因为在有向图（di-graph）的情况下（u，v）与（v，u）不同。这对形状（u，v）表示从顶点u到顶点v有一条边。这些边可能包含重量/价值/成本。 图被用来表示许多现实生活中的应用：图被用来表示网络。网络可以包括城市或电话网络或电路网络中的路径。图形也被用于社交网络，如linkedIn、Facebook。例如，在Facebook中，每个人都用一个顶点（或节点）表示。每个节点都是一个结构，包含个人id、姓名、性别和地区等信息。看见 这 更多关于图形的应用。 下面是一个有5个顶点的无向图的示例。
null
![图片[1]-图及其表示-yiteyi-C++库](https://cdncontribute.geeksforgeeks.org/wp-content/uploads/undirectedgraph.png)
以下两种是图形最常用的表示形式。 1. 邻接矩阵 2. 邻接表 还有其他表示法，如关联矩阵和关联列表。图形表示的选择是根据具体情况而定的。这完全取决于要执行的操作类型和易用性。 邻接矩阵： 邻接矩阵是一个大小为V x V的二维数组，其中V是图中的顶点数。假设2D数组是adj[]]，槽adj[i][j]=1表示从顶点i到顶点j有一条边。无向图的邻接矩阵总是对称的。邻接矩阵也用于表示加权图。如果adj[i][j]=w，那么从顶点i到顶点j有一条带权w的边。
上述示例图的邻接矩阵为：
赞成的意见： 表示更容易实现和遵循。删除边需要O（1）个时间。诸如从顶点“u”到顶点“v”是否有边这样的查询是有效的，可以在O（1）中完成。 欺骗： 消耗更多的空间O（V^2）。即使图是稀疏的（包含较少的边），它也会占用相同的空间。添加顶点是O（V^2）时间。 请看 这 以获取邻接矩阵的Python实现示例。 邻接列表： 使用一组列表。数组的大小等于顶点的数量。让数组为数组[]。条目数组[i]表示与元素相邻的顶点列表 我 第四顶点。这种表示法也可用于表示加权图。边的权重可以表示为对的列表。以下是上图的邻接列表表示。
注意，在下面的实现中，我们使用动态数组（C++/ArrayList中的vector，Java中的vector）来表示邻接列表，而不是链表。矢量实现具有缓存友好的优点。
C++
// A simple representation of graph using STL #include <bits/stdc++.h> using namespace std; // A utility function to add an edge in an // undirected graph. void addEdge(vector< int > adj[], int u, int v) { adj[u].push_back(v); adj[v].push_back(u); } // A utility function to print the adjacency list // representation of graph void printGraph(vector< int > adj[], int V) { for ( int v = 0; v < V; ++v) { cout << " Adjacency list of vertex " << v << " head " ; for ( auto x : adj[v]) cout << "-> " << x; printf ( "" ); } } // Driver code int main() { int V = 5; vector< int > adj[V]; addEdge(adj, 0, 1); addEdge(adj, 0, 4); addEdge(adj, 1, 2); addEdge(adj, 1, 3); addEdge(adj, 1, 4); addEdge(adj, 2, 3); addEdge(adj, 3, 4); printGraph(adj, V); return 0; } |
C
// A C Program to demonstrate adjacency list // representation of graphs #include <stdio.h> #include <stdlib.h> // A structure to represent an adjacency list node struct AdjListNode { int dest; struct AdjListNode* next; }; // A structure to represent an adjacency list struct AdjList { struct AdjListNode* head; }; // A structure to represent a graph. A graph // is an array of adjacency lists. // Size of array will be V (number of vertices // in graph) struct Graph { int V; struct AdjList* array; }; // A utility function to create a new adjacency list node struct AdjListNode* newAdjListNode( int dest) { struct AdjListNode* newNode = ( struct AdjListNode*) malloc ( sizeof ( struct AdjListNode)); newNode->dest = dest; newNode->next = NULL; return newNode; } // A utility function that creates a graph of V vertices struct Graph* createGraph( int V) { struct Graph* graph = ( struct Graph*) malloc ( sizeof ( struct Graph)); graph->V = V; // Create an array of adjacency lists. Size of // array will be V graph->array = ( struct AdjList*) malloc ( V * sizeof ( struct AdjList)); // Initialize each adjacency list as empty by // making head as NULL int i; for (i = 0; i < V; ++i) graph->array[i].head = NULL; return graph; } // Adds an edge to an undirected graph void addEdge( struct Graph* graph, int src, int dest) { // Add an edge from src to dest. A new node is // added to the adjacency list of src. The node // is added at the beginning struct AdjListNode* check = NULL; struct AdjListNode* newNode = newAdjListNode(dest); if (graph->array[src].head == NULL) { newNode->next = graph->array[src].head; graph->array[src].head = newNode; } else { check = graph->array[src].head; while (check->next != NULL) { check = check->next; } // graph->array[src].head = newNode; check->next = newNode; } // Since graph is undirected, add an edge from // dest to src also newNode = newAdjListNode(src); if (graph->array[dest].head == NULL) { newNode->next = graph->array[dest].head; graph->array[dest].head = newNode; } else { check = graph->array[dest].head; while (check->next != NULL) { check = check->next; } check->next = newNode; } // newNode = newAdjListNode(src); // newNode->next = graph->array[dest].head; // graph->array[dest].head = newNode; } // A utility function to print the adjacency list // representation of graph void printGraph( struct Graph* graph) { int v; for (v = 0; v < graph->V; ++v) { struct AdjListNode* pCrawl = graph->array[v].head; printf ( " Adjacency list of vertex %d head " , v); while (pCrawl) { printf ( "-> %d" , pCrawl->dest); pCrawl = pCrawl->next; } printf ( "" ); } } // Driver program to test above functions int main() { // create the graph given in above fugure int V = 5; struct Graph* graph = createGraph(V); addEdge(graph, 0, 1); addEdge(graph, 0, 4); addEdge(graph, 1, 2); addEdge(graph, 1, 3); addEdge(graph, 1, 4); addEdge(graph, 2, 3); addEdge(graph, 3, 4); // print the adjacency list representation of the above // graph printGraph(graph); return 0; } |
JAVA
// Java code to demonstrate Graph representation // using ArrayList in Java import java.util.*; class Graph { // A utility function to add an edge in an // undirected graph static void addEdge(ArrayList<ArrayList<Integer> > adj, int u, int v) { adj.get(u).add(v); adj.get(v).add(u); } // A utility function to print the adjacency list // representation of graph static void printGraph(ArrayList<ArrayList<Integer> > adj) { for ( int i = 0 ; i < adj.size(); i++) { System.out.println( "Adjacency list of vertex" + i); System.out.print( "head" ); for ( int j = 0 ; j < adj.get(i).size(); j++) { System.out.print( " -> " + adj.get(i).get(j)); } System.out.println(); } } // Driver Code public static void main(String[] args) { // Creating a graph with 5 vertices int V = 5 ; ArrayList<ArrayList<Integer> > adj = new ArrayList<ArrayList<Integer> >(V); for ( int i = 0 ; i < V; i++) adj.add( new ArrayList<Integer>()); // Adding edges one by one addEdge(adj, 0 , 1 ); addEdge(adj, 0 , 4 ); addEdge(adj, 1 , 2 ); addEdge(adj, 1 , 3 ); addEdge(adj, 1 , 4 ); addEdge(adj, 2 , 3 ); addEdge(adj, 3 , 4 ); printGraph(adj); } } |
Python3
""" A Python program to demonstrate the adjacency list representation of the graph """ # A class to represent the adjacency list of the node class AdjNode: def __init__( self , data): self .vertex = data self . next = None # A class to represent a graph. A graph # is the list of the adjacency lists. # Size of the array will be the no. of the # vertices "V" class Graph: def __init__( self , vertices): self .V = vertices self .graph = [ None ] * self .V # Function to add an edge in an undirected graph def add_edge( self , src, dest): # Adding the node to the source node node = AdjNode(dest) node. next = self .graph[src] self .graph[src] = node # Adding the source node to the destination as # it is the undirected graph node = AdjNode(src) node. next = self .graph[dest] self .graph[dest] = node # Function to print the graph def print_graph( self ): for i in range ( self .V): print ( "Adjacency list of vertex {} head" . format (i), end = "") temp = self .graph[i] while temp: print ( " -> {}" . format (temp.vertex), end = "") temp = temp. next print ( " " ) # Driver program to the above graph class if __name__ = = "__main__" : V = 5 graph = Graph(V) graph.add_edge( 0 , 1 ) graph.add_edge( 0 , 4 ) graph.add_edge( 1 , 2 ) graph.add_edge( 1 , 3 ) graph.add_edge( 1 , 4 ) graph.add_edge( 2 , 3 ) graph.add_edge( 3 , 4 ) graph.print_graph() # This code is contributed by Kanav Malhotra |
C#
// C# code to demonstrate Graph representation // using LinkedList in C# using System; using System.Collections.Generic; class Graph { // A utility function to add an edge in an // undirected graph static void addEdge(LinkedList< int >[] adj, int u, int v) { adj[u].AddLast(v); adj[v].AddLast(u); } // A utility function to print the adjacency list // representation of graph static void printGraph(LinkedList< int >[] adj) { for ( int i = 0; i < adj.Length; i++) { Console.WriteLine( "Adjacency list of vertex " + i); Console.Write( "head" ); foreach ( var item in adj[i]) { Console.Write( " -> " + item); } Console.WriteLine(); } } // Driver Code public static void Main(String[] args) { // Creating a graph with 5 vertices int V = 5; LinkedList< int >[] adj = new LinkedList< int >[ V ]; for ( int i = 0; i < V; i++) adj[i] = new LinkedList< int >(); // Adding edges one by one addEdge(adj, 0, 1); addEdge(adj, 0, 4); addEdge(adj, 1, 2); addEdge(adj, 1, 3); addEdge(adj, 1, 4); addEdge(adj, 2, 3); addEdge(adj, 3, 4); printGraph(adj); Console.ReadKey(); } } // This code is contributed by techno2mahi |
Javascript
<script> // Javascript code to demonstrate Graph representation // using ArrayList in Java // A utility function to add an edge in an // undirected graph function addEdge(adj,u,v) { adj[u].push(v); adj[v].push(u); } // A utility function to print the adjacency list // representation of graph function printGraph(adj) { for (let i = 0; i < adj.length; i++) { document.write( "<br>Adjacency list of vertex" + i+ "<br>" ); document.write( "head" ); for (let j = 0; j < adj[i].length; j++) { document.write( " -> " +adj[i][j]); } document.write( "<br>" ); } } // Driver Code // Creating a graph with 5 vertices let V = 5; let adj= []; for (let i = 0; i < V; i++) adj.push([]); // Adding edges one by one addEdge(adj, 0, 1); addEdge(adj, 0, 4); addEdge(adj, 1, 2); addEdge(adj, 1, 3); addEdge(adj, 1, 4); addEdge(adj, 2, 3); addEdge(adj, 3, 4); printGraph(adj); // This code is contributed by avanitrachhadiya2155 </script> |
输出：
Adjacency list of vertex 0 head -> 1-> 4 Adjacency list of vertex 1 head -> 0-> 2-> 3-> 4 Adjacency list of vertex 2 head -> 1-> 3 Adjacency list of vertex 3 head -> 1-> 2-> 4 Adjacency list of vertex 4 head -> 0-> 1-> 3
赞成的意见： 节省空间O（|V |+|E |）。在最坏的情况下，图中可能有C（V，2）个边，因此消耗O（V^2）空间。添加顶点更容易。 欺骗： 诸如从顶点u到顶点v是否有边这样的查询是无效的，可以通过O（v）来完成。
参考： http://en.wikipedia.org/wiki/Graph_%28abstract_data_type%29 相关帖子： 使用STL进行竞争性编程的图表示|集1（未加权和无向的DFS） 利用STL实现竞争编程|集2（加权图） 本文由 阿希什·巴恩瓦尔 并由Geeksforgeks团队审核。如果您发现任何不正确的地方，或者您想分享有关上述主题的更多信息，请写下评论。
© 版权声明
文章版权归作者所有，未经允许请勿转载。
THE END
![关于”PostgreSQL错误：关系[表]不存在“问题的原因和解决方案-yiteyi-C++库](https://www.yiteyi.com/wp-content/themes/zibll/img/thumbnail.svg)
