## Graphs
Graph is a useful data structure for representing most of the real-world problems involving a set of users/candidates/nodes and their relations. A graph consists of two parameters:
```
V = a set of vertices
E = a set of edges
```
Each edge in `E` connects any two vertices from `V`. Based on the type of edge, graphs can be of two types:
1. **Directed**: The edges are directed in nature, which means that when there is an edge from node `A` to `B`, it does not imply that there is an edge from `B` to `A`. An example of a directed edge graph is the **follow** feature of social media. If you follow a celebrity, it doesn't imply that they follow you.
2. **Undirected**: The edges don't have any direction. So if `A` and `B` are connected, we can assume that there is an edge from both `A` to `B` and `B` to `A`. For example, in a social media graph, if two persons are friends, it implies that both are friends with each other.
### Components of a Graph
**Vertices:** Vertices are the fundamental units of the graph. Sometimes, vertices are also known as vertex or nodes. Every node/vertex can be labeled or unlabelled.
**Edges:** Edges are used to connect two nodes of the graph. They can be an ordered pair of nodes in a directed graph. Edges can connect any two nodes in any possible way. There are no rules. Sometimes, edges are also known as arcs. Every edge can be labeled/unlabeled.
Graphs are used to solve many real-life problems. Graphs are used to represent networks. The networks may include paths in a city, telephone network, or circuit network. Graphs are also used in social networks like LinkedIn, Facebook. For example, on Facebook, each person is represented with a vertex (or node). Each node is a structure and contains information like person id, name, gender, locale, etc.
### Graph Representation
Graph can be represented in the following ways:
**Set Representation:** Set representation of a graph involves two sets: Set of vertices V = {V1, V2, V3, V4} and set of edges E = {{V1, V2}, {V2, V3}, {V3, V4}, {V4, V1}}. This representation is efficient for memory but does not allow parallel edges.
**Sequential Representation:** This representation of a graph can be represented by means of matrices: Adjacency Matrix, Incidence matrix, and Path matrix.
**Adjacency Matrix:** This matrix includes information about the adjacent nodes. Here, aij = 1 if there is an edge from Vi to Vj; otherwise, it's 0. It is a matrix of order V×V.
**Incidence Matrix:** This matrix includes information about the incidence of edges on the nodes. Here, aij = 1 if the jth edge Ej is incident on the ith vertex Vi; otherwise, it's 0. It is a matrix of order V×E.
**Path Matrix:** This matrix includes information about the simple path between two vertices. Here, Pij = 1 if there is a path from Vi to Vj; otherwise, it's 0. It is also called the reachability matrix of graph G.
**Linked Representation:** This representation gives information about the nodes to which a specific node is connected, i.e., adjacency lists. This representation gives the adjacency lists of the vertices with the help of arrays and linked lists. In the adjacency lists, the vertices connected to the specific vertex are arranged in the form of lists that are connected to that vertex.
### Real-Time Applications of Graph
Graphs are used to represent the flow of control in computers.
Graphs are used in social networking sites where users act as nodes, and connections between them act as edges.
In an operating system, graphs are used as resource allocation graphs.
Graphs are used in Google Maps to find the shortest route.
Graphs are also used in the airline system for effective route optimization.
In state transition diagrams, the graph is used to represent states and their transitions.
In transportation, graphs are used to find the shortest path.
In circuits, graphs can be used to represent circuit points as nodes and wires as edges.
Graphs are used in solving puzzles with only one solution, such as mazes.
Graphs are used in computer networks for Peer to Peer (P2P) applications.
Graphs, basically in the form of DAG (Directed Acyclic Graph), are used as an alternative to blockchain for cryptocurrency. For example, cryptocurrencies like IOTA and Nano are mainly based on DAG.
### Advantages of Graph
Using graphs, we can easily find the shortest path, neighbors of the nodes, and many more.
Graphs are used to implement algorithms like DFS and BFS.
They are used to find minimum spanning trees, which have many practical applications.
Graphs help in organizing data.
Because of their non-linear structure, graphs help in understanding complex problems and their visualization.
### Disadvantages of Graph
Graphs use lots of pointers, which can be complex to handle.
They can have large memory complexity.
If the graph is represented with an adjacency matrix, then it does not allow parallel edges, and multiplication of the graph is also difficult.
### Representation
1. **Adjacency Lists**: Each node is represented as an entry, and all the edges are represented as a list emerging from the corresponding node. So, if vertex 1 has edges to 2, 3, and 6, the list corresponding to 1 will have 2, 3, and 6 as entries. Consider the following graph:
```
0: 1-->2-->3
1: 0-->2
2: 0-->1
3: 0-->4
4: 3
```
It means there are edges from 0 to 1, 2, and 3; from 1 to 0 and 2, and so on.
2. **Adjacency Matrix**: The graph is represented as a matrix of size |V| x |V|, and an entry 1 in cell (i, j) implies that there is an edge from i to j. 0 represents no edge. The matrix for the above graph:
```
0 1 2 3 4
0 0 1 1 1 0
1 1 0 1 0 0
2 1 1 0 0 0
3 1 0 0 0 1
4 0 0 0 1 0
```
没有合适的资源?快使用搜索试试~ 我知道了~
Java 算法实现代码集.zip
共864个文件
java:827个
md:13个
yml:11个
1.该资源内容由用户上传,如若侵权请联系客服进行举报
2.虚拟产品一经售出概不退款(资源遇到问题,请及时私信上传者)
2.虚拟产品一经售出概不退款(资源遇到问题,请及时私信上传者)
版权申诉
0 下载量 57 浏览量
2024-05-14
06:52:57
上传
评论
收藏 817KB ZIP 举报
温馨提示
java 简单性 Java看起来设计得很像C++,但是为了使语言小和容易熟悉,设计者们把C++语言中许多可用的特征去掉了,这些特征是一般程序员很少使用的。例如,Java不支持goto语句,代之以提供break和continue语句以及异常处理。Java还剔除了C++的操作符过载(overload)和多继承特征,并且不使用主文件,免去了预处理程序。因为Java没有结构,数组和串都是对象,所以不需要指针。Java能够自动处理对象的引用和间接引用,实现自动的无用单元收集,使用户不必为存储管理问题烦恼,能更多的时间和精力花在研发上。 面向对象 Java是一个面向对象的语言。对程序员来说,这意味着要注意其中的数据和操纵数据的方法(method),而不是严格地用过程来思考。在一个面向对象的系统中,类(class)是数据和操作数据的方法的集合。数据和方法一起描述对象(object)的状态和行为。每一对象是其状态和行为的封装。类是按一定体系和层次安排的,使得子类可以从超类继承行为。在这个类层次体系中有一个根类,它是具有一般行为的类。Java程序是用类来组织的。
资源推荐
资源详情
资源评论
收起资源包目录
Java 算法实现代码集.zip (864个子文件)
.clang-format 4KB
CODEOWNERS 40B
Dockerfile 1KB
.gitpod.dockerfile 554B
.gitignore 708B
AES.java 47KB
Blowfish.java 30KB
SinglyLinkedList.java 13KB
KDTree.java 13KB
FibonacciHeap.java 12KB
ClosestPair.java 12KB
MemoryManagementAlgorithms.java 12KB
DoublyLinkedList.java 12KB
DES.java 11KB
AhoCorasick.java 11KB
MatrixGraphs.java 11KB
SquareFreeIntegerTest.java 10KB
SkipList.java 10KB
LinkListSort.java 10KB
BinaryTree.java 9KB
BSTRecursiveGeneric.java 9KB
RedBlackBST.java 9KB
ConwayTest.java 9KB
KochSnowflake.java 9KB
FFT.java 8KB
QuickSelectTest.java 8KB
SinglyLinkedListTest.java 8KB
HashMapCuckooHashing.java 8KB
Mandelbrot.java 8KB
BoruvkaAlgorithmTest.java 7KB
Dijkstra.java 7KB
ColumnarTranspositionCipher.java 7KB
RgbHsvConversion.java 7KB
HorspoolSearch.java 7KB
A_Star.java 7KB
Deques.java 7KB
BoruvkaAlgorithm.java 7KB
BankersAlgorithm.java 6KB
QuickSortLinkedList.java 6KB
MatrixRank.java 6KB
MazeRecursion.java 6KB
MatrixUtil.java 6KB
CheckIfBinaryTreeBalanced.java 6KB
GenericTree.java 6KB
CRCAlgorithm.java 6KB
Luhn.java 6KB
BSTIterative.java 6KB
RegexMatching.java 6KB
HillCipher.java 6KB
MonteCarloTreeSearch.java 6KB
SkylineAlgorithm.java 6KB
MedianOfRunningArrayTest.java 6KB
BellmanFord.java 6KB
Anagrams.java 6KB
Area.java 6KB
AVLTree.java 6KB
Verhoeff.java 6KB
PerlinNoise.java 6KB
DynamicArray.java 6KB
AnyBaseToAnyBase.java 6KB
ORSet.java 6KB
GrahamScan.java 5KB
SortingAlgorithmTest.java 5KB
PriorityQueues.java 5KB
BinarySearch2dArrayTest.java 5KB
CursorLinkedList.java 5KB
BufferedReader.java 5KB
MaxHeap.java 5KB
LazySegmentTree.java 5KB
MinHeap.java 5KB
AhoCorasickTest.java 5KB
QueueUsingTwoStacks.java 5KB
Implementing_auto_completing_features_using_trie.java 5KB
WelshPowellTest.java 5KB
OptimalJobScheduling.java 5KB
FFTTest.java 5KB
CircularBufferTest.java 5KB
WordBoggle.java 5KB
NQueens.java 5KB
EulerMethod.java 4KB
BSTRecursive.java 4KB
Kosaraju.java 4KB
ColorContrastRatio.java 4KB
LinearDiophantineEquationsSolver.java 4KB
StrassenMatrixMultiplication.java 4KB
LRUCache.java 4KB
AESEncryption.java 4KB
LWWElementSet.java 4KB
TarjansAlgorithm.java 4KB
LinkedQueue.java 4KB
MRUCache.java 4KB
PlayfairCipher.java 4KB
StackArray.java 4KB
QuickSelect.java 4KB
TrieImp.java 4KB
EditDistance.java 4KB
Kruskal.java 4KB
Graphs.java 4KB
Queues.java 4KB
MiniMaxAlgorithm.java 4KB
共 864 条
- 1
- 2
- 3
- 4
- 5
- 6
- 9
资源评论
野生的狒狒
- 粉丝: 2544
- 资源: 2149
下载权益
C知道特权
VIP文章
课程特权
开通VIP
上传资源 快速赚钱
- 我的内容管理 展开
- 我的资源 快来上传第一个资源
- 我的收益 登录查看自己的收益
- 我的积分 登录查看自己的积分
- 我的C币 登录后查看C币余额
- 我的收藏
- 我的下载
- 下载帮助
安全验证
文档复制为VIP权益,开通VIP直接复制
信息提交成功